Experiments with a Generic Dantzig-Wolfe
Decomposition for Integer Programs
Gerald Gamrath1 and Marco E. Lübbecke2
1

Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany
gamrath@zib.de
2
Technische Universität Darmstadt, Fachbereich Mathematik,
Dolivostr. 15, 64293 Darmstadt, Germany
luebbecke@mathematik.tu-darmstadt.de

Abstract. We report on experiments with turning the branch-priceand-cut framework SCIP into a generic branch-price-and-cut solver. Thatis, given a mixed integer program (MIP), our code performs a DantzigWolfe decomposition according to the user’s speciﬁcation, and solves theresulting re-formulation via branch-and-price. We take care of the column
generation subproblems which are solved as MIPs themselves, branch
and cut on the original variables (when this is appropriate), aggregate
identical subproblems, etc. The charm of building on a well-maintainedframework lies in avoiding to re-implement state-of-the-art MIP solving
features like pseudo-cost branching, preprocessing, domain propagation,
primal heuristics, cutting plane separation etc.

1

Situation

Over the last 25 years, branch-and-price algorithms developed into a very powerful tool to optimally solve huge and extremely diﬃcult combinatorial optimization problems. Their success relies on exploiting problem structures in an integer
program (via a decomposition or re-formulation) to which standard branch-andcut algorithms are essentially “blind.” While both, commercial and open-source
solvers feature very eﬀective generic implementations of branch-and-cut, almost
every application of branch-and-price is ad hoc, that is, problem speciﬁc. Even
though the situation improved considerably due to the availability of open-source
branch-price-and-cut frameworks, implementations are often started from scratchor from previous projects. In addition, even though all concepts are reasonably
easy to understand, experience and expert knowledge is still indispensable to getmost out of the approach. In order to easily test new ideas, while using the current
state-of-the-art, it would be much more satisfactory to have a generic implementation. This—ideally—performs a decomposition if this is likely to be promising,and takes care of branch-and-price (not to forget: -and-cut), without the user’s
notice and interaction—just as it is the case for generic branch-and-cut today. A
future solver could terminate with the message
Integer optimal solution found (1209.71 sec., 2 threads)
P. Festa (Ed.): SEA 2010, LNCS 6049, pp. 239–252, 2010.
c Springer-Verlag Berlin Heidelberg 2010


240

G. Gamrath and M.E. Lübbecke

Mixed integer rounding cuts applied: 65
Dantzig-Wolfe decomposition performed (3 subproblems)
While one may be sceptical about such a complete automatism (it requires atleast detecting decomposable structures, and deciding how to best exploit them),a publicly available generic implementation which requires only a little userinteraction is rather a matter of months than years from now. Our work is acontribution to this aim.
Related Work. There are several frameworks which support the implementation of branch-and-price algorithms like ABACUS [7], BCP [13], and MINTO [9], toname only a few. We restrict attention to (non-commercial) codes which performa Dantzig-Wolfe decomposition of a general (mixed) integer program, and handle
the resulting column generation subproblems in a generic way. François Vanderbeck has been developing important features [16,18,19,20] for his own implementation called BaPCod [17] which is a “prototype code that solves mixed integer
programs (MIPs) by application of a Dantzig-Wolfe reformulation technique.”Also the COIN-OR initiative (www.coin-or.org) hosts a generic decomposition
code, called DIP [12] (formerly known as DECOMP), which is a “framework for
implementing a variety of decomposition-based branch-and-bound algorithms
for solving mixed integer linear programs” as described in [11]. The constraint
programming G12 project develops “user-controlled mappings from a high-level
model to diﬀerent solving methods,” one of which is branch-and-price [10]. Asof this writing, among these projects (including ours), only DIP is open to the
public (as trunk development, there is no release yet).
Our Approach. We witness a development towards generic, re-usable implementations, however, in a sense, again started from scratch each time, at least interms of standard MIP techniques like preprocessing and tree management etc.
This is why, in this paper, we follow the diﬀerent approach in complementing an
existing, well-accepted, and well-maintained MIP solver, namely SCIP [1]. The
rationale behind this is, of course, to have the full range of MIP tools available in
one solver one future day, including a generic and automatic decomposition; so
we found it reasonable to start from the state-of-the-art in non-commercial MIP
solving [8]. The implementation is in such a way that it beneﬁts from improvements of the solver itself, e.g., when better branching or node selection rules
become available, preprocessing or propagation are getting more eﬀective.

2

Decomposition of Integer Programs

We wish to solve an MIP, which is called the original (or compact ) problem,min{ct x | Ax ≥ b, Dx ≥ d, x ∈ Zn+ × Qq+ } .

(OP)

It exposes a structure in the sense that X = {x ∈ Zn+ × Qq+ | Dx ≥ d} is a mixed
integer set, optimization over which is considerably easier (computationally)

Experiments with a Generic Decomposition

241

than solving (OP) itself. For many problems, D can be brought into a (bordered)block-diagonal form, so that (OP) can be written as
ctk xk |Ak xk ≥ b, Dk xk ≥ dk ∀k, xk ∈ Zn+k × Qq+k ∀k} . (OPk)
min{
k

k

In this case X = X1 × · · · × XK (possibly permuting variables), that is, X
decomposes into Xk = {xk ∈ Zn+k × Qq+k | Dk x ≥ d
. . , K, with allk }, k = 1, .
matrices and vectors of compatible dimensions and k nk = n, k qk = q. We
discuss two ways of exploiting this structure when solving (OP). A very thoroughexposition of advantages and disadvantages, possibilities, extensions, examples,and much more context can be found in the most recent survey [22].
Convexification. By the Minkowski-Weyl theorem we express each xk ∈ conv(Xk )as a convex combination of extreme points Pk of conv(Xk ) plus a non-negative
combination of extreme rays Rk of conv(Xk ), with Pk and Rk ﬁnite. For ease ofpresentation, we assume Xk bounded, i.e., Rk = ∅. In analogy to a Dantzig-Wolfe
decomposition of linear programs, we introduce a variable λkp for each p ∈ Pk and
require p∈Pk λkp = 1 (convexity constraints). Substituting xk = p∈Pk pλkp , weobtain the extended formulation




ckp λkp |akp λkp ≥ b,
λkp = 1, xk =pλkp ∀k,
min{
p∈Pk
p∈Pk
k p∈Pkk p∈Pk(EPC)|P |xk ∈ Zn+k × Qq+k ∀k, λk ∈ Q+ k ∀k}where ckp = ck p and akp = Ak p. Integrality is required on the original variables.
Discretization. For pure integer programs, i.e., qk = 0 for all k, one can implicitly
express xk as an integer convex combination of the integer points in Xk , i.e., xk =kkp∈Xk pλp , λp ∈ {0, 1} ∀k [16]. Unifying the notation with the convexiﬁcation
approach, we denote the set Xk of points by Pk and obtain



|P |
min{
ckp λkp |akp λkp ≥ b,
λkp = 1, λk ∈ Z+ k ∀k} . (EPD)k p∈Pkk p∈Pkp∈PkThis can be generalized to MIPs, when continuous variables are convexiﬁed [21].
Often, some or all Xk are identical, e.g., for bin packing, vertex coloring, orsome vehicle routing problems. This introduces a symmetry which is avoided byaggregating (summing up) the λkp variables. We choose a representative P := P1 ,
substitute λp := k λkp , and add up the convexity constraints. This leads to theaggregated extended formulation



|P |
cp λp |
ap λp ≥ b,
λp = K, λ ∈ Z+ } .
(EPDa)
min{
p∈P

p∈P

p∈P

Column Generation and Branch-and-Price. For the LP relaxation of theextended problem, we drop the integrality constraints, and also omit the original

242

G. Gamrath and M.E. Lübbecke

variables in the convexiﬁcation approach. We obtain the master problem



|P |
ckp λkp |akp λkp ≥ b,
λkp = 1, λk ∈ Q+ k ∀k} .
min{
(MP)
k p∈Pkk p∈Pkp∈Pk

Since (MP) typically has an exponential number of variables, it is solved via
column generation. That is, we work with a restricted master problem (RMP )that contains only a subset of the variables. In each node of the branch-andbound tree, the RMP is solved to optimality, and variables with negative reduced
cost are added. One iterates until no more variables are found. As the reduced
cost of a variable λkp is given by c̄kp = ctk p − (π t Ak p + γk ) with (π t , γ t )t being
the optimal dual solutionto the RMP,
each block k ∈ [K], the we solve, for 
pricing problem c̄k = min ctk − π t Ak x − γk | x ∈ Xk . The LP relaxation canbe strengthened by additional valid inequalities (in diﬀerent ways). If the solution
is still fractional, branching takes places, for convexiﬁcation typically on theoriginal variables, but see e.g., [20] for a diﬀerent generic rule which does notinterfere with the pricing problem and avoids symmetry.

3

Some Details on the Implementation in SCIP

Our implementation GCG (generic column generation) extends SCIP [1] which
was well received in the computational mathematical programming community.
While the ﬂexible plugin-based architecture enables the user to easily implement
column generation in every node of the search tree, it neither provides methods
for decomposition nor does it work with original and extended problem formulations simultaneously. Our work aims at complementing SCIP in this respect,turning the branch-price-and-cut framework into a branch-price-and-cut solver.
3.1

Overview: Synchronizing Two Trees

We maintain two SCIP instances, one for the original, one for the extended problem (called original and extended instance, respectively). The original instance isthe primary one which coordinates the solving process, the extended instance iscontrolled by a relaxation handler that is included into the original instance. At
the moment, information about the structure of the problem has to be provided
by an additional input ﬁle, that deﬁnes the relation between variables and blocks
and may explicitly force constraints as linking constraints, i.e., constraints thatwill be transferred to the extended (master) problem.
After the original instance is presolved, the relaxator performes the DantzigWolfe decomposion and initializes the extended SCIP instance as well as the
SCIP instances representing the pricing problems. The extended instance initially contains no variables. Original variables that are labeled to be part of a
block, and constraints containing variables of just one block are copied into thecorresponding pricing problem unless explicitly forced otherwise. All remaining
constraints are transferred to the extended problem.

Experiments with a Generic Decomposition

243

During the solving process, the extended instance builds the branch-andbound tree in the same way as the original instance. There is a bijection
between nodes of the original instance and nodes of the extended instance;
two corresponding nodes are solved at the same time. When solving a nodeof the original instance, the node lower bound is not computed by solving thenode’s LP relaxation, but the special relaxator is used for this purpose which
instructs the extended SCIP instance to solve the next node. A special node selector in the extended instance chooses as the next node to be processed the nodecorresponding to the current node in the original instance. Branching restrictions are imposed by a branching rule included in the original instance, so they
have to be transferred to the node of the extended instance when it is activated.
The solving process of the node starts with domain propagation, i.e., tightening
the domains of the variables for the local problem, a concept that is also used forthe enforcement of branching decisions. The LP relaxation of the problem
corresponding to the node—the master problem—is then solved by column
generation.
After the master problem is solved, bounding is performed and branching is
performed if needed, creating two children without further problem restrictions.
The solving process of the extended problem is then halted and the relaxatorin the original instance transfers the local dual bound and the master problem’scurrent solution as well as new primal solutions to the original instance. The
current node in the original instance is pruned if and only if the corresponding
node in the extended instance was pruned, since both nodes have the same dualbound and both instances have the same primal bound—each solution of one
instance corresponds to a solution of the other instance with the same objectivefunction value. However, it is possible that the master solution is fractional but
leads to an integral solution to the original problem. In this case, the current
subproblem is solved to optimality, otherwise, branching is performed. Two children are created and branching restrictions are imposed in the original instance,that will be transferred to the corresponding nodes in the extended instance on
activation. After the branching, the original instance selects a next node and theprocess is iterated. Fig. 1 shows GCG’s solving process.
We decided to work with both formulations simultaneously rather than transforming the original problem into an extended problem and solving this problem
with a branch-price-and-cut algorithm, since it ﬁts better into the SCIP framework and makes better use of the functionalities already provided. The original
problem can be read in a variety of formats by the original instance using SCIP’s
default ﬁle reader plugins. If we do not read a ﬁle deﬁning the structure of the
problem, the problem is solved by SCIP with a branch-and-cut algorithm. Otherwise, the special relaxator is activated, creates the extended SCIP instance,
performs the Dantzig-Wolfe decomposition, and substitutes the LP relaxationin the branch-and-bound process. Both problems are solved in parallel, so thattechniques that speed up the solving process, like presolving, domain propagation, and heuristics, can be used in both instances. For details see [6].

244

G. Gamrath and M.E. Lübbecke

Presolving

Start

Decomposition

Node selection

Stop

Select corresponding node
and apply branching changes

Domain propagation

Domain propagation

Solve relaxation

Solve master problem
with column generationand cut separation

Transfer solution
Constraint enforcement
Constraint enforcement

Branching

Branchingoriginal SCIP instanceextended SCIP instanceFig. 1. Solving process of GCG

3.2

Pricing

We structure the pricing implementation in variable pricer and a set of pricing
solvers. The former coordinates the pricing process, while the latter are called by
the variable pricer to solve a speciﬁc pricing problem. A variable pricer plugin
is added to the extended instance. These plugins have two essential callbacks
that are called during the pricing process, one for Farkas pricing, which is called
by SCIP whenever the RMP is infeasible, the other for the reduced cost pricing,which is called in case the RMP is feasible.
We introduced the concept of pricing solvers, which are used by the pricer ina black box fashion: Whenever a speciﬁc pricing problem should be solved, it isgiven to the set of solvers, solved by one of the solvers, and a set of solutions
is returned. We chose this concept, which is similar to the way the LP solver ishandled in SCIP, in order to provide a possiblity to add further problem speciﬁcsolvers as external plugins without the need to modify the variable pricer.
We compute the intermediate Lagrangean dual bounds every time all pricing
problems were solved to optimality in a pricing round and update the dualbound of the current node each time this leads to an improvement. We make useof early termination, i.e., if all solutions have integral values—this is detected in
the presolving process of the original problem—we abort the pricing process at
a node whenever LB ≥ zRMP for the current local dual bound LB and the
optimal objective value zRMP of the RMP in this pricing iteration.

Experiments with a Generic Decomposition

245

When using the discretization approach, we identify identical subproblems
and automatically aggregate them. That is, if Xi = Xj for all i, j ∈ {1, . . . , k},
we deﬁne aggregate variables λp = k λkp in the master problem.
3.3

Branching Rules

We provide two branching rules, one that branches on the variables of the original
problem and Ryan and Foster’s branching scheme [14] for problems with a set
partitioning master problem. When branching on original variables, the mastersolution is transferred into a solution of the original problem, an integer variable
xki with fractional value v is identiﬁed and the domain of the variable is split
by adding constraints xki ≥ v and xki ≤ v , respectively, to the two childnodes. These constraints can be enforced in the pricing problems as well as in
the extended problem. The latter leads to an additional constraint in the masterproblem, its dual variable is respected in the objective function of the pricing
problem like it is done for the other master constraints. Enforcing the branchingdecisions in the pricing problems can lead to better dual bounds at the expensethat all variables in the master problem have to be checked for their feasibility
w. r. t. the current pricing problems. This is done via domain propagation in theextended instance; variables that are not compatible with branching decisions are
locally ﬁxed to zero. It is well-known that the choice of the variable to branch on
has a big impact on the performance of the branch-and-bound process [2]. Hence,apart from most infeasibility branching, we provide the possibility to make use ofpseudocosts of the variables in the original problem. This leads to a considerable
decrease of computational time for the class of capacitated p-median problems(Sect. 4.1). The Ryan and Foster branching scheme is used for problems with aset partitioning master structure and for problems with identical blocks.
3.4

Presolve and Propagation

We perform standard SCIP presolving on the original problem. Furthermore, ateach node, we perform domain propagation in the original instance as well as
the extended instance. In the extended instance, we use it primarily to remove
variables from the problem, that are not valid for the current pricing problem.
In the original instance, standard domain propagation methods are used thatlead to domain reductions especially when branching on the original variables.
These reductions can then be imposed on the variables of the pricing problems,
too. Variables that fulﬁll these bounds are called proper [21].
3.5

Cutting Plane Separators

A by now “standard” way to strengthen the dual bound it to derive valid inequalities from the original variables. An original fractional solution
can be separated

by SCIP’s default cut separation plugins. Note that xk = p∈Pk pλkp is not a basic solution in (OPk), thus we cannot use Gomory mixed integer cuts or strong
Chvátal-Gomory cuts. Nevertheless, we can use all kinds of cutting planes that

246

G. Gamrath and M.E. Lübbecke

do not need any further information besides the problem and the current solution in their separation routine. This applies, for example, to knapsack covercuts, mixed integer rounding cuts, and flow cover cuts. An alternative is to derive cuts from the extended formulation. This may lead to stronger cuts but has
the drawback that the dual variable of a cut has to be respected in the pricing
problems, which typically results in additional variables and constraints added
to the pricing problems, see [5] for a very recent uniﬁed view.
3.6

Primal Heuristics

The default primal heuristics of SCIP (including sophisticated ones) are applied
to the extended instance. Simple rounding heuristics are performed in each iteration of the column generation process which often ﬁnd feasible primal solutions.
Currently, most heuristics make use of the LP relaxation, so we cannot run themon the original instance. This is to be changed in the future.
3.7

Customization and Extendibility

It is to be expected that a tailor-made approach will outperform a generic one,so we keep the possibility to extend and customize the framework, in addition toadding pricing solvers. SCIP’s interface for branching rules is extended in orderto give the possibility to deﬁne branching rules operating on both the originalas well as the extended formulation. This includes ways to enforce branchingdecisions in the pricing problems and to store pseudocosts for branching on constraints. Finally, problem speciﬁc plugins for presolving, node selection, domain
propagation, separation and primal heuristics can be added to either one of the
two SCIP instances as usual.

4

Computational Study

We tested our solver GCG 0.7 on MIPs which expose various diﬀerent structuresusing SCIP 1.2.0.5 with CPLEX 12.1 as embedded LP solver. The computations
presented in Section 4.1 and 4.2 were performed on a 2.66 Ghz Core2 Quad with
4MB Cache and 4GB RAM, those of Section 4.3 on a 2.83 GHz Core2 Quad with
6MB cache and 16GB RAM. We compute averages using the shifted geometricmean, i.e., for non-negative numbers a1 , . . . , ak ∈ R+ , e.g., the number of nodes,
the solving time, or the ﬁnal gap of the individual instances of a test set, and ashift s ∈ R+ , the average is deﬁned by kγs (a1 , . . . , ak ) =1
k(ai + s)

− s.

i=1

We use a shift of 10 for the runtime and the number of branch-and-bound nodes
and 100 for the ﬁnal gap in percent. The average value of multiple test sets iscomputed in the same way, using the shifted geometric means of the individual
test sets.

Experiments with a Generic Decomposition

247

SCIP

GCG

no pseudocost

knapsack

nodes

cpmp50s
cpmp100s
cpmp150s
cpmp200s
sh. geom. mean

896.2
14234.2
15128.7
26263.98454.9

44.9
587.1
847.6
1753.3
461.8

82.5
1962.62211.75577.71216.642.1
491.6
1228.62338.0515.1

time (outs)

Table 1. Comparison of GCG and SCIP for the capacitated p-median test sets. We
list the shifted geometric mean of the number of branch-and-bound nodes (top), andthe runtime (bottom) for SCIP (ﬁrst column) and GCG (second column) with default
settings. The next columns illustrate the performance eﬀect of disabling the pseudocost
branching rule and using the most fractional rule instead (third column) and of using a
specialized knapsack solver to solve the pricing problems (last column). Following theruntime, in brackets, we list the absolute number of timeouts.
test set

cpmp50s
cpmp100s
cpmp150s
cpmp200s
sh. geom. mean

14.5 (0)234.8 (3)714.5 (9)1950.7 (7)294.0 (19)12.8 (0)184.7 (1)493.5 (5)1243.9 (3)220.1 (9)20.7 (0)469.5 (6)920.3 (10)2978.0 (10)439.7 (26)

1.8 (0)37.8 (0)253.8 (1)519.3 (0)84.3 (1)

4.1

Diﬀerent Subproblems: The Capacitated p-Median Problem

In the capacitated p-median problem we are given a set N of nodes, each with ademand qn ∈ Z+ , n ∈ N . In each node n ∈ N , a facility with capacity C canbe opened; p of which have to opened in total. The distance between a noden ∈ N and a facility placed at node m ∈ N is given as dn,m ∈ Z. Nodes are
assigned to opened facilities so that the total sum of connection distances isminimized and the capacity constraints are respected. To solve large instancesby branch-and-price, so far an ad hoc implementation was necessary [4].
The problem can be decomposed by deﬁning one block for each possible facility
location which contains the capacity constraint corresponding to this location.
The blocks are not identical since the objective function coeﬃcients of the variables depend on the location represented by this block. Therefore, we branchon the original variables. We used a subset of the instances used in [4] and deﬁned four test sets cpmpNs, each of which contains instances with N nodes,
N ∈ {50, 100, 150, 200}. In order to reduce the computational eﬀort, we missed
out every second instance in the test sets with up to 150 nodes and selected only
12 instances for test set cpmp200s, three for each number of facilities.
Tab. 1 shows that the generic branch-and-price approach performs better thanplain SCIP. It particularly pays oﬀ to have a state-of-the-art branching rule athand: using most fractional branching instead of pseudocost branching doubles
the shifted geometric mean of the solution time. Furthermore, by using a dynamic
programming knapsack solver to solve the pricing problems and customizing thecode in this way, we are able to decrease the shifted geometric mean of thesolving time by more than 60% compared to GCG with default settings. Moredetailed computational experiments are reported in [6].

248

G. Gamrath and M.E. Lübbecke

Table 2. Computational results for the 180 instances of each size in the bin packing
test set

number of items

total

nodes
sh. geom. mean

total

time
sh. geom. mean

50
100
200

713
1617
5229

3.3
6.7
17.6

54.7
254.4
2186.8

0.3
1.4
11.7

4.2

Identical Subproblems: Bin Packing

Bin packing instances have identical blocks and a set partitioning master problem, so the variables were aggregated and Ryan and Foster’s branching scheme
was used. It is well-known that the Dantzig-Wolfe decomposition of the bin
packing problem leads to strong dual bounds, so we were able to solve all 540
instances (all 180 instances with 50, 100, and 200 items, respectively, of data
set 1 of [15]) in less than 90 minutes altogether, cf. Tab. 2. For each number of
items, GCG solves the whole test set faster than SCIP solves the ﬁrst instance ofthe set.
4.3

No Block Structure: A Resource Allocation Problem

The following generalized knapsack problem [3] does not have a block structure(but staircase structure). Given a number of periods n ∈ N and items i ∈ I,
each item has a proﬁt pi , a weight wi , and a starting and ending period. In eachperiod, the knapsack has capacity C and items consume capacity only during
their life time. The problem can be modelled in the following way:
pi xi |
wi xi ≤ C ∀n ∈ N, xi ∈ {0, 1} ∀i ∈ I} ,
(RAP)
max{
j∈I

i∈I(n)

where I(n) is the set of items that are alive in period n ∈ N . The matrix canbe transformed into block structure by splitting the capacity constraints into
groups of size M [3]. For each variable that appears in more than one group, wecreate a copy of this variable for each group and link the values of these copies toeach other by additional constraints. These additional constraints will be part ofthe extended formulation, the M capacity constraints corresponding to a block
are transferred to this block’s pricing problem.
We performed computational experiments (see Tab. 3) for the instances described in [3]. We used SCIP 1.2.0.5 for solving formulation RAP explicitly, and
GCG 0.7 to solve the reformulation of the problem grouping 32 and 64 constraints
to form one block, respectively. The same grouping was used in [3]. SCIP wasable to solve ﬁve instances within the timelimit of one hour, the remaining 65
instances remained unsolved with a ﬁnal gap between 0.1 and 3.0 percent. For
both numbers of constraints grouped per block, GCG was able to solve 56 instances, the ﬁnal gap of the remaining instances was typically lower than 0.3

Experiments with a Generic Decomposition

249

Table 3. Computational results for the test set of RAP instances. We list the ﬁnal
gap, the number of branch-and-bound nodes and the runtime for SCIP, GCG with 32
constraints assigned to a block, and GCG with 64 constraints assigned to a block.
SCIP
nodes

GCG (32)
GCG (64)
time gap nodes
time gap nodes
time

instance

gap

new1 1
new1 2
new1 3
new1 4
new1 5
new1 6
new1 7new1 8new1 9new1 10new2 1
new2 2
new2 3
new2 4
new2 5
new2 6
new2 7new2 8new2 9new2 10new3 1
new3 2
new3 3
new3 4
new3 5
new3 6
new3 7new3 8new3 9new3 10
new4 1
new4 2
new4 3
new4 4
new4 5
new4 6
new4 7
new4 8
new4 9new4 10

1.3 >757186 >3600.0
1.7 >589833 >3600.0
1.6 >408635 >3600.0
1.7 >296254 >3600.0
2.0 >262849 >3600.0
1.4 >194120 >3600.0
1.5 >163145 >3600.0
1.7 >161800 >3600.0
1.8 >108307 >3600.0>84190 >3600.0
2.2
2.0 >750775 >3600.0
1.4 >580746 >3600.0
1.1 >415357 >3600.0
1.2 >428950 >3600.0
1.9 >207493 >3600.0
2.0 >198288 >3600.0
1.6 >188555 >3600.0
1.7 >142970 >3600.0>75900 >3600.0
1.8
1.9 >131284 >3600.0
1.3 >233708 >3600.0>89037 >3600.0
1.2>75770 >3600.0
1.3>84830 >3600.0
1.4>19150 >3600.0
1.7>8632 >3600.0
2.2>35455 >3600.0
1.8>30130 >3600.0
1.8>25500 >3600.0
2.4>864 >3600.0
2.6
0.0
4907
16.1
0.0
187
4.8
0.0
132
6.0
0.1 >1571331 >3600.0
0.0
70140
342.6
0.2 >792713 >3600.0
0.0670545 3406.9
0.2 >535592 >3600.0
0.2 >546140 >3600.0
0.2 >507737 >3600.0

0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.1
0.0
0.0
0.1
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0

29
201.2 0.0
119979.6 0.023359.7 0.0
187 1888.9 0.0
41828.6 0.0
17468.5 0.027460.6 0.0
13583.6 0.087 1687.5 0.0
35 1085.1 0.0
7109.5 0.0
136
898.0 0.023
299.5 0.0
1118.9 0.0
161 1622.6 0.1
11425.6 0.036642.2 0.0
13399.6 0.031702.4 0.0
151 1489.0 0.0
31 1205.1 0.0>119 >3600.0
0.0
13 1227.5 0.0
39 2596.2 0.0
33 1937.4 0.0>55 >3600.0
0.0>88 >3600.0
0.0
53 3535.1 0.0>40 >3600.0 73.8
>45 >3600.0
0.2
126.1 0.0
117.9 0.0
1
24.6 0.0
173.0 0.0
1386.4 0.0
158.8 0.0
157.0 0.04
99.3 0.0
3
92.6 0.0
361.0 0.0

3
111.4
13
350.5
9
529.5
7
473.3
11
562.3
39 1143.4
1
478.7
3
350.6
2
453.4
7
896.1
3
140.0
44
744.7
2
135.9
1
367.1
>154 >3600.0
4
326.9
13
740.3
14
782.2
1
293.5
41 1274.4
1 1205.8>49 >3600.0>7>3600
9 1688.5
9 3039.5>39 >3600.0>62 >3600.0
5 3172.4>1 >3600.0>27 >3600.0
1
15.6
1
17.1
1
28.4
1
44.5
13
106.3
1
66.1
1
54.1
3
59.0
3
93.6
5
154.4

250

G. Gamrath and M.E. Lübbecke
Table 3. (continued )GCG (32)
GCG (64)
time gap nodes
time gap nodes
time

SCIP
nodes

instance

gap

new5 1
new5 2
new5 3
new5 4
new5 5
new5 6
new5 7
new5 8
new5 9new5 10
new6 1
new6 2
new6 3
new6 4
new6 5
new6 6
new6 7
new6 8
new6 9new6 10
new7 1
new7 2
new7 3
new7 4
new7 5
new7 6
new7 7
new7 8
new7 9new7 10

0.7 >640409
1.3 >317663
0.9 >318430
1.4 >247945
1.4 >120474
1.3 >147990
1.0 >135050
1.3 >114213
1.2 >78548
1.7 >22990
1.0 >215663
1.2 >159970
1.0 >92896
1.0 >93850
1.1 >69570
1.8 >14540
2.3 >10384
>6209
1.6
1.7 >38634>772
3.0
1.4 >537230
1.5 >373513
1.4 >230756
1.8 >164797
1.3 >147376
1.7 >158523
1.7 >95711
2.2 >96525
1.7 >80942
2.4 >78398

3600.03600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0>3600.0
>
>

0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.1
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.1
0.0
0.0

23
254.4
11
248.6
3
177.1
75 1445.6
42871.3
161 3570.1
133 2008.2
15
554.7>124 >3600.0
85 2109.2
25
692.2
7
518.3
27
975.0
17 1091.2
29 1546.7
13 1094.0>51 >3600.0>77 >3600.0>37 >3600.0>55 >3600.0
58
614.3
31
624.5
46
823.1
25
665.2
9
486.2
>186 >3600.0>140 >3600.0>148 >3600.0
31 1051.1>107 >3600.0

0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.1
0.0
0.0
0.1

1
130.1
1
230.7
3
282.4
3
265.3
17
887.4
>129 >3600.0
13
730.5
1
564.4
>87 >3600.0
25 1799.1
7
484.2
3
686.3
11
559.0
1
628.5
21 1826.8
7 1714.0
3 1368.9>38 >3600.0
3 2030.4>35 >3600.07276.9
41 1263.9
11545.2>37 >3600.0
9791.8
34 3032.1>74 >3600.0
19 3205.4
11 1800.4>42 >3600.0

total
97.1 16259k 237776.4 0.4 3484.0 98169.6 74.3 1305.0 95403.1
timeouts
65/70
14/70
14/70
sh. geom. mean 1.4 97564.0
2772.4 0.0
32.2
727.4 0.8
11.5
670.7

percent. For both sizes of blocks, GCG was about four times faster than SCIP in
the shifted geometric mean.
The relaxation given by the master problem is tighter the more constraints
are assigned to a block, so with 64 constraints per block, we need less nodes tosolve the problems. The shifted geometric mean of the number of nodes accounts
11.5 for the former variant, compared to 21 nodes when assigning 32 constraints
to each block. In return, more time is needed to solve the master problem, but
this pays oﬀ for this test set since the total time is reduced by 8%. The average
gap is higher when grouping 64 constraints, however, this is caused by one single

Experiments with a Generic Decomposition

251

instance for which the master problem at the root node could not be solved
within the time limit of one hour so that just a trivial dual bound is obtained,leading to a gap of more than 70 percent.

5

Summary and Discussion

We report ﬁrst computational experiments with a basic generic implementationof a branch-price-and-cut algorithm within the non-commercial framework SCIP.
Given an MIP and information about which rows belong to which subproblem(or the master problem), either a convexiﬁcation or discretization style decomposition is performed. For structured problems, the approach is very promising.
The modular design of SCIP allowed us to include the described functionality
in the form of plugins. A true integration would require a few extensions, some ofwhich have been incorporated into SCIP during this project already, but some arestill missing. Examples include per-row dual variable stabilization, column pool,
primal heuristics on original variables, LP basis of original variables for cutting
planes like Gomory cuts, etc. It is planned that our implementation becomespart of a future release of SCIP. We hope that this enables researchers to playwith and quickly test ideas in decomposing mixed integer programs.
It remains to be demonstrated that there really is a signiﬁcant share of problems on which decomposition methods are more eﬀective than (or a reasonable
complement to) standard branch-and-cut, even when one does not know about
a possibly contained structure. This requires detecting whether it may pay to
decompose any given MIP, and if so, how this should be done. This is, of course,
a much more challenging question which is the subject of our current research.
Acknowledgment. We thank Alberto Ceselli and Enrico Malaguti for providing us with the p-median and RAP instances from Sections 4.1 and 4.3,
respectively.

References
1. Achterberg, T.: SCIP: Solving constraint integer programs. Math. Programming
Computation 1, 1–41 (2009)
2. Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Operations
Research Letters 33, 42–54 (2005)
3. Caprara, A., Furini, F., Malaguti, E.: Exact algorithms for the temporal knapsackproblem. Technical report OR-10-7, DEIS, University of Bologna (2010)
4. Ceselli, A., Righini, G.: A branch-and-price algorithm for the capacitated p-medianproblem. Networks 45, 125–142 (2005)
5. Desaulniers, G., Desrosiers, J., Spoorendonk, S.: Cutting planes for branch-andprice algorithms, Les Cahiers du GERAD G-2009-52, HEC Montréal (2009)
6. Gamrath, G.: Generic branch-cut-and-price. Master’s thesis, Institut für Mathematik, Technische Universität Berlin (2010)
7. Jünger, M., Thienel, S.: The ABACUS system for branch-and-cut-and-pricealgorithms in integer programming and combinatorial optimization. Softw. Pract.
Exper. 30, 1325–1352 (2000)

252

G. Gamrath and M.E. Lübbecke

8. Mittelmann, H.: Benchmarks for optimization software (2010),
http://plato.asu.edu/bench.html
9. Nemhauser, G., Savelsbergh, M., Sigismondi, G.: MINTO, a Mixed INTeger Optimizer. Oper. Res. Lett. 15, 47–58 (1994)
10. Puchinger, J., Stuckey, P., Wallace, M., Brand, S.: Dantzig-Wolfe decomposition
and branch-and-price solving in G12. Constraints (to appear, 2010)
11. Ralphs, T., Galati, M.: Decomposition and dynamic cut generation in integer linear
programming. Math. Programming 106, 261–285 (2006)
12. Ralphs, T., Galati, M.: DIP – decomposition for integer programming (2009),
https://projects.coin-or.org/Dip
13. Ralphs, T., Ladányi, L.: COIN/BCP User’s Manual (2001),
http://www.coin-or.org/Presentations/bcp-man.pdf
14. Ryan, D., Foster, B.A.: An integer programming approach to scheduling. In: Wren,
A. (ed.) Computer Scheduling of Public Transport Urban Passenger Vehicle andCrew Scheduling, pp. 269–280. North Holland, Amsterdam (1981)
15. Scholl, A., Klein, R.: Bin packing instances: Data set 1,
http://www.wiwi.uni-jena.de/Entscheidung/binpp/
16. Vanderbeck, F.: On Dantzig-Wolfe decomposition in integer programming andways to perform branching in a branch-and-price algorithm. Oper. Res. 48, 111–128(2000)
17. Vanderbeck, F.: BaPCod – a generic branch-and-price code (2005),
https://wiki.bordeaux.inria.fr/realopt/pmwiki.php/Project/BaPCod
18. Vanderbeck, F.: Implementing mixed integer column generation. In: Desaulniers,G., Desrosiers, J., Solomon, M. (eds.) Column Generation, pp. 331–358. Springer,
Heidelberg (2005)
19. Vanderbeck, F.: A generic view of Dantzig-Wolfe decomposition in mixed integer
programming. Oper. Res. Lett. 34, 296–306 (2006)
20. Vanderbeck, F.: Branching in branch-and-price: A generic scheme. Math. Programming (to appear, 2010)
21. Vanderbeck, F., Savelsbergh, M.: A generic view of Dantzig-Wolfe decompositionin mixed integer programming. Oper. Res. Lett. 34, 296–306 (2006)
22. 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)