Automatic Decomposition
and Branch-and-Price—A Status Report
Marco E. Lübbecke
RWTH Aachen University, Operations Research, Kackertstraße 7,
D-52072 Aachen, Germany
marco.luebbecke@rwth-aachen.de

Abstract. We provide an overview of our recent eﬀorts to automatize
Dantzig-Wolfe reformulation and column generation/branch-and-pricefor structured, large-scale integer programs. We present the need forand the beneﬁts from a generic implementation which does not need any
user input or expert knowledge. A focus is on detecting structures in
integer programs which are amenable to a Dantzig-Wolfe reformulation.
We give computational results and discuss future research topics.

1

Modeling with Integer Programs

Integer programming oﬀers undeniably a powerful and versatile, yet industriallyrelevant approach to model and solve discrete optimization problems from virtually all areas of scientiﬁc and practical applications. To get an impression onmodeling, consider a simple combinatorial optimization problem, the bin packing
problem. We are given n items of size ai , i = 1, . . . , n, which have to be packed
into a minimum number of bins of capacity b each. A standard integer program
for this problem is built on binary variables xij ∈ {0, 1} to decide whether item
i is packed in bin j or not. It is common that a single variable imposes relatively
little structure on the overall solution. The model is as follows.

min

n


yj

j=1
n


(1a)

xij = 1i = 1, . . . , n(1b)ai xij ≤ b

j = 1, . . . , n(1c)xij ≤ yj

i, j = 1, . . . , n(1d)xij , yj ∈ {0, 1}

i, j = 1, . . . , n

(1e)

j=1
n

i=1

We call this the original formulation. Every item has to be packed because of
the set partitioning constraint (1b); whenever a bin is used it has to be opened
R. Klasing (Ed.): SEA 2012, LNCS 7276, pp. 1–8, 2012.
c Springer-Verlag Berlin Heidelberg 20122

M.E. Lübbecke

via the logical implication (1d); and no bin is overpacked because of the knapsack constraint (1c). The objective function (1a) reﬂects the goal of minimizing
the number of opened bins. Note that n bins always suﬃce. A few remarks are
in order. We observe that there is a symmetry w.r.t. the bins, that is, for agiven solution (x̄, ȳ) and a permutation σ of the bin indices, we get essentially“the same” solution with the same objective function value by replacing x̄ij byx̄iσ(j) and ȳj by ȳσ(j) . Also note that there are rather “local” constraints (1c),namely those concerning the packing of a single bin; and there are “global”
constraints (1b), namely those which ensure that for every item we open somebin. In particular, there is a knapsack problem to solve for each bin (which is
NP-hard, but a computationally very easy combinatorial optimization problem),and the “individual” solutions to the knapsack problems are linked by a “coordinating” constraint which enforces a global structure in the overall solution.
This is typical for many practical situations in which decisions are taken in a
distributed way, but which in fact need synchronization in order to achieve a
global goal (this is a feature which brings optimal solutions to such decision
problems way out of reach of human planners). Examples are vehicle routing,crew and machine scheduling, location problems, and many more.
A standard solver does not “see” this concept of constructing a complex solution out of easier building blocks either, as a branch-and-bound algorithm works“everywhere” on the overall solution simultaneously by construction. One way tomake these partial solutions “visible” to the solver is by formulating a diﬀerent
model which is based on “more meaningful” variables. For bin packing, we could
base a model on binary variables λpj ∈ {0, 1} which represent whether or not
we pack an entire conﬁguration or pattern p in bin j. A pattern is a collectionof items that respects the knapsack capacity and therefore “knows” about the
local constraints. All patterns for bin j are collected in a set Pj , and with theshorthand notation i ∈ p to state that pattern p contains item i, the new modelreads as follows.

min

n



λpj

(2a)

j=1 p∈Pjn

λpj = 1i = 1, . . . , n(2b)

λpj ≤ 1

j = 1, . . . , n(2c)

λpj ∈ {0, 1}

j = 1, . . . , n, p ∈ Pj

(2d)

j=1 p∈Pj :i∈p



p∈Pj

Constraint (2b) has the same role as constraint (1b) before: we must be surethat among all patterns for all bins, every item is contained in exactly one ofthose selected. The convexity constraint (2c) is new and ensures that at mostone pattern is chosen per bin (a bin may also be “empty,” that is, closed). No
knapsack constraint is needed any more, at the expense of the fact that, for eachAutomatic Decomposition and Branch-and-Price—A Status Report

3bin, we essentially enumerated all feasible solutions to the knapsack constraint.
After all, this is what we wanted. From a solution to this model
we can uniquelyreconstruct a solution to the original model (1) via xij = p∈Pj :i∈p λpj , that is,summing over all patterns for bin j that contain an item i. The new model (2)is still symmetric in the bins as all sets of patterns are identical for all bins. Thissymmetry could be eliminated by noting that we only need to ensure that foreach item some pattern is selected; exactly which bin is used is not of importance.
This leads us to an aggregated version of model (2).

min



νp

(3a)

p∈P



νp = 1i = 1, . . . , n(3b)νp ∈ {0, 1}

p∈P

(3c)

p∈P :i∈p

A binary variable νp represents whether we select a pattern p or not. Set P
contains all feasible patterns, but no longer any information on bin indices. Thisis also true for the aggregated variables νp = nj=1 λpj . As a consequence of thesymmetry breaking, there is no unique reconstruction of an original solution tomodel (1) from a solution to model (3). Of course, one could have formulated a
set partitioning model like (3) for the bin packing problem without going throughthe above reformulations, and this is what often happens.

2

Dantzig-Wolfe Reformulation

There is a major reason for favoring models (2) or (3) over model (1): the former
is usually stronger in the sense that the linear relaxation, i.e., relaxing variabledomains from {0, 1} to [0, 1], gives a tighter bound on the integer optimum.
Intuitively, this is because the “more meaningful” variables in (3) impose morestructure on the overall solution because a part of all original constraints (the“local” knapsack constraints) is already fulﬁlled with integrality. The theoreticalreason is that model (2) is derived from (1) via a Dantzig-Wolfe reformulation.
A sketch of this reformulation is as follows (see e.g., [3] for details). Consider
an original integer program of the form
min{ct x : Ax ≥ b, Dx ≥ d, x ∈ Zn+ } .

(4)

The polyhedron X := conv{x ∈ Zn+ : Dx ≥ d} gives an inspiration for the “moremeaningful” variables. We assume that X is bounded, but this is no restriction.
We express x ∈ X as a convex combination of the (ﬁnitely many) extreme points
P of X, which leads to an equivalent extended formulation


λp p,
λp = 1, λp ≥ 0, x ∈ Zn+ } .
(5)min{ct x : Ax ≥ b, x =
p∈P

p∈P

4

M.E. Lübbecke

The reformulation (5) contains the so-called master constraints Ax ≥ b, theconvexity constraint, and the constraint linking the original x variables to theextended λ variables. In general, model (5) has an exponential number (in n) of
λ variables, so its LP relaxation needs to be solved by column generation [3].
That is, one starts with a small subset of λ variables and iteratively adds morevariables of negative reduced cost until no such variables can be identiﬁed. The
pricing subproblem to check whether there exist variables with negative reduced
cost is a minimization problem of a linear objective function over X, so it canbe solved again as an integer program. The column generation process needs to
be invoked in every node of the branch-and-bound tree, yielding a branch-andprice algorithm. Special care must be taken when deciding on how to branch on
fractional variables [4,16,17].
In the classical setting, k disjoint sets of constraints are reformulated, namely
when the matrix D has a block-diagonal form
⎛
⎜
⎜
D=⎜
⎝

⎞

D1

⎟
⎟
⎟ ,
⎠

D2
..

.

(6)

Dk
where Di ∈ Qmi ×ni , i = 1, . . . , k. In other words, Dx ≥ d partitions in Di xi ≥ di ,i = 1, . . . , k, where x = (x1 , x2 , . . . , xk ), with an ni -vector xi , i = 1, . . . , k. Every
Di xi ≥ di is individually Dantzig-Wolfe reformulated. We call k the number ofblocks of the reformulation. A matrix of the form
⎛
⎜
⎜
⎜
⎜
⎜
⎝

⎞

D1

⎟
⎟
⎟
⎟
.
⎟
Dk ⎠
A1 A2 · · · Ak
D2

..

(7)

with Ai ∈ Qm ×ni , i = 1, . . . , k is called bordered block-diagonal, see Fig. 1(b). It
is this form we would like to see in the coeﬃcient matrix of an integer programin order to apply a Dantzig-Wolfe reformulation.
Depending on your background, the following may or may not apply to you:you regularly formulate models like (1) (but cannot solve even moderately sized
instances); you have already noticed that going from model (1) to model (2) is
by application of a Dantzig-Wolfe reformulation (but you don’t know of what use
this knowledge may be to you, practically speaking); you would like to implement
your own column generation and branch-and-price code and use it to optimallysolve models like (2) or (3) (but you don’t know whether it is worth the timeand considerable eﬀort); you already have your branch-and-price code running(but don’t want to change and adapt it every time you consider a new problem).
You are any of this kind? Read on. . .

Automatic Decomposition and Branch-and-Price—A Status Report

35

In Need for an Automatic Decomposition

In 2004, when collecting material for “the primer” [3], we learned about François
Vanderbeck’s eﬀorts to write a generic branch-and-price code BaPCod [12], andwe were fascinated by the idea ever since. Vanderbeck developed important contributions [11,13,14,15], so that not only a Dantzig-Wolfe reformulation could
be performed according to a user speciﬁcation but also branching was done in a
generic way. Further generic decomposition codes became available like DIP [10]and within the G12 project [9]. However, none of these codes could be used bysomeone not knowledgeable in decomposition techniques as the user needs topropose how the input integer program is to be decomposed. It is still up to themodeler which constraints Dx ≥ d she considers as “local,” that is, to be reformulated. Sometimes the choice may be rather obvious as in our introductory
example, but sometimes there is more freedom, and thus more freedom to makemistakes, and one needs to know what one is doing.
It simply felt wrong that there are the well-understood and in many special
cases successfully applied concepts of Dantzig-Wolfe decomposition, column generation, and branch-and-price, but they are not “out-of-the-box” usable e.g., to“everyday” OR practitioners, despite the availability of generic implementations.
And yet those who ran their own codes often needed to start all over with every
new application.
In order to close the last—but maybe most crucial—gap, we made ﬁrst experiments in [2] with detecting matrix structures suited for reformulation (seeSection 4). At that time, this detection and our generic branch-and-price code
GCG (see Section 5) were not merged into one project, but results were encouraging. Testing on general mixed integer programs was very nice and gave a
successful proof-of-concept, but diverted our attention from the true target instances of this research: those which bear structure. In this talk, we report on
experiments with automatic detection of decomposable matrix structures, andgeneric branch-and-price on a suitable test set of “structured” instances.

4

Recognizing Matrix Structures for Decomposition

The typical matrix structure for which Dantzig-Wolfe decomposition was proposed is a bordered block-diagonal form (7). With a little experience with thetechnique and an automatic recognition of types of constraints (like set partitioning constraints, knapsack constraints, and the like) one can come up quite
easily with a suggestion for a decomposition. This works well for standard problems, but may fail for “unknown” problems. Then, a possibility is to exploit afolklore connection between matrices and graphs [5].
Given a matrix A, construct a hypergraph H = (V, R∪C) as follows. With every
aij = 0 associate a vertex vij ∈ V . For every row i introduce a hyperedge ri ∈ R
which contains exactly all vertices vri j ∈ V that correspond to non-zero entriesof the row; analogously introduce a hyperedge cj ∈ C for every column j. WhenH partitions into several connected components, the matrix A is a block-diagonal
matrix, with a bijection between blocks in A and connected components in H.

6

M.E. Lübbecke

Hypergraph H can also be used to detect a bordered block-diagonal form.
Without the rows in the “border” the remaining matrix is block-diagonal. Thus,a removal of (a minimum number of) hyperedges from R such that the remaining
graph partitions into connected components reveals a bordered block-diagonal
form in A (with a minimum number of rows in the border). The problem is NPhard and we experimented with heuristics to solve it. Figure 1 shows a matrix
as given in the original model, and a structure detected with this minimum
hypergraph partitioning approach.

(a) original 10teams(b) detected structure

Fig. 1. (a) Matrix structure directly from the LP ﬁle (10teams) and (b) with a borderedblock-diagonal structure detected by our algorithm

The algorithm needs as input the number k of connected components we lookfor in H. Thus, in practice, we check for diﬀerent small numbers of k. As theresults sometimes look artiﬁcial, we suggest that a more tailored hypergraphpartitioning algorithm should be sought, exploiting the fact that H is extremely
sparse and of degree 2. In a diﬀerent line of research we replace hypergraphpartitioning by hypergraph clustering, which eliminates the need to specify the
number of blocks (connected components, clusters) beforehand. Experimentation
with these alternatives is still under way, but preliminary results look plausible.

5

Towards a Standalone Solver

Based on the discussion above, we developed GCG [6] (“generic column generation”) which is based on the SCIP framework [1] which is free for academic
purposes (scip.zib.de). Together with the LP ﬁle describing the integer program, GCG takes as input a second ﬁle (“the decomposition”) describing whichconstraints belong to the master problem and which to the blocks, respectively.
Alternatively, several of the matrix structure detection algorithms only sketchedabove are applied to the instance. GCG then performs a Dantzig-Wolfe reformulation according to a “best guess” (in addition one can specify whether theso-called convexiﬁcation or discretization approach should be applied); identiﬁes identical blocks, and aggregates them (the same as going from model (2)Automatic Decomposition and Branch-and-Price—A Status Report7

to model (3)); performs column generation on the given decomposition; maintains both formulations (the original in the x-variables, and the extended in the
λ-variables) which allows branching and cutting plane separation on the original variables; it has specialized branching rules like Ryan/Foster branching andgeneric primal heuristics [7,8]; and overall GCG uses SCIP’s rich functionality of
being a state-of-the-art MIP solver (like availability of pseudo-costs, pre-solving,propagation techniques, etc.). This turns the branch-price-and-cut framework
SCIP into a branch-price-and-cut solver [6]. A ﬁrst stable version is about to bereleased as this abstract goes to press.

6

Discussion

What are the goals of our project? Certainly, expecting a decomposition code
to beat a state-of-the-art branch-and-cut code on the average instance is notrealistic. On the other hand, anything but outperforming the general-purpose
solver on instances that contain a decomposable problem structure would bea failure. Thus, the art remains to tell the instances that are amenable to a
Dantzig-Wolfe reformulation from those which are not. And so we are back at
the most important and most interesting algorithmic challenge: to eﬃciently andreliably detect “structure” in an instance or conclude that “none” is contained.
This is an area which may not only produce new and improved algorithms,
e.g., for partitioning/clustering the graph underlying a coeﬃcient matrix. We
also need a much better theoretical understanding of what makes a good “structure” to look for, and we believe that this will give us insights into how to set
up a good integer programming model in the ﬁrst place. It is this algorithm
engineering feature which makes this project so interesting to us: to improvethe design of a long-known algorithm, letting computational experiments guideour way. We hope that our work contributes to closing the gap between thealgorithm on paper and its usefulness to a non-expert in practice.
Acknowledgments. I enjoyed discussions with Michael Bastubbe, Martin
Bergner, Alberto Ceselli, Jacques Desrosiers, Fabio Furini, Gerald Gamrath,Marc Pfetsch, and Emiliano Traversi on automated decompositions. This project
was supported by the German Science Foundation’s (DFG) priority program
1307 “algorithm engineering,” under contracts LU 770/4-1 and LU 770/4-2,
within the project “generic decomposition algorithms for integer programs.”

References
1. Achterberg, T.: SCIP: Solving constraint integer programs. Math. Programming
Computation 1(1), 1–41 (2009)
2. Bergner, M., Caprara, A., Furini, F., Lübbecke, M.E., Malaguti, E., Traversi,
E.: Partial Convexiﬁcation of General MIPs by Dantzig-Wolfe Reformulation. In:
Günlük, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 39–51.
Springer, Heidelberg (2011)

8

M.E. Lübbecke

3. Desrosiers, J., Lübbecke, M.: A primer in column generation. In: Desaulniers,G., Desrosiers, J., Solomon, M. (eds.) Column Generation, pp. 1–32. Springer,
Heidelberg (2005)
4. Desrosiers, J., Lübbecke, M.: Branch-price-and-cut algorithms. In: Cochran, J. (ed.)
Encyclopedia of Operations Research and Management Science. John Wiley &Sons, Chichester (2011)
5. Ferris, M., Horn, J.: Partitioning mathematical programs for parallel solution.
Math. Programming 80, 35–61 (1998)
6. Gamrath, G., Lübbecke, M.E.: Experiments with a Generic Dantzig-Wolfe Decomposition for Integer Programs. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049,
pp. 239–252. Springer, Heidelberg (2010)
7. Joncour, C., Michel, S., Sadykov, R., Sverdlov, D., Vanderbeck, F.: Column generation based primal heuristics. In: International Conference on Combinatorial Optimization (ISCO). Electronic Notes in Discrete Mathematics, vol. 36, pp. 695–702.
Elsevier (2012)
8. Lübbecke, M., Puchert, C.: Primal heuristics for branch-and-price algorithms. In:
Operations Research Proceedings 2011. Springer (to appear, 2012)
9. Puchinger, J., Stuckey, P., Wallace, M., Brand, S.: Dantzig-Wolfe decomposition
and branch-and-price solving in G12. Constraints 16(1), 77–99 (2011)
10. Ralphs, T., Galati, M.: DIP – decomposition for integer programming (2009),
https://projects.coin-or.org/Dip
11. Vanderbeck, F.: On Dantzig-Wolfe decomposition in integer programming and ways
to perform branching in a branch-and-price algorithm. Oper. Res. 48(1), 111–128(2000)
12. Vanderbeck, F.: BaPCod – a generic branch-and-price code (2005),
https://wiki.bordeaux.inria.fr/realopt/pmwiki.php/Project/BaPCod
13. Vanderbeck, F.: Implementing mixed integer column generation. In: Desaulniers,G., Desrosiers, J., Solomon, M. (eds.) Column Generation, pp. 331–358. Springer(2005)
14. Vanderbeck, F.: A generic view of Dantzig-Wolfe decomposition in mixed integer
programming. Oper. Res. Lett. 34(3), 296–306 (2006)
15. Vanderbeck, F.: Branching in branch-and-price: A generic scheme. Math. Programming 130(2), 249–294 (2011)
16. Vanderbeck, F., Wolsey, L.: Reformulation and decomposition of integer programs.
In: Jünger, M., Liebling, T., Naddef, D., Nemhauser, G., Pulleyblank, W., Reinelt,
G., Rinaldi, G., Wolsey, L. (eds.) 50 Years of Integer Programming 1958–2008.
Springer, Berlin (2010)
17. Villeneuve, D., Desrosiers, J., Lübbecke, M., Soumis, F.: On compact formulations
for integer programs solved by column generation. Ann. Oper. Res. 139(1), 375–388(2005)