Contributed to the Wiley Encyclopedia of Operations Research and Management Science (EORMS).

Branch-Price-and-Cut Algorithms
Jacques Desrosiers
HEC Montréal and GERAD
3000, chemin de la Côte-Sainte-Catherine
Montréal, Québec, Canada H3T 2A7
jacques.desrosiers@hec.ca
Marco E. Lübbecke
Technische Universität Darmstadt
Fachbereich Mathematik, AG Optimierung
Dolivostr. 15, 64293 Darmstadt, Germany
luebbecke@mathematik.tu-darmstadt.deApril 8, 2010; revised July 7, 2010

Abstract
In many mixed integer programs there is some embedded problem structure which can be
exploited, often by a decomposition. When the relaxation in each node of a branch-andbound tree is solved by column generation, one speaks of branch-and-price. Optionally,
cutting planes can be added in order to strengthen the relaxation, and this is called branchprice-and-cut. We introduce the common concepts of convexification and discretization
to arrive at a Dantzig-Wolfe type reformulation of a mixed integer program. The relation
between the original and the extended formulations helps us understand how cutting
planes should be formulated and how branching decisions can be taken while keeping thecolumn generation subproblems manageable.
Key words: Integer programming; Dantzig-Wolfe decomposition; column generation; cutting planes; branch-and-bound.

1Decompositions and reformulations of mixed integer programs are classical approaches toobtaining stronger relaxations and reduce symmetry. These often entail the dynamic additionof variables (columns) and/or constraints (cutting planes) to the model. When the linear
relaxation in each node of a branch-and-bound tree is solved by column generation, one
speaks of branch-and-price. Optionally, as in standard branch-and-bound, cutting planes canbe added in order to strengthen the relaxation, and this is called branch-price-and-cut. Now,
having understood and familiarized oneself with the three concepts, branch-and-bound (seealso 1.4.2.1), column generation (see also 1.1.2.7), and cutting planes (see also 1.4.4) one
may think that the above explanation is the end of the story. Actually, this understanding
is precisely where the story begins. Strengthening the relaxation by means of cutting planes
and performing branching on fractional variables both interfere with column generation andmay entirely ruin the mentioned advantages of a decomposition when done naively.
In early years, one attempted to circumvent these complications in an ad hoc fashion [1] but
over time a generic theoretical understanding developed. The state-of-the-art relies on therelation between the original problem and its extended reformulation, as first used in [2].
There are very successful applications of branch-and-price in industry (see [3], and also e.g.,
4.4.4, vehicle routing and scheduling) and also to generic combinatorial optimization problems
like bin packing and the cutting stock problem [4], graph coloring [5], machine scheduling [6],the p-median problem [7], the generalized assignment problem [8], and many others. The
method today is an indispensable part of the integer programming toolbox.

1

Column Generation

Consider the following integer master problemXmin
cj λ jsubject toj∈JXa j λj

(1)

≤ b

j∈J

|J|

λ ∈ Z+ .
In many applications, |J| is huge (but always finite) and we solve the linear relaxation of (1),called the master problem, by column generation as follows (see also 1.1.2.7). The restricted
master problem (RMP) contains only a subset J ′ ⊆ J of variables, initially possibly none. In
each iteration, (a) we obtain λ∗ and π ∗ , the primal and dual optimal solutions to the RMP,
respectively. Then, (b) the following pricing problem (subproblem) is to be solved
v := min{c(x) − πa(x)} ,

(2)

x∈X

where cj = c(xj ) and aj = a(xj ) reflect that each column j ∈ J is associated with an element
xj ∈ X from a domain X over which we can optimize, often a set of combinatorial objects
like paths or other subgraphs (so, usually, the xj bears much more information than just thecolumn a(xj )). When v < 0 the variable λj and its coefficient column (cj , aj ) corresponding
to a minimizer xj are added to the RMP, and the process is iterated. Otherwise, v ≥ 0 provesthat there is no such improving variable, and the current λ∗ is an optimal solution to themaster problem.
2

2

Decompositions and Reformulations

In general, when solving mathematical programs involving integer variables, a good model isof utmost importance, see e.g., [9] for some general considerations (see also 1.4.1, models).
After all, the whole integer programming machinery is about better describing the convex hullof feasible integer solutions: tighter relaxations from a different modeling choice and cutting
planes fulfill this purpose. Also branch-and-price is motivated by the perspective for better
dual bounds and reduced problem symmetry. In the following we describe the groundwork.

2.1

Dantzig-Wolfe Decompositions for Integer Programs

The Dantzig-Wolfe decomposition principle in linear programming [10] was devised to exploit
sparsity and special structure in linear programs (see also 1.1.2.3, Dantzig-Wolfe decomposition). However, it reveals its true strength only when adapted to integer programs. We assume
that optimizing over the mixed integer set X = {x ∈ Zn+ × Qq+ | Dx ≤ d} is “relatively easy,”
which however, is overshadowed by additional complicated constraints, i.e.,
min cxsubject to Ax ≤ b
x ∈ X

(3)

is rather hard to solve when the “hidden” structure X is not exploited. The mixed integer
program (3) is called the original problem in this context and we call x the original variables.
As we will see, a decomposition will lead to a master and a pricing problem as above. It wasnoted already by Geoffrion [11] in the context of Lagrangean relaxation (see also 1.1.2.4) that
decomposing (3) by solving over X as a mixed integer program (and penalizing the violationof Ax ≤ b in the objective function) may yield a stronger dual bound than the standard linear
relaxation when the convex hull conv(X) is not an integral polyhedron. In this article, X is
assumed to be a pure integer set, i.e., q = 0; we only point to the mixed integer generalization
when needed.
2.1.1

Convexification

The classical decomposition approach builds on the representation theorems by Minkowski
and Weyl [12] and convexifies X, hence the name. Each x ∈ X can be expressed as a convex
combination of finitely many extreme points {xp }p∈P plus a non-negative combination offinitely many extreme rays {xr }r∈R of conv(X), i.e.,
X
X
X|P |+|R|x=xp λp +
xr λr ,
λp = 1, λ ∈ Q+
.
(4)
p∈P

r∈R

p∈P

Substituting for x in (3) and applying the linear transformations cj = cxj and aj = Axj ,j ∈ P ∪ R one obtains an extended formulation equivalent to (3), which is an integer master3

problem as (1):minsubject to

X

p∈P
X

X

cp λ p +a p λp +p∈P

cr λ rr∈RXa r λr
r∈R
X

≤

b

λp

=

1

λ
x

≥
=

0
X

(5)

p∈P

x

∈

xp λp +

p∈P
Zn+ .

X

xr λr

r∈R

The constraints involving only λ variables are called coupling constraints and convexity constraint, respectively. It is important to note that integrality is still imposed on the original x
variables. Due to the large cardinality of P ∪ R the LP relaxation of (5) is solved by column
generation (see also 1.1.2.7 and Sect. 1), where the constraints linking x and λ variables canbe dropped. Thus, only the dual variables π and π0 remain relevant where π0 corresponds tothe convexity constraint. The pricing problem is the integer programmin {cx − πAx − π0 | x ∈ X} ,(6)

for which, ideally, a tailored combinatorial algorithm is available; and if not, we need to solve
it with some standard IP solver which may be very time consuming.
2.1.2

Discretization

In contrast to convexification where conv(X) is reformulated, discretization is a reformulationof X itself. It enables us to require integrality on the master variables which is not validin (5). Vanderbeck [13] introduced the concept since “it allows for the development of aunifying and complete theoretical framework to deal with all relevant issues that arise in theimplementation of a branch-and-price algorithm.” As we will see he was in particular thinkingof cutting planes and branching. We need the fact [9] that every integer x ∈ X can be written
as an integral combination
X
X
X|P |+|R|x=xp λ p +xr λ r ,λp = 1, λ ∈ Z+
(7)
p∈P

r∈R

p∈P

with finite sets of integer points {xp }p∈P ⊆ X and integer rays {xr }r∈R of X. Note that
we slightly abused notation here since the set P of generators is usually not identical to thecorresponding extreme points of the convexification approach, and rays in R are scaled to be
integer. Substitution for x in (3) yields an integer master problemXXmincp λ p +cr λ rsubject to

p∈P
X

p∈P

a p λp +r∈RXa r λr
r∈R
X

≤ b
(8)

λp = 1p∈P|P |+|R|λ ∈ Z+
4,

where integrality is now imposed on the master variables λ, and again cj = cxj and aj = Axj ,j ∈ P ∪ R. Note that in fact λp ∈ {0, 1} for p ∈ P . It is known [13] that the LP relaxation
gives the same dual bound as (5). When solving (8) by column generation the pricing problem
is the same as above, but it needs to be able to generate integer solutions in the interior of
X. When X is bounded, (8) is a linear integer program even when the original problem (3)has non-linear P
cost function c(x):P Because of the convexity constraint, variables λ are binary,
thus c(x) = c( p∈P xp λp ) = p∈P cp λp turns into a linear objective function.

The discretization approach generalizes to a mixed integer set X in that integer variables are
discretized and continuous variables are reformulated using the convexification approach [14].
For general integer variables this is not straight forward using the convexification approach,but in the important special case X ⊆ [0, 1]n of combinatorial optimization, convexificationand discretization coincide. Both approaches yield the same dual bound which equals that of
Lagrangean relaxation (see also 1.1.2.5 and [15]).

2.2

Bordered Block-Diagonal Matrices

For many problems, X = X1 ×· · ·×XK (possibly permuting variables), that is, X decomposesdk }, k = 1, . . . , K, with all matrices and vectors of
into Xk = {xk ∈ Zn+k × Qq+kP| Dk xk ≤ Pcompatible dimensions and k nk = n, k qk = q. This is another way of saying that D canbe brought into a block-diagonal form, so that the original problem (3) readsX
c k xkminkX(9)
Ak xk ≤ b
subject tokxk∈ Xk ,

k = 1, . . . , K .

This is the classical situation for applying a Dantzig-Wolfe decomposition. Each xS
k is expressed using (4) or (7), with the introduction of λkj variables, j ∈ Pk ∪Rk , where P = K
k=1 Pk
S
R
.
It
is
an
importantspecial
case
that
some
or
all
(D
,
d
)
are
identical,
e.g.,
and R = Kkk
k=1 k
for bin packing, vertex coloring, or vehicle routing problems. This implies a symmetry since“the same” solution can be expressed in many different ways by permuting the k indices.
Symmetry is beautiful in many areas of mathematics, however, for an integer program it may
be a major source of inefficiency in a branch-and-bound algorithm and should be avoided
P by
all means. Typically, one aggregates (sums up) the λkp variables, substituting νp := k λkp ,and adding up the K convexity constraints. Extreme rays need no aggregation. Choosing a
representative P1 , we obtain the aggregated extended formulation
XX
cp ν p +cr λ rmin
subject to

r∈R
p∈P1
X
X
a p νp +a r λr ≤ b

p∈P1

r∈R
X

p∈P1

νp = K(10)|P |ν ∈ Z+ 1|R|
λ ∈ Z+ ,here in the discretization
P version. This also condenses the original xk variables into aggregatedoriginal variables z = k xk .
5

2.3

Extended Reformulations

Lifting a mixed integer problem to a higher-dimensional space, obtaining a stronger formulation there, and projecting this back to the original variables’ space is a well-known concept
in integer programming (see also 1.4.5.1, disjunctive inequalities and higher-dimensional representations). Not only for branch-and-price it is helpful to know some basic ideas. The very
recommendable survey [16] presents decomposition approaches in this context.
A polyhedron Q = {(x, λ) ∈ Rn × Rℓ | Ax + Lλ ≤ b} is called an extended formulation of apolyhedron O ⊆ Rn if Q can be projected to O, i.e., if O = projx (Q), where projx (Q) denotes
the projection of Q on the x variables, i.e., projx (Q) = {x ∈ Rn | ∃λ ∈ Rℓ : (x, λ) ∈ Q}.
Polyhedron Q is an extended formulation of the integer set X if X = projx (Q) ∩ Zn+ . Moregenerally, Q may itself be a mixed integer set, and we call Q an extended formulation of themixed integer set X if X = projx (Q). The discretization approach provides an example. We
also speak of a problem being an extended formulation, e.g., we call the linear relaxation of
the master problem (5) an extended formulation of the original problem (3).
As stated above, extended formulations are typically stronger than their original counterparts,and the special interest in Dantzig-Wolfe type extended reformulations Q of mixed integer
sets X lies in the fact that they are tight, i.e., projx (Q) = conv(X). That is, they are best ina well-defined sense at the expense that they may contain an exponential number of variables.
It is of main interest in our context that some experience and creativity with projections andextended formulations may help us reformulating a problem before a Dantzig-Wolfe decomposition is applied, be it implicit or explicit. This becomes important when formulating cutting
planes (Sect. 3) and branching rules (Sect. 4). In order to provide some intuition consider aflow-based formulation for the minimum spanning tree problem in a graph G = (V, E) where
one sends one unit of flow from a designated root node to all other nodes, i.e., |V | − 1 units
in total. An integer variable xij represents the amount of flow on edge (i, j) ∈ E, and binary
variables yij indicate whether (i, j) ∈ E is in the spanning tree. Edge (i, j) ∈ E may carryflow only when it is part of the tree, i.e., xij ≤ (|V | − 1) · yij . This “big-M ” formulation canbe much improved by extending the formulation by introducing
P k a separate flow commodity
k = 1, . . . , |V | for each node, that is, reformulate xij = k xij . The above mentioned constraint becomes xkij ≤ yij which obviously better reflects the integrality of the yij variables,
and thus gives stronger branching and cutting opportunities.
Reducing problem symmetry can be another reason to consider an extended formulation [17].
For problems like bin packing, graph coloring, and many others, binary variables xij assign
items i to identical entities j. The symmetry in index j can be broken e.g., by binary variables
zij which reflect the assignment of items i and j to the same entity but not items i < k < j.
Cutting planes are reported to be effective at the cost of a more complicated pricing problem.

2.4

Reversing Dantzig-Wolfe Decomposition

Column generation can be applied without a prior decomposition. Examples are set coveringor set partitioning problems like in the classical cutting stock problem or in vehicle and crewscheduling (see also 4.4.4). One directly formulates an integer master problem (1) together
with a pricing problem (2). Without a decomposition, there is no original problem. However,as we describe later, such an original problem can be very helpful in designing branching6rules and cutting planes. Consequently, we would like to construct a corresponding original
problem from (1) and (2). That is, in a sense, one aims at reversing the Dantzig-Wolfe
decomposition. Under a mild assumption which is typically true, this can be done [18]. The
idea exploits the fact that the pricing problem is formulated in original variables, e.g., when
the pricing problem constructs a path in a network, the decisions taken are typically whether
an edge is included in the path or not. Conformingwith our previous notation, we assume
Pthat we know an integer upper bound K on j∈J λj in (1) (the maximum number of vehicles,
paper rolls, bins, etc.). When the zero column a0 = 0 has cost c0 = 0 we can assume equality
constraints in an original formulation. We duplicate the pricing problem’s domain K times,
i.e., we set Xk = X, k = 1, . . . , K, and obtain a bordered block-diagonal form:
minsubject to

K
X

k=1
K
X

c(xk )a(xk ) = b

(11)

k=1

∈ Xk k = 1, . . . , K .

xk

Performing a Dantzig-Wolfe decomposition on (11) one obtains a formulation equivalent to (1)where each of the K pricing problems contributes, due to the convexity constraints, at mostone unit to the master solution. Note that this introduces the symmetry of identical subproblems by design of the construction and one needs to aggregate the xk variables. We haveproduced a projection to the variables implicitly given in the pricing problem. This is just one
option; symmetry avoiding projections are preferable, e.g., by explictly producing different
pricing problems.

3

Cutting Planes

Just as in standard branch-and-cut adding valid inequalities can strengthen the LP relaxation,yielding what is known as branch-price-and-cut. In the earlier days, this combination has been
considered problematic since the pricing problem must be aware of the coefficients in cutting
planes as these need to be lifted when new variables are generated. With the introduction of
the two viewpoints presented in this section the notion of compatibility became obsolete.
In the convexification approach (5) integrality is required on the x variables just as in theoriginal problem (3). Thus, it is only natural to formulate valid inequalities on these variables.
On the other hand, remembering the motivation for extended formulations (cf. Section 2.3),
this ignores the potential of the higher-dimensional space, or in other words: We would liketo formulate valid inequalities on the integer master variables of the discretization reformulation (8) as well. Our presentation follows [19], and several examples can be found therein.

7

3.1

Cutting Planes on the Original Variables

Assume that we know a set F x ≤ f of inequalities valid for the original problem (3), i.e.,
min cxsubject to Ax ≤ b
Fx ≤ fx ∈ X(12)

has the same integer feasible solutions. Via a Dantzig-Wolfe reformulation these inequalities
directly transfer to the master problem, both in convexification and discretization:XX
f p λp +f r λr ≤ f
(13)
p∈P

r∈R

with the linear transformations fj = F xj for j ∈ P ∪R. The dual variables α of the additional
inequalities (13) can be easily taken care of in the pricing problem, cf. (6):min{cx − πAx − αF x − π0 | x ∈ X}

(14)

or in other words, with the dynamic addition of valid inequalities formulated in the originalx variables, only the pricing problem’s objective function needs to be updated. We mayalternatively enforce the cutting planes in the pricing problem by reducing its domain to
XF = {x ∈ X | F x ≤ f }. The reason for doing so is that inequalities added to X are
convexified when we solve the pricing problem as an integer program, and thus we may hopefor a stronger dual bound. The pricing problem (6) becomesmin{cx − πAx − π0 | x ∈ XF } ,(15)which, interestingly, may sometimes be of the same structure as before the modification. Sets
P and R need to be updated in the master problems (5) or (8); moreover, variables λj withF xj > f , j ∈ P ∪ R, have to be eliminated.
Generic cutting planes (see also 1.4.4, polyhedral combinatorics) formulated on the originalx variables sometimes seem to have little or no effect on improving the usually already strong
dual bound (see also ?.?.?.?, decomposition techniques). This may also be due to the fact thatusually no basic solution to the original problem is available on which several generic cutting
planes rely (a crossover might help here). Currently, problem specific valid inequalities are
the alternative to go.
It is known that separation of particularly structured (e.g., integer) points may be considerablyeasier than separating arbitrary fractional solutions. This motivates to use the decomposition
to aid separation: A fractional master solution is a convex combination of integer solutions to
the pricing problems which can be recovered and separated separately. In [20] this is called
structured separation or decompose and cut.

3.2

Cutting Planes on the Master Variables

In many applications, and in particular in the discretization approach, the master variables
are integer variables. It is clear that not every inequality in the master λ variables can be8derived from the original x variables via a Dantzig-Wolfe decomposition, and this complicatesmatters as we will see. Assume that we already separated a set Gλ ≤ g of valid inequalities
in the master problem, i.e.,minsubject to

X

p∈P
X

p∈P
X

cp λ p +a p λp +gp λ p +

p∈P

X

r∈R
X

r∈R
X

cr λ ra r λr ≤ b(16)

gr λ r ≤ g

r∈RX

λp = 1p∈P|P |+|R|λ ∈ Z+.

The dual variables β of these cuts need to be respected when calculating reduced costs in thepricing problem—if we don’t we may re-generate “cut off” variables and end up in an infinite
loop of separation and pricing. Certainly, we would lose the strength of a cut if we didn’t lift
it. If we think of the cuts’ coefficients of a variable λj , j ∈ P ∪ R, as the result of a function
gj = g(aj ), the pricing problem readsmin{cx − πAx − βg(Ax) − π0 | x ∈ X} .

(17)

Function g can be quite complicated; it may be non-linear as in the case of a Chvátal-Gomory
rank-1 cut [9, 21] with rational multipliers u ∈ [0, 1)nXX⌊uap ⌋λp +⌊uar ⌋λr ≤ ⌊u1⌋ .
p∈P

r∈R

It can be helpful from a conceptual viewpoint to introduce new variables y = g(Ax) tocompute the coefficients from a solution to the pricing problem. An example is to introduce
new resources, one for each cutting plane, in the resource-constrained shortest path pricing
problem typically used in vehicle routing problems. As just mentioned we cannot hope thatg is linear, but if it is, i.e., y = g(Ax) = F x we immediately see that cutting planes on themaster variables contain those which can be derived from the original variables.
Desaulniers et al. [19] note that introducing additional variables in the pricing problem hints
at an extended original (possibly non-linear) formulation from which cutting planes in themaster variables follow by Dantzig-Wolfe decomposition (in the spirit of Section 2.4):
min cxsubject to Ax
y
x
y

≤
≤
∈
=

b
g
X
g(Ax) ,

(18)

where y ≤ g remains in the master problem while y ≤ g(Ax) goes in the pricing problem.
Cutting planes on the master variables is a recent topic. So far a successful separation ofclique inequalities [22], Chvátal-Gomory rank-1 cuts [21] (and subsets [23]) has been reported
only for a very few problems. The modified subproblems become harder, in particular when
the computation of cut coefficients requires severe modifications in the pricing problem.
9

3.3

Using an Extended Formulation

As noted in Sect. 2.3, extended formulations may give rise to tighter relaxations as they
may “better reflect integrality requirements of the problem.” Column generation based algorithms often offer natural candidates for such extended formulations when the pricing problem is solved via dynamic programming. Simple examples are the bin packing [24] or cutting
stock [25] master problems where the subproblem is a knapsack problem. The dynamic program for the knapsack problem with capacity B can be formulated as a longest path problem
in an acyclic network of pseudo-polynomial size, namely with B nodes representing the usedcapacity of the knapsack. Arcs between vertices i and j represent picking an item of size j − iwhen already a capacity of i is used. Zero-cost arcs between consecutive vertices represent
unused capacity. Using these arcs as variables for a reformulation of the pricing problem one
obtains a network flow problem.
In general, variables represent state transitions of the dynamic program and this may allow toformulate complex cutting planes, expressed in a simple way and without significant changes
to the pricing problem. In the capacitated vehicle routing problem [26] this approach leads
to variables xdij which state that some vehicle arrives in j, coming from i, with a remaining
capacity of d. Besides such “capacity-indexed formulations” e.g., time-indexed formulations
are used in scheduling problems. Flow conservation reformulated in these variables gives what
they call a base equality from which many families of valid inequalities can be derived.
There is good experience with such kinds of cutting planes also for the capacitated minimum
spanning tree problem [27], machine scheduling problems [28], and several more [16].

4Branching

Even though branching decisions can be imposed by additional constraints (which we know
how to do) we still have to find good branching rules. Disjunctive branching on the mastervariables is either not feasible (in convexification nobody asks for integer master variables) or
not advisable: In discretization branching a master variable to zero has essentially no effect on
the dual bound, while the up-branch significantly changes the solution, and thus potentiallythe dual bound. This produces an unbalanced search tree. Moreover, down-branching forbids
certain solutions to the pricing problem to be re-generated. This problem brought up thenotion of compatibility between pricing problem and branching rule which means that thepricing problem should not complicate after branching. Working simultaneously with original
and master formulation, i.e., branching on original variables helped a lot, but introduces new
problems, in particular when pricing problems are identical; we follow the classification of [16]which contains a thorough exposition. Let λ∗ denote an optimal solution to the restricted
master problem.

4.1

Convexification: Branching on Original Variables

When all pricing problems are distinct, in particular, when there is only one pricing problem,the convexification approach with its integrality requirement on original variables is the natural way
immediate by (5), branching candidates are all original xi variables with
P to go. As is∗∗/ Z+ , where xji denotes the i-th component of xj , j ∈ P ∪R. Dichotomic
xi = j∈P ∪R xji λj ∈10branching on xi creates two new problems, on the down-branch by imposing xi ≤ ⌊x∗i ⌋, andon the up-branch by requiring xi ≥ ⌈x∗i ⌉. There are two general options on how to enforce thebranching decision, either in the master problem or in the pricing problem. We only discuss
the down-branch, the up-branch is handled analogously.
Master Problem. The branching constraint xi ≤ ⌊x∗i ⌋ is reformulated via convexification,i.e., we add to the master problem (5) the constraintXX
xpi λp +xri λr ≤ ⌊x∗i ⌋ .
(19)
p∈P

r∈R

The additional dual variable αi is respected in the pricing problem as in (14), i.e., only its
objective function needs modification. However, no integer points in the interior of conv(X)can be obtained from the pricing problem, and we may miss an optimal solution in the caseof general integer variables x.
Pricing Problem. The second option is to change the bound xi ≤ ⌊x∗i ⌋ directly in thepricing problem, which forbids the generation of extreme points and rays which violate thebranching decision. Master variables already present but incompatible with the branchingdecision need to be eliminated. This can be done by addingXX
λj = 0or equivalently,
λj = 1(20)
j∈P ∪R:xji =1j∈P ∪R:xji =0to the master problem (5) which can be seen as modifying the convexity constraint (its dual
variable is still denoted by π0 ). The pricing problem then becomesmin{cx − πAx − π0 | x ∈ X ∩ {x | xi ≤ ⌊x∗i ⌋}} .

(21)

This may complicate the pricing problem, however, if it stays tractable, this option is to bepreferred. The main reason is the potentially stronger dual bound from the master problem
relaxation since the bound change is convexified:≤min{cx | Ax ≤ b, x ∈ conv(X), xi ≤ ⌊x∗i ⌋}min{cx | Ax ≤ b, x ∈ conv(X ∩ {x | xi ≤ ⌊x∗i ⌋})} .

(22)

Furthermore, adding disjunctive bounds to the pricing problem, i.e., partitioning its domain
allows to generate points in the interior of conv(X) after branching.
Our presentation discussed the root node but both options directly extend to any node in thetree. One only needs to keep track of the modifications to the master and pricing problems
which are local to subtrees. Both options generalize to the case of mixed integer programs.

4.2

Discretization: Avoiding the Symmetry

Branching on original variables works well when all pricing problems are distinct sinceXxk =xp λkp
(23)
p∈Pk

11

defines a unique projection from the λ variables into the original x variable space. As pointed
out in Section 2.2, the case of identical pricing problems
bears a symmetry which shouldP
be avoided. One may aggregate original variables k xk = z and obtain a single pricing
problem as above. Branching decisions disaggregate variables again and create distinct pricing
problems [18]. However, as any permutation of the index set {1, . . . , K} gives an equivalentsolution, this does not eliminate the symmetry in the xk variables [29].
Consider the aggregatedPmaster problem (10) of the discretization approach. Disaggregationof the variables νp =k λkp and using (23) to obtain an original x solution is neither
unique nor does integrality of ν necessarily imply integrality of x. The trick to avoid theseshortcomings and symmetry at the same time is to present a projection from the master into
the original variable space which does not use the one-to-one correspondence (23) between λkp
and xk variables. In other words, the grouping of λ variables is only implicit. Vanderbeck [29](see also [16]) proposed to obtain values x∗1 , . . . , x∗K (in that order) by summing variables λkp
in lexicographic order of the corresponding xp , where xq ≺ xp means that xq precedes xp inthat ordering. For all k = 1, . . . , K and p ∈ P let
¾
½
k−1
X
X
©
ª
.
λ∗κp , max 0, k −λ∗kp = min 1, νp −
νq∗

(24)

q:xq ≺xp

κ=1

We obtain x∗k = p∈P xk λ∗kp . The lexicographic sorting guarantees that we always work witha unique representative solution x out of the many symmetric possibilities. This is a standard
trick which has been used in symmetry breaking of integer programs recently [30].
P

Aggregate Original
When there happens to be a fractional aggregate original
P Variables.
∗∗/ Z+ , which needs not be the case in general, branching canvariable value yi = p∈P xpi νp ∈be performed on such a variable by imposingXXyi =xpi νp∗ ≤ ⌊yi∗ ⌋oryi =xpi νp∗ ≤ ⌈yi∗ ⌉
(25)
p∈P

p∈P

in the master. This only affects the pricing problem’s objective function but this may considerably change it’s character. This simple rule may give only little improvement on the dualbound [16].
Auxiliary Original Variables. When the previous rule fails, i.e., when an integer y does
not yield an integer x (“the set of branching objects is not rich enough.” [16]), one may try
to work with an extended original formulation by introducing auxiliary variables to branchon, cf. Sect. 2.3. As an example consider the set partitioning problem
½X
¾
X
X
|P |
min
cxp νp |xp νp = 1,
νp = K, ν ∈ {0, 1}
.
(26)
p∈P

p∈P

p∈P

Many problems lead to such a Dantzig-Wolfe reformulation like bin packing or vertex coloring.
For the latter problem, original variables xki ∈ {0, 1} state whether vertex i receives color k
and columns xp correspond to independent sets in the underlying graph. Aggregate variables

12Pyi∗ = p∈P xpi vp∗ = 1 for any master solution, so the previous rule does not apply. However,
it is well-known that in a fractional master solution there must exist rows i and j withX∗νp∗ =: wij∈/ {0, 1} .
(27)p∈P
xpi =xpj =1

We (conceptually) introduce wij as auxiliary variables in the original problem for every pair(i, j) of vertices (and in the pricing problem as well) and branch on these variables. It may not
be straight forward to impose the branching decision in the pricing problem directly; Ryan
and Foster branching [31] is an example in which wij ∈ {0, 1} is enforced by letting xi = xj inone branch and xi 6= xj in the other. When the pricing problem is solved via a combinatorial
algorithm, often a dynamic program, this naturally suggests an extended formulation of thepricing problem which translates to an extended original formulation [16], see also Sect. 3.3.
Nested Partition of the Convexity Constraint. The most general rule is to split themaster variables by modification of the convexity constraint [29]. IfXνp = δ ∈/ Z+(28)p∈P :xpi ≥ℓifor an index i (corresponding to original variable xi ) and an integer bound ℓi , one creates two
branches withXX
νp ≥ K − ⌊δ⌋ .
(29)
νp ≥ ⌈δ⌉orp∈P :xpi ≤ℓi −1p∈P :xpi ≥ℓi

The pricing problems must respect the variable bounds xi ≥ ℓi and xi ≤ ℓi − 1, respectively.
In order to guarantee a fractional δ in (28) one may need to impose bounds on a set S oforiginal variables. In fact, such sets are found recursively, and this generalizes the partitionin (29) in a nested way, producing more than two branches in general. The pricing problems
must respect the bounds on variables in S and the respective complementary sets. There areseveral technical details to consider for which we refer to [29].
This last rule provides the strongest dual bound among the above proposals and implies thesmallest impact in the pricing problem (only bound changes). It should be noted that points
in the interior of conv(X) can be generated with this generic rule and that the depth of thesearch tree is polynomially bounded.

5

Implementation Issues

Even when the whole lot of work of implementing a branch-price-and-cut algorithm will pay
off, it will be a whole lot of work, even in 2010. We have seen that the freedom of choice canbe enormous and some experience will certainly help. Nonetheless, it has never been easierthan today with the great body of literature available.
At least when working with a convexification approach, one needs access to the values ofthe original variables. A trivial (but probably not efficient) way of doing this is to keep
the constraints linking them to the master variables in the formulation (keeping the master13

constraints on the original variables is called the explicit master [17]). This facilitates e.g.,
branching on binary original variables since a simple bound change on the x variables implies
eliminating incompatible master variables since their upper bounds are automatically changed
to zero.
Even though an original (fractional) solution x∗ is available, there is a drawback which has notbeen satisfactorily addressed so far: Typically, x∗ is not a basic solution. This is importantsince several generic cutting planes and primal heuristics rely on that. Performing a cross-overhas been suggested (Matthew Galati in personal communication referred to John Forrest) as
a possible remedy but there are no experiences reported on this yet.

5.1

Frameworks

There are several frameworks which support the implementation of branch-and-price algorithms like ABACUS [32], BCP [33], and MINTO [34], SCIP [35], SYMPHONY [36], to name only a few.
In addition there are codes which perform a Dantzig-Wolfe decomposition of a general (mixed)
integer program, and handle the resulting column generation subproblems in a generic way.
BaPCod [37] is a “prototype code that solves mixed integer programs (MIPs) by applicationof a Dantzig-Wolfe reformulation technique.” The COIN-OR initiative (www.coin-or.org)
hosts a generic decomposition code, called DIP [38] (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 [20]. The constraint programming
G12 project develops “user-controlled mappings from a high-level model to different solving
methods,” one of which is branch-and-price [39]. The attempt to turn the branch-price-andcut framework SCIP into a branch-price-and-cut solver is called GCG [40].

5.2

When everything fails. . .

Many problems which are approached by branch-price-and-cut are so large and complex that
optimal solutions are out of reach in a reasonable computation time. What to do then? The
most honorable answer to that is: Research your problem! Is there any particular structure
you can exploit, e.g., by using a combinatorial algorithm to solve your pricing problems(instead of solving them as MIPs); by formulating cutting planes; or by re-thinking the entire
formulation? After all, this is what drives the innovations! The most practicable answer
probably is to run a profiler to check where your code spends the CPU time, and search thebag of tricks for accelerating the weak spots. In particular, you may consider acceleration
techniques [41] for solving the relaxations by column generation. The quickest (and sometimes
the most promising, but certainly the dirtiest) answer is to go with a heuristic. In particularin practical applications you may not need to close the last percents of the optimality gap.
Many practitioners will use price-and-branch, i.e., column generation is used only in the root
node. In particular, if the problem is of set covering type (which it often is), one may branch
on master variables and don’t care about the theory. This is not elegant, but it often works.
However, if the solver allows this, one should try to fix some variables (e.g., by branching)and generate further columns; this usually perceptively improves the solution quality.

14

6

A Remark and Recommendations for Further Reading

A final remark on the notion branch-price-and-cut. There is consent on using branch-and-cut
and branch-and-price; so consequently the integration was named branch-and-cut-and-price inthe first references. Adam Letchford (personal communication, 2005) remarked that a betterstyle English is to omit the first and. Additionally exchanging cut and price reflects theirorder when solving the relaxation in each node, so we suggest to use branch-price-and-cut.
The classical—by now a bit outdated—survey on branch-and-price is [42]. The book [43] oncolumn generation is, in fact, a book on branch-and-price and contains a lot of applications, inparticular vehicle routing, the cutting stock problem, and machine scheduling. The book also
contains an introductory text to the topic [44] with a focus on convexification. Implementation
issues can be found in [45].

References[1] G.L. Nemhauser and S. Park. A polyhedral approach to edge coloring. Oper. Res. Lett.,
10(6):315–322, 1991.
[2] J. Desrosiers, F. Soumis, and M. Desrochers. Routing with time windows by column
generation. Networks, 14:545–565, 1984.
[3] J. Desrosiers and M.E. Lübbecke. Selected topics in column generation. Oper. Res.,
53(6):1007–1023, 2005.
[4] F. Vanderbeck. Computational study of a column generation algorithm for bin packing
and cutting stock problems. Math. Programming, 86(3):565–594, 1999.
[5] A. Mehrotra and M.A. Trick. A column generation approach for graph coloring. INFORMS J. Comput., 8(4):344–354, 1996.
[6] J.M. van den Akker, J.A. Hoogeveen, and S.L. van de Velde. Parallel machine schedulingby column generation. Oper. Res., 47(6):862–872, 1999.
[7] A. Ceselli and G. Righini. A branch-and-price algorithm for the capacitated p-medianproblem. Networks, 45(3):125–142, 2005.
[8] M.W.P. Savelsbergh. A branch-and-price algorithm for the generalized assignment problem. Oper. Res., 45(6):831–841, 1997.
[9] G.L. Nemhauser and L.A. Wolsey. Integer and Combinatorial Optimization. John Wiley& Sons, Chichester, 1988.
[10] G.B. Dantzig and P. Wolfe. Decomposition principle for linear programs. Oper. Res.,
8:101–111, 1960.
[11] A.M. Geoffrion. Lagrangean relaxation for integer programming. Math. Programming
Stud., 2:82–114, 1974.
[12] A. Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, Chichester,
1986.
15

[13] F. Vanderbeck. On Dantzig-Wolfe decomposition in integer programming and ways toperform branching in a branch-and-price algorithm. Oper. Res., 48(1):111–128, 2000.
[14] F. Vanderbeck and M.W.P. Savelsbergh. A generic view of Dantzig-Wolfe decompositionin mixed integer programming. Oper. Res. Lett., 34(3):296–306, 2006.
[15] F. Vanderbeck. A generic view of Dantzig-Wolfe decomposition in mixed integer programming. Oper. Res. Lett., 34(3):296–306, 2006.
[16] F. Vanderbeck and L. Wolsey. Reformulation and decomposition of integer programs. In
M. Jünger, Th.M. Liebling, D. Naddef, G.L. Nemhauser, W.R. Pulleyblank, G. Reinelt,
G. Rinaldi, and L.A. Wolsey, editors, 50 Years of Integer Programming 1958–2008.
Springer, Berlin, 2010.
[17] Marcus Poggi de Aragão and Eduardo Uchoa. Integer program reformulation for robuts
branch-and-cut-and-price. In Annals of Mathematical Programming in Rio, pages 56–61.
Búzios, Brazil, 2003.
[18] D. Villeneuve, J. Desrosiers, M.E. Lübbecke, and F. Soumis. On compact formulations
for integer programs solved by column generation. Ann. Oper. Res., 139(1):375–388,
2005.
[19] G. Desaulniers, J. Desrosiers, and S. Spoorendonk. Cutting planes for branch-and-pricealgorithms. Les Cahiers du GERAD G-2009-52, HEC Montréal, 2009. Forthcoming in
Networks.
[20] T.K. Ralphs and M.V. Galati. Decomposition and dynamic cut generation in integer
linear programming. Math. Programming, 106(2):261–285, 2006.
[21] B. Petersen, D. Pisinger, and S. Spoorendonk. Chvátal-gomory rank-1 cuts used ina Dantzig-Wolfe decomposition of the vehicle routing problem with time windows. In
B. Golden, S. Raghavan, and E. Wasil, editors, The Vehicle Routing Problem: Latest
Advances and New Challenges, pages 397–419. Springer, Berlin, 2008.
[22] S. Spoorendonk and G. Desaulniers. Clique inequalities for the vehicle routing problem
with time windows. INFOR. Forthcoming.
[23] M. Jepsen, B. Petersen, S. Spoorendonk, and D. Pisinger. Subset-row inequalities applied
to the vehicle-routing problem with time windows. Oper. Res., 56(2):497–511, 2008.
[24] J.M. Valério de Carvalho. Exact solution of bin-packing problems using column generation and branch-and-bound. Ann. Oper. Res., 86:629–659, 1999.
[25] J.M. Valério de Carvalho. Exact solution of cutting stock problems using column generation and branch-and-bound. Int. Trans. Opl. Res., 5(1):35–44, 1998.
[26] R. Fukasawa, H. Longo, J. Lysgaard, M. Poggi de Aragão, M. Reis, E. Uchoa, and
R. Werneck. Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming, 106(3):491–511, 2006.
[27] E. Uchoa, R. Fukasawa, J. Lysgaard, A.A. Pessoa, M. Poggi de Aragão, and D. Andrade.
Robust branch-cut-and-price for the capacitated minimum spanning tree problem over alarge extended formulation. Math. Programming, 112(2):443–472, 2008.
16

[28] A. Pessoa, E. Uchoa, M. Poggi de Aragão, and R. Rodrigues. Algorithms over arc-timeindexed formulations for single and parallel machine scheduling problems. Report RPEP
Vol. 8 no. 8, Universidade Federal Fluminense, 2008.
[29] F. Vanderbeck. Branching in branch-and-price: A generic scheme. Math. Programming,
2010. In press.
[30] F. Margot. Symmetry in integer linear programming. In M. Jünger, Th.M. Liebling,
D. Naddef, G.L. Nemhauser, W.R. Pulleyblank, G. Reinelt, G. Rinaldi, and L.A. Wolsey,
editors, 50 Years of Integer Programming 1958–2008. Springer, Berlin, 2010.
[31] D.M. Ryan and B.A.Foster. An integer programming approach to scheduling. In A. Wren,
editor, Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew
Scheduling, pages 269–280. North Holland, Amsterdam, 1981.
[32] Michael Jünger and Stefan Thienel. The ABACUS system for branch-and-cut-and-pricealgorithms in integer programming and combinatorial optimization. Softw. Pract. Exper.,30(11):1325–1352, 2000.
[33] T.K. Ralphs and L. Ladányi. COIN/BCP User’s Manual, 2001. http://www.coin-or.
org/Presentations/bcp-man.pdf.
[34] G.L. Nemhauser, M.W.P. Savelsbergh, and G.S. Sigismondi. MINTO, a Mixed INTeger
Optimizer. Oper. Res. Lett., 15:47–58, 1994.
[35] T. Achterberg. SCIP: Solving constraint integer programs. Math. Programming Computation, 1(1):1–41, 2009.
[36] T.K. Ralphs. Symphony version 5.1 users manual. Corl laboratory technical report,
2006.
[37] F. Vanderbeck. BaPCod – a generic branch-and-price code. https://wiki.bordeaux.
inria.fr/realopt/pmwiki.php/Project/BaPCod, 2005.
[38] T.K. Ralphs and M.V. Galati. DIP – decomposition for integer programming. https://projects.coin-or.org/Dip, 2009.
[39] J. Puchinger, P.J. Stuckey, M.G. Wallace, and S. Brand. Dantzig-Wolfe decomposition
and branch-and-price solving in G12. Constraints, 2010. To appear.
[40] G. Gamrath and M.E. Lübbecke. Experiments with a generic Dantzig-Wolfe decomposition for integer programs. In P. Festa, editor, Proceedings of the 9th International
Symposium on Experimental Algorithms (SEA), volume 6049 of Lect. Notes Comput.
Sci., pages 239–252, Berlin, 2010. Springer-Verlag.
[41] G. Desaulniers, J. Desrosiers, and M.M. Solomon. Accelerating strategies in column
generation methods for vehicle routing and crew scheduling problems. In C.C. Ribeiro
and P. Hansen, editors, Essays and Surveys in Metaheuristics, pages 309–324, Boston,
2001. Kluwer.
[42] C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh, and P.H. Vance.
Branch-and-price: Column generation for solving huge integer programs. Oper. Res.,
46(3):316–329, 1998.
17

[43] G. Desaulniers, J. Desrosiers, and M.M. Solomon, editors. Column Generation. SpringerVerlag, Berlin, 2005.
[44] J. Desrosiers and M.E. Lübbecke. A primer in column generation. In Desaulniers et al.
[43], pages 1–32.
[45] F. Vanderbeck. Implementing mixed integer column generation. In Desaulniers et al.
[43], pages 331–358.

18