391 research outputs found
A New Dantzig-Wolfe Reformulation And Branch-And-Price Algorithm For The Capacitated Lot Sizing Problem With Set Up Times
No full textThe textbook Dantzig-Wolfe decomposition for the Capacitated LotSizing Problem (CLSP),as already proposed by Manne in 1958, has animportant structural deficiency. Imposingintegrality constraints onthe variables in the full blown master will not necessarily givetheoptimal IP solution as only production plans which satisfy theWagner-Whitin condition canbe selected. It is well known that theoptimal solution to a capacitated lot sizing problem willnotnecessarily have this Wagner-Whitin property. The columns of thetraditionaldecomposition model include both the integer set up andcontinuous production quantitydecisions. Choosing a specific set upschedule implies also taking the associated Wagner-Whitin productionquantities. We propose the correct Dantzig-Wolfedecompositionreformulation separating the set up and productiondecisions. This formulation gives the samelower bound as Manne'sreformulation and allows for branch-and-price. We use theCapacitatedLot Sizing Problem with Set Up Times to illustrate our approach.Computationalexperiments are presented on data sets available from theliterature. Column generation isspeeded up by a combination of simplexand subgradient optimization for finding the dualprices. The resultsshow that branch-and-price is computationally tractable andcompetitivewith other approaches. Finally, we briefly discuss how thisnew Dantzig-Wolfe reformulationcan be generalized to other mixedinteger programming problems, whereas in theliterature,branch-and-price algorithms are almost exclusivelydeveloped for pure integer programmingproblems.branch-and-price;Lagrange relaxation;Dantzig-Wolfe decomposition;lot sizing;mixed-integer programming
Post-l1-penalized estimators in high-dimensional linear regression models
No full textIn this paper we study post-penalized estimators which apply ordinary, unpenalized linear regression to the model selected by first-step penalized estimators, typically LASSO. It is well known that LASSO can estimate the regression function at nearly the oracle rate, and is thus hard to improve upon. We show that post-LASSO performs at least as well as LASSO in terms of the rate of convergence, and has the advantage of a smaller bias. Remarkably, this performance occurs even if the LASSO-based model selection 'fails' in the sense of missing some components of the 'true' regression model. By the 'true' model we mean here the best s-dimensional approximation to the regression function chosen by the oracle. Furthermore, post-LASSO can perform strictly better than LASSO, in the sense of a strictly faster rate of convergence, if the LASSO-based model selection correctly includes all components of the 'true' model as a subset and also achieves a sufficient sparsity. In the extreme case, when LASSO perfectly selects the 'true' model, the post-LASSO estimator becomes the oracle estimator. An important ingredient in our analysis is a new sparsity bound on the dimension of the model selected by LASSO which guarantees that this dimension is at most of the same order as the dimension of the 'true' model. Our rate results are non-asymptotic and hold in both parametric and nonparametric models. Moreover, our analysis is not limited to the LASSO estimator in the first step, but also applies to other estimators, for example, the trimmed LASSO, Dantzig selector, or any other estimator with good rates and good sparsity. Our analysis covers both traditional trimming and a new practical, completely data-driven trimming scheme that induces maximal sparsity subject to maintaining a certain goodness-of-fit. The latter scheme has theoretical guarantees similar to those of LASSO or post-LASSO, but it dominates these procedures as well as traditional trimming in a wide variety of experiments.
Théorie des probabilités. Exposés sur ses fondements et ses applications, par MM. P. Gillis, R. von Mises, R. Ballieu, D. van Dantzig, R. Coutrez, L. Bouckaert, I. Prigogine, F. Campus, A. Fauville, M. Fréchet et G. Hirsch. Publié par la Société belge de logique et de philosophie des sciences
No full textDopp Joseph. Théorie des probabilités. Exposés sur ses fondements et ses applications, par MM. P. Gillis, R. von Mises, R. Ballieu, D. van Dantzig, R. Coutrez, L. Bouckaert, I. Prigogine, F. Campus, A. Fauville, M. Fréchet et G. Hirsch. Publié par la Société belge de logique et de philosophie des sciences. In: Revue Philosophique de Louvain. Troisième série, tome 52, n°34, 1954. pp. 337-338
Continuous and discrete self-similarity via classification schemes of Markov processes, and the van Dantzig problem
No full text213 pagesThis dissertation has three chapters, the first two of them are focused on the self-similar Markov semigroups, and the third chapter deals with the classical van Dantzig problem, which has some connections with the self-similar Markov processes on the positive real line (). One of the main focuses of this thesis is the development of functional analytic theory for continuous and discrete self-similar Markov semigroups, which are studied elaborately in Chapter 2 and Chapter 3 respectively. Spectral theory of Markov semigroups is a fast-growing literature with many applications in the analysis of convergence rate of Markov processes, functional inequalities, analysis of linear PDEs and many more. The Markov semigroups of our interest are self-similar, that is, they have the following scaling property:\begin{align*} P_{t}d_\alpha=d_\alpha P_{\alpha t} \quad \forall \alpha,t>0 \end{align*} where is the classical dilation operator on . It is important to observe that the notion of self-similarity is dependent on how one defines the dilation operator. More precisely, any multiplicative semigroup acting on a certain subset of can be thought as a dilation operator. With this motivation in mind, in Chapter 3 we define \emph{discrete self-similar Markov chains} on and study their analytical properties. Self-similar semigroups, both in continuous and discrete state spaces, are, in general, not self-adjoint (not even normal), which is why their spectral analysis is much more involved. In this dissertation, we exploit the concept of \emph{weak similarity} and \emph{intertwining relationship} whose original motivation comes from group representation theory and functional analysis. In the context of Markov semigroups, we say that two semigroups and , where are Hilbert spaces, are weakly similar if there exists a densely defined injective operator with dense range such that on a dense set. In particular, when is a Markov kernel, the weak similarity boils down to the intertwining relation. The earliest instance of intertwining relationship in Markov processes goes back to E.B. Dynkin \cite{dynkin:1965}, where he considered bijective transformations of Markov processes via the similarity transform of the semigroups. Later, Pitman and Rogers \cite{Pitman-Rogers-81} introduced \emph{Markov intertwining} operators to prove that the distribution of the Brownian motion reflected around its running maximum coincides with the Bessel process of dimension 3. In more recent years, Carmona, Petit and Yor \cite{Carmona-Petit-Yor-98} proved intertwining relationship among the class of Bessel processes to derive certain distributional identities. Chapter 2 of this thesis is motivated from the aforementioned work, where we prove weak similarity relation among the class of (log) self-similar Markov semigroups on . Using this weak similarity relation and the self-similarity of the self-adjoint Bessel semigroup in , we provide a spectral representation of the non-self-adjoint self-similar Markov semigroup, and a detailed description of the spectrum including the point, continuous and the residual spectrum. We carry out the similar program in Chapter 3 for the \emph{discrete Laguerre chain}, which are obtained by a perturbation of the discrete self-similar Markov chains. We show that both the discrete self-similar and the Laguerre chains have a \emph{gateway} relation with their continuous analogues. This enables us to obtain the spectral representation, hypocoercivity and hypercontractivity of the non-reversible Laguerre chains. The final chapter of the thesis deals with the classical van Dantzig problem which can be stated very simply as follows: find all analytic characteristic functions (of probability measure) such that is also a characteristic function, where for all . In the seminal paper \cite{Lukacs}, E. Lukacs studied the solution to the above problem within the class of entire functions with real zeros. Let denote the class of all such functions. After observing the fact that any function solving the van Dantzig problem must be even, by means of analytical methods, Lukacs obtained several closure properties of the class . In this chapter, we first discuss how the class of functions is related to the Riemann Hypothesis and the Lee-Yang property in statistical mechanics. Then, we provide a new class of solutions to the van Dantzig problem, which may have complex zeros. We point out that these functions are also the eigenfunctions of certain self-similar Markov semigroups on . All work in this thesis was done in collaboration with Pierre Patie. The work in Chapter 3 was done with the additional collaboration with Laurent Miclo and the work in Chapter 4 was done in collaboration with Takis Konstantopoulos. The contents of Chapter 2 -- 4 have been submitted to peer-reviewed journals as follows:\begin{itemize} \item Pierre Patie and Rohan Sarkar, \href{https://www.researchgate.net/publication/360139361_Weak_similarity_orbit_of_log-self-similar_Markov_semigroups_on_the_Euclidean_space}{Weak similarity orbit of (log)-self-similar Markov semigroups on the euclidean space}, submitted, 55pp., 2022. \item Laurent Miclo, Pierre Patie and Rohan Sarkar, \href{https://www.researchgate.net/publication/354700530_Discrete_self-similar_and_ergodic_Markov_chains}{Discrete self-similar and ergodic Markov chains}, \emph{The Annals of Probability}, accepted, 50pp., 2022. \item Takis Konstantopoulos, Pierre Patie, and Rohan Sarkar, \href{https://www.researchgate.net/publication/355972844_A_new_class_of_solutions_to_the_van_Dantzig_problem_the_Lee-Yang_property_and_the_Riemann_hypothesis}{A new class of solutions to the van Dantzig problem, the Lee-Yang property, and the Riemann Hypothesis}, submitted, 35pp., 2021. \end{itemize
CROSS-SECTION MEASUREMENT FOR QUASI-ELASTIC PRODUCTION OF CHARMED BARYONS IN NEUTRINO NUCLEUS INTERACTIONS
No full textCombining Column Generation and Lagrangian Relaxation
No full textAlthough the possibility to combine column generation and Lagrangian relaxation has been known for quite some time, it has only recently been exploited in algorithms. In this paper, we discuss ways of combining these techniques. We focus on solving the LP relaxation of the Dantzig-Wolfe master problem. In a first approach we apply Lagrangian relaxation directly to this extended formulation, i.e. no simplex method is used. In a second one, we use Lagrangian relaxation to generate new columns, that is Lagrangian relaxation is applied to the compact for-mulation. We will illustrate the ideas behind these algorithms with an application in Lot-sizing. To show the wide applicability of these techniques, we also discuss applications in integrated vehicle and crew scheduling, plant location and cutting stock problems.column generation;Lagrangean relaxation;cutting stock problem;lotsizing;vehicle and crew scheduling
Reformulation and decomposition of integer programs
No full textIn this survey we examine ways to reformulate integer and mixed integer programs. Typically, but not exclusively, one reformulates so as to obtain stronger linear programming relaxations, and hence better bounds for use in a branch-and-bound based algorithm. First we cover in detail reformulations based on decomposition, such as Lagrangean relaxation, Dantzig-Wolfe column generation and the resulting branch-and-price algorithms. This is followed by an examination of Benders’ type algorithms based on projection. Finally we discuss in detail extended formulations involving additional variables that are based on problem structure. These can often be used to provide strengthened a priori formulations. Reformulations obtained by adding cutting planes in the original variables are not treated here.Integer program, Lagrangean relaxation, column generation, branch-and-price, extended formulation, Benders' algorithm
Colloquium on boundary value problems : Amsterdam 20.05.1958 : organized by the Mathematical Centre at Amsterdam under the chairmanship of D. van Dantzig
No full text
The CHORUS honeycomb tracker and its bitstream electronics
No full textThe CHORUS experiment searches for nu(mu)nu(tau) oscillation. To aid in the momentum reconstruction of charged hadrons, a honeycomb tracker was built with three orientations of six planes each. The planes are manufactured by point-welding together two precision folded conductive polycarbonate foils, forming hexagonal tubes with 30 mu m thick anode wires in the center. The honeycomb tracker in CHORUS is read out using a bitstream principle. The amplified signal of each wire is binary sampled every 5 ns and stored in a 256 bit circular buffer, implemented in dual-port memories. This technique allows a full reconstruction of a 1.28 mu s history of each wire. Eighteen cards, each handling 72 wires, are read out over a single flat cable using a card-to-card pipeline. (C) 1998 Elsevier Science B.V. All rights reserved
- …
