Invited Session Thu.3.H 2032

Thursday, 15:15 - 16:45 h, Room: H 2032

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

Branch-and-price IV: Primal heuristics


Chair: Marco Lübbecke



Thursday, 15:15 - 15:40 h, Room: H 2032, Talk 1

Christian Puchert
Large neighborhood search and diving heuristics in column generation algorithms

Coauthor: Marco E. Lübbecke


In many MIP applications, a problem with a particular structure is to be solved. For those problems, the {branch-and-price} scheme using the {column generation} procedure has proven to be a successful approach, which relies on the {Dantzig-Wolfe decomposition}.
The performance of this scheme may be improved by supplying it with additional features such as {primal heuristics}. We present heuristics that are specially tailored for Column Generation and exploit a given problem structure, but are still generic in that they are not restricted to any particular problem.
In particular, we lay focus on two special kinds of heuristics, namely {large neighborhood search} and {diving heuristics}. The former explore a MIP neighborhood of one or more given feasible (or at least LP feasible) solutions. The latter perform a depth-first search on the branch-and-bound tree, where they may branch either on the original variables or the master variables. We will investigate the impact of these heuristics and give a comparison to classical heuristic approaches.



Thursday, 15:45 - 16:10 h, Room: H 2032, Talk 2

François Vanderbeck
Primal heuristics for branch-and-price

Coauthors: Cédric Joncour, Sophie Michel, Pierre Pesneau, Artur Pessoa, Marcus Poggi, Ruslan Sadykov, Eduardo Uchoa


Primal heuristics have become an essential component in mixed
integer programming (MIP). Generic heuristic
paradigms of the literature remain to be extended to
the context of a column generation solution approach. As the Dantzig-Wolfe
reformulation is typically tighter than the original compact
formulation, techniques based on
rounding its linear programming solution have better chance to yield
good primal solutions. However,
the dynamic generation of variables requires specific adaptation of
heuristic paradigms. We develop diving methods and consider
their combination with sub-MIPing, relaxation induced neighborhood
search, truncated backtracking using a Limited Discrepancy
Search, and feasibility pump. These add-ons serve as local-search or
diversification/intensification mechanisms.



Thursday, 16:15 - 16:40 h, Room: H 2032, Talk 3

Michael Bastubbe
A branch-and-price algorithm for rearranging a matrix into doubly bordered block-diagonal form

Coauthors: Martin Bergner, Alberto Ceselli, Marco E. Lübbecke


We consider rearranging the rows and the columns of a matrix into
doubly bordered block-diagonal (a.k.a. arrowhead) form. For a given
number of blocks and some given balance condition on the blocks, this
becomes an optimization problem in which the total number of border
rows and border columns is to be minimized. In this talk we present
an exact branch-and-price algorithm to this optimization problem.
For us, this matrix form is particularly interesting because it may
help us applying a Dantzig-Wolfe decomposition of the underlying mixed
integer program.
We extend a naive assignment IP formulation (that has a weak LP
relaxation) by an exponentially number of block pattern variables to
strengthen the LP relaxation. Our branch-and-price algorithm first
solves the pricing problem heuristically by exploiting its special
structure. If the heuristic solution of the pricing problem does not
yield variables with negative reduced costs the pricing problem is
solved exactly by an IP. We present the improvement of the LP
relaxation and discuss the practicability of the algorithm.


  To apply for Payday Loans In United States you don't have to seek the help of relatives or go to a bank. What can cause long-term use of Canadian Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.