Invited Session Thu.1.H 2032

Thursday, 10:30 - 12:00 h, Room: H 2032

Cluster 11: Integer & mixed-integer programming [...]

Branch-and-price II: Column and row generation


Chair: Marco Lübbecke



Thursday, 10:30 - 10:55 h, Room: H 2032, Talk 1

Pedro Munari
Using interior point methods in branch-price-and-cut framework

Coauthor: Jacek Gondzio


Branch-price-and-cut framework has proven to be a very powerful method for solving integer programming problems. It combines decomposition techniques with the generation of both columns and valid inequalities and relies on strong bounds to guide the search in the branch-and-bound tree. In this talk, we present how the performance of branch-price-and-cut framework can be improved by using the primal-dual interior point method. We discuss in detail how the challenges involved in combining the primal dual interior point method with the integer programming techniques are addressed. The effort to overcome the difficulties pays off in a number of advantageous features offered by the new approach. We present the computational results of solving the well-known instances of the Vehicle Routing Problem with Time Windows, a challenging integer programming problem. The results confirm that the proposed approach delivers the best overall performance when compared with other branch-price-and-cut frameworks available in the literature.



Thursday, 11:00 - 11:25 h, Room: H 2032, Talk 2

Kerem Bulbul
Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows

Coauthors: S. Ilker Birbil, Ibrahim Muter


We develop a simultaneous column-and-row generation algorithm that could be applied to a general class of large-scale linear programming (LP) problems. These problems typically arise in the context of LP formulations with exponentially many variables. The defining property for these formulations is a set of linking constraints, which are either
too many to be included in the formulation directly, or the full set of linking constraints can only be identified, if all variables are generated explicitly. Due to this dependence between columns and rows, we refer to this class of LPs as problems with column-dependent-rows. To solve these problems efficiently, we need to be able to generate both columns and rows on-the-fly. We emphasize that the generated rows are structural constraints and distinguish our work from the branch-and-cut-and-price framework. We first characterize the underlying assumptions for the proposed column-and-row generation algorithm. We then introduce in detail a set of pricing subproblems, and prove the optimality of the algorithm. We conclude by applying the proposed framework to the multi-stage cutting stock and the quadratic set covering problems.



Thursday, 11:30 - 11:55 h, Room: H 2032, Talk 3

Ruslan Sadykov
Column generation for extended formulations

Coauthor: François Vanderbeck


Working in an extended variable space allows one to develop tight reformulations for mixed integer programs. However, a direct treatment by a MIP solver is not possible because of the size of the reformulation.
If the extended formulation stems from a decomposition principle: a sub-problem admits an extended formulation from which is derived the extended formulation for the original problem, then, one can implement column generation for this extended formulation by transposing the equivalent procedure for the Dantzig-Wolfe reformulation. Pricing sub-problem solutions are expressed in the variables of the extended formulation and added to the current restricted version of the extended formulation along with the active sub-problem constraints. This so-called "column-and-row generation'' procedure is revisited here in an unifying presentation and extended to the case of working with an approximate extended formulations.
Numerical comparison of column-and-row generation with standard column generation shows that lifting pricing problem solutions in the space of the extended formulation permits their recombination into new sub-problem solutions and results in faster convergence.


  Most online loan lenders allow getting New Jersey Payday Loans without visiting a bank, straight to your bank account. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra Without Prescription influence on blood clots.