Loading...
Please wait, while we are loading the content...
Similar Documents
Column generation for extended formulations (2011).
| Content Provider | CiteSeerX |
|---|---|
| Author | Sadykov, Ruslan Vanderbeck, François |
| Abstract | Working in an extended variable space allows one to develop tight reformulations for mixed integer programs. However, the size of the extended formulation grows rapidly too large for a direct treatment by a MIP-solver. Then, one can use projection tools and derive valid inequalities for the original formulation, or consider an approximate extended formulation (f.i., by aggregating variables). Both approaches result in outer approximations of the intended extended formulation. An alternative is to work with inner approximations defined and improved by generating dynamically the variables of the extended formulation. It assumes that the extended formulation stems from a decomposition principle: a subproblem admits an extended formulation from which the original problem extended formulation is derived. Then, one can implement column generation for this extended formulation by transposing the equivalent procedure for the Dantzig-Wolfe reformulation. Pricing subproblem solutions are expressed in the variables of the extended formulation and added to the current restricted version of the extended formulation along with the subproblem constraints that are active for the subproblem solution. Such “column-and-row generation ” procedure is reviewed and analysed herein. We compare numerically a direct handling of the extended formulation, a standard column generation approach, and the “column-and-row generation ” procedure, highlighting a key benefit of the latter: lifting pricing problem solutions in the space of the extended formulation permits their recombination into new subproblem solutions and results in faster convergence. |
| File Format | |
| Publisher Date | 2011-01-01 |
| Access Restriction | Open |
| Subject Keyword | Extended Formulation Column Generation Extended Formulation Ruslan Sadykov Subproblem Solution Column-and-row Generation Procedure Subproblem Constraint Mixed Integer Program Standard Column Generation Approach Direct Treatment Derive Valid Inequality Extended Variable Space Original Formulation Dantzig-wolfe Reformulation Original Problem Extended Formulation Grows Key Benefit Equivalent Procedure New Subproblem Solution Lifting Pricing Problem Solution Tight Reformulations Faster Convergence Decomposition Principle Inner Approximation Projection Tool Outer Approximation Current Restricted Version Direct Handling |
| Content Type | Text |
