446 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
Correspondence with D. Van Dantzig [International Organization for Standardization]
No full textJuly-August 1953. 3 letters
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.
Spatial Attention is Driven by Mental Simulations
No full textIntroduction: Many studies have shown that task performance
is affected by the relation between the
spatial location and the meaning of a target
word. These effects have been obtained for
object names that have typical positions
in the physical world (Zwaan and Yaxley,
2003; Bergen et al., 2007; Šeticˇ and Domijan,
2007; Estes et al., 2008) and for concepts
that are metaphorically related to spatial
position (Richardson et al., 2003; Meier and
Robinson, 2004; Schnall and Clore, 2004;
Schubert, 2005; Giessner and Schubert,
2007; Casasanto, 2009; Van Dantzig, 2009).
Although these findings are consistent
with a mental simulation account, at least
some of the interactions between meaning
and spatial location might be explained by
polarity alignment. In our study (Pecher
et al., 2010) we tested whether spatial congruency
effects are best explained by mental
simulations or by polarity alignment. ..
Combining 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
Enkele voorbeelden van berekening van waterbeweging onder invloed van wind : (KNAW, verslag vergadering (natuurkunde), 65(1956), nr 3, p 39-44)
No full text
Eerste rapport ijklijnproblemen : Opmerkingen over een oplossing van een speciaal geval van dit probleem van dr. J. E. Drion
No full text- …
