OPERATIONS RESEARCH

informs

Vol. 53, No. 6, November–December 2005, pp. 1007–1023
issn 0030-364X  eissn 1526-5463  05  5306  1007®

doi 10.1287/opre.1050.0234© 2005 INFORMS

Selected Topics in Column Generation
Marco E. Lübbecke

Technische Universität Berlin, Institut für Mathematik, Sekr. MA 6-1, Straße des 17. Juni 136,
D-10623 Berlin, Germany, m.luebbecke@math.tu-berlin.deJacques Desrosiers

HEC Montréal and GERAD, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada H3T 2A7,
jacques.desrosiers@hec.ca

Dantzig-Wolfe decomposition and column generation, devised for linear programs, is a success story in large-scale integer programming. We outline and relate the approaches, and survey mainly recent contributions, not yet found in textbooks. We emphasize the growing understanding of the dual point of view, which has brought considerable progress tothe column generation theory and practice. It stimulated careful initializations, sophisticated solution techniques for the
restricted master problem and subproblem, as well as better overall performance. Thus, the dual perspective is an everrecurring concept in our “selected topics.”
Subject classiﬁcations: integer programming: column generation, Dantzig-Wolfe decomposition, Lagrangian relaxation,
branch-and-bound; linear programming: large scale systems.
Area of review: Optimization.
History: Received December 2002; revision received March 2004; accepted October 2004.

1. Introduction

programming column generation solution process. On thetheoretical side, we give a primer on decomposition andcolumn generation, pointing out that in general one cannot
simply impose integrality constraints on the generated variables. On the algorithmic side, we emphasize the boundingrole of the column generation algorithm and the importance of dual solutions for achieving a good overall performance. This paper is divided in two major parts. The ﬁrst
part covers the theory that is needed to expose integer programming column generation algorithms. In §2, we recall
the classical decomposition principle in linear programming, which leads to the formulation of linear programswith a huge number of variables. In §3, we present bothconvexiﬁcation and discretization approaches for extending the decomposition principle to handle integrality constraints. The second part is the algorithmic counterpartof the ﬁrst. Sections 4, 5, and 6 cover the solution of
linear programming column generation, expanding respectively on the strategies developed for getting dual solutions
to the restricted master problems, generating new variables,
and compensating for bad convergence behaviors. Section 7
integrates integer programming considerations, putting thepreceding algorithms in perspective. Our conclusion brings
attention to the strongest and most promising ideas thatare presented, in the hope that ever more complex column
generation applications could be successfully solved.

Almost ﬁve decades have passed since Ford and Fulkerson(1958) suggested dealing only implicitly with the variablesof a multicommodity ﬂow problem. Dantzig and Wolfe(1960) pioneered this fundamental idea, developing a strategy to extend a linear program columnwise as neededin the solution process. This technique was ﬁrst put toactual use by Gilmore and Gomory (1961, 1963) as partof an efﬁcient heuristic algorithm for solving the cuttingstock problem. Column generation is nowadays a prominent method to cope with a huge number of variables.
The embedding of column generation techniques within
a linear-programming-based branch-and-bound framework,
introduced by Desrosiers et al. (1984) for solving a vehicle
routing problem under time window constraints, was the
key step in the design of exact algorithms for a large classof integer programs.
This paper is a survey on column generation biased
toward solving integer programs. Numerous integer programming column generation applications are described in
the literature, as can be seen in Table 1. Generic algorithms for solving problems by integer programming column generation were presented by Barnhart et al. (1998b)
and Vanderbeck and Wolsey (1996). Algorithmic efﬁcacy
is considered by Desaulniers et al. (2001b). Some dissertations (Ben Amor 2002, Sol 1994, Vanderbeck 1994,
Villeneuve 1999) are a rich source of computational testing. Previous general reviews include those by Desrosiers
et al. (1995), Soumis (1997), and Wilhelm (2001).
We merge promising contemporary research works withmore classical solution strategies to cover the whole integer

2. Column Generation and Dantzig-Wolfe
Decomposition
In applications, constraint matrices of (integer) linear programs are typically sparse and well structured. Subsystems
1007

Lübbecke and Desrosiers: Selected Topics in Column Generation

1008

Operations Research 53(6), pp. 1007–1023, © 2005 INFORMS

Table 1.

Some applications of integer programming column generation.

Reference(s)Application(s)Agarwal et al. (1989); Desaulniers et al. (2001b);
Desrochers et al. (1992); Löbel (1997, 1998);
Ribeiro and Soumis (1994)
Borndörfer et al. (2003); Desaulniers et al. (2001b);
Desrochers and Soumis (1989)
Desrosiers et al. (1984)
Krumke et al. (2002)
Lübbecke and Zimmermann (2003); Sol (1994)

Various vehicle routing problems
Crew schedulingMultiple traveling salesman problem with time windows
Real-time dispatching of automobile service units
Multiple pickup and delivery problem with time windows

Anbil et al. (1998); Crainic and Rousseau (1987)
Barnhart and Schneur (1996)
Erdmann et al. (2001)
Barnhart et al. (1998a); Desaulniers et al. (1997);
Ioachim et al. (1999)

Airline crew pairing
Air network design for express shipment service
Airline schedule generation
Fleet assignment and aircraft routing and scheduling

Crama and Oerlemans (1994)
Eben-Chaime et al. (1996)
Park et al. (1996)
Ribeiro et al. (1989)
Sankaran (1995)
Vanderbeck (1994)
Vanderbeck (1994)
Hurkens et al. (1997); Valério de Carvalho (1999,
2000, 2002b); Vance (1998); Vance et al. (1994);
Vanderbeck (1999)

Job grouping for ﬂexible manufacturing systems
Grouping and packaging of electronic circuits
Bandwidth packing in telecommunication networks
Trafﬁc assignment in satellite communication systems
Course registration at a business school
Graph partitioning, e.g., in VLSI, compiler design
Single-machine multi-item lot sizing
Bin packing and cutting-stock problems

Alvelos and Valério de Carvalho (2000);
Barnhart et al. (1997, 2000)
Bourjolly et al. (1997)
Hansen et al. (1998)
Johnson et al. (1993)
Mehrotra and Trick (1996)
Savelsbergh (1997)

Integer multicommodity ﬂows
Maximum stable-set problem
Probabilistic maximum satisﬁability problem
Minimum cut clustering
Graph coloring
Generalized assignment problemof variables and constraints appear in independent groups,
linked by a distinct set of constraints and/or variables.
Multicommodity ﬂow formulations for vehicle routing
and crew scheduling problems are well-known examples(Desaulniers et al. 1998, Desrosiers et al. 1995).
The general idea behind the decomposition paradigm isto treat the linking structure at a superior, coordinating level
and to independently address the subsystem(s) at a subordinated level, exploiting their special structure algorithmically. We are concerned with linking constraints, or pricedirective decomposition only; see, for example, Benders(1962), Lasdon (1970), and Van Roy (1983) for different
points of view.

pricing step, given the vector u  0 of dual variables, wewish to ﬁnd(2)
arg min c̄j = cj − uT aj  j ∈ J

2.1. Column Generation

 T a  a ∈ c̄  = min c a − u

Let us call the following linear program the master problem (MP):z = min cj jreturns an answer to the pricing problem. If c̄   0, no¯ (embedded in
reduced cost coefﬁcient c̄j is negative and 
J  ) optimally solves the MP as well. Otherwise, we add
to the RMP a column derived from the oracle’s answer, andrepeat with re-optimizing the RMP. For its role in the algorithm, (3) is also called the column generation subproblem,or the column generator.
The advantage of solving an optimization problem in (3)instead of an enumeration in (2) becomes even more apparent when we remember that vectors a ∈  often encodej∈J

subject to


j∈J

(1)

aj j  bj  0j ∈JIn each iteration of the simplex method we look for a nonbasic variable to price out and enter the basis. That is, in the

An explicit search of J may be computationally impossible
when J  is huge. In practice, one works with a reasonably
small subset J  ⊆ J of columns, with a restricted masterproblem (RMP). Assuming that we have a feasible solution,¯ and u be primal and dual optimal solutions of thelet RMP, respectively. When columns aj , j ∈ J , are implicitly
given as elements of a set  = , and the cost coefﬁcient cj
can be computed from aj , then the subproblem or oracle(3)

Lübbecke and Desrosiers: Selected Topics in Column Generation

1009

Operations Research 53(6), pp. 1007–1023, © 2005 INFORMS

combinatorial objects like paths, sets, or permutations.
Then,  and the interpretation of cost are naturally deﬁned
on these structures, and we are provided with valuable
information about what possible columns “look like.”
Consider the one-dimensional cutting-stock problem,the classical example in column generation introduced by
Gilmore and Gomory (1961). Given are paper rolls ofwidth W , and m demands bi , i = 1  m, for orders ofwidth wi . The goal is to minimize the number of rolls to be
cut into orders, such that the demand is satisﬁed. A standard formulation isJ  
min 1T   A  b  ∈ + 

(4)where A encodes the set of J  feasible cutting patterns,
i.e., aij ∈ + denotes how often order i is obtained whencutting a roll according to j ∈ 
J . From the deﬁnition offeasible patterns, the condition m
i=1 aij wi  W must holdfor every j ∈ J , and j determines how often the cutting
pattern j ∈ J is used. The linear relaxation of (4) is thensolved via column generation, where the pricing problem
is a knapsack problem.
With the usual precautions against cycling of the simplex
method, column generation is ﬁnite and exact. In addition,
we have a knowledge about the intermediate solution quality during the process. Let z̄ denote the optimal objectivefunction value to the RMP. Note that by duality we have T b. Interestingly, when an upper bound   j∈J jz̄ = uholds for an optimal solution of the master problem, weestablish not only an upper bound on z in each iteration,
but also a lower bound: We cannot reduce z̄ by more than times the smallest reduced cost c̄  , hence,z̄ + c̄    z  z̄(5)

In the optimum of (1), c̄  = 0 for the basic variables,
and the bounds close. The lower bound in (5) is computationally cheap and readily available when (3) is solved
to optimality. When the objective already is a sum of thevariables, that is, c ≡ 1, we use z instead of  and obtain
the improved lower bound z̄/ 1 − c̄   z . For c  0,
Farley (1990) proposes a more general lower bound at theexpense of a slightly increased computational effort. Let T aj > 0. Then,j  ∈ arg minj∈J cj /
u T aj  uz̄ · cj  /uT aj   z  z̄(6)

Valério de Carvalho (2002b); Vance (1998), and Vanceet al. (1994) tailor this to the cutting-stock problem withc ≡ 1. See Hurkens et al. (1997) for an implementation ofboth bounds.
2.2. The Decomposition Principle in Linear
Programming
We brieﬂy review the classical decomposition principle inlinear programming, due to Dantzig and Wolfe (1960).

Consider a linear program (the original or compact formulation)z = min cT x
subject to Ax  b(7)

Dx  dx0

Let P = x ∈ n+  Dx  d = . It is well known (Schrijver
1986) that we can write each x ∈ P as a convex combination of extreme points pq q∈Q plus a nonnegative combination of extreme rays pr r∈R of P , i.e.,
x=


q∈Q

pq  q +r∈R

p r r q∈Qq = 1Q+R ∈ +

(8)

where the index sets Q and R are ﬁnite. Substituting for xin (7) and applying the linear transformations cj = cT pj
and aj = Apj , j ∈ Q ∪ R, we obtain an equivalent extensive
formulationz = minc q q + c r rq∈Q

subject to


q∈Q

r∈R

aq  q +r∈Rar r  b



q∈Q

(9)

q = 10

It typically has a large number Q + R of variables, but
possibly
substantially fewer rows than (7). The equation
q∈Q q = 1 is referred to as the convexity constraint. If
x ≡ 0 is feasible for P in (7) at zero cost, it may beomitted in Q. The convexity constraint is then replacedby q∈Q q  1. Although the compact and the extensive
formulations are equivalent in that they give the same optimal objective function value z , the respective polyhedra
are not combinatorially equivalent (Adler and Ülkücü 1973,
Nazareth 1987). As (8) suggests, x uniquely reconstructs
from a given , but not vice versa.
 , v̄ to the RMP obtained
Given a dual optimal solution ufrom (9), where variable v corresponds to the convexity
constraint, the subproblem (3) in Dantzig-Wolfe decom T aj − v̄. By ourposition is to determine minj∈Q∪R cj − uprevious linear transformation, this results in T A x − v̄  Dx  d x  0c̄  = min cT − u(10)This is a linear program again. We assumed that P = .
When c̄   0, no negative reduced cost column exists, andthe algorithm terminates. When c̄  < 0 and ﬁnite, the optimal solution to (10) is an extreme point pq of P , and we
add the column "cT pq  Apq T  1#T to the RMP. When c̄  =−, we identify an extreme ray pr of P as a homogeneous
solution to (10), and we add the column "cT pr  Apr T  0#T

Lübbecke and Desrosiers: Selected Topics in Column Generation

1010

Operations Research 53(6), pp. 1007–1023, © 2005 INFORMS

to the RMP. From (5) together with the convexity constraint, we obtain at each iterationz̄ + c̄  z  z̄

(11) T b + v̄ is again the optimal objective function
where z̄ = uvalue of the RMP. Note that the lower bound is also valid
in the case when the subproblem generates an extreme ray,that is, when c̄  = −. Dantzig-Wolfe type approximation
algorithms with guaranteed convergence rates have been
proposed for certain linear programs; see Klein and Young(1999), and the references given therein.
2.3. Block Diagonal Structure
The decomposition principle has an interpretation as decentralized planning without complete information at thecenter; see Chvátal (1983) and Lasdon (1970). In that context, many applications have a block diagonal structureof D, i.e.,
 1

 1
d
D
2



2
D


d 
D=
d =  



 
D
d
where Dk and dk are of compatible size. This special structure can be exploited. Each P k = x  Dk x  dk  x  0,
k = 1  , is independently represented in the senseof (8). A superscript k to the entities cjk , ajk , and kj for
j ∈ Qk ∪ Rk , indicates the respective subsystem k ∈ K =
1  . In analogy to (9), the MP readsz = minsubject to





k∈K

q∈Qk

cqk kq +





k∈K

q∈Qk


r∈Rk

aqk kq +crk krr∈Rkark kr

q∈Qk

 b

(12)

kq = 1k ∈ K

k  0k∈K

Denoting by vk the dual variable associated with thekth convexity constraint, the  subproblems are analoguesof (10):
 T Ak xk − v̄k  Dk xk  dk  xk  0c̄ k = min ckT − uk ∈ K (13)and the algorithm terminates when c̄ k  0 for all k ∈ K.
Otherwise, extreme points and rays identiﬁed in (13) giverise to new columns to be addedto the RMP. By linear
 T b + k∈K v̄k , and we obtainprogramming duality, z̄ = u
the bounds
 k
z̄ +
c̄  z  z̄
(14)
k∈K

3. Decomposition of Integer Programs
In almost every application, we are interested in optimizing
over a discrete set X, that is,z = min cT x
subject to

Ax  b

(15)

x∈X
We consider the case of integer programming, where X =P ∩+ and P ⊆ n is a polyhedron. However, X could havea much more complicated nonlinear deﬁnition (Desaulniers
et al. 1998). We assume that z is ﬁnite.
3.1. Lagrangian Relaxation
A popular approach to solving (15) is Lagrangian relaxation. Relaxing constraints Ax  b and penalizing their violation in the objective function via Lagrangian multipliersu  0 results in the following Lagrangian subproblem:
L u = min cT x − uT Ax − b
x∈X

(16)

L u is a lower bound on z , because L u  min cT x −uT Ax − b  Ax  b x ∈ X  z . The best such boundon z is computed in the Lagrangian dual problem
 = max L u

(17)

u0

Assume that we are given optimal multipliers u for (17).
By solving (16), we ensure that x ∈ X; the optimality of u
implies that uT Ax − b = 0 (complementary slackness),
but Ax  b (feasibility) has to be veriﬁed to prove optimality. If this condition is violated, the primal-dual pair x u
is not optimal.
The Lagrangian function L u , u  0, is the lower envelope of a family of functions linear in u, and therefore isconcave. It is piecewise linear and only subdifferentiable
in its breakpoints. The most popular (very easy to implement) and well-documented choice to obtain (near) optimal multipliers are subgradient algorithms (Wolsey 1998).
An alternative way is by linear programming. Replace X
by conv X in (15); this does not change z . Changing
the Lagrangian subproblem and the dual accordingly, weare enabled to write (16) and (17) in terms of extreme
points and rays of conv X . This turns the Lagrangian
 ofdual into a linear program, and for a given vector umultipliers
 = u T b + v + min
L ux∈conv X

 T A x − v = z̄ + c̄  
cT − u(18)

that is, the lower bound obtained from the RMP in DantzigWolfe decomposition in (11) is the same as the Lagrangian
bound.

Lübbecke and Desrosiers: Selected Topics in Column Generation

1011

Operations Research 53(6), pp. 1007–1023, © 2005 INFORMS

3.2. Convexiﬁcation

subject to

The strong relation of Dantzig-Wolfe decomposition and
Lagrangian relaxation is now investigated (see Nemhauser
and Wolsey 1988). When X = , which may happen during branch and bound, then  =  in (17). Otherwise, letagain Q and R denote the index sets of extreme points andextreme rays, respectively, of conv X . For given multipliers u, the Lagrangian bound is

−




if cT −uT A pr < 0 for some r ∈ R

L u = cT p −uT Ap −b

q
q


for some q ∈ Q otherwise(19)

Because we assumed z to be ﬁnite, we wish to avoid
L u = −. We state this as follows: = max min cT pq − uT Apq − bu0 q∈Q

cT − uT A pr  0

subject to(20)r ∈ R

or as a linear program with many constraints:
 = max v
subject touT Apq − b + v  cT pq q ∈ Q

Tr ∈ R

Tu Apr  c pr 

(21)

u0
The dual linear program of (21), composed of many variables, reads
 = min T
c p q q + c T p r rq∈Q

subject to


q∈Q

r∈R

Apq q +r∈R

Apr r  b

q∈Q


q∈Q

q 

(22)

q = 10Consequently, we can solve (17) by either (21) or (22); theformer gives us the multipliers, but the latter provides us
with an x feasible to (15) via the substitution (8). Moreover,in (22) we get complementary slackness and feasibility ofAx  b for free, which is not the case in subgradient algorithms. Also, x ∈ conv X ; therefore only one issue remains
to be checked: The integrality of x, cf. §7.
Applying Dantzig-Wolfe decomposition to (15) with
X replaced by conv X , we directly obtain the above
correspondence. This explains the notion of convexiﬁcation(Vanderbeck 1994),z = minq∈Qc q q +r∈R

c r rq∈Qaq  q +r∈Rar r  bq∈Qq = 1
(23)
  0
p q q + p r r 
x=
q∈Q

r∈R

x ∈ n+ 
where again cj = cT pj and aj = Apj , j ∈ Q ∪ R. When werelax the integrality of x, there is no need to link x and in (23), and we may also relax the coupling constraint,
obtaining precisely (22). Still, to get integer solutions, wehave to impose additional conditions on the x variables.
These conditions will appear in the compact formulation (15), at the level of the master problem or of the subproblem, or both, and the decomposition process—such as
Lagrangian relaxation or Dantzig-Wolfe decomposition—
has to be repeated at every node of the search tree.
One objection against subgradient algorithms for solving
the Lagrangian dual is that they exploit only local information for the iterative update of the dual multipliers. On
the contrary, solving an RMP based on (22) is a moreelaborate update strategy which makes use of all the information gathered during the solution process, but the partly
occurring large linear programs could not be solved until
recently. Still, when the number of rows, and thus dual
multipliers is very large, subgradient algorithms may be theonly practical alternative. Hybrid methods are good compromises (Barahona and Jensen 1998, Kallehauge et al.
2001, Kohl and Madsen 1997), e.g., starting the multiplieradjustment with a subgradient algorithm and ﬁnishing thecomputation using a linear program.
Besides subgradients and simplex-based methods, theLagrangian dual can be solved with more advanced (nonlinear) alternatives with stronger convergence properties.
Among them are the bundle method (Hiriart-Urruty andLemaréchal 1993) based on quadratic programming, andthe analytic center cutting-plane method (Gofﬁn and Vial
2003), an interior point solution approach. However, theperformance of these alternatives is still to be evaluated in
the context of integer programming.
3.3. Discretization
Requiring integrality of the variables  of the MPs (22)or (23) does not lead to an integer program equivalentto (15), because the optimum integer solution of (15) may
be an interior point of conv X . Alternatively, discretization(Johnson 1989, Vanderbeck 2000) is a true integer analogue
to the decomposition principle. It is based on the following(see Nemhauser and Wolsey 1988).
Theorem 1. Let P = x ∈ n  Dx  d x  0 =and
X = P ∩ n . Then, there exists a ﬁnite set of integer points
pq q∈Q ⊆ X and a ﬁnite set of integer rays pr r∈R of P

Lübbecke and Desrosiers: Selected Topics in Column Generation

1012

Operations Research 53(6), pp. 1007–1023, © 2005 INFORMS

such that
X = x ∈ n+  x =p q q + p r  r 
r∈R

q∈Q



Q+R

q∈Q


(24)

q = 1  ∈ +

Substitution for x in (15) as given by (24) yields an
integer MPz = minc q q + c r rq∈Q

subject to


q∈Q

r∈R

a q q +r∈Rar r  b



q∈Q

(25)

q = 1 j ∈ + j ∈ Q ∪ Rwhere again cj = cT pj and aj = Apj , j ∈ Q ∪ R. It is interesting that, when X is bounded, (25) is a linear integer
program even for arbitrary linear and nonlinear cost functions c x in (15). Because of the convexity constraint,
variables q , q ∈ Q are restricted to binary values, thusc x =cq∈Q

p q q = c p q  = c q  =q∈Q

3.4. Column Generation for Integer Programs
Consider the following integer program (IP):z = min cj j

j∈J

(26)

aj j  b
 j ∈ + 



yk

k∈K



subject tok∈K

i=1 mRemark. In the important special case that X ⊆ "0 1#nconvexiﬁcation and discretization coincide. All integral
points in the bounded set X are already vertices of conv X ,and only binary q , q ∈ Q in (24) make sense. That is,
x is the trivial convex combination of only one vertex,
and therefore x ∈ 0 1n ⇔  ∈ 0 1Q . Many large-scale
applications belong to this class, in particular, many decomposition procedures that give rise to set-partitioning andset-covering problems.

subject tomin

cq  qholds for precisely one q  ∈ Q. This cannot be generalized
to the unbounded case, because there need not be a uniquerepresentation of x as a combination of the s. This is thecase when we can combine a point in X by a point in Q
and several extreme rays. Then, the objective function valuec x depends on the actual combination.

j∈Jthe situation in §3.2, we do not have available an explicit
compact formulation on which we can analyze the solutionof the linear relaxation of (26) and decide how to branch.
Villeneuve et al. (2005) constructively show that a compact formulation equivalent to (26) exists under very mild
assumptions. Their proposal involves a duplication of thevariables and the domain of the oracle in such a way that a
block diagonal structure with identical subproblems results.
Their general branching strategy works on the variables of
the compact formulation. Multicommodity ﬂow formulations for various applications of vehicle routing and crewscheduling proposed by Desaulniers et al. (1998) follow
this scheme. For the classical cutting-stock problem (4), theabove procedure leads to Kantorovich’s (1960) formulation,
where a commodity is deﬁned for each (identical) available
roll. Let K be the set of rolls of width W . Deﬁne y k , k ∈ K,
as a binary variable assuming value 1 if roll k is used and0 otherwise, and xik , k ∈ K, i = 1  m, as a nonnegative
integer variable that denotes the number of times order i is
cut in roll k. The compact formulation reads as follows:j ∈ J

for which the linear relaxation is solved by column generation using a given oracle for the pricing subproblem. Unlike

xik  bi 

i = 1

 m

wi xik  Wy k k ∈ K

y k ∈ 0 1

k ∈ K

xik ∈ + k ∈ K i = 1

(27)

m

There are alternative compact formulations which leadto the same linear relaxation when the decomposition principle of §3.2 is used. Valério de Carvalho (1999, 2002a)
proposes a network-based compact formulation where theclassical knapsack subproblem is solved as a particularminimum cost ﬂow problem. Each subproblem path ﬂow
in that network gives a valid cutting pattern, and it corresponds to an extreme ray, except the null pattern which isthe single extreme point. However, no master problem isused, but each generated column is split into its arc components, i.e., in terms of the original arc ﬂow variables.
A restricted compact problem is solved on the current subset of arcs, and the remaining arcs have to be priced out toprove optimality or to identify arcs to be included in theformulation. The ﬂow conservation constraints are activatedonly as needed, i.e., for the terminal nodes of the generated
arcs. Similar techniques to solve large-scale linear multicommodity ﬂow problems are used by Löbel (1997, 1998)
and Mamer and McBride (2000).
Some imagination is needed to ﬁnd an appropriate compact formulation, but we strongly recommend to look forone. Once this is established, ﬁnding integer solutions tothe compact formulation is theoretically no more difﬁcult
than for any integer program; only a lower bound is computed via column generation. A valid argument to prefer anLübbecke and Desrosiers: Selected Topics in Column Generation

1013

Operations Research 53(6), pp. 1007–1023, © 2005 INFORMS

extensive formulation over its compact counterpart is thatthe former may be stronger in the sense that its linear programming relaxation gives a tighter approximation to theconvex hull of integer points; see §5.3.1 on the integrality
property.
Let us ﬁnally stress again the need for generating columns
in every node of the branch-and-bound tree. There are cases
where the MP has to be solved in integers, but it is wellknown that the linear program RMP may be integer infeasible (Barnhart et al. 1998b). Villeneuve et al. (2005) demonstrate the defect that even if feasibility could be ensured,
without branching we may miss (probably all) optimal integer solutions. Consider the following example. If c2 > 1,
variable z2 cannot be generated using Dantzig’s rule:
min z1 + c2 z2 + z3
subject toz1 + 2z2 + 3z3 = 2(28)

z1  z2  z3 ∈ +
Given the dual variable u ∈  associated with the equality
constraint, z2 is of minimum reduced cost if and only if
c2 − 2u  1 − u and c2 − 2u  1 − 3u; that is, if c2  1 − u,in contradiction to c2 > 1. If 1 < c2 < 2, the unique optimal
integer solution is z1  z2  z3 = 0 1 0 of value c2 while
the solution restricted to the variables that can be generated
is z1  z3 = 2 0 of cost 2 > c2 .

4. The Restricted Master Problem
The purpose of the RMP (as is the purpose of subgradient algorithms in Lagrangian relaxation) is to provide dual
variables—to be transferred to the subproblem, and to control our stopping criterion. In the end only, we have torecover from the RMP a primal feasible solution to thecompact formulation.
Primal methods, like column generation, maintain primal
feasibility and work towards dual feasibility. It is therefore
only natural to monitor the dual solution in the course of
the algorithm. In our opinion, the dual point of view reveals
most valuable insight into the algorithm’s functioning. We
call the polyhedron associated with the dual of the RMP thedual polyhedron. A dual solution to the RMP needs not be
unique, e.g., if the primal is degenerate. This is signiﬁcant
inasmuch the dual solution directly inﬂuences the selectionof new columns. Because a dual basic solution corresponds
to an extreme point of the optimal face, it may be a bad
representative of all the dual solutions obtainable.
Solving the RMP by the simplex method leads to an optimal basis essentially chosen at random, whereas the application of an interior point method produces a solution in
the relative interior of the optimal face (Bixby et al. 1992).
Therefore, e.g., analytic centers (Elhedhli and Gofﬁn 2004,
Gofﬁn et al. 1993), volumetric centers, central path methods (Kirkeby Martinson and Tind 1999), and central prices(Gofﬁn et al. 1993) have been proposed. The computationaluse of these various proposals for obtaining integer solutions is evaluated by Briant et al. (2004).
Extreme point dual solutions are immediately available
when using the simplex method, and because of their “random” nature they may result in different, even complementary kinds of columns (Vanderbeck 1994). More elaborate
suggestions in the spirit of the above may speed up computation times for very difﬁcult RMPs; see also Anbil et al.
(1998).
4.1. Solution Methods
4.1.1. Initialization. No matter what method we use,
we have to initialize the RMP. The well-known simplex ﬁrst
phase carries over to column generation (Chvátal 1983).
Artiﬁcial variables, one for each constraint, penalized bya “big M” cost, are kept in the RMP to ensure feasibility in a branch-and-bound algorithm. A smaller M gives atighter upper bound on the respective dual variables, andmay reduce the heading-in effect (Vanderbeck 2005) of initially producing irrelevant columns. Details on initialization, especially for mixed integer programs, are given by
Vanderbeck (1994, 2005).
In some applications, the unit basis is already feasible.
Then, an estimate of the actual cost coefﬁcients should be
used instead of M. Heuristic estimates of the optimal dual
variable values are imposed as artiﬁcial upper bounds by
Agarwal et al. (1989) by introducing unit columns withappropriate cost. The bounds are gradually relaxed until
they are no longer binding. This relates to the stabilization
approach (see §6.2). Similar techniques are proposed, e.g.,
by Vanderbeck (2005).
Poorly chosen initial columns lead the algorithm astraywhen they do not resemble the structure of a possible optimal solution at all. They must then be interpreted as amisleading bound on an irrelevant linear combination of
the dual variables. Even an excellent initial integer solution
is detrimental to solving a linear program by column generation (Vanderbeck 1994). On the other hand, bounds onmeaningful linear combinations of dual variables give goodexperiences (Ben Amor 2002, Valério de Carvalho 2000),
cf. §4.2.1. Another option is a warm start from primal solutions obtained in earlier, similar runs (Anbil et al. 1998).
However, the best results are obtained when both estimatesof the primal and the dual solutions are used (Ben Amor
2002, du Merle et al. 1999).
4.1.2. Traditional Approaches: Simplex and Barrier.
As is the case for general linear programs, depending on
the application and the available solvers, we do not know
beforehand which of the several traditional ways of solving the RMP will perform “best.” Lasdon (1970) commentson the suitability of primal, dual, and primal-dual simplex methods. In presence of primal degeneracy, the dual
simplex may be preferred to the primal. The sifting method
can be a reasonable complement for large scale RMPs; see
Anbil et al. (1998), Bixby et al. (1992), and Chu et al.

Lübbecke and Desrosiers: Selected Topics in Column Generation

1014(1997). For some linear programs Barrier methods (Bixby
2002) can prove most effective, although there is no possible warm start.
4.1.3. Subgradients and Volume Algorithm. The
RMP may itself be solved by subgradient algorithms byrelaxing all its constraints in the objective function (Caprara
et al. 1999, 2000; Wedelin 1995). This approach has been
applied to set-covering applications for which these authors
provide ways to compute a number of integer primal solutions at each iteration of the column generation process.
The solution method may be dynamically switched during
the solution process (see, for example, Bixby et al. 1992).
Because of these alternatives, we do not even need to maintain a basis.
Rather than computing an exact solution to the RMP, anapproximation may sufﬁce. Assuming P is nonempty andbounded, the volume algorithm (Barahona and Anbil 2000)
is an extension of subgradient algorithms, and rapidly produces primal as well as dual approximate solutions to the
RMP. It is named after a new way of looking at linear programming duality, using volumes below the active faces tocompute the dual variable values and the direction of movement. The pricing subproblem is called with a dual solution“in a neighborhood” of an optimal dual solution. Then,
one can compute the probability that a particular column(which induces a face of the dual polyhedron) is generated.
The subgradient method is modiﬁed to furnish estimates ofthese probabilities, i.e., approximate primal values for q ,q ∈ Q, that sum to 1. Primal feasibility may be mildly
violated.
When used in alternation with the simplex method, thevolume algorithm produces dual solutions with a large
number of nonzero variables (Anbil et al. 1998). This quality is claimed to accelerate column generation for reasons
as discussed above. Promising computational experienceis given for various combinatorial optimization problems(Barahona and Anbil 2002, Barahona and Jensen 1998).
Advantages of the volume algorithm are a straightforward
implementation with small memory requirements, numerical stability, and fast convergence.
Elaborate hybrids may evolve; see, e.g., Anbil et al.
(1998), Bixby et al. (1992), Borndörfer et al. (2003), andDesaulniers et al. (2001b). Heuristics are used to construct
or improve dual variable values at any time in the algorithm. The choice of a method in general will also dependon how fast or how accurate a solution is needed, whether
particular problem structures are present, and what implementation skills or solvers are available. One apparent trend
is not to insist on optimality, but to attack even larger
problems, for which a guaranteed approximation quality
can be obtained. This is especially true for integer programs; see §7.1.

Operations Research 53(6), pp. 1007–1023, © 2005 INFORMS

from the RMP may still violate constraints of the full dual
MP. Thus, the pricing problem is a separation problem forthe dual. Dantzig-Wolfe decomposition and related methods can be interpreted as special cases of Kelley’s (1961)
cutting-plane method devised for solving convex programs.
It is sometimes more instructive and revealing to adopt thedual perspective.
Remark. Consequences from the equivalence of separation and optimization (Grötschel et al. 1988) arise in thiscontext. Exponential size RMP linear programs are polynomially solvable by column generation under the assumption that the pricing problem is solvable in polynomial
time (Mehlhorn and Ziegelmann 2000, Minoux 1987). Conversely, solving an RMP is  -hard, if the pricing problem
is (Johnson et al. 1993).
4.2.1. Restriction of the Dual Master Problem. It
is known that set-partitioning type master problems canbe converted to set-covering type, preserving the optimal
objective function value, when taking subsets does notincrease cost. This constrains the dual space by restricting
the dual variables in sign. Further, we are not restricted toonly add columns from the master program. Using structural information we can do better (Ben Amor 2002, Valériode Carvalho 2000, Holmberg and Jörnsten 1995). Consider a pair of feasible and bounded primal and dual MPs
min cT   A = b   0 and max bT u  AT u  c, andtheir extended counterparts of the form
min cT  + f T y

max bT u

subject tosubject toA + F y = bAT u  c
F T u  f

 y  0

where structural inequalities F T u  f are added to thedual at initialization time, i.e., before column generation
starts. We assume that these inequalities do not change theoptimal objective function value. These constraints correspond to additional variables y  0 in the primal, which are
not present in the original MP. From the primal perspective, we obtain a relaxation. The size of a primal basis is
not affected. A good restriction of the dual polyhedron issought, ideally to the optimal face.
Structural inequalities exploit speciﬁc problem knowledge. Consider the one-dimensional cutting-stock problem (4). It can be easily shown that if the orders are ranked
such that w1 < w2 < · · · < wm , then the dual multipliers satisfy u1  u2  · · ·  um . Hence, we can impose m − 1 dual
constraints that must be satisﬁed at each iteration of thecolumn generation process. These constraints can be generalized to larger sets. Let Si = s  ws < wi . Then,ws  w i ⇒s∈S

us  u i S ⊂ Si(29)

4.2. A Dual Point of Views∈S

The dual of the RMP is the dual MP with rows omitted, hence, a relaxation. An optimal dual solution obtained

A primal interpretation of these constraints is given by
Valério de Carvalho (2000); a direct proof of their validity

Lübbecke and Desrosiers: Selected Topics in Column Generation

1015

Operations Research 53(6), pp. 1007–1023, © 2005 INFORMS

in the dual space can be found in Ben Amor (2002). Using
the above m − 1 simplest dual constraints and, for eachorder i, at most one constraint of type (29) with S = 2,
there is a considerable speedup for solving the linear relaxation of (4).
We also observe that in the case of the so-called “difﬁcult” triplet problems, where each roll is cut into exactly
three orders without any waste, the optimal dual multipliers are known in advance and assume values ui = wi /W ,i = 1  m. Using this a priori perfect dual information,
the number of column generation iterations dramaticallydecreases for a number of test problems (Ben Amor 2002).
Computational experiments conducted by Ben Amor
(2002) on the multiple depot vehicle scheduling problem
show that by constraining the dual multipliers to a smallinterval around their optimal values, column generation canbe accelerated by a factor of 100. This is because poor dual
cutting planes, with respect to the interval, are not generated. Optimal multipliers are usually not available. Goodestimates can be obtained from a relaxation of the problem,from tests of previous experiments, or derived by subgradient algorithms. As a further beneﬁt, restricting the dual
space may partly remove primal degeneracy (Ben Amor
2002, Valério de Carvalho 2000). See also §6.2.
4.2.2. Row Aggregation for Set-Partitioning Problems. When the MP is a set-partitioning problem, large
instances are difﬁcult to solve due to massive degeneracy,say, when the number of nonzero elements per column
roughly exceeds 10. Then, the value of the dual variables
is not a meaningful measure for which column to adjoin
to the RMP. As a remedy, Elhallaoui et al. (2005) proposea dynamic row aggregation technique. Their intuition isthat in applications like vehicle routing and crew scheduling, some activity sequences are more likely to occur thanothers: In airline crew scheduling a pilot usually stays in
the aircraft with which he starts his duty day. Because aircraft itineraries are known prior to solving the crew-pairing
problem, it is natural to “guess” some aggregation of theﬂights to cover. This allows for a considerable reduction of
the size of the RMP in each iteration.
No aggregation is done at the level of the subproblem
and the cost of a column remains unchanged, regardless ofwhether aggregated or not. Still, the aggregated RMP provides us with aggregated dual multipliers. These are split
into estimates of the dual multipliers for the unaggregated
RMP solving shortest-path problems, based on the columns
already generated and the reduced cost optimality criterion.
The estimated duals are used in the subproblem to generate
new columns. To ensure proper convergence and optimality, the aggregation is dynamically updated throughout thesolution process.
Tests conducted on the linear relaxation of the simultaneous vehicle and bus driver scheduling problem in urban
mass transit show that this solution approach signiﬁcantly
reduces the size of the MP, the degeneracy, and the solution

times, especially for larger problems: For an instance with1,600 set-partitioning constraints, the RMP solution time is
reduced by a factor of eight.

5. The Pricing Problem
We are free to choose a subset of nonbasic variables, anda criterion according to which a column is selected fromthe chosen set. According to the classical Dantzig rule, onechooses among all columns the one with the most negative
reduced cost. Various schemes are proposed in the literature
like full, partial, or multiple pricing (Chvátal 1983). Column generation is a pricing scheme for large-scale linear
programs. In Gamache et al. (1999), up to 300  -hardsubproblems arise, and partial column generation is used.
That is, only a subset of subproblems is chosen at each
iteration to generate new columns. This also avoids thegeneration of many similar columns.
The role of the pricing subproblem is to provide a column that prices out proﬁtably or to prove that none exists.
It is important to see that any column with negative reduced
cost contributes to this aim. In particular, there is no needto solve (3) exactly; an approximation sufﬁces until the last
iteration. We may add many negative reduced cost columns
from a subproblem; even positive ones are sometimes used.
We may solve a temporary restriction of the subproblem,
or a relaxation, which is the case for the vehicle routing
problem with time windows (Desrochers et al. 1992).
5.1. Dominance and Redundancy of Columns
Let us speak about strength of dual constraints. A column
with reduced cost c̄ is dominated if there exists anothercolumn with reduced cost no larger than c̄ for all dual variables ranging within their respective domains (Vanderbeck1994). On the other hand, a column with reduced cost c̄ isundominated, if for all other columns there exists a set ofdual variables yielding reduced cost strictly larger than c̄.
If dominance is detected after the solution of the pricing
problem, the column is replaced by the dominating column in a post-processing phase. For instance, let  be thecollection of sets of a set-covering problem. A column as
corresponding to a set s ⊆  is dominated, if adding to s
an element r ∈ \ s incurs no cost, because cs − uT as cs − uT as − ur = cs∪ r − uT as∪ r for all u  0.
An even stronger concept is introduced by Sol (1994).
By analogy with the search for strong cutting planes, ideally facets of the dual polyhedron, we ask for strong
columns in the RMP. A column as is called redundant if thecorresponding constraint is redundant for the dual problem.
That is,
as = ar r and cs  cr r
(30)
r⊂s

r⊂s

A column is strictly redundant if (30) holds with strict
inequality. The pair  c satisﬁes the subcolumn property if cr < cs for all subsets r ⊂ s ∈ . In this case,Lübbecke and Desrosiers: Selected Topics in Column Generation

1016

Operations Research 53(6), pp. 1007–1023, © 2005 INFORMS

a set-partitioning problem can be solved as a set-covering
problem. If only cr  cs holds, strict inequality can beobtained by modifying the cost structure by cr = cr + r.
This adds to z a constant term equal to the number ofrows and does not change the problem. Sol (1994) givesa characterization of redundant columns in the case thatall subproblems are identical. He also proves that there is
no redundant column when all subproblems are different
from one another. For set-partitioning problems with identical subproblems the generation of redundant columns can
be avoided using an alternative pricing rule.
Proposition 2. Let  c satisfy the subcolumn property
 be a vector of dual
for a set-partitioning problem and umultipliers. If as ∈  is a strictly redundant column, then it
cannot be an optimal solution to the pricing problemmin
 T a c a −u
a
∈


1T a

(31)

5.2. Alternative Pricing Rules
Proposition 2 indicates that not using the Dantzig rule may
be theoretically advantageous. For example, steepest-edge
pricing (Forrest and Goldfarb 1992, Goldfarb and Reid
1977) and the practical Devex variant (Harris 1973) are
reported to perform particularly well for set-partitioning
RMPs (Sol 1994). The rationale behind the dual pendant
deepest-cut (Vanderbeck 1994) is to cut away as much of
the dual space as possible. While steepest-edge is inherently based on the simplex method, deepest-cut is more
independent from a particular solution method. This latter property leads to the lambda pricing rule (Bixby et al.
1992). Assume that cj  0, j ∈ J . Clearly, the reduced cost
 T aj are nonnegative for all j ∈ J if and only if
cj − uminj∈Jcj  T

a
>
0
1
u

j
 T aju(32)

At ﬁrst glance, this is just a reformulation. However, (32)takes advantage of structural properties of (particular) setpartitioning problems: Picking columns with a small ratio
accounts for smaller cost coefﬁcients as well as for more
nonzero entries in aj .
Many publications on simplex pricing are available, only
a few of which have been related to column generation.
One proposal is to generate columns which maximally
improve the objective function value (Swoveland 1974).
The computational usefulness of such comparably aged
proposals needs assessment from a modern implementation point of view. The natural question for which columns
serve our goals best is not consistently to answer owing to
the multiple, sometimes contrary, evaluation criteria. Computational efforts may cancel theoretical beneﬁts. When the
subproblem is solved by dynamic programming, many negative reduced cost columns are available. Among these,
a posteriori choosing columns according to the alternative

proposals is a practicable compromise in view of possible
difﬁculties in efﬁciently implementing alternative pricing
rules.
Still, pricing rules are sensitive to the dual variable values, in case of nonunique dual solutions. Although primal
as well as dual information went into pricing strategies,
complementary slackness conditions have not been satisfactorily exploited or applied.
5.3. Pricing Integer Programs
When the compact formulation (15) is an integer program,so is the pricing problem. It may be difﬁcult to solve,
and the efﬁciency of decomposition hinges on the question whether repeatedly solving the subproblems is “easier”
than solving (15) at once.
5.3.1. Integrality Property. When conv X is an integral polyhedron, already the linear program (18) gives aninteger solution. This is called the integrality property ofthe subproblem. Of course, it intimately depends on the
subproblem formulation. For subproblems whose natural
formulation gives integral optimal solutions anyway, e.g.,shortest-path problems, the lower bound on the optimal
integral z in (15) obtained from the linear relaxation of
the extensive formulation is no better than the one obtained
from the compact formulation (Geoffrion 1974). On theother hand, when this property does not hold, one has
potential to improve the lower bound, but one has to work
harder to obtain integral subproblem solutions in the ﬁrst
place. Thus, when the integrality gap is large, one would
prefer a subproblem without the integrality property; thisalso holds for Lagrangian relaxation (Geoffrion 1974). On
the other hand, in presence of the integrality property, thecomputation time gained by fast combinatorial algorithms
and their ease to implement may outmatch the disadvantage
of a large gap.
When the polyhedron conv X is well studied like, e.g.,a knapsack polytope, the relevant literature can be exploited
to strengthen the linear relaxation of the pricing integer
programs (Vanderbeck 1994). When problems are small orcuts are of insufﬁcient strength, plain branch and boundmay be the faster alternative. A more thorough investigation of the subsystem polytope can give encouraging
results when adding strong valid inequalities to the pricing problem before using branch and bound (Johnson et al.
1993). A combinatorial algorithm to solve the subproblem,
if available, may be even more efﬁcient. This is the casefor constrained shortest-path problems. Dynamic programming algorithms usually provide many columns per iteration. This is to be preferred over adding only one from a
linear program.
5.3.2. Structured Sets of Columns. What columns
are good for integer solutions? Even columns that are partof an (optimal) integer solution may interfere with solving the linear RMP by inﬂuencing its “guide,” namely, thedual variable values (Vanderbeck 1994). The RMP may

Lübbecke and Desrosiers: Selected Topics in Column Generation

1017

Operations Research 53(6), pp. 1007–1023, © 2005 INFORMS

require longer solution times due to the enlarged problem
size. Conversely, columns which are of no use for the linear
relaxation may be required for the integer feasibility of the
RMP. The concept of adjoining partial solutions seems tooffer signiﬁcant advantages as for obtaining integer solutions. Desrochers et al. (1992) remark that adding columns
to a set-partitioning RMP that are orthogonal sets replicate
the structure of the optimal integer solution. Savelsbergh
and Sol (1998) observe that less similar columns are generated when the dual solution is far from optimal.
Lagrangian pricing exploits the problem information
provided by the original formulation (Löbel 1997, 1998).
Based on a dual solution to the RMP, one obtains primal solutions from several Lagrangian relaxations anddeduces the columns to be adjoined to the RMP. Considerable customization is necessary, e.g., deciding which
Lagrangian subproblems to use. Furthermore, the deduction of columns can be nontrivial. Nonetheless, the charmof using Lagrangian relaxations of the compact formulation
rests upon controlling the structure of added columns. Verylarge-scale linear programs emerging from practical vehicle routing problems are optimally solved using this pricing
scheme.

6. The Tailing-Off Effect
Simplex-based column generation is known for its poor
convergence. While usually a near optimal solution is approached considerably fast, only little progress per iteration
is made close to the optimum. Also, it may be relatively
time consuming to prove optimality of a degenerate optimal solution. Figuratively speaking, the solution process
exhibits a long tail (Gilmore and Gomory 1963), hence,
this phenomenon is called the tailing-off effect. There is an
intuitive assessment of the phenomenon, but a theoreticalunderstanding has only been partly achieved to date; themonographs by Lasdon (1970) and Nazareth (1987) makenotable contributions.
6.1. Computational Difﬁculties
In general, the trajectory of solutions to (7) as constructedfrom solutions  to the RMP passes through the interiorof x ∈ n  Dx  d x  0. In the optimum, complementary slackness conditions have to be satisﬁed. Becausechanges of primal and dual variables are applied iteratively, not simultaneously, a certain amount of “cleaningup” (Nazareth 1987) is to be expected. Very small adjustments may be necessary close to optimum.
Finding an appropriate combination in (8) might be hindered by the possibly “complex combinatorial structure” offaces of the polyhedron deﬁned by the subproblem (Kimand Nazareth 1991). This complication may be worse in thepresence of several subproblems. A problem speciﬁc reformulation of the pricing problem to a priori restrict attention
to a set of well-structured columns may help (Hurkens et al.
1997); see also Barnhart et al. (1998b). The diameter ofthe polyhedron associated with (9) is not smaller than thatof the polyhedron corresponding to (7) (Adler and Ülkücü
1973). This is interesting, considering that the diameteris the maximal number of steps an ideal vertex-following
algorithm takes.
In ﬁnite precision arithmetic one has to cope with numerical instability. There are examples for bad numerical characteristics of the MP in contrast to a well-behaving compact
formulation (Nazareth 1984, 1987). Then, our stopping criterion may not work correctly (Ho 1984, Minoux 1986).
We remark, however, that tailing off also occurs whencolumns are computed exactly, e.g., by use of combinatorial algorithms.
6.2. Stabilized Column Generation
It has been observed that the dual variable values do notsmoothly converge to their respective optima, but vehemently oscillate, seemingly following no regular pattern.
This behavior is regarded as a major efﬁciency issue, andits absence is seen as a (possibly the) desirable property.
A simple idea was mentioned in §4.1.1, viz. bounding
the dual variable values (Agarwal et al. 1989). A moresophisticated control of the dual variables is as follows.
 denote an optimal solution to the current
Let again u
restricted dual RMP. By imposing lower and upper bounds,
respectively, dual variables are constrained to lie in a “box .” The such restricted RMP is re-optimized. Ifaround u
the new dual optimum is attained on the boundary of thebox, we have a direction towards which the box should be
relocated. Otherwise, the optimum is attained in the box’sinterior, producing the sought global optimum. This is theprinciple of the Boxtep method introduced by Marsten(1975) and Marsten et al. (1975). Several other stabilization approaches have been proposed, see, e.g., Senneand Lorena (2001), where a so-called Lagrangian/surrogate
relaxation is used for this purpose. In the following we
describe three of these.
6.2.1. Weighted Dantzig-Wolfe Decomposition.
Inthe computation of the Lagrangian dual (17), one cansearch “for good Lagrangian multipliers in the neighborhood of the best multipliers found so far” (Wentges 1997).
 k+1 inIn lieu of pricing with the optimal dual variables uthe (k + 1)st iteration, a convex combination is used: k+1 =uubest k1 k /k − 1 best k
 +

u
u

/k
/k
i

  i = 1∈ arg max L u

(33)
 k

where L u is deﬁned in (16), and/k = min const k + number of improvements
 best · /2of L uwith const  2. Obviously, (33) is biased towards the dual
solution, which produced the respective best Lagrangian1018
lower bound in the column generation process. This emphasis becomes even stronger as the algorithms proceeds,
and grows with the number of improvements of the lower
bound. This can be seen as a stabilization of heuristically good multipliers. The constant “const” is instrumental
in ensuring the consideration of enough fresh informationfrom the current RMP.
 k+1 = u
 best k + /−1
k − u best k , theRewriting (33) as u
k umethod is interpreted as feasible direction search, emerging
 best k in the direction of the current dual solution ukfrom u−1
with step length /k . Finiteness of this weighted version is proven. In computational experience with capacitated facility location problems, the method delivers better
Lagrangian lower bounds, when termination is guided bya small size of the duality gap. On the other hand, thesame experiments indicate that the primal objective function value of the RMP decreases more slowly when using
this method.
This is an example where ideas from proposals for multiplier adjustment in subgradient methods can be transferred to the column generation context. In fact, the two
approaches are combined (Barahona and Jensen 1998), i.e.,
for every few iterations some or all of the dual variables
obtained from the RMP are improved by some iterationsof a subgradient algorithm before passing them to the subproblem. In early iterations, this produces good multipliers, and later on improves the lower bound. Considerably
reduced computation times are reported for their particular application. A similar observation is made by Mahey(1986). The voluminous fund of “Lagrangian literature”
may further provide stimulation in this direction.
6.2.2. Trust Region Method. It is desirable not having
to customize the stabilization device. For a direct controlof dual variables Kallehauge et al. (2001) consider the dual
RMP with additional box constraints centered around thecurrent dual optimal solution û, i.e., ui − 0  ui  ui + 0.
The method is related to the work of Madsen (1975) in thesense that these bounds are adjusted automatically, depending on how well the dual restricted MP approximates the
Lagrangian dual problem. This type of method is called atrust region method. The trust region parameter 0 is updated
in each iteration according to the original update scheme by
Marquardt (1963). Only iterations yielding primal progress
are actually performed, and Kelley’s (1961) cutting-plane
method is applied to generate rows of the dual RMP, i.e.,columns of the primal. When the duality gap closes (upto a preset accuracy) for a dual solution in the interior of
the current box, optimality is reached, and the algorithm
terminates.
6.2.3. A Stabilization Approach Using Primal andDual Strategies.
Stabilized column generation (Ben
Amor 2002, du Merle et al. 1999) involves a more ﬂexible, linear programming concept of a box, together with an
1-perturbation of the right-hand side. Consider the follow-

Lübbecke and Desrosiers: Selected Topics in Column Generation
Operations Research 53(6), pp. 1007–1023, © 2005 INFORMS

ing linear program:min cT  − T− y− + T+ y+
subject toA − y− + y+ = by−   − (34)y+  +  y−  y+  0
After changing the sign of w− , w+ , respectively, its dual
reads
max bT u − T− w− − T+ w+
subject to

AT u  c−u − w−  −− (35)u − w+  + 
w−  w+  0
In (34), surplus and slack variables y− and y+ , respectively,
account for a perturbation of b by  ∈ "−−  + #, helping
to reduce degeneracy. Their usage is penalized via − , + ,respectively. The interpretation of (35) is more interesting.
The original dual variables u are restricted to the interval"− − w−  + + w+ #, that is, deviation of u from the interval "−  + # is penalized by an amount of − , + per unit,
respectively. The motivation is to steer u towards a hopefully good estimate of an optimal solution u to the unperturbed problem min cT   A = b   0. When does(34) yield an optimal solution this problem? Sufﬁcient is(a) − = + = 0, or (b) − < û < + , where û is an optimal
solution to (35); (a) for the obvious reason, and (b) by complementary slackness conditions and ±  0. Therefore, thestopping criteria of a column generation algorithm becomec̄  = 0 and y− = y+ = 0.
The parameters are updated dynamically so as to makegreatest use of the respective latest information. With intent
to reduce the dual variables’ variation, select ± to forma small box containing the (in the beginning estimated)current dual solution, and solve the linear program (34). If
the new û lies in the box described by ± , reduce its widthand augment the penalty given by ± . Otherwise, enlarge
the box and decrease the penalty. This allows for fresh dual
solutions when our estimate was bad. The update could
be performed in each iteration, or alternatively, each time
a dual solution of currently best quality is obtained. Thislatter method proves most effective in implementations. An
update of the dual estimates can be seen as a serious stepin the bundle method.
It is clear that a problem speciﬁc adaptation of theparameter choice is needed. The experiments by Ben Amor
(2002) and du Merle et al. (1999) indicate considerable
speedup of up to a factor of 10 or a growth in thesize of manageable problems when using the stabilization approach. A related proposal (Agarwal et al. 1989)

Lübbecke and Desrosiers: Selected Topics in Column Generation

1019

Operations Research 53(6), pp. 1007–1023, © 2005 INFORMS

gives similar experiences. Vanderbeck (2005) concludes
that among more sophisticated implementation techniques,stabilization may promise the largest performance gains. It
is important to note that (34) is a relaxation of the unperturbed problem which is computed faster, and can be used
in a branch-and-bound algorithm.

7.2. Pricing Out the Original x Variables
Assume that in (15) we have a linear subproblem X =x ∈ n+  Dx  d = . Column generation then essentiallysolves the linear program
min cT x

7. Integer Solutions

subject to Ax  b Dx  d

Having introduced decomposition techniques for integer
programs in §3, we still need ideas on how to actuallyobtain integer solutions. The literature is rich on that subject; see Table 1. In fact, X may as well contain nonlinear
aspects other than discreteness. Various notions have beencoined for the synthesis of column generation and branch
and bound, like branch and price (Barnhart et al. 1998b)
and IP column generation (Vanderbeck and Wolsey 1996).
Our point is that—besides the decomposition principles—essentially, it all boils down to branch and bound. Consequently, this section is about lower bounds and branchingdecisions.

We obtain an optimal primal solution x , but only the dual
multipliers u associated with the constraint set Ax  b.
However, Walker (1969) describes how to retrieve the dual
variables w associated with Dx  d: Take the dual vector
obtained from solving the linear subproblem in the last iteration of the column generation process. Knowing the full
dual information allows for a pricing of the original variables, and therefore a possible elimination of some of them.
Together with an integral solution this can be exploited todiscard original binary variables with reduced cost larger
than the optimality gap. Hadjar et al. (2001) apply this technique to remove more than 90% of the ﬂow variables in
multiple depot vehicle scheduling problems.
In the general case of a linear integer or even nonlinear
pricing subproblem, the above procedure does not work.
Poggi de Aragão and Uchoa (2003) suggest to directly use
the extensive
 formulation:
 If we keep the coupling constraint x = q∈Q pq q + r∈R pr r in the MP (23), it sufﬁces to impose x   for a small  > 0 at the end of
the process. The shadow prices of these constraints are thereduced costs of the x vector of original variables. Notethat there is no need to impose the additional constraints
on already positive variables. Computational experiments
underline the beneﬁts of this procedure.

7.1. Lower Bounds and Early Termination
In each node of a branch-and-bound tree we derive lower
bounds on the best possible integer solution in the respective branch from solving the RMP linear relaxation bycolumn generation. One would expect that the tailing-off
effect would be ampliﬁed by the multitude of linear programs to solve. However, the contrary is true. The need for
integer solutions provides us with a very simple amendment: Stop generating columns when tailing off occurs andtake a branching decision. This early termination is basedon the following. Assuming cj ∈ , j ∈ J , column generation can be terminated as soon as LB = z̄, with LB,e.g., one of the lower bounds of §2.1. For this purpose they
have been widely used in the literature, e.g., Sol (1994),
Vanderbeck (1994), and Vanderbeck and Wolsey (1996).
With the incumbent integral objective function value ẑ,a node can be pruned as soon as LB  ẑ.
Early termination makes the algorithm effective for integer programs in contrast to linear programs. Of course,
we need not wait until LB = z̄; we may terminate
heuristically even earlier. Here is a trade-off between computational efforts and the quality of the obtained lower
bound upon premature termination. We remind the reader
that this is the usual way to stop subgradient algorithms
in Lagrangian relaxation. Note that monitoring the relative
decrease of the objective function value over a predeﬁned
number of iterations (Gilmore and Gomory 1963) is notrobust against temporary stalls.
Integrality helps us also in other places. For a single subproblem the computation of an a priori upper bound on c̄ 
is given in Vanderbeck and Wolsey (1996, Proposition 4).
When the subproblem is solved as an integer program, an
initial upper cutoff can be applied. When the pricing problem is detected to be infeasible, we terminate.

x0

7.3. Branching and Cutting Decisions
A valid branching scheme divides, desirably partitions, thesolution space in such a way that the current fractional solution is excluded, integer solutions remain intact, and ﬁniteness of the algorithm is ensured. Moreover, some generalrules of thumb prove useful, such as to produce branches ofpossibly equal size, sometimes referred to as balancing thesearch tree. Important decisions should be made early inthe tree. In the case that we require the variables of the MP
to be integer, like in (25), a so-called compatible branching
scheme is needed which prevents columns that have been
set to zero on from being regenerated without a signiﬁcant complication of the pricing problem (Johnson 1989,
Savelsbergh 1997, Vance 1998). This, in general, would
lead to ﬁnding the kth best subproblem solution insteadof the optimal one (Ribeiro et al. 1989). Aside from theconceptual complication, this modiﬁed or destroyed a possibly well-exploited structure. This is all the more important when, e.g., combinatorial algorithms are used for the
subproblem solution.
When integer solutions are sought for the MP, generalbranching schemes are given by Vanderbeck (2000) andLübbecke and Desrosiers: Selected Topics in Column Generation

1020

Operations Research 53(6), pp. 1007–1023, © 2005 INFORMS

Vanderbeck and Wolsey (1996). The most common schemein conjunction with column generation is Ryan and Foster’s(1981) that is designed for set-partitioning problems.


Proposition 3. Given A ∈ 0 1m×J  and a fractional
basic solution to A = 1,   0, i.e.,   0 1m .
Then,there exists r s ∈ 1  m such that 0 <a
rj asj j < 1.
j∈JWhen such two rows are identiﬁed, we obtain one branch
in which these rows must be covered by the same column,i.e., j∈J  arj asj j = 1, and one branch inwhich they must
be covered by two distinct columns, i.e., j∈J  arj asj j = 0.
Note that this information can be easily transferred to andobeyed by the pricing problem.
This excellent scheme already hints to a powerful insightwhich is used already in standard branch and bound, viz.
to branch on meaningful sets of variables. Our most valuable source of information are the original variables of thecompact formulation; they must be integer, and they arewhat we branch and cut on, see e.g., Desaulniers et al.
(1998), Gamache et al. (1998), and Sol (1994). To thisend, let us assume that we have a compact formulationon hand; see §3.4. Branching and cutting decisions both
involve the addition of constraints, at least implicitly. One
could require integrality of x at any node of a branch-andbound tree (Holm and Tind 1988), but this is not efﬁcient.
A problem speciﬁc penalty function method is proposed by
Hurkens et al. (1997). Alternatively, given an added set of
constraints, these restrictions on the compact formulation(15) can be incorporated in Ax  b, in x ∈ X, or partiallyin both structures. In any case, the new problem is of thegeneral form of (15) to which we apply a decomposition.
The new RMP is still a linear program, and as long as
the possible modiﬁcation of the subproblem’s structure is
tractable, we face no severe complications.
Consider, for example, the vehicle routing problem withtime windows (Desaulniers et al. 2001a, Desrochers et al.
1992): Decisions can be taken on the network ﬂow variables as well as on the starting time of the service at acustomer. Additionally, we may impose subtour elimination
constraints, or more generally, -path cuts, where  is alower bound on the number of vehicles needed to service
a certain set of customers (Kohl et al. 1999). Also possible
are the trivial cuts on the total number of vehicles and on
the value of the objective function, decisions on a single
arc, or on a linear combination of arc ﬂow and time values.
Ioachim et al. (1999) perform branching on time variables that are already integer, but obtained as a convex
combination of several time values. Gamache et al. (1998)
impose a very deep cut into the subproblem structure. It
does not only cut off the current infeasible solution, but
at the same time it also removes a number of nonoptimal
integer solutions from the subproblem structure. Generally
speaking, a decision imposed on the pricing problem ispreferable to one imposed on the MP as it directly controls
the generated columns. An example of that is the 2-cycle

elimination for constrained shortest paths with time windows (Desrochers et al. 1992), generalized by Irnich andVilleneuve (2003). The choice of the structure on which
to impose decisions is a matter of algorithmic efﬁciency
and performance. We remark that adding cutting planes in
conjunction with column generation in a branch-and-boundsearch is usually called branch and price and cut; see e.g.,
Barnhart et al. (1998a), Barnhart et al. (2000), and Parket al. (1996).
Finally, one should be aware that even if a new decision set goes into the MP structure, the pricing problem
may change. Ioachim et al. (1999), in the routing andscheduling area, have linear combinations of time variables
that appear in the MP structure; this has the consequencethat these time variables also appear in the objective function of the subproblem together with the ﬂow variables.
This changes the way to solve the constrained shortest-path
problem (Ioachim et al. 1998).
The implementation of a column-generation-based integer programming code still is an issue. This is not so
because of the complex interaction of components, but
because of the vast possibilities to tune each of them. All
strategies from standard branch and bound apply, including depth-ﬁrst search for early integer solutions, heuristic fathoming of nodes, rounding and (temporary) ﬁxingof variables, pre- and postprocessing, and many more
(Desaulniers et al. 2001b, Vanderbeck 2005).
Concluding, two decades ago, Chvátal (1983) saw no
efﬁcient way of handling the difﬁculty of ﬁnding an
optimal integer solution to a problem solved using acolumn generation scheme. Today, this is no longer true
when a compact formulation is available and columns are
generated at each node of the search tree. This fundamental and indeed extremely simple approach has been in use
now for more than 20 years (Desrosiers et al. 1984), andis being reﬁned ever since. The price we have to pay forthis simplicity is that besides RMP, subproblem, and branch
and bound, the compact formulation has to be represented
to recover a solution in terms of the original variables x.

8. Conclusions
The growing understanding of the dual point of viewbrought considerable progress to the column generation
theory and practice. It stimulated careful initializations,
sophisticated solution techniques for the restricted MP and
the subproblem, as well as better overall performance.
Computational defects of Dantzig-Wolfe decomposition
are well documented, and we cannot recommend its classical implementation as a pricing scheme for large-scale linear programs. However, structural dual inequalities, primaland dual stabilization strategies, as well as nonlinear implementations turn column generation into a very promising
approach to decomposable linear programs.
Column generation is clearly a success story in largescale integer programming. The linear programming boundLübbecke and Desrosiers: Selected Topics in Column Generation
Operations Research 53(6), pp. 1007–1023, © 2005 INFORMS

obtained from an extensive reformulation is often stronger,
the tailing-off effect can be lessened or circumvented atall, and the knowledge of the original compact formulation
provides us with a strong guide for branching and cutting
decisions in the search tree. Today we are in a position
that generic integer programming column generation codes
solve many large-scale problems of “industrial difﬁculty,”that no standard commercial MIP solver could cope with.
This is all the more true because nonlinearities occurring inpractical problems can be taken care of in the subproblem.
For very hard problems, the best algorithmic choice may
not be obvious. Having identiﬁed the computational bottleneck, one should invest in implementing more sophisticated ideas which we discuss in this paper. The good news
is: There are plenty of them. In addition, all components
greatly beneﬁt from customization and tailoring. Problem
adequate heuristics are most vital ingredients in an actual
implementation. Thus, ample room for research and experiments is left, and hopefully some directions have been
pointed out.
References
Adler, I., A. Ülkücü. 1973. On the number of iterations in Dantzig-Wolfe
decomposition. D. M. Himmelblau, ed. Decomposition of Large Scale
Problems. North-Holland, Amsterdam, The Netherlands, 181–187.
Agarwal, Y., K. Mathur, H. M. Salkin. 1989. A set-partitioning-based
exact algorithm for the vehicle routing problem. Networks 19
731–749.
Alvelos, F., J. M. Valério de Carvalho. 2000. Solving multicommodity ﬂow problems with branch-and-price. Technical report, Dept.
Produção e Sistemas, Universidade do Minho, Braga, Portugal.
Anbil, R., J. J. Forrest, W. R. Pulleyblank. 1998. Column generation andthe airline crew pairing problem. Proc. Internat. Congress of Mathematicians Berlin. Extra volume ICM Doc. Math. J. DMV, 677–686.
Barahona, F., R. Anbil. 2000. The volume algorithm: Producing primal solutions with a subgradient method. Math. Programming 87(3)385–399.
Barahona, F., R. Anbil. 2002. On some difﬁcult linear programs comingfrom set partitioning. Discrete Appl. Math. 118(1–2) 3–11.
Barahona, F., D. Jensen. 1998. Plant location with minimum inventory.
Math. Programming 83 101–111.
Barnhart, C., R. R. Schneur. 1996. Air network design for express shipment service. Oper. Res. 44(6) 852–863.
Barnhart, C., C. A. Hane, P. H. Vance. 1997. Integer multicommodity ﬂow
problems. Lecture Notes Econom. Math. Systems 450 17–31.
Barnhart, C., C. A. Hane, P. H. Vance. 2000. Using branch-and-price-andcut to solve origin-destination integer multicommodity network ﬂow
problems. Oper. Res. 48(3) 318–326.
Barnhart, C., E. L. Johnson, G. L. Nemhauser, M. W. P. Savelsbergh,
P. H. Vance. 1998b. Branch-and-price: Column generation for solving
huge integer programs. Oper. Res. 46(3) 316–329.
Barnhart, C., N. L. Boland, L. W. Clarke, E. L. Johnson, G. L. Nemhauser,
R. G. Shenoi. 1998a. Flight string models for aircraft ﬂeeting androuting. Transportation Sci. 32(3) 208–220.
Ben Amor, H. 2002. Stabilisation de l’algorithme de génération decolonnes. Ph.D. thesis, École Polytechnique de Montréal, Montréal,
Québec, Canada.
Benders, J. F. 1962. Partitioning procedures for solving mixed-variables
programming problems. Numer. Math. 4 238–252.
Bixby, R. E. 2002. Solving real-world linear programs: A decade andmore of progress. Oper. Res. 50(1) 3–15.

1021
Bixby, R. E., J. W. Gregory, I. J. Lustig, R. E. Marsten, D. F. Shanno.
1992. Very large-scale linear programming: A case study in combining interior point and simplex methods. Oper. Res. 40(5) 885–897.
Borndörfer, R., M. Grötschel, A. Löbel. 2003. Duty scheduling in public
transit. W. Jäger, H.-J. Krebs, eds. Mathematics—Key Technology for
the Future. Springer-Verlag, Berlin, 653–674.
Bourjolly, J.-M., G. Laporte, H. Mercure. 1997. A combinatorial column
generation algorithm for the maximum stable set problem. Oper. Res.
Lett. 20(1) 21–29.
Briant, O., C. Lemaréchal, K. Monneris, N. Perrot, C. Tadonki,
F. Vanderbeck, J.-P. Vial, C. Beltram. 2004. Comparison of Kelley’s
cutting plane, bundle, and proximal analytic center algorithms foruse in branch-and-price. Technical report, Université Bordeaux 1,
Bordeaux, France. In preparation.
Caprara, A., M. Fischetti, P. Toth. 1999. A heuristic method for the set
covering problem. Oper. Res. 47 730–743.
Caprara, A., M. Fischetti, P. Toth. 2000. Algorithms for the set covering
problem. Ann. Oper. Res. 98 353–371.
Chu, H. D., E. Gelman, E. L. Johnson. 1997. Solving large scale crewscheduling problems. Eur. J. Oper. Res. 97 260–268.
Chvátal, V. 1983. Linear Programming. W. H. Freeman and Company,
New York.
Crainic, T. G., J.-M. Rousseau. 1987. The column generation principle
and the airline crew pairing problem. Infor 25 136–151.
Crama, Y., A. G. Oerlemans. 1994. A column generation approach to job
grouping for ﬂexible manufacturing systems. Eur. J. Oper. Res. 78(1)58–80.
Dantzig, G. B., P. Wolfe. 1960. Decomposition principle for linear programs. Oper. Res. 8 101–111.
Desaulniers, G., J. Desrosiers, M. M. Solomon. 2001b. Accelerating strategies in column generation methods for vehicle routing and crewscheduling problems. C. C. Ribeiro, P. Hansen, eds. Essays andSurveys in Metaheuristics. Kluwer, Boston, MA, 309–324.
Desaulniers, G., J. Desrosiers, Y. Dumas, M. M. Solomon, F. Soumis.
1997. Daily aircraft routing and scheduling. Management Sci. 43(6)841–855.
Desaulniers, G., J. Desrosiers, A. Erdmann, M. M. Solomon, F. Soumis.
2001a. The VRP with pickup and delivery. P. Toth, D. Vigo, eds. The
Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, Chapter 9. SIAM, Philadelphia, PA.
Desaulniers, G., J. Desrosiers, I. Ioachim, M. M. Solomon, F. Soumis,
D. Villeneuve. 1998. A uniﬁed framework for deterministic time constrained vehicle routing and crew scheduling problems. T. G. Crainic,
G. Laporte, eds. Fleet Management and Logistics. Kluwer, Norwell,MA, 57–93.
Desrochers, M., F. Soumis. 1989. A column generation approach to urban
transit crew scheduling. Transportation Sci. 23 1–13.
Desrochers, M., J. Desrosiers, M. M. Solomon. 1992. A new optimization
algorithm for the vehicle routing problem with time windows. Oper.
Res. 40(2) 342–354.
Desrosiers, J., F. Soumis, M. Desrochers. 1984. Routing with time windows by column generation. Networks 14 545–565.
Desrosiers, J., Y. Dumas, M. M. Solomon, F. Soumis. 1995. Time
constrained routing and scheduling. M. O. Ball, T. L. Magnanti,
C. L. Monma, G. L. Nemhauser, eds. Network Routing, Vol. 8.
Handbooks in Operations Research and Management Science. NorthHolland, Amsterdam, The Netherlands, 35–139.
du Merle, O., D. Villeneuve, J. Desrosiers, P. Hansen. 1999. Stabilized
column generation. Discrete Math. 194 229–237.
Eben-Chaime, M., C. A. Tovey, J. C. Ammons. 1996. Circuit partitioning
via set partitoning and column generation. Oper. Res. 44(1) 65–76.
Elhallaoui, I., D. Villeneuve, F. Soumis, G. Desaulniers. 2005. Dynamic
aggregation of set partitioning constraints in column generation.
Oper. Res. 53(4) 632–645.
Elhedhli, S., J.-L. Gofﬁn. 2004. The integration of an interior-point
cutting-plane method within a branch-and-price algorithm. Math.
Programming. In press.

1022
Erdmann, A., A. Nolte, A. Noltemeier, R. Schrader. 2001. Modeling andsolving an airline schedule generation problem. Ann. Oper. Res. 107
117–142.
Farley, A. A. 1990. A note on bounding a class of linear programming problems, including cutting stock problems. Oper. Res. 38(5)922–923.
Ford, L. R., D. R. Fulkerson. 1958. A suggested computation for maximal
multicommodity network ﬂows. Management Sci. 5 97–101.
Forrest, J. J., D. Goldfarb. 1992. Steepest-edge simplex algorithms forlinear programming. Math. Programming 57 341–374.
Gamache, M., F. Soumis, G. Marquis, J. Desrosiers. 1999. A column
generation apporach for large-scale aircrew rostering problems. Oper.
Res. 47(2) 247–263.
Gamache, M., F. Soumis, D. Villeneuve, J. Desrosiers, E. Gélinas. 1998.
The preferential bidding system at Air Canada. Transportation Sci.
32(3) 246–255.
Geoffrion, A. M. 1974. Lagrangean relaxation for integer programming.
Math. Programming Stud. 2 82–114.
Gilmore, P. C., R. E. Gomory. 1961. A linear programming approach tothe cutting-stock problem. Oper. Res. 9 849–859.
Gilmore, P. C., R. E. Gomory. 1963. A linear programming approach tothe cutting stock problem—Part II. Oper. Res. 11 863–888.
Gofﬁn, J.-L., J.-Ph. Vial. 2003. Convex nondifferentiable optimization:
A survey focused on the analytic center cutting plane method. Optim.
Methods Software 17 805–867.
Gofﬁn, J.-L., A. Haurie, J.-Ph. Vial, D. L. Zhu. 1993. Using central
prices in the decomposition of linear programs. Eur. J. Oper. Res. 64
393–409.
Goldfarb, D., J. K. Reid. 1977. A practicable steepest-edge simplex algorithm. Math. Programming 12 361–371.
Grötschel, M., L. Lovász, A. Schrijver. 1988. Geometric Algorithms andCombinatorial Optimization. Springer, Berlin, Germany.
Hadjar, A., O. Marcotte, F. Soumis. 2001. A branch-and-cut algorithm
for the multiple depot vehicle scheduling problem. Les Cahiers du
GERAD G-2001-25, HEC, Montréal, Québec, Canada.
Hansen, P., B. Jaumard, M. Poggi de Aragão. 1998. Mixed-integer column
generation algorithms and the probabilistic maximum satisﬁability
problem. Eur. J. Oper. Res. 108 671–683.
Harris, P. M. J. 1973. Pivot selection methods of the Devex LP code.
Math. Programming 5 1–28.
Hiriart-Urruty, J.-B., C. Lemaréchal. 1993. Convex Analysis and Minimization Algorithms, Part 2: Advanced Theory and Bundle Methods,
Vol. 306. Grundlehren der mathematischen Wissenschaften. Springer,
Berlin, Germany.
Ho, J. K. 1984. Convergence behavior of decomposition algorithms forlinear programs. Oper. Res. Lett. 3(2) 91–94.
Holm, S., J. Tind. 1988. A uniﬁed approach for price directive decomposition procedures in integer programming. Discrete Appl. Math. 20
205–219.
Holmberg, K., K. Jörnsten. 1995. A simple modiﬁcation of Dantzig-Wolfe
decomposition. Optimization 34(2) 129–145.
Hurkens, C. A. J., J. L. De Jong, Z. Chen. 1997. A branch-and-pricealgorithm for solving the cutting strips problem. Appl. Math., Ser. B(English ed.) 12(2) 215–224.
Ioachim, I., J. Desrosiers, F. Soumis, N. Bélanger. 1999. Fleet assignmentand routing with schedule synchronization constraints. Eur. J. Oper.
Res. 119(1) 75–90.
Ioachim, I., S. Gélinas, F. Soumis, J. Desrosiers. 1998. A dynamic programming algorithm for the shortest path problem with time windows
and linear node costs. Networks 31 193–204.
Irnich, S., D. Villeneuve. 2003. The shortest path problem with resource
constraints and k-cycle elimination for k  3. INFORMS J. Comput.
Forthcoming.
Johnson, E. L. 1989. Modelling and strong linear programs formixed integer programming. S. W. Wallace, ed. Algorithms andLübbecke and Desrosiers: Selected Topics in Column Generation
Operations Research 53(6), pp. 1007–1023, © 2005 INFORMS

Model Formulations in Mathematical Programming. Springer, Berlin,
Germany, 1–43.
Johnson, E. L., A. Mehrotra, G. L. Nemhauser. 1993. Min-cut clustering.
Math. Programming 62 133–151.
Kallehauge, B., J. Larsen, O. B. G. Madsen. 2001. Lagrangean duality applied on vehicle routing with time windows. Technical report
IMM-TR-2001-9, Informatics and Mathematical Modelling, Technical University of Denmark, Kgs. Lyngby, Denmark.
Kantorovich, L. V. 1960. Mathematical methods of organising and planning production. Management Sci. 6 366–422. Translation from
Russian original 1939.
Kelley, J. E., Jr. 1961. The cutting-plane method for solving convex programs. J. Soc. Indust. Appl. Math. 8(4) 703–712.
Kim, K., J. L. Nazareth. 1991. The decomposition principle and algorithms for linear programming. Linear Algebra Appl. 152 119–133.
Kirkeby Martinson, R., J. Tind. 1999. An interior point method in DantzigWolfe decomposition. Comput. Oper. Res. 26(12) 1195–1216.
Klein, P., N. Young. 1999. On the number of iterations for Dantzig-Wolfe
optimization and packing-covering approximation algorithms. Proc.
7th Internat. IPCO Conf., Graz, Austria. Lecture Notes in Computer
Science, No. 1610. Springer, Berlin, Germany, 320–327.
Kohl, N., O. B. G. Madsen. 1997. An optimization algorithm for thevehicle routing problem with time windows. Oper. Res. 45 395–406.
Kohl, N., J. Desrosiers, O. B. G. Madsen, M. M. Solomon, F. Soumis.
1999. 2-path cuts for the vehicle routing problem with time windows.
Transportation Sci. 33(1) 101–116.
Krumke, S. O., J. Rambau, L. M. Torres. 2002. Real-time dispatching ofguided and unguided automobile service units with soft time windows. R. H. Möhring, R. Raman, eds. Proc. 10th Annual Eur. Sympos.
Algorithms, Rome, Italy. Lecture Notes in Computer Science, 2461
Springer, Berlin, Germany, 637–648.
Lasdon, L. S. 1970. Optimization Theory for Large Systems. Macmillan,
London, UK.
Löbel, A. 1997. Optimal vehicle scheduling in public transit, Ph.D. thesis,
Technische Universität Berlin, Berlin, Germany.
Löbel, A. 1998. Vehicle scheduling in public transit and Lagrangean pricing. Management Sci. 44(12) 1637–1649.
Lübbecke, M. E., U. T. Zimmermann. 2003. Engine routing and scheduling at industrial in-plant railroads. Transportation Sci. 37(2) 183–197.
Madsen, K. 1975. An algorithm for minimax solution of overdetermined
systems of non-linear equations. J. Inst. Math. Appl. 16 321–328.
Mahey, P. 1986. A subgradient algorithm for accelerating the DantzigWolfe decomposition method. Proc. X. Sympos. Oper. Res., Part I:
Sections 1–5. Methods in Operations Research, 53 Königstein/Ts.,
Athenäum/Hain/Scriptor/Hanstein, 697–707.
Mamer, J. W., R. D. McBride. 2000. A decomposition-based pricing procedure for large-scale linear programs—An application to the linear
multicommodity ﬂow problem. Management Sci. 46(5) 693–709.
Marquardt, D. W. 1963. An algorithm for least-squares estimation of nonlinear parameters. SIAM J. Appl. Math. 11 431–441.
Marsten, R. E. 1975. The use of the boxstep method in discrete optimization. Math. Programming Stud. 3 127–144.
Marsten, R. E., W. W. Hogan, J. W. Blankenship. 1975. The Boxstep
method for large-scale optimization. Oper. Res. 23 389–405.
Mehlhorn, K., M. Ziegelmann. 2000. Resource constrained shortest paths.
Proc. 8th Annual Eur. Sympos. Algorithms, Saarbrücken, Germany.
Lecture Notes in Computer Science, 1879. Springer, Berlin, Germany,
326–337.
Mehrotra, A., M. A. Trick. 1996. A column generation approach for graphcoloring. INFORMS J. Comput. 8(4) 344–354.
Minoux, M. 1986. Mathematical Programming. John Wiley and Sons,
Chichester, UK.
Minoux, M. 1987. A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations. RAIRO
Rech. Opér. 21 105–136.
Nazareth, J. L. 1984. Numerical behaviour of LP algorithms based upon
the decomposition principle. Linear Algebra Appl. 57 181–189.

Lübbecke and Desrosiers: Selected Topics in Column Generation
Operations Research 53(6), pp. 1007–1023, © 2005 INFORMS

Nazareth, J. L. 1987. Computer Solution of Linear Programs. Oxford
University Press, Oxford, UK.
Nemhauser, G. L., L. A. Wolsey. 1988. Integer and Combinatorial
Optimization. John Wiley and Sons, Chichester, UK.
Park, K., S. Kang, S. Park. 1996. An integer programing approach to the
bandwidth packing problem. Management Sci. 42(9) 1277–1291.
Poggi de Aragão, M., E. Uchoa. 2003. Integer program reformulation forrobust branch-and-cut-and-price algorithms. Proc. Conf. Math. Program in Rio: A Conf. in Honour of Nelson Maculan, Rio de Janeiro,
Brazil, 56–61.
Ribeiro, C. C., F. Soumis. 1994. A column generation approach to themultiple-depot vehicle scheduling problem. Oper. Res. 42(1) 41–52.
Ribeiro, C. C., M. Minoux, M. C. Penna. 1989. An optimal columngeneration-with-ranking algorithm for very large scale set partitioning
problems in trafﬁc assignment. Eur. J. Oper. Res. 41 232–239.
Ryan, D. M., B. A. Foster. 1981. An integer programming approachto scheduling. A. Wren, ed. Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling. North-Holland,
Amsterdam, The Netherlands, 269–280.
Sankaran, J. K. 1995. Column generation applied to linear programs incourse registration. Eur. J. Oper. Res. 87(2) 328–342.
Savelsbergh, M. W. P. 1997. A branch-and-price algorithm for the generalized assignment problem. Oper. Res. 45(6) 831–841.
Savelsbergh, M. W. P., M. Sol. 1998. DRIVE: Dynamic routing of independent vehicles. Oper. Res. 46(4) 474–490.
Schrijver, A. 1986. Theory of Linear and Integer Programming. John
Wiley and Sons, Chichester, UK.
Senne, E. L. F., L. A. N. Lorena. 2001. Stabilizing column generation
using Lagrangean/surrogate relaxation: An application to p-medianlocation problems. EURO 2001—The European Operational Res.
Conference, Erasmus University Rotterdam, July 9–11.
Sol, M. 1994. Column generation techniques for pickup and delivery problems. Ph.D. thesis, Eindhoven University of Technology, Eindhoven,
The Netherlands.
Soumis, F. 1997. Decomposition and column generation. M. Dell’Amico,
F. Mafﬁoli, S. Martello, eds. Annotated Bibliographies in Combinatorial Optimization. John Wiley and Sons, Chichester, UK, 115–126.
Swoveland, C. 1974. A note on column generation in Dantzig-Wolfe
decomposition algorithms. Math. Programming 6 365–370.
Valério de Carvalho, J. M. 1999. Exact solution of bin-packing problems
using column generation and branch-and-bound. Ann. Oper. Res. 86
629–659.
Valério de Carvalho, J. M. 2000. Using extra dual cuts to acceleratecolumn generation. Technical report, Dept. Produção e Sistemas,
Universidade do Minho, Braga, Portugal. INFORMS J. Comput.
Forthcoming.

1023
Valério de Carvalho, J. M. 2002a. LP models for bin-packing and cutting
stock problems. Eur. J. Oper. Res. 141(2) 253–273.
Valério de Carvalho, J. M. 2002b. A note on branch-and-price algorithms
for the one-dimensional cutting stock problem. Comput. Optim. Appl.
21(3) 339–340.
Van Roy, T. J. 1983. Cross decomposition for mixed integer programming.
Math. Programming 25 46–63.
Vance, P. H. 1998. Branch-and-price algorithms for the one-dimensional
cutting stock problem. Comput. Optim. Appl. 9(3) 211–228.
Vance, P. H., C. Barnhart, E. L. Johnson, G. L. Nemhauser. 1994. Solving
binary cutting stock problems by column generation and branch-andbound. Comput. Optim. Appl. 3(2) 111–130.
Vanderbeck, F. 1994. Decomposition and column generation for integer
programs. Ph.D. thesis, Université Catholique de Louvain, Louvainla-Neuve, Belgium.
Vanderbeck, F. 1999. Computational study of a column generation algorithm for bin packing and cutting stock problems. Math. Programming 86(3) 565–594.
Vanderbeck, F. 2000. On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Oper. Res. 48(1) 111–128.
Vanderbeck, F. 2005. Implementing mixed integer column generation.
G. Desaulniers, J. Desrosiers, M. M. Solomon, eds. Column Generation. Springer-Verlag, Boston, MA.
Vanderbeck, F., L. A. Wolsey. 1996. An exact algorithm for IP column
generation. Oper. Res. Lett. 19 151–159.
Villeneuve, D. 1999. Logiciel de génération de colonnes. Ph.D. thesis,
École Polytechnique de Montréal, Montréal, Québec, Canada.
Villeneuve, D., J. Desrosiers, M. E. Lübbecke, F. Soumis. 2005. On compact formulations for integer programs solved by column generation.
Ann. Oper. Res. 139(1) 375–388.
Walker, W. E. 1969. A method for obtaining the optimal dual solution toa linear program using the Dantzig-Wolfe decomposition. Oper. Res.
17 368–370.
Wedelin, D. 1995. An algorithm for large scale 0-1 integer programming with application to airline crew scheduling. Ann. Oper. Res. 57
283–301.
Wentges, P. 1997. Weighted Dantzig-Wolfe decomposition of linear mixed-integer programming. Internat. Trans. Oper. Res. 4(2)151–162.
Wilhelm, W. E. 2001. A technical review of column generation in integer
programming. Optim. and Engrg. 2 159–200.
Wolsey, L. A. 1998. Integer Programming. John Wiley and Sons,
Chichester, UK.