European Journal of Operational Research xxx (2014) xxx–xxx

Contents lists available at ScienceDirect

European Journal of Operational Research
journal homepage: www.elsevier.com/locate/ejor

Discrete Optimization

Row-reduced column generation for degenerate master problems
Jacques Desrosiers a,⇑, Jean Bertrand Gauthier a, Marco E. Lübbecke bab

GERAD & HEC Montréal, 3000, Chemin de la Côte-Sainte-Catherine, Montréal, Québec H3T 2A7, Canada
RWTH Aachen University, Chair of Operations Research, Kackertstraße 7, D-52072 Aachen, Germanya r t i c l e

i n f oArticle history:
Received 9 February 2013
Accepted 7 December 2013
Available online xxxx
Keywords:
Column generation
Degeneracy
Dynamic row-reductiona b s t r a c t
Column generation for solving linear programs with a huge number of variables alternates between solving a master problem and a pricing subproblem to add variables to the master problem as needed. The
method is known to often suffer from degeneracy in the master problem. Inspired by recent advancesin coping with degeneracy in the primal simplex method, we propose a row-reduced column generation
method that may take advantage of degenerate solutions. The idea is to reduce the number of constraints
to the number of strictly positive basic variables in the current master problem solution. The advantage ofthis row-reduction is a smaller working basis, and thus a faster re-optimization of the master problem.
This comes at the expense of a more involved pricing subproblem, itself eventually solved by column
generation, that needs to generate weighted subsets of variables that are said compatible with the
row-reduction, if possible. Such a subset of variables gives rise to a strict improvement in the objectivefunction value if the weighted combination of the reduced costs is negative. We thus state, as aby-product, a necessary and sufﬁcient optimality condition for linear programming.
This methodological paper generalizes the improved primal simplex and dynamic constraints aggregation
methods. On highly degenerate linear programs, recent computational experiments with these twoalgorithms show that the row-reduction of a problem might have a large impact on the solution time.
We conclude with a few algorithmic and implementation issues.
Ó 2013 Elsevier B.V. All rights reserved.

1. Introduction
Column generation, invented to solve large-scale linear programs (LPs), is particularly successful in the context of branchand-price (Barnhart, Johnson, Nemhauser, Savelsbergh, & Vance,
1998; Lübbecke & Desrosiers, 2005) for solving well-structured
integer programs. Column generation is used to solve the LP relaxations at each node of a search tree, and often produces strong dualbounds. It alternates between solving a restricted master problem(an LP) and one or several subproblems (usually integer programs)
in order to dynamically add new variables to the model. Like theprimal simplex method, column generation suffers from degeneracy. This defect is particularly visible when solving LP relaxationsof combinatorial optimization problems, a main application areaof branch-and-price.
In this methodological paper, we present a row-reduced column
generation (RrCG) method which turns degeneracy into a potential
advantage. Our method differs from standard column generation
only in iterations where degeneracy occurs in the restricted masterproblem (RMP). We dynamically partition the RMP constraints⇑ Corresponding author. Tel.: +1 514 340 6505; fax: +1 514 340 5634.
E-mail addresses: jacques.desrosiers@hec.ca (J. Desrosiers), jean-bertrand.
gauthier@hec.ca (J.B. Gauthier), marco.luebbecke@rwth-aachen.de (M.E. Lübbecke).

based on the numerical values of the current basic variables. The
idea is to keep only those constraints in the RMP that correspondto strictly positive basic variables. This leads to a row-reduced
restricted master problem which does not only discard most variables from consideration in column generation, but also reduces
the number of constraints, and in particular the size of the current
working basis. In linear algebra terms, we work with a projection
into the subspace spanned by the column-vectors of the nondegenerate variables. This is similar to the idea of a deﬁcient basis
in the simplex method (Pan, 1998). This row reduction comes atthe expense of a computationally more involved pricing subproblem which needs itself to be solved by column generation.
Degeneracy in column generation has been dealt with using
perturbation of the right-hand side as in the standard primal
simplex method. In particular, certain dual variable stabilization
approaches explicitly use perturbation, see Ben Amor, Desrosiers,and Frangioni (2009) for a stabilized column generation frameworkand the many references therein. Recently, a new line of research
emerged for coping with primal degeneracy in linear programming, namely the improved primal simplex method (IPS) (Elhallaoui, Metrane, Desaulniers, & Soumis, 2010; Raymond, Soumis, &Orban, 2010). Our work generalizes IPS for solving degeneratelinear programs and the dynamic constraints aggregation method(Elhallaoui, Desaulniers, Metrane, & Soumis, 2008; Elhallaoui,

0377-2217/$ - see front matter Ó 2013 Elsevier B.V. All rights reserved.
http://dx.doi.org/10.1016/j.ejor.2013.12.016

Please cite this article in press as: Desrosiers, J., et al. Row-reduced column generation for degenerate master problems. European Journal of Operational
Research (2014), http://dx.doi.org/10.1016/j.ejor.2013.12.016

2

J. Desrosiers et al. / European Journal of Operational Research xxx (2014) xxx–xxx

Villeneuve, Soumis, & Desaulniers, 2005; Elhallaoui, Metrane,
Soumis, & Desaulniers, 2010) for solving LP relaxations of set partitioning problems (by column generation) stemming from vehicle
routing and crew scheduling applications. The referenced papers
suggest that, on highly degenerate linear programs, a row-reduction of a problem shows great promise in reducing overall solution
times.
The paper is organized as follows. Section 2 recalls the column
generation method with the deﬁnitions of the master problem MP,
its variable-restricted version RMP and its pricing subproblem SP.
Section 3 presents the RrCG approach. It essentially deﬁnes therow and column partitions of the master problem based on a current degenerate solution, introduces the row-reduced restricted
master problem RrRMP and its associated pricing subproblem rSP,
and ﬁnally brings in a specialized column generator cSP for single
columns compatible with the row-reduced master problem. Section 3.4 discusses the case of inequality constraints followed byan algorithm. Section 3.6 provides a necessary and sufﬁcient
optimality condition for linear programs. Finally, Section 4 discusses some properties followed by implementation issues. Our
conclusions complete the paper in Section 5.

2. Column generation
Let us brieﬂy recall the mechanism of standard column generation, see Lübbecke and Desrosiers (2005) for a general introduction. We would like to solve the following linear program, called
the master problem (MP), with a prohibitively large number ofvariables k 2 RnþzH
min c| k
MP :¼
s:t:

Ak

¼

b

k

P 0;

½p

ð1Þ

where A 2 Rm  Rn ; c 2 Rn , and b 2 Rm . The corresponding dual
variables p 2 Rm are listed in brackets. We assume that k includes
m non-negative artiﬁcial variables, hence A is of full row rank,
and MP is feasible if b P 0. In applications, every coefﬁcient column
a of A encodes a combinatorial object x 2 X like a path, permutation,set, or multi-set. To stress this fact, we write a ¼ aðxÞ and c ¼ cðxÞfor its cost coefﬁcient. Column generation works with a restricted
master problem (RMP) which involves a small subset of variables
only. At each iteration, RMP is solved to optimality ﬁrst. Then, likein the primal simplex algorithm, we look for a non-basic variable
to price out and enter the current basis. That is, we either ﬁnd a column aðxÞ of cost cðxÞ with a negative reduced cost cðxÞ or need toprove that no such variable exists. This is accomplished by solving
the pricing subproblem (SP)|cH
SP :¼ minfcðxÞ  p aðxÞg:
x2X

ð2Þ

If cHSP P 0, no negative reduced cost columns exist and the current solution k of RMP (embedded into Rnþ ) optimally solves MP (1)as well. Otherwise, a minimizer of SP (2) gives rise to a variable tobe added to RMP, and we iterate.
Functions cðxÞ and aðxÞ may be linear functions, as in a DantzigWolfe reformulation of a linear program (Dantzig & Wolfe, 1960),
but cðxÞ is typically non-linear in many practical applications suchas in rich vehicle routing and crew scheduling (Desaulniers et al.,1998). Functions aðxÞ are also non-linear when Chvátal-Gomory
cuts are derived from the master problem variables, see Desaulniers, Desrosiers, and Spoorendonk (2011). Non-linearities may
increase the difﬁculty in solving SP, but it always ends up in ascalar cost cj and a vector aj of scalar coefﬁcients for each variable
kj in MP, j 2 f1; . . . ; ng.

2.1. Notation
Vectors are written in bold face. We denote by Ik the k  k identity matrix and by 0 (resp. 1) a vector/matrix with all zero (resp.
one) entries of appropriate contextual dimensions. For subsets
I # f1; . . . ; mg of row-indices and subsets J # f1; . . . ; ng of columnindices we denote by AIJ the sub-matrix of A containing the rows
and columns indexed by I and J, respectively. We further use standard linear programming notation like AJ kJ , the subset of columnsof A which are indexed by J multiplied by the corresponding
sub-vector of variables kJ . There is one notable exception: The set
N will not denote the non-basis (but usually a superset). Even
though one never actually computes the inverse of a basis matrix,
our exposition will sometimes rely on‘‘tableau data,’’ when it isconceptually more convenient.
3. Row-reduced column generation
RMP is a column-reduced MP and its variables are generated asneeded by solving SP. The row-reduced column generation comes
into play when the current solution of RMP is degenerate withp < m positive variables. In what follows, we deﬁne a row-reduced
RMP, denoted RrRMP, which decreases the number of rows to only
p. The case with equality constraints is treated ﬁrst as formulatedin (1), and a generalization to the inequality-constrained case ispresented in Section 3.4.
3.1. Row and column partitions
Let k be a feasible solution to MP, with the index set
F  f1; . . . ; ng of variables at strictly positive value, that is, kF > 0.
These variables are free to increase or decrease relatively to theircurrent values. All other possibly present variables assume a nullvalue, that is, kN ¼ 0 for N :¼ f1; . . . ; ng n F. We assume that k isdegenerate in the sense that the number of positive variables isless than the number of rows of MP, i.e., jFj ¼ p < m. The columnsof AF are required to be linearly independent, which is no restriction when k is computed with a simplex algorithm. This assumption allows us to construct a basis matrix AB for MP representing
the solution k in the following way. Identify a subset
P  f1; . . . ; mg of p linearly independent rows of AF and ‘‘ﬁll up’’with m  p unit columns to provide for artiﬁcial basic variablesin the rows indexed by Z :¼ f1; . . . ; mg n P. More precisely, thisyields the following form


AB ¼

APF

0

AZF

Imp


:

ð3Þ

One way to accomplish this form is to initialize the RMP withcolumns AF and m artiﬁcial variables and apply a phase I of the primal simplex algorithm. The above construction induces row andcolumn partitions, and MP (and the corresponding vector of dual
variables p) reads aszH
min c|F kF
MP :¼

þ c|N kN

s:t:

APF kFþ APN kN

¼

bP

½pP 

AZF kFþ AZN kN

¼

bZ

½pZ 

kF ;

kN

ð4Þ

P 0:

The inverse of the above basis matrix (3) has a particularly easy
form,

"
A1
B ¼

A1
PF

0

AZF A1
PF

Imp

#
:

ð5Þ

If we left-multiply (4) by A1
B , we obtain the equivalent ‘‘tableau
data’’ formulation

Please cite this article in press as: Desrosiers, J., et al. Row-reduced column generation for degenerate master problems. European Journal of Operational
Research (2014), http://dx.doi.org/10.1016/j.ejor.2013.12.016

3

J. Desrosiers et al. / European Journal of Operational Research xxx (2014) xxx–xxx

zH
min c|F kF
MP :¼

þ c|N kN

s:t:kF

þ APN kN
AZN kNkF ;kN

pricing problem rSP in terms of kN , the current vector of nullvariables:

P
b
0

¼
¼

cH
min ~c|N kN
rSP :¼

P 0;

s:t:

1
where APN ¼ A1PF APN and AZN ¼ AZN  AZF APF APN . We can see that our

choice of basis reveals that our row partition reﬂects the degenerate
 > 0g and Z ¼ fijb
 ¼ 0g.
solution in the tableau form, where P ¼ fijbii
 P ; 0Þ is a degenerate basic solution to MP whereIndeed, ðkF ; kN Þ ¼ ðb
1
kF ¼ A1
PF bP is computed using the smaller working basis APF , a p  pmatrix. Finally, observe that there is no need to left-multiply thesystem of constraints in row-set P by A1
PF . Hence, MP can be expressed as follows:zH
min c|F kF
MP :¼
s:t:

c|N kNþ

APF kFþ APN kN

¼

bP

½wP 

AZN kN

¼

0

½wZ 

kN

P 0;

kF ;

ð6Þ

where the new dual vector w is given by"½w|P ; w|Z  ¼ ½

|
P;

|
Z

p p

Ip

0

AZF A1
PF

Imp

#
|
¼ ½p|P þ p|Z AZF A1
PF ; pZ :

ð7Þ

1| kN

¼

1

½l

AZN kN

¼

0

½wZ 

kN

P 0:

ð11Þ

We have assumed (1) to be feasible which means that it either
has a ﬁnite optimal value or is unbounded. In both scenarios, thepricing problem (11) and its dual are always feasible and bounded.
Indeed, in a context of column generation, it is always possible togenerate a basic variable of reduced cost 0. With respect to the unbounded case, the detection of this eventuality is done during thestep size stage according to the ratio-test mechanism as stated in
the following section.
The reader who is more accustomed to IPS will remember thatthe basic variables are not available for pricing. That being said,
one could modify the convexity constraint with a less-than-orequal-to sign. The repercussion in (10) is the added upper boundof l 6 0. For all intent and purposes, this is equivalent to having
an artiﬁcial column of null content priced at 0 that could be selected in the pricing problem when the current solution is
optimal.

Pricing subproblem SP now equivalently writes as

cH
SP :¼



Z ðxÞ :min cðxÞ  w|P aP ðxÞ  w|Z a
x2X

ð8Þ

We emphasize that the basis we constructed for MP is not unique. The form we propose has convenient properties, but even
there it is our choice which rows appear in P, see Section 4.1.
3.2. The row-reduced master and the pricing subproblem
To exploit the degeneracy of the solution exhibited in (6), we
row-reduce the RMP, denoted by RrRMP. To this end, we discard
the rows in set Z:

c|F kFþþ APN kN ¼ bP ½wP 

kF ;kN P 0:zH
min
RrRMP :¼
s:t: APF kF

c|N kNð9Þ

Solution ðkF ; kN Þ is optimal for MP (6) if no negative reduced costcolumns exist, that is, if cH
SP P 0, or equivalently, if cN P 0. From (6)or (9), it holds that w|P ¼ c|F A1.
However,thevalueof dual vector wZPF
is not known. Consequently, we cannot solve the pricing subproblem SP as expressed in (8), and we need to come up with analternative.
c|N :¼ c|N  w|P APN
Compute the partial reduced cost vector ~
|
| 1
cN in
¼ cN  cF APF APN and write the current reduced cost vector (6) in terms of the unknown vector wZ of dual variables:
c|N  w|Z AZN . To verify the non-negativity of cN , one can ﬁndc|N ¼ ~
the minimum value of its components by solving
maxfljl 6 cj ; 8j 2 Ng, i.e., by solving the following pricing subproblem rSP over l and the unknown vector wZcH
maxrSP :¼
s:t:l
1l þ A|ZN wZ 6 ~cN ½kN ;

ð10Þ

where kN P 0 acts as the dual variable vector. In other words, given
only the non-degenerate variables kF > 0 of cost cF and the associated columns in AF from which we derive the row-partition, we
compute the dual vector wP and check whether any vector wZ exists
such that l < 0 (to generate a column with negative reduced cost to
be added to problem RrRMP) or to otherwise prove the optimality ofkF for RrRMP and hence for MP (see Theorem 1 for this necessary
and sufﬁcient optimality condition). The dual of (10) deﬁnes the

3.3. Solving the pricing step
An optimal solution kH
N to (11) may contain a single variableZj ¼ 0, or more generally, a convex
for which a
combination of several positive variables such that AZN kH
N ¼ 0.
In the pricing step, we consider two subproblems: rSP as deﬁned by (11) for the general case and a specialized one denotedcSP and used ﬁrst to generate an optimal solution comprising asingle variable, if any. Subproblem cSP exploits the following
property:kH
j ¼ 1; j 2 N,

Deﬁnition 1. Given the solution vector kF > 0 of positive variables, aP
vector a ¼
is called compatible with row-set P if and only ifaZZ :¼ aZ  AZF A1a
PF aP ¼ 0.
 Z ¼ 0 and so are the column-vecVector b is compatible since b
tors of AF . When appropriate, we also say that a variable associatedwith a compatible column is compatible. The artiﬁcial basic variables we selected are incompatible. More generally, degenerate basic variables are incompatible. The interest in compatibility comesfrom the fact that a compatible column aj with negative reduced
cost cj yields a non-degenerate pivot. Indeed, the step size givenby the ratio-test is computed only on the row-set P, that is,nobi > 0; 8i 2 P, then q > 0 and > 0 . Because b
q ¼ min
ja
j

i2P

ij
a

ij

i

j

the objective of MP strictly improves by qj cj < 0, unless
ij 6 0; 8i 2 P, in which case MP is unbounded.
aOn the one hand, if we restrict our attention to only generatingcompatible columns (which is a natural idea in our context), matters can sometimes simplify considerably as there is no need toknow wZ . Given the dual vector w|P ¼ c|F A1
PF retrieved from the solution of RrRMP (9), we deﬁne a specialized subproblem cSP which isthe pricing subproblem SP (8) augmented with a set of linear
constraints imposing compatibility with the row-reduced masterproblem for solution-column aðxÞ, that is,

n
o
1
| 1
cH
cSP :¼ min cðxÞ  cF APF aP ðxÞjaZ ðxÞ  AZF APF aP ðxÞ ¼ 0 :
x2X

ð12Þ

Adding the set of constraints aZ ðxÞ  AZF A1
PF aP ðxÞ ¼ 0 may
destroy the structure of the subproblem and makes it more difﬁcult to solve in some cases. Anyhow, if a non-basic compatible

Please cite this article in press as: Desrosiers, J., et al. Row-reduced column generation for degenerate master problems. European Journal of Operational
Research (2014), http://dx.doi.org/10.1016/j.ejor.2013.12.016

4

J. Desrosiers et al. / European Journal of Operational Research xxx (2014) xxx–xxx

column aj ; j 2 N, with cj ¼ cH
cSP < 0 is generated from the solutionof (12), one updates the current solution as:

kj ¼ qj

8k 2 N n fjg

kk ¼ 0P  q a
kF ¼ bj Pj

jSj ¼ s and denote by Z :¼ f1; . . . ; mg n ðF [ SÞ the set of remaining
rows. The basis can be written in terms of kF > 0, the slack variables dS > 0, and again artiﬁcial variables for the m  p  s remaining constraints. Basis AB and its inverse write asð13Þ P þ q cH :zRrRMP ¼ cF b
j cSP
The number of positive variables in the new solution is at mostp, that is, it can be more degenerate.
On the other hand, we can solve rSP (11) to look for a convex
combination of columns to improve the objective value of MP. Subproblem rSP is a linear program solved by column generation over
1
X. In its pricing step, we look for a column with a reducedaZ ðxÞ
|Z ðxÞ of negative value, wherecost cðxÞ ¼ l þ ~cðxÞ  wZ a|
Z ðxÞ :¼ aZ ðxÞ  AZF A1~cðxÞ :¼ cðxÞ  w|P aP ðxÞ and a
PF aP ðxÞ. Given wP ¼
c|F A1
PF obtained from the solution of RrRMP (9) together with land wZ retrieved from the current solution of (11), the pricing
subproblem for generating variables as needed for solving rSP isgiven byno|cH :¼ l þ min cðxÞ  c|F A1
PF aP ðxÞ  wZ aZ ðxÞ
x2X
n
o
1
|
|
¼ l þ min cðxÞ  ðc|F A1
PF  wZ AZF APF ÞaP ðxÞ  wZ aZ ðxÞ :

ð14Þ

x2X

Upon left-multiplication by the inverse, the transformed masterproblem becomes:zH
min c|F kF
MP :¼

þ c|N kN

s:t:

þ APN kN

kF
dS
kF ;

Subproblem rSP (11) combines variables in N such that AZN kH
N ¼ 0.
H
Hence, vector AN kH
N (of reduced cost value c rSP ) is compatible withrow-set P. Given kH
N , the updated values are computed according
to RrRMP (9) as

ð15Þ

N

3.4. Inequality constraints
Consider the following linear master problem MP withinequalities:|zH
s:t: Ak P b;
MP :¼ min c k

k P 0:

ð16Þ

Introducing a vector of surplus variables d 2 Rm
þ , one obtains MP
in standard form:|zH
s:t: Ak  d ¼ b;
MP :¼ min c kk; d P 0:

ð17Þ

The case with less-than-or-equal-to constraints Ak 6 b can betreated in a similar way by considering the transformation
Ak P b. When the current basic solution to (16) with vectorof positive variables kF > 0 is such that AF kF – b, the basis also contains some vector of surplus variables dS > 0, for S  f1; . . . ; mg. Let

dP ;

dZ

¼

0

dZ

P 0:

þ c|N kN
þ APN kN

P bP

½wP 

ASF kFþ ASN kN

P bS

½wS 

kF P 0;

ð19Þ

kN P 0;where wP P 0 and wS P 0. Current (known) dual values are|
w|P ¼ c|F A1
PF and wS ¼ 0. Therefore, subproblem cSP for generatingcompatible variables is given by (12) and it only depends on the column-vectors AF of the positive variables kF > 0. Subproblem rSP,
again written in terms of the current null variable vectors kN ; dP ,and dZ , becomes:

s:t:

|

1 kN
kN ;

The
numberofpositivevariables
is
at
most
p þ ðm  p þ 1Þ  1 ¼ m and the new solution could be less as well
as more degenerate.
Finally, several compatible columns can be retrieved from thepricing problem cSP and added simultaneously to (9). Moreover,the positive variables of kH
N solution of rSP can be entered one by
one in RMP (1), in any order, see Elhallaoui, Metrane, Desaulniers, et al. (2010): the last variable entered ensures a nondegenerate pivot because the convex combination AN kH
N iscompatible.



kN ;

zH
min c|F kF
RrRMP :¼
s:t: APF kF

AZN kN P þ qcH :zRrRMP ¼ cF brSP

AZN kN

From (18), we can derive RrRMP, cSP, and rSP. The row-reduced
master problem with p þ s constraints is obtained by discardingrow-set Z from the formulation while keeping the original data
matrices and inequality constraints:zH
min ~c|N kN
rSP :¼

kN ¼ qkHN P  qAPN kH
kF ¼ b¼

ASF A1PF dP
AZF A1
PF dP

ð18Þ

Apart from the constant term l, (14) is the usual subproblem SP(2) with dual vector
1||
ðp|P ; p|Z Þ ¼ ðc|F A1
PF  wZ AZF APF ; wZ Þ:þ ASN kN

dS ;

¼

P
b
S
b

 A1
PF dP

þ c|F A1
PF dP
þ 1| d PAZF A1
PF dP
dP ;þ 1| dZ

¼

1

½l

 dZ

¼

0

½wZ 

dZ

P 0:
ð20Þ

It is solved by column generation except that the dP and dZ variables need not be generated. Therefore, (14) can be used to priceout the valuable columns of kN . Its solution is a convex combination of the variables in kN ; dP and dZ such that1 H
H
AZN kHN  AZF APF dP  dZ ¼ 0.
3.5. An RrCG algorithm
We summarize our discussion with a pseudo-code of our
row-reduced column generation algorithm for degenerate masterproblems. As long as the solution is non-degenerate, we have theclassical alternation between RMP and SP (until line 9). When adegenerate solution is identiﬁed in line 10 (p < m), the rowreduced RrRMP beneﬁts from this (lines 11 to 19).
After solving RMP (line 4) or RrRMP (line 13), the optimality testfor MP is via the solution of a pricing subproblem, either the classical SP (line 8) if the current solution is non-degenerate or rSP
which is solved by column generation (line 17). In both situations,H
new columns are added to RMP if cH
SP < 0 or crSP < 0, otherwise MP
is optimal.
If the current RMP solution is degenerate in line 10, row-index
sets P and Z are deﬁned/updated (line 11), and the RrRMP is built
and solved (line 13). In that case, priority can be given to the specialized pricing subproblem cSP (line 14) and, if cH
cSP < 0, compatible columns are added to RrRMP (line 15). Otherwise, the pricing

Please cite this article in press as: Desrosiers, J., et al. Row-reduced column generation for degenerate master problems. European Journal of Operational
Research (2014), http://dx.doi.org/10.1016/j.ejor.2013.12.016

J. Desrosiers et al. / European Journal of Operational Research xxx (2014) xxx–xxx

subproblem rSP needs to be solved by column generation (line 17).
If cHrSP < 0 in line 18, we add subsets of incompatible columns to
RMP and iterate (again from line 4). The algorithm stops when
RMP and hence MP are optimal (line 19).
Algorithm 1.

5enters the basis of RrRMP, a non-degenerate pivot occurs (unlessPj 6 0 in which case MP is unbounded), and the objective functionaimproves by qj cH
rSP < 0.
More generally, if kH
N contains several positive variables, thep-dimensional vector APN kH
N can enter the basis of RrRMP as aH
i Þi2P :¼ APN kH
single column. Let ða
N . Because AZN kN ¼ 0, its reduced~| H Hc|N kH
cost is computed as 
N ¼ cN kN ¼ crSP < 0. Unless all components
i Þi2P are non-positive, it strictly improves the objectiveof vector ða
function value by qcH
< 0 when added to RrRMP, where
n
o rSP
bi 
q ¼ mini2P ai jai > 0 . This contradicts the optimality of ðkF ; kN Þ
and completes the proof.

h4. Some properties and implementation issues
4.1. Selection of a working basis APF

3.6. A characterization of LP optimality
Column generation generalizes the primal simplex algorithm. In
the same spirit, the improved primal simplex method (IPS) used forsolving degenerate linear programs (Elhallaoui, Metrane, Desaulniers, et al., 2010; Raymond et al., 2010) can be seen as a special
case of the row-reduced column generation RrCG. The main difference is that rSP (11) itself needs to be solved by column generation,
whereas in IPS all columns are explicitly given in advance. Moreover, given basis AB , all variables can be characterized a priori as
either compatible or incompatible. Hence, in IPS, the row-reduced
master problem is deﬁned on the compatible variables and acomplementary pricing subproblem is solved over the incompatible
variables only. Although not explicitly stated in previous IPS
papers, the following result is a direct consequence of the pricing
subproblem structure.
Theorem 1. A feasible solution ðkF > 0; kN ¼ 0Þ, jFj 6 m, is optimalfor the linear program (1) if and only if there exists some dual vector
wZ such that cH
rSP P 0, rSP being deﬁned by (11).
Proof. For necessity, recall that MP (1) is equivalent to MP (6).
Firstly, kF ¼ A1PF bP and kN ¼ 0 is primal feasible for MP (6). Secc|F ¼ 0, i.e., w|P ¼ cF A1
ondly, kF being basic, PF . If there exists a dual|c|N ¼ c|N  c|F A1
vector wZ such that 
PF APN  wZ AZN P 0, the reduced|
costs of all variables are non-negative and ðc|F A1
PF ; wZ Þ is dual feasi
ble for MP (6). Thirdly, since kN ¼ 0 and bZ ¼ 0, primal objectivefunction c|F kF is equal to the dual objective function w|P bP . Therefore½kF ; kN  is optimal.
To show sufﬁciency, let ½kF ; kN  be an optimal solution andassume cH< 0. With the row-partition induced by basis AB , vector
 rSP H

H
H
H
AN kH
N ¼ APN kN AZN kN . Because vector AZN kN ¼ 0 in (11), AN kN is
H
compatible. If kN contains a single variable kH
¼
1;
j
2
N,
then
j
Zj ¼ 0, vector aj is compatible, and cj ¼ ~cj ¼ cH
arSP < 0. The pdimensional column aPj , and the associated variable kj in MP

Given the current solution ðkF ; kN Þ to RMP, the p  p working basis APF is a matrix containing p linearly independent rows of AF , notuniquely deﬁned if p < m. Matrix APF does not only characterize therow-partition of the constraints of RrRMP, rSP and cSP, but also, for
j 2 N, the partial reduced costs coefﬁcients ~cj ¼ cj  c|F A1
PF aPj , andj , that is, aPj ¼ A1
column components of aand
PF aPjZj ¼ aZj  A1a
PF aPj . However, we show by a linear algebra argument
that, for any set of p linearly independent rows of AF , the pricing
subproblem holds the same information based on AF and thus provides the same solution set. That is, the latter is independent of therow-partition induced by the selected working basis APF . This
comes from the fact that only compatible columns belong to thevector space spanned by AF .
Proposition 1. Given the solution vector kF > 0 of positive variables,
vector a is compatible with the row-set P if and only if it belongs to thevector space spanned by AF .

Proof. Assume vector a ¼ AF y, that is, it can be written as a linear


 
APF
aP
combination of the columns of AF , or equivalently,
y¼
.
AZF
aZ
Since APF is invertible, one obtains y ¼ A1PF aP from the ﬁrst set of
constraints. Substituting in the second set, we have AZF A1
PF aP ¼ aZ
which means that a is compatible by Deﬁnition 1. To show the converse, let a be compatible with with the row-set P, that is,1
Z :¼ aZ  AZF A1a
PF aP ¼ 0, where aP :¼ APF aP . Hence, aZ ¼ AZF aP andaP ¼ APF aP , or equivalently, a ¼ AF aP . Hence a belongs to the vector
space spanned by AF . h
This has a nice interpretation in set partitioning models that arecommon in vehicle routing, crew scheduling, and many otherapplications. Given an integer solution, AF forms a set of p groupsof rows. Hence, compatible columns are those combining thesegroups (and APF is the identity matrix Ip ). For a fractional solution,
the p independent rows of APF can be chosen as follows: keep one
row from each group of identical rows of APF . Again this forms a setof p groups of rows, and the same compatibility interpretation
applies. This is what is being used in the dynamic constraints
aggregation method (Elhallaoui et al., 2005; Elhallaoui et al.,2008; Elhallaoui, Metrane, Soumis, et al., 2010; Benchimol,
Desaulniers, & Desrosiers, 2012). Furthermore, the convex combination of incompatible variables in (11) simply expresses thefundamental exchange mechanism of set partitioning solutions,that is, removing elements from some groups to insert them backin other groups.
Another interpretation can be given in the context of the minimum cost ﬂow problem with non-negative ﬂow variables, see

Please cite this article in press as: Desrosiers, J., et al. Row-reduced column generation for degenerate master problems. European Journal of Operational
Research (2014), http://dx.doi.org/10.1016/j.ejor.2013.12.016

6

J. Desrosiers et al. / European Journal of Operational Research xxx (2014) xxx–xxx

Ahuja, Magnanti, and Orlin (1993). Any feasible ﬂow can be represented (in the residual network) as a collection of positive arcs (thenon-degenerate arcs forming a forest) and all other arcs at zero(the degenerate ones). The column-vectors of the positive arcs
form AF . A degenerate arc is compatible if and only if it can be written in terms of the unique subset of positive arcs forming a cyclewith it. Fig. 1 represents the residual network in which the ﬂow
on the non-degenerate (positive) arcs is free to go in both directions while the degenerate arcs are at zero. Arc (8,9) can be written
in terms of the free arcs (9,10), (11,10) and (11,8), hence the corresponding variable x8;9 is compatible. An incompatible arc must link
two trees of the forest. The combination of several incompatible
arcs together with a selection of free arcs can form a cycle. In
Fig. 1 are two incompatible arcs. However, combined with free arcs
(9,10), (11,10), (5,1) and (1,6), they form a cycle, hence the sum
x6;9 þ x5;11 of these two incompatible variables is compatible aswell as their convex combination with an equal weight of one-halfon each. Now observe the row partition derived from that network
ﬂow example. In the small tree composed of free arcs (1,5) and(1,6), two independent ﬂow conservation constraints need to be
selected to be part of set P, hence any one amongst nodes 1, 5 or
6 appears in set Z. This is the same mechanism for the larger treecomposed of the ﬁve arcs (2,11), (2,7), (11,10), (11,8), and (9,10):
any one amongst nodes 2, 7, 11, 10, 8 or 9 is selected to be partof set Z while the remaining four ﬂow conservation constraints
are in the set of independent rows of P. This leads us to thefollowing two propositions regarding the choice of the working
basis.
Consider two different working bases APF and AQF , where Q provides an alternative set of p linearly independent rows of AF . The
reduced costs of the positive basic variables are zero, hence independent of the selected working basis. However, their column
coefﬁcients in RrRMP (9) are different since they are given by thecolumn coefﬁcients of the selected working basis. For cSP, Proposition 2 shows that the reduced costs of the compatible variables areindeed identical in the two subproblem versions, namely cSPP andcSPQ and their coefﬁcient components are equivalent. Therefore
cSP, the specialized pricing subproblem for generating compatible
variables, is independent of the selected working basis. The proof ispresented in Appendix A.
Proposition 2. Given two working bases APF and AQF of AF , thecorresponding pricing subproblems cSPP and cSPQ are equivalent
programs.

Fig. 1. Compatible and incompatible arcs in a minimum cost ﬂow problem.

Although the reduced cost coefﬁcients and column components
of incompatible variables in rSP (11) clearly depend on the selectedworking basis, say either APF or AQF , Proposition 3 shows that thesolution set of the corresponding pricing subproblems rSPP andrSPQ is the same as well as the values of their optimal objectivefunctions. Hence they are equivalent programs. Again the proof ispostponed to Appendix A.
Proposition 3. Given two working bases APF and AQF of AF , thecorresponding pricing subproblems rSPP and rSPQ are equivalent
programs.
Regarding the interpretations in set partitioning models andminimum cost ﬂow problems, we have the following. In the ﬁrst
case, for both integer or fractional solutions, each group iscomposed of identical rows in AF , hence a single one per group isselected to appear in row-set P. The choice is therefore irrelevant.
In the second case, each tree t of the forest contains nt nodes andnt  1 free arcs. One (root) node per tree has to be removed andits ﬂow conservation constraint appears in row-set Z. The choiceof a root node per tree of the forest, currently nodes 1 and 2 inFig. 1, does not change the composition of any cycle nor its costor reduced cost.
4.2. Flexibility in an implementation
A consequence of the necessary and sufﬁcient optimality condition of Theorem 1 is that the role of RrRMP could be relegated toonly updating the current feasible solution, see (15). Indeed, there
is no need to keep the generated columns, except those comprisedin the current solution. Pricing problem rSP is sufﬁcient to prove
optimality of the solution or to provide a convex combination ofcolumns for a strict improvement of the objective function. However in practice, several subsets of columns are selected at every
iteration, either from cSP or from rSP, and sent to RrRMP or to
RMP for an improvement of the current solution, by solving a linear
program. This is possible because the compatibility notion is somewhat ﬂexible. For example, one can include or not in the set ofdegenerate variables a variable that is at an implicit upper bound.
In set partitioning models, this is the case for variables at valueone.
Deﬁnition 2. Given the solution vector kF > 0 of non-degeneratevariables, vector a is compatible with row-set Q # P if and only if
Z ¼ 0 for Z :¼ f1; . . . ; mg n Q .
aThis row-compatibility induces a two-step pivot procedure to
enforce a strict improvement of the current solution. Firstly, a selected row-set Q # P for RrRMP (still of row-size p 6 m) constrains
the set of possible exiting variables from the current basis, the ratio-test being computed only for those jQ j :¼ q 6 p constraints.
Secondly, a specialized pricing subproblem cSP selects an enteringZj ¼ 0, this zero vector being
variable kj ; j 2 N, such that cj < 0 and adeﬁned on Z :¼ f1; . . . ; mg n Q according to the row-compatibility
in use. This supports various implementation strategies. For example, one could temporarily restrain the search for entering
variables to those for which Q is a strict subset of P and, for all
i are relatively large. This can be considered as a partial
i 2 Q; bpricing strategy and should accelerate the solution of RrRMP since
only signiﬁcant step sizes are expected.
Alternatively, when the entering variable is compatible with thesolution kF , the pivot is non-degenerate but the new basic solution
may become degenerate, say kQ > 0; kNnQ ¼ 0, with Q # P. Then
one can update or not the current row-partition of RrRMP, namely
RrRMPP. If it is updated, it becomes RrRMPQ with only q rows andZ :¼ f1; . . . ; mg n Q . If not, it should be pointed out that this also
results in an exact algorithm as it still solves the transformed MP

Please cite this article in press as: Desrosiers, J., et al. Row-reduced column generation for degenerate master problems. European Journal of Operational
Research (2014), http://dx.doi.org/10.1016/j.ejor.2013.12.016

7

J. Desrosiers et al. / European Journal of Operational Research xxx (2014) xxx–xxx

formulation in (6). In that case, the current compatibility rule withrow-set P is simply maintained. No overhead computations areneeded for an update of RrRMPP and the entering variables are stillZj ¼ 0, where Z :¼ f1; . . . ; mg n P is a strictly
selected such that asmaller set of rows than what would be required in an updated
pricing subproblem. In that case, degenerate pivots may occur
because of the degeneracy of some RrRMPP solutions.

5. Summary and conclusions
Classical column generation works with a restricted masterproblem (RMP), that is, a subset of a model’s variables that are
dynamically added via a pricing subproblem SP. Like the simplex
method, column generation is known to suffer from degeneracy.
Inspired by recent successes in coping with degeneracy in the primal simplex method, we propose a row-reduced column generation
method (RrCG). RrCG exploits degeneracy as the restricted masterproblem only has as many rows as there are positive basic
variables.
Columns/variables are characterized as compatible or incompatible with respect to RrRMP. Compatible columns allow for astrict decrease of the objective function when entered into the basis, that is, a non-degenerate pivot. Two types of subproblems areproposed to generate variables: a specialized subproblem cSP for
compatible variables, and rSP to price out any type of variables.
The latter also needs to be solved by column generation. Pricing
subproblem cSP is the original subproblem SP augmented with aset of linear constraints imposing compatibility requirements. It
selects compatible columns as long as they are useful for nondegenerate pivots in RrRMP. When the reduced costs of all compatible columns are zero (or larger than a speciﬁed threshold), thepricing subproblem rSP is solved. It selects a convex combinationof columns such that, again, the objective value strictly improves
when they all enter into the current basis. In both cases, therow-size of RrRMP can be dynamically modiﬁed. The structure of
the pricing problem rSP allows to derive a necessary and sufﬁcient
optimality condition for linear programs.
Decomposition in column generation for integer programs isbased on the modeling structure of a compact formulation. It
exploits the pricing subproblem for the selection of objects x 2 X.
Row-partition in RrCG takes advantage of degenerate solutions,
reduces the row-size of the master problem and its associatedworking basis, and thus, the computational effort for re-optimization. Combining column generation and dynamic row-partition
during the solution process allows for exploiting both the modeling structure of its formulation and the algebraic structure of its
solutions. Two special cases of RrCG are the improved primal
simplex method and the dynamic constraints aggregation method
for solving by column generation LP relaxations of set partitioning
problems. On highly degenerate instances, recent computational
experiments with these algorithms have shown a substantial
impact on the solution time. This already opened the door tofurther research within that ﬁeld, notably an integral simplex
algorithm for the set partitioning problem (Zaghrouti, Soumis, &Elhallaoui, 2011) and a specialized version for the capacitatednetwork ﬂow problem which turns out to be strongly polynomial(Desrosiers, Jacques, Gauthier, Jean Bertrand, & Lübbecke, 2013).
Of course, only experimentation can show whether the potential speedup when re-optimizing the master problem is notovercompensated by a slowed down solution of the pricing step.
Specialized subproblem cSP may be more difﬁcult to solve thanrSP or the original SP, in particular when the latter is solved by acustomized algorithm. The additional constraints enforcing
compatibility in cSP may modify or even destroy the subproblem
structure. On the positive side, the subproblems do not automati-

cally inherit degeneracy from the master problem, since at least
part of the overrepresentation of the current basic solution isremoved from the pricing subproblem as well.
We expect that the new method is most helpful in cases where
re-optimization of the master problem is very difﬁcult, as it is thecase for many large-scale vehicle routing and crew schedulingproblems. As for any simplex or column generation algorithm,
future work is needed on RrCG, mainly on implementation
strategies. Amongst these are the moment for an update of therow-partition of RrRMP, efﬁcient solvers for cSP and rSP, which
pricing subproblem to call, whether to add many incompatible
columns or their (single column) convex combination as returned
from rSP, and much more on relaxed compatibility.
Acknowledgements
We would like to thank François Soumis from École Polytechnique de Montréal for giving us useful feedback on an earlier draftof this paper. This research has been supported by an NSERC(Canada) grant for the ﬁrst author.
Appendix A. Proofs
In this Appendix, we provide the proof of Proposition 3 followedby that of Proposition 2. Let us ﬁrst express rSP (11) in terms of thevariables kN , and as a function of the working basis APF and theoriginal cost and data coefﬁcients:

cH
min ðc|  c|F A1
PF AP ÞkNrSP :¼
s:t:

1| kN

¼

ðAZ  AZF A1
PF AP ÞkN
kN

¼ 0
P 0:

1

Consider another working basis deﬁned on row-set Q and
denoted AQF . It is again of dimension p  p and kF ¼ A1
QF bQ ¼ bQ .
Duplicate rows in set Q such that MP becomeszH
min c|F kF
MP :¼

þ c|N kN

s:t:

APF kFþ APN kN¼

bP

AZF kFþ AZN kN¼

bZ

AQF kFþ AQN kN

¼

bQ

kF ;

kN

P 0:

Given the vector of positive variables kF > 0, consider the following
two bases, the ﬁrst being deﬁned according to the working basis APF
while the second is given according to the working basis AQF :The corresponding inverses are given as follows:

Pricing subproblem rSP can now be written according to theselected basis, namely rSPP and rSPQ:cH
min ðc|  c|F A1
PF APN ÞkNrSPP :¼
s:t:

1| kN

¼

1

ðAZN  AZF A1
PF APN ÞkNðAQN  AQF A1
PF APN ÞkN

¼

0

¼

0

kN

P 0

ð21Þ

Please cite this article in press as: Desrosiers, J., et al. Row-reduced column generation for degenerate master problems. European Journal of Operational
Research (2014), http://dx.doi.org/10.1016/j.ejor.2013.12.016

8

J. Desrosiers et al. / European Journal of Operational Research xxx (2014) xxx–xxx

and

cH
rSPQ :¼

min ðcs:t:|Proof. The proof is similar to that of Proposition 3 except that vector kN is not involved. Multiplying the last set of constraints of (23)

 c|F A1QF AQN ÞkN

1| k N¼

1ðAZN  AZF A1
QF AQN ÞkN¼

0ðAPN  APF A1
QF AQN ÞkN

¼

0

kN

P 0:

by APF A1
QF , one obtains the corresponding constraint set of (24).

ð22Þ

Proposition 3. Given two working bases APF and AQF of AF , thecorresponding pricing subproblems rSPP and rSPQ are equivalent
programs.
Proof. We show that the solution set of rSPP and rSPQ is the sameand the value of their objective functions is equal for any optimal
convex combination kH
N . Left-multiplying the third set of constraints of (21) by APF A1
QF , one obtains the third set of constraintsof (22):
1
1
APF A1
QF ðAQN  AQF APF APN ÞkN ¼ ðAPN  APF AQF AQN ÞkN ¼ 0:

From the above equation, we have the identity APN kN ¼ APF A1
QF AQN kN .
Substituting for APN kN in the objective function and in the second
constraint set of (21), one completes the linear transformation ofrSPP into rSPQ:
1
| 1
| 1
|
|
ðc|  c|F A1
PF APN ÞkN ¼ c k  cF APF APF AQF AQN kN ¼ ðc  cF AQF AQN ÞkN

and
1
1
ðAZN  AZF A1
PF APN ÞkN ¼ AZN kN  AZF APF APF AQF AQN kN¼ ðAZN  AZF A1
QF AQN ÞkN :

We next show that the reduced costs of the compatible variables are indeed identical in the two versions of cSP, namely cSPP
and cSPQ and their coefﬁcient components are equivalent. Therefore cSP, the specialized pricing subproblem for generating compatible variables, is independent of the selected working basis.
We ﬁrst provide these two versions of cSP, adapted from (12):cH
min cðxÞ  c|F A1
PF aP ðxÞcSPP :¼
x2X

s:t:aZ ðxÞ  AZF A1
PF aP ðxÞ

¼ 0

aQ ðxÞ  AQF A1
PF aP ðxÞ

¼ 0

ð23Þ

and

cH
min cðxÞ  c|F A1
QF aQ ðxÞcSPQ :¼
x2X

s:t:aZ ðxÞ  AZF A1¼ 0
QF aQ ðxÞaP ðxÞ  APF A1
PF aQ ðxÞ

ð24Þ

¼ 0:

Proposition 2. Given two working bases APF and AQF of AF , thecorresponding pricing subproblems cSPP and cSPQ are equivalent
programs.

Since aP ðxÞ ¼ APF A1
PF aQ ðxÞ, it can be substituted in the objectivefunction and the ﬁrst set of constraints of (23). This shows thatcSPP and cSPQ are equivalent programs. hReferences
Ahuja, Ravindra K., Magnanti, Thomas L., & Orlin, James B. (1993). Network ﬂows:
Theory algorithms and applications. Prentice Hall.
Barnhart, Cynthia, Johnson, Ellis L., Nemhauser, George L., Savelsbergh, Martin W. P.,& Vance, Pamela H. (1998). Branch-and-price: Column generation for solving
huge integer programs. Operations Research, 46(3), 316–329. http://dx.doi.org/
10.1287/opre.46.3.316.
Ben Amor, Hatem M. T., Desrosiers, Jacques, & Frangioni, Antonio (2009). On the
choice of explicit stabilizing terms in column generation. Discrete Applied
Mathematics, 157(6), 1167–1184. http://dx.doi.org/10.1016/j.dam.2008.06.021.
Benchimol, Pascal, Desaulniers, Guy, & Desrosiers, Jacques (2012). Stabilized
dynamic constraint aggregation for solving set partitioning problems.
European Journal of Operational Research, 223(2), 360–371. http://dx.doi.org/
10.1016/j.ejor.2012.07.004.
Dantzig, George B., & Wolfe, Philip (1960). Decomposition principle for linear
programs. Operations Research, 8(1), 101–111. http://dx.doi.org/10.1287/
opre.8.1.101.
Desaulniers, Guy, Desrosiers, Jacques, Ioachim, Irina, Solomon, Marius M., Soumis,
François, & Villeneuve, Daniel (1998). A uniﬁed framework for deterministic
time constrained vehicle routing and crew scheduling problems. In T. G. Crainic& G. Laporte (Eds.), Fleet management and logistics (pp. 57–93). Kluwer. http://dx.doi.org/10.1007/978-1-4615-5755-5_3.
Desaulniers, Guy, Desrosiers, Jacques, & Spoorendonk, Simon (2011). Cutting planes
for branch-and-price algorithms. Networks, 53(4), 301–310. http://dx.doi.org/
10.1002/net.20471.
Desrosiers, Jacques, Gauthier, Jean Bertrand, & Lübbecke, Marco E. (2013). A
contraction-expansion algorithm for the capacitated minimum cost ﬂow
problem. Presentation at VeRoLog 2013, EURO working group on vehicle
routing and logistics optimization, Southampton, UK.
Elhallaoui, Issmail, Villeneuve, Daniel, Soumis, François, & Desaulniers, Guy (2005).
Dynamic aggregation of set partitioning constraints in column generation.
Operations Research, 53(4), 632–645. http://dx.doi.org/10.1287/opre.1050.0222.
Elhallaoui, Issmail, Desaulniers, Guy, Metrane, Abdelmoutalib, & Soumis, François(2008). Bi-dynamic constraint aggregation and subproblem reduction.
Computers & Operations Research, 35(5), 1713–1724. http://dx.doi.org/10.1016/
j.cor.2006.10.007.
Elhallaoui, Issmail, Metrane, Abdelmoutalib, Desaulniers, Guy, & Soumis, François(2010). An improved primal simplex algorithm for degenerate linear programs.
INFORMS Journal on Computing. http://dx.doi.org/10.1287/ijoc.1100.0425.
Elhallaoui, Issmail, Metrane, Abdelmoutalib, Soumis, François, & Desaulniers, Guy(2010). Multi-phase dynamic constraint aggregation for set partitioning typeproblems. Mathematical Programming, 123(2), 345–370. http://dx.doi.org/
10.1007/s10107-008-0254-5.
Lübbecke, Marco E., & Desrosiers, Jacques (2005). Selected topics in column
generation. Operations Research, 53(6), 1007–1023. http://dx.doi.org/10.1287/
opre.1050.0234.
Pan, Ping-Qi (1998). A basis deﬁciency-allowing variation of the simplex method forlinear programming. Computers & Mathematics with Applications, 36(3), 33–53.
http://dx.doi.org/10.1016/S0898-122(98)00127-8.
Raymond, Vincent, Soumis, François, & Orban, Dominique (2010). A new version of
the Improved Primal Simplex for degenerate linear programs. Computers &Operations Research, 37(1), 91–98. http://dx.doi.org/10.1016/j.cor.2009.03.020.
Zaghrouti, Abdelouahab, Soumis, François, & Elhallaoui, Issmail (2011). Integral
simplex using decomposition for the set partitioning problem. Technical report,
GERAD, Montréal, Canada.

Please cite this article in press as: Desrosiers, J., et al. Row-reduced column generation for degenerate master problems. European Journal of Operational
Research (2014), http://dx.doi.org/10.1016/j.ejor.2013.12.016