François Vanderbeck
email: fv@math.u-bordeaux1.fr

Branching in Branch-and-Price: a Generic Scheme

Keywords: Integer Programming, Dantzig-Wolfe reformulation, Branch-and-Price

Developing a branching scheme that is compatible with the column generation procedure can be challenging. Application specific and generic schemes have been proposed in the literature, but they have their drawbacks. One generic scheme is to implement standard branching in the space of the compact formulation to which the Dantzig-Wolfe reformulation was applied. However, in the presence of multiple identical subsystems, the mapping to the original variable space typically induces symmetries. An alternative, in an application specific context, can be to expand the compact formulation to offer a wider choice of branching variables. Other existing generic schemes for use in branch-and-price imply modifications to the pricing problem. This is a concern because the pricing oracle on which the method relies might become obsolete beyond the root node. This paper presents a generic branching scheme in which the pricing oracle of the root node remains of use after branching (assuming that the pricing oracle can handle bounds on the subproblem variables). The scheme does not require the use of an extended formulation of the original problem. It proceeds by recursively partitioning the subproblem solution set. Branching constraints are enforced in the pricing problem instead of being dualized via Lagrangian relaxation, and the pricing problem is solved by a limited number of calls to the pricing oracle. This generic scheme builds on previously proposed approaches and unifies them. We illustrate its use on the cutting stock and bin packing problems. This is the first branch-and-price algorithm capable of solving such problems to integrality without modifying the subproblem or expanding its variable space.

Introduction

Many mixed integer programming problems have a decomposable structure, which makes them well suited for Dantzig-Wolfe reformulation and for which Branch-and-Price can be a competitive solution approach. However, branching can be challenging. One needs a scheme that not only has good properties in terms of leading to integrality of the solution and yielding dual bound improvements, but that is also "compatible" with column generation. In particular, branching constraints may result in modifications to the structure of the pricing problem and impair its tractability. This is a main concern since the competitiveness of the decomposition approach typically relies on the availability of an efficient pricing problem solver.

The issue of branching in a branch-and-price context has not been explored in full detail to date, because, for many practical applications, branching is straightforward. In particular, branching can be implemented in a standard way in the space of the compact formulation to which the Dantzig-Wolfe reformulation was applied and this implementation is competitive in many situations. Villeneuve et al. [START_REF] Villeneuve | On Compact Formulations for Integer Programs Solved by Column Generation[END_REF] suggest that one can always proceed by using standard branching in an "original" formulation and re-apply Dantzig-Wolfe reformulation to the problem augmented with branching constraints. However, when the decomposition involves multiple identical subproblems, this typically induces symmetries. As an alternative, specialized branching rules for use in Branch-and-Price have been developed. Ryan and Foster [START_REF] Ryan | An integer programming approach to scheduling[END_REF] proposed a scheme for applications that can be reformulated as set partitioning problems, a generalization of which was developed by Vanderbeck [START_REF] Vanderbeck | On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm[END_REF]. However, both of these specialized schemes may result in structural modifications to the pricing problem. Another line of branching schemes reported in the literature can be understood as implicitly using an extended ("original") formulation and branch on the new variables of the reformulation (as in Belov et al. [START_REF] Belov | A Node-Flow Model for the 1D Stock Cutting: Robust Branch-Cut-and-Price[END_REF] or Valério de Carvalho [START_REF] Valério De Carvalho | Exact solution of bin packing problems using column generation and branch-and-bound[END_REF]). Such approach is application specific and requires to a pricing problem solver that works in this expanded variable space.

The scheme proposed in this paper builds on and unifies previously proposed generic approaches, while avoiding their drawbacks. It can be seen as special case of the implementation of the scheme of [START_REF] Vanderbeck | On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm[END_REF] in which fractional solutions are cut off by bounding the number of columns selected from specific subsets. This particular implementation permits the use of the original pricing problem oracle after branching, as does the scheme of [START_REF] Villeneuve | On Compact Formulations for Integer Programs Solved by Column Generation[END_REF]. The new scheme can also be understood as a refinement of the scheme of [START_REF] Villeneuve | On Compact Formulations for Integer Programs Solved by Column Generation[END_REF]: the branching constraints of the new scheme are shown to implicitly fix bounds on the variables of the original formulation, while [START_REF] Villeneuve | On Compact Formulations for Integer Programs Solved by Column Generation[END_REF] implements explicit bounds on the original variables. This refinement allows us to avoid the symmetry drawback of the scheme of [START_REF] Villeneuve | On Compact Formulations for Integer Programs Solved by Column Generation[END_REF] in the case of multiple identical subproblems, as we will show. In the new scheme, as in that of [START_REF] Villeneuve | On Compact Formulations for Integer Programs Solved by Column Generation[END_REF], branching constraints can be enforced directly in the subproblem if the pricing oracle can handle bounds on the subproblem variables. Since branching constraints are not dualized (i.e., not placed in the master as in [START_REF] Vanderbeck | On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm[END_REF]), they induce better improvements of dual bounds. Finally, when the master is a set partitioning problem, the proposed scheme resembles that of [START_REF] Ryan | An integer programming approach to scheduling[END_REF], but with a different pricing procedure.

A motivation for this work is the development of a generic code for branch-and-price. Previously existing framework for implementing branch-and-price such as Abacus [START_REF] Thienel | ABACUS -A Branch-And-CUt System[END_REF], BCP [START_REF] Ladányi | Branch, Cut, and Price: Sequential and Parallel[END_REF], G12 [START_REF] Puchinger | From High-Level Model to Branch-and-Price Solution in G12. CPAIOR[END_REF], or Minto [START_REF] Savelsbergh | Functional description of MINTO, a Mixed INTeger Optimizer[END_REF] are tool boxes that leave it to the user to implement an application specific branching scheme. Other existing codes have been developed for specific classes of applications (such as the vehicle routing problem and its variants); examples include Gencol [START_REF] Desaulniers | GENCOL, a mathematical optimizer[END_REF] and Maestro [START_REF] Chabrier | Génération de Colonnes et de Coupes utilisant des sous-problèmes de plus court chemin[END_REF]. In these references, the branching issue has been seen so far as a barrier to the automation of branch-and-price. The branching scheme of this paper allows the overcoming of this barrier. The proposed scheme is valid for any column generation application; the only requirement is a pricing oracle that can handle upper and lower bounds on the subproblem variables. The scheme requires no input from the user since the same pricing problem solver can be used after branching. Hence, the scheme leads to a possible black box implementation of branch-and-price. We are currently working on a prototype of a generic branch-and-price implementation, called BaPCod [START_REF] Vanderbeck | BaPCod -A generic Branch-And-Price Code[END_REF].

The presentation given herein is not limited to the principles underlying the new scheme. As the implementation of the proposed scheme is not trivial, the paper makes specific proposals regarding the separation of fractional solutions and the pricing procedure after branching. An analysis of the scheme properties allows us to show that the worst case complexity of the enumeration is no worse than when branching in the original variable space.

The paper is organized as follows. Section 2 reviews the Dantzig-Wolfe reformulation principle. Section 3 provides an overview of the new scheme, explaining its principle and introducing the features needed for its implementation. A formal presentation follows for the special case of a binary integer program in Sections 4 to 10, detailing a mapping from the Dantzig-Wolfe reformulation to the original problem variable space; presenting how to branch at the root node and beyond, and how column generation is implemented after branching; giving the expression of the resulting dual bound and showing how preprocessing yields simplifications, specifically in the special case where the master is a set partitioning problem. In Section 11, we briefly explain how the scheme can be extended to a general mixed integer program. Section 12 presents computational experiments on cutting stock and bin packing problems. The conclusion summarizes the scheme, its contributions, and its limitations.

The Dantzig-Wolfe approach

Let us introduce our notation and briefly review the Dantzig-Wolfe approach: the decomposition of a mixed integer program, its reformulation, the column generation procedure, and Lagrangian duality results. To simplify the presentation, we assume a pure integer program (IP) whose variables are bounded. The extension to the unbounded case is presented in [START_REF] Vanderbeck | On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm[END_REF], while the extension to the mixed integer case is presented in [START_REF] Vanderbeck | A Generic View of Dantzig-Wolfe Decomposition in Mixed Integer Programming[END_REF]. We consider a well structured IP whose constraint matrix is of the form

        A 1 A 2 . . . A R B 1 0 . . . 0 0 B 2 . . . 0 . . . . . . . . . 0 0 . . . B R         , (1)
where A r and B r , for r = 1, . . ., R, are rational matrices. I.e., there are R diagonal blocks and the problem can be formulated as

Z P = min R ∑ r=1 c r x r (2) [P] R ∑ r=1 A r x r ≥ a (3) B r x r ≥ b r for r = 1, . . ., R (4)
l r ≤ x r ≤ u r for r = 1, . . ., R

x r ∈ Z n for r = 1, . . ., R

where c r , a, and b r are rational vectors of appropriate dimension and l r (resp. u r ) are lower (resp. upper) bound vectors. Let P LP denote its linear programming (LP) relaxation and Z P LP its optimal LP value. A subsystem X r ≡ {x ∈ Z n : B r x ≥ b r , l r ≤ x ≤ u r } [START_REF] Eisenbrand | Carathéodory Bounds for Integer Cones[END_REF] can be associated with each block r. Let X r LP be the polyhedron associated to its LP relaxation.

Throughout the paper, we shall distinguish two cases. Either we have non-identical subsystems: A r and the data of subsystems X r depend on r. Or the subsystems are identical: A r and the data of subsystems X r do not depend on r. The combined case could also occur for which matrix B is made of non-identical blocks, each of which decomposes into identical sub-blocks: an example would be a Vehicle Routing Problem (VRP) with different vehicle types and several vehicles of each type.

The Dantzig-Wolfe reformulation of problem [P] can be introduced in several ways. For this paper, we adopt the discretization approach of [START_REF] Vanderbeck | A Generic View of Dantzig-Wolfe Decomposition in Mixed Integer Programming[END_REF]. Let G r be an enumerated set of generators (a terminology introduced in [START_REF] Vanderbeck | A Generic View of Dantzig-Wolfe Decomposition in Mixed Integer Programming[END_REF]) for subsystem X r . Since we assume a bounded and pure integer program, G r is simply the enumerated set of all discrete integer solutions of X r , i.e., X r = {x g } g∈G r , where x g is the solution vector associated to generator g, and X r can be reformulated as

X r ≡ {x = ∑ g∈G r x g λ g : ∑ g∈G r λ g = 1, λ g ∈ {0, 1} ∀g ∈ G r } .
Then, the Dantzig-Wolfe reformulation principle refers to the application of this variable change to [P], which gives rise to the reformulation:

Z DM = min R ∑ r=1 ∑ g∈G r c r x g λ r g [DM] R ∑ r=1 ∑ g∈G r A r x g λ r g ≥ a (8)
∑ g∈G r λ r g = 1 for r = 1, . . ., R λ r g ∈ {0, 1} for r = 1, . . . , R, g ∈ G r .

Thus, in our notation, g denotes the generator (g is also used as an index referring to the generator),

x g denotes its characteristic vector, (c r x g , A r x g ) is the associated column vector in formulation [DM], and λ r g is the associated decision variable. For simplicity, we shall commonly refer to g as a column in the sequel. Let DM LP denote the LP relaxation of [DM] and Z DM LP be its optimal LP value.

In the case where all subsystems are identical, i.e., A r = A, B r = B, c r = c, X r = X and G r = G for r = 1, . . ., R, one can aggregate λ r g variables using:

ν g = R ∑ r=1 λ r g . (9)
Then, the Dantzig-Wolfe reformulation takes the form:

Z M = min ∑ g∈G c x g ν g ( 10
)
[M]

∑ g∈G A x g ν g ≥ a (11) ∑ g∈G ν g = R (12) ν g ∈ IN ∀g ∈ G ( 13
)
Let M LP denote its LP relaxation and Z M LP be its optimal LP value. Observe that the aggregation (9) removes the symmetry in r that is present in the original formulation [P] (where a permutation of the r indexing in vector x gives rise to an alternative representation of the same solution) or in [DM]. We assume the equality convexity constraint [START_REF] Parker | A column generation algorithm for brandwidth packing[END_REF] although considering convexity constraints of the form L ≤ ∑ g∈G ν g ≤ U is a straightforward extension.

The enumeration of set G (or G r in the case of non-identical subsystems) is only theoretical. In practice, the solution of the Dantzig-Wolfe reformulation is handled through dynamic generation of its variables and associated columns in the course of the optimization, a procedure known as column generation. In this context, the reformulation is called the master program: we refer to [DM], given in [START_REF] Gendreau | Vehicle Routing with Time Windows and Split Deliveries[END_REF], as the disaggregated master used in the case of non-identical subsystems, while [M] is the commonly used form of the master in the case of identical subsystems. Thus, solving the LP relaxation of [M] by column generation proceeds as follows. (The LP solution of [DM] is analogous.) The master LP is initialized with a subset of (possibly artificial) columns. This restricted program is solved to LP optimality. Let π be the dual solution vector associated with constraints [START_REF] Ladányi | Branch, Cut, and Price: Sequential and Parallel[END_REF]. Then, a pricing problem is solved:

ζ (π) := min{(c -πA)x : B x ≥ b, l ≤ x ≤ u, x ∈ Z n x∈X } . ( 14
)
When its solution, x g := x * , defines a negative reduced cost column, the column (c x g , A x g ) and associated ν g variable are added to the master and the procedure reiterates. Otherwise, the current LP solution has been proven optimal.

The principal assumption underlying the Dantzig-Wolfe approach is that ( 14) is a problem that can be solved rather efficiently, compared to [P]. Throughout this paper, we assume that a solver is available for [START_REF] Ryan | An integer programming approach to scheduling[END_REF] that requires reasonable computing time (although typically not polynomial time). It can be a specialized combinatorial algorithm or one might even use a general purpose commercial MIP solver. We refer to this solver as the oracle. Observe that we have included bounds on the variables in the definition of the pricing problem, as our branching scheme proceeds by amending these bounds. In some applications, the bounded version of the pricing problem can be harder (complexity wise) than the unbounded case. On the other hand, considering a bounded pricing problem often yields a stronger dual bound Z M LP or Z DM LP (see [START_REF] Vanderbeck | Implementing Mixed Integer Column Generation[END_REF]).

At each iteration of the column generation procedure, a dual bound can be computed from the pricing problem solutions: dualizing [START_REF] Ladányi | Branch, Cut, and Price: Sequential and Parallel[END_REF] in [M] gives rise to the Lagrangian dual bound

θ (π) := π a + R ζ (π) , (15)
where ζ (π) is defined by [START_REF] Ryan | An integer programming approach to scheduling[END_REF]. These bounds, θ (π), are computed for each dual solution, π, to the restricted master LP. They converge (although not monotonically) towards the optimal value of the master LP. The latter is known to be equivalent to the Lagrangian dual that results from dualizing constraints (3) in [P] (see [START_REF] Geoffrion | Lagrangian relaxation for integer programming[END_REF]), i.e.,

Z M LP = max π≥0 θ (π) = min{ ∑ r c x r : ∑ r A x r ≥ a, x r ∈ conv(X r ) ∀r} , (16)
where the third form is the Lagrangian bi-dual (see [START_REF] Briant | Comparison of Bundle and Classical Column Generation[END_REF]), reminding us that the Dantzig-Wolfe approach produces a bound equal to the LP solution over a polyhedron where the subproblem is "convexified". Thus, the comparison of the LP and IP values of the above formulations is

Z P LP ≤ Z M LP = Z DM LP ≤ Z M = Z DM = Z P . When conv(X r ) = X r
LP , the master gives rise to an LP bound that can be better than that of [P].

Thus, Dantzig-Wolfe reformulation allows a solution approach that exploits the availability of an efficient specialized oracle for a subproblem; it avoids symmetry in r in the case of identical subsystems; and it often leads to better quality dual bounds. To apply a branch-and-bound approach based on the Dantzig-Wolfe reformulation, one needs to embed a column generation procedure into a branch-and-bound algorithm. The combined algorithm is known as branch-and-price [START_REF] Barnhart | Branchand-Price: Column Generation for Huge Integer Programs[END_REF]. This raises several issues: (i) the choice of branching on variables of the original formulation or those of the reformulation, or branching on constraints, and the equivalence that may or may not exist between these approaches; (ii) where to enforce the branching constraint (in the master or in the subproblem) and the impact on the strength of resulting Lagrangian dual bound after branching; (iii) potential structural modifications to the pricing problem that may only be compatible with specific solution methods or may make it much harder to perform pricing.

Branching directly on individual variables ν g (resp. λ r g ), using disjunctive constraints ν g ≤ ⌊v⌋ or ν g ≥ ⌈v⌉, was tested, for instance, by [START_REF] Parker | A column generation algorithm for brandwidth packing[END_REF][START_REF] Vance | Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem[END_REF]. The resulting branch-and-bound tree is unbalanced (constraint ν g ≤ ⌊v⌋ is weak) and it combines badly with column generation (in the branch ν g ≤ ⌊v⌋, one must avoid regenerating the specific column g ∈ G either by adding constraints to the pricing problem or by looking for the next best subproblem solution). The alternative is to branch on constraints.

A natural combination of variables ν g (resp. λ r g ) on which to branch is that expressing the value of the variables of the original formulation [P]: mapping ν (resp. λ ) solutions into x solutions and implementing a branching scheme based on disjunctive constraints for the original variables. In the case of non-identical subsystems, this scheme will suffice to enforce integrality since the mapping

x r = ∑ g∈G r x g λ r g , (17)
defines a unique projection to the original variable space and disjunctive branching constraints of the form ∑ g∈G r x g i λ r g ≤ ⌊α⌋ or ∑ g∈G r x g i λ r g ≥ ⌈α⌉ in [DM LP ] are therefore equivalent to enforcing

x r i ≤ ⌊α⌋ or x r i ≥ ⌈α⌉ , (18)
in the original problem for each subproblem r and component i that would have fractional value α ∈ Z (see [START_REF] Barnhart | Branchand-Price: Column Generation for Huge Integer Programs[END_REF]). Branching can then be enforced directly in the pricing problem: one simply needs to reset a component bound in the subproblem.

However, in the case of identical subsystems, one is working with reformulation [M]. Then, the disaggregated original variable values, x r , are not available through a uniquely defined mapping. Note that using [DM] even in the case of identical subsystems would allow one to branch on the original variables but it has an obvious symmetry drawback due to the artificial re-introduction of the r indices on identical subsystems. With [M], one can only enforce the integrality of aggregate variables

x = R ∑ r=1 x r = ∑ g∈G x g ν g , (19)
using disjunctive branching constraints of the form

∑ g∈G x g i ν g ≤ ⌊α⌋ or ∑ g∈G x g i ν g ≥ ⌈α⌉ , (20)
for components i that have fractional value α ∈ Z. But branching constraints on aggregate variables are typically not sufficient to eliminate all fractional solutions, and they cannot in general be enforced directly in the pricing problem. In the literature, alternative "original formulations" have sometimes been considered to allow branching on the aggregate value of original variables. Such reformulations typically imply an expanded variable space which can even be of pseudo-polynomial size [START_REF] Belov | A Node-Flow Model for the 1D Stock Cutting: Robust Branch-Cut-and-Price[END_REF][START_REF] Valério De Carvalho | Exact solution of bin packing problems using column generation and branch-and-bound[END_REF].

Other forms of branching-on-constraint strategies have been developed to handle the case of identical subsystems. When the master takes the form of a set partitioning problem, i.e., min{

∑ g∈G c x g ν g : ∑ g∈G x g i ν g = 1 ∀i, ∑ g∈G ν g = R, ν g ∈ {0, 1} ∀g ∈ G} (21)
with x g ∈ {0, 1} n , integrality can be enforced using Ryan and Foster's scheme [START_REF] Ryan | An integer programming approach to scheduling[END_REF]. For any fractional solution, ν ∈ {0, 1} |G| , there exists a pair of items (i, j) such that the fractional solution ν can be separated using the disjunction ∑ g:

x g i =x g j =1 ν g ≤ 0 or ∑ g:x g i =x g j =1 ν g ≥ 1.
In the first branch, as no column that has both x g i = 1 and x g j = 1 can be used, the pricing problem is augmented with constraint x i + x j ≤ 1. In the second branch, as items i and j are entirely covered by columns with x g i = x g j = 1, the pricing problem is augmented with constraint x i = x j . The modifications to the pricing problem may change its structure.

Vanderbeck [START_REF] Vanderbeck | On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm[END_REF] proposes a scheme that generalizes that of Ryan and Foster to master programs not restricted to set partitioning problems. It consists in considering progressively more specific subsets Ĝ ⊂ G and enforcing ∑ g∈ Ĝ ν g ∈ Z through disjunctive branching constraints of the form:

∑ g∈ Ĝ ν g ≤ L -1 or ∑ g∈ Ĝ ν g ≥ L (22)
for L ∈ IN. In practice, sets Ĝ are defined as subsets of columns whose vector x g satisfy prescribed bounds on some of its components: Ĝ = G ∩ {sx ≥ l}, where l ∈ Z n is a vector of bounds and s ∈ {-1, 1} n defines the sign of each component bound. Then the pricing problem must be modified to account for the dual variable associated with branching constraint [START_REF] Vanderbeck | Extending Dantzig's Bound to the Bounded Multi-Class Binary Knapsack Problem[END_REF] for the columns of Ĝ and not for those of G \ Ĝ.

Overview of the proposed scheme

The branching scheme of this paper addresses the case of identical subsystems: the master program is [M] given by [START_REF] Horowitz | Computing partitions with applications to the knapsack problem[END_REF][START_REF] Ladányi | Branch, Cut, and Price: Sequential and Parallel[END_REF][START_REF] Parker | A column generation algorithm for brandwidth packing[END_REF][START_REF] Puchinger | From High-Level Model to Branch-and-Price Solution in G12. CPAIOR[END_REF] and branching on the aggregate value of the original variables does not suffice to achieve integrality. The complete generic scheme consists in using first branching disjunctions of the form [START_REF] Vanderbeck | On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm[END_REF] to achieve integrality of the aggregate value of the "original" variables, and then to apply the scheme proposed herein to finalise the elimination of fractional solution if needed. This complete scheme can serve as a default branching for a generic branch-and-price solver: an informed user might want to use application specific branching rules (such as branching on constraints) before using the default scheme. Applying the new scheme to the case of non-identical subsystems amounts to reproducing the standard branching scheme [START_REF] Vance | Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem[END_REF].

The idea underlying the new scheme is to return to the non-identical subsystem situation, by making use of a progressive subproblem differentiation, introducing new subsystems dynamically. Using formulation [DM] in the case of identical subsystems amounts to an "a priori" subproblem differentiation, but it induces symmetry. Instead, one can differentiate the subsystem progressively in the course of branching. Viewing the aggregate convexity constraint (12) as a "special ordered set" (SOS), one can branch by progressively partitioning subsystem X , or equivalently the generator set G, and enforcing separate convexity constraints on each subset. A natural scheme is to partition subsystem X by imposing disjunctive constraints on the integer subproblem variables x i ∈ Z: a generator subset, Ĝ ⊆ G, which we call a "column class", is defined in terms of bound restrictions on some components of x g . Then, one can do the pricing over Ĝ using the oracle for [START_REF] Ryan | An integer programming approach to scheduling[END_REF]. To allow us to price columns from each individual column class, Ĝ, independently, we need to implement further branching by partitioning previously defined subsystems, i.e. a nested partition scheme is required.

The proposed scheme can be seen as a specific implementation of the scheme of [START_REF] Vanderbeck | On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm[END_REF]: instead of selecting sets, Ĝ, arbitrarily (as illustrated on the left part of Figure 1), they are defined so as to form a nested partition of the pricing problem solution set (as illustrated on the right part of Figure 1). Moreover, instead of modifying the pricing problem by introducing indicator variables associated with each column class Ĝ, we solve separate pricing subproblems. Thus, branching constraints are enforced directly in the pricing problem through this enumeration procedure.

To guarantee that the number of newly introduced subproblems is bounded by R, the number of diagonal blocks in (1), we use only branching constraints that enforce lower bound on column classes:

∑ g∈ Ĝ ν g ≥ L , (23)
with L ≥ 1. By the pigeon hole principle, there cannot be more than R such constraints that are active. This is implemented using a non binary enumeration tree: the branch

∑ g∈ Ĝ ν g ≤ U is replaced by Ĝ1 Ĝ2 → Ĝ1 Ĝ2 Ĝ3
Figure 1: Partitioning of the pricing problem solution set: using the scheme of [START_REF] Vanderbeck | On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm[END_REF] on the left, and the nested partition of the new scheme on the right. enumerating ways in which ∑ g∈G\ Ĝ ν g ≥ R -U . We show that each branching constraint of the form [START_REF] Vanderbeck | Implementing Mixed Integer Column Generation[END_REF] induces progress in reaching primal integrality that can be measured in the compact space of the original variables: each branching constraint implicitly fixes a bound on at least one original variable. To establish such equivalence we consider the projection of the master solution in the original formulation. This shows that integrality of the solution must be achieved after adding a polynomial number of branching constraints (assuming fixed bounds on the original variables), even though the number of column classes on which one could branch is exponential.

The dynamic introduction of differentiated pricing subproblems is similar to what is done in the scheme of Villeneuve et al. [START_REF] Villeneuve | On Compact Formulations for Integer Programs Solved by Column Generation[END_REF] in its dynamic implementation where pricing subproblems are introduced as needed. Our proposal goes further by providing a practical way of iteratively refining the column class definitions to separate fractional solutions. But, more importantly, our scheme differs by the fact that branching constraints concern groups of subproblems instead of one at the time. Column classes, Ĝ, on which we branch expand over several subsets G r of formulation [DM] given in [START_REF] Gendreau | Vehicle Routing with Time Windows and Split Deliveries[END_REF] but with no explicit reference to any r index. The link between master and original solution spaces established through our projection tool is only implicit (there is no one-to-one correspondence) and it must remain so to avoid symmetry.

Our proposal is completed by a practical strategy to handle the multiple pricing subproblems associated with the various column classes defined at a given branch-and-price node. As column classes are nested, one can organize the enumeration of the associated pricing subproblem in a tree. Then, using appropriate tree search strategies, one can truncate the enumeration of pricing subproblems as soon as a negative reduced cost column is found and still get a dual bound on the best reduced cost. Finally, we show that preprocessing yields significant simplifications to the generic scheme and, in particular, in the special case of a set partitioning problem. The Ryan and Foster scheme is shown to be closely related to the form taken by our scheme when the master is a set partitioning problem.

To simplify the detailed presentation, we assume from now on that the subsystem involves binary variables only :

X = {x ∈ {0, 1} n : B x ≥ b} . (24)
Then, column classes, Ĝ, are defined as subsets of columns, g, whose indicator vector, x g , has some components fixed to zero or one. For instance, S =< x 1 , x 2 , x 3 > denotes a sequence of component bounds in which x 1 is fixed to one, x 2 to zero and x 3 to one. The associated class of columns is

G(S) = {g ∈ G : x g 1 + x g 2 + x g 3 = 3}, where x g 2 = 1 -x g 2 .
Note that this model can correspond to a practical strategy that consists in branching on the binary variables resulting from a 0-1 transformation of an integer program. Extensions to the general mixed integer case are outlined in Section 11.

A mapping that preserves integrality

Each solution ν to [M] (resp. λ to [M LP ]) can be transformed into a solution x to [P] (resp.

[P LP ]). One can disaggregate the solution ν to [M] into a solution {λ r } r=1,...,R to [DM] and then use transformation [START_REF] Valério De Carvalho | Exact solution of bin packing problems using column generation and branch-and-bound[END_REF] to get R solution vectors x r ∈ [0, 1] n for [P]. The procedure is not unique. A possible disaggregation for an LP solution is: λ r g =

ν g R ∀r = 1, . . ., R, g ∈ G.
But it can yield a fractional solution x, even when ν happens to be integer. An alternative disaggregation that preserves integrality can be defined recursively as follows. Assume an ordering of the generator set, defined by a precedence operator:

g 1 ≺ g 2 if g 1 precedes g 2 in the list of generators G. Then, let λ r g = min{1, ν g - r-1 ∑ ρ=1 λ ρ g , (r -∑ γ:γ≺g ν γ ) + } ∀r = 1, . . . , R, g ∈ G . (25)
An integer solution ν decomposes into an integer solution λ : λ r g = 1 if ∑ γ≺g ν γ ≤ r -1 and ∑ γ g ν γ ≥ r. The resulting mapping procedure into the X space is given in Table 1 and illustrated in Example 1. Each ordering yields a valid mapping, however a lexicographic ordering provides a better chance to generate an integer solution.

Example 1 We shall use the following numerical example to illustrate the developments to come. The constraints of [M] are defined by

A =    1 0 1 0 0 1 0 1 1 1 0 2    and a =    5 5 10    .
Assume R = 5 identical subsystems and a set G of feasible columns given below, as well as a master LP solution νg : νg 0 1 2 1 1 2 0 0 1 1 0 0 1 2 0 1 2 0 0 x 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 x 2 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 x 3 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 x 4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 Using the mapping of Table 1, we get a solution to the original formulation { xr } r=1,...,5 :

x1 =      1 1 0 1 2      , x2 =      1 1 2 1 2 1 2      , x3 =      1 0 0 0      , x4 =      0 1 1 1      , x5 =      0 1 2 1 2 0      . Table 1: Transforming a solution ν to [M] (resp. [M LP ]) into a solution for [P] (resp. [P LP ]) 1. Let Λ = {g : νg > 0}.
2. Sort the columns g ∈ Λ in lexicographic decreasing order of vectors x g .

Initialize xr

i = 0 for all i, r; let z = 0 and r = 1.

4. For each g ∈ Λ in lexicographic order, do while ( νg > 0), do let λ r g = min{ νg , r -z};

for all i = 1, . . ., n, do xr i = xr i + x g i λ r g ; νg = νg -λ r g ; z = z + λ r g ; if (z == r) then r = r + 1 ;
In the sequel, we refer to a figurative representation of a master solution. We define a "strip" associated with a column or a column class as follows:

Definition 1 Consider a master solution ν where columns are sorted lexicographically. Let us represent the solution geometrically by a rectangle with height n and width R. In this rectangle, each column, g, defines a "strip" of "width" νg at a specific position in the sequence of sorted columns. More generally, any column class Ĝ of consecutive columns in lexicographic order defines a " Ĝ-strip" of "width" ν( Ĝ) = ∑ g∈ Ĝ νg .

The mapping of master solution ν into an x solution requires slicing the rectangle of width R to partition it into R sub-strips of width 1, each of which shall be associated with an index r. Each column g that is involved in the r th strip contributes to the definition of xr proportionally to its value λ r g which represents its width in the r th strip: see [START_REF] Valério De Carvalho | Exact solution of bin packing problems using column generation and branch-and-bound[END_REF]. In Table 1, z stands for the current position in the G-strip of width R.

The mapping of Table 1 was designed to preserve integrality. Inversely, the resulting x solution can only be binary if ν is integer:

Proposition 1 If x is a solution generated from a solution ν to [M LP ] using the procedure of Table 1, then xr i ∈ {0, 1} ∀i, r ⇐⇒ νg ∈ IN ∀g Proof: It is trivial to note that if νg ∈ IN ∀g, then xr i ∈ {0, 1} ∀i, r.
Let us prove the reverse implication by contradiction. Assuming F = {g : νg -⌊ νg ⌋ > 0} = / 0, we show that xr i ∈ {0, 1} for some pair (i, r). Let g 1 be the first fractional column of F in lexicographic order. Let r = argmax{ρ : λ ρ g 1 > 0} be the last index of a vector xr to the definition of which g 1 contributes. Observe that 0 < λ r g 1 = ( νg 1 -⌊ νg 1 ⌋) < 1. Hence, there exists another column g 2 : g 1 ≺ g 2 with 0 < λ r g 2 < 1. Let i be the first component in which g 1 and g 2 differ:

x g 1 i = 1 while x g 2 i = 0. Then, 0 < λ r g 1 < xr i ≤ 1 -λ r g 2 < 1.
Thus, when the subsystems are binary problems, checking the integrality of the solution ν in [M LP ] is equivalent to checking the integrality of the associated solution x in [P LP ]. However, when some of the x variables are general integer, the mapped solution can be integer while ν is not.

Separation of a fractional solution at the root node

Branching is implemented by bounding the "value" of "column classes" that are defined by "component bound sequences".

Definition 2 A "component bound sequence", S, is an ordered set of bounding restrictions on the components of the subproblem solution vector, x. For the binary case, bounding restrictions amount to fixing components to zero or one:

S =< ẍ[1] , ẍ[2] , . . . , ẍ[|S|] >, (26)
where [p] is the index of the component bound in the p th position in the sequence, and the notation ẍ[p] stands for either the case in which the variable is fixed to one (ẍ

[p] = x [p] ) or fixed to zero (ẍ [p] = x [p] ).
The "last" component of the sequence is the component x i defined by index i = [|S|]. The "column class" associated with S is defined as

G(S) = {g ∈ G : ∑ i∈S ẍg i = |S|}
where the notation i ∈ S is a short cut for saying that sequence S includes a bound on component x i , also denoted as x i ∈ S or x i ∈ S. The "value" of the class is the cumulative value of its columns in the current master solution, ν:

ν(S) = ν(G(S)) = ∑ g∈G(S)
νg .

The column class value is its "width" in the geometric solution representation of Definition 1.

At the root node, the separation of a fractional solution, ν, to [M LP ] proceeds as follows. Identify a "column class", G(S), whose value, ν(S), is fractional, and impose disjunctive constraints to enforce its integrality. The proof of Proposition 1 provides a possible selection of S defined by the first i components of the characteristic vector, x g 1 , of the first fractional column, g 1 . However, the implementation of the branching scheme is sensitive to the size of the chosen sequence S: a smaller size S shall induce fewer branch-and-bound nodes and a more balanced branch-and-bound tree. Hence, we seek to implement separation based on sequences, S, with few component bounds.

Reference [START_REF] Vanderbeck | On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm[END_REF] presents two separation procedures, one that yields a minimal size subset of component bounds (using an enumeration scheme that has exponential worst case complexity) and another that achieves the best complexity in the worst case. The procedure proposed here, in Table 2, is a compromise between these two: it partially relies on enumeration in search for a minimal size component sequence, S, while guaranteeing a polynomial worst case complexity. Its use is illustrated in Example 2. Amongst component sequences with the same size that are candidates for branching, we select the sequence S whose "last component" has the highest branching priority (assuming branching priorities and directions are defined for the "original" variables of the subproblem). We shall indeed show later that branching on G(S) is equivalent to implicitly fixing the last component of S in the original formulation. One could give more emphasis on selecting a last component of higher priority by allowing the size of S to increase. In Table 2, F = {g : νg -⌊ νg ⌋ > 0} denotes the set of fractional columns; ν(F) = ∑ g∈F νg denotes its value; F(S) = F ∩ G(S) is the set of fractional columns satisfying component bounds in S; record is the list of identified sequences S with fractional value f = ν(F(S)) ∈ IN on which we could branch; and priority i denotes the branching priority level associated with component x i of subproblem solution vector x ∈ {0, 1} n .

Example 2 (Example 1 continued) Consider the fractional master solution ν provided in Exam

- ple 1. It yields ν(F(x i )) = ν(F(x i )) = 1 for i = 1, . . . , 4 .
Assume that subproblem variables are indexed in order of non-increasing priority. Hence, we make recursive calls to the routine Separate of Table 2 to split further the column class defined by S =< x 1 > and < x 1 >. In the first call to Separate, we get ν(F(x 1 ,

x i )) = ν(F(x 1 , x i )) = 1 2 for i = 2, 3
and pick the highest priority set: S =< x 1 , x 2 > or S =< x 1 , x 2 > depending on priority in branching directions. On the other hand, in the second call, further splitting the column class defined by S =< x 1 > yields the branching sequence S =<

x 1 , x 2 > or S =< x 1 , x 2 >.
Observe that |F| ≤ m, where m is the number of constraints in the master formulation at the current branch-and-bound node (assuming that ν is obtained as an extreme LP solution to the master program). Each call to subroutine Separate(F, I, S, record) of Table 2 requires O(n |F|) operations where n is the number of binary components. Routine Separate is called recursively. The depth of Table 2: Separation of a fractional master solution, ν, at the root node.

1. Let F = {g : νg -⌊ νg ⌋ > 0}, I = {1, . . . , n}, S =<>, record= / 0.
2. Separate(F, I, S, record) (a) Check whether the current set of columns has fractional columns:

If F = / 0, return. (b) Compute values of aggregate variables (α i ) i∈I : For all i ∈ I, let α i = ∑ g∈F x g i νg . (c) Detect fractional α i if any: Found = false; For all i ∈ I, do if ( f = α i -⌊α i ⌋ > 0) add the pair (< S, x i >, f ) to record; Found = true; If (Found), return. (d) Identify discriminating components: J = {i ∈ I : 0 < α i < ν(F)}.
(e) Partition according to the component with highest branching priority:

Let i * = argmax j∈J {priority j }; Separate(F (< S, x i * >), J \ {i * }, < S, x i * >, record); Separate(F (< S, x i * >), J \ {i * }, < S, x i * >, record); return;
3. Select a branching sequence S in record according to branching priorities on its last component.

the tree of recursive calls is bounded by n. The number of leaf nodes in the tree of recursive calls is bounded by |F|, since the fractional column set is partitioned at each stage and we only explore non-empty subsets. Therefore, the overall complexity is O(n 2 |F| 2 ). One could reduce the complexity to O(n|F| log |F|) by applying the recursive call to only one side of the partition in Step (f), selecting the subset of fractional columns with the smallest value.

Given a component bound sequence S whose associated class has fractional value ν(S) ∈ IN for the current master solution ν, one implements branching by adding a disjunctive constraint that eliminates this fractional solution. A natural scheme would be to use a binary disjunction ν(S) ≤ ⌊ ν(S)⌋ or ν(S) ≥ ⌈ ν(S)⌉ .

However, the branching constraint ν(S) ≤ ⌊ ν(S)⌋ of the first branch is typically weaker than that of the second branch (leading to an unbalanced tree). A stronger disjunctive constraint can be derived by using a non binary branching tree, as illustrated in Example 3 below. A general presentation of the branching scheme follows the example. An important remark concerning the proposed scheme is that the solution sets associated with the descendant nodes are not necessarily disjoint (we do not have a partition of the master solution space). We prove however that the scheme yields a valid separation: Proposition 2 shows that the fractional solution is eliminated and no integer solution is lost. The finiteness of the scheme shall be proved in Section 6: we show that the size of the branch-and-price tree is bounded (in particular, we give a polynomial bound on the depth of the tree).

Example 3 (Example 2 continued)

Assume that set S =< x 1 , x 2 > was selected for branching and that one uses a binary disjunction: ν(x 1 , x 2 ) ≤ 1 or ν(x 1 , x 2 ) ≥ 2 . In the first branch, one may have the solution:

νg 0 0 1 3 4 0 0 1 1 0 1 2 1 4 0 1 2 0 0 x 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 x 2 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 x 3 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 x 4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

(this fractional solution can easily be seen to satisfy the master constraints of Example 1

). An alternative scheme can be derived considering the following intuitive argument. The branching constraint ν(x 1 , x 2 ) ≤ 1 force the LP solver to use fewer columns from class G(x 1 , x 2 ) compared to the current solution, ν. As the total number of columns is fixed, ν(G) = R, this can only be achieved by increasing the number of columns selected from G \ G(x 1 , x 2 ) = G(x 1 , x 2 ) ∪ G(x 1 ). Hence, from an IP perspective, we can define two new branches: either ν(x 1 , x 2 ) ≥ 2 (assuming implicitly that ν(x 1 ) ≥ 3), or ν(x 1 ) ≥ 3 (which implies ν(x 1 ) ≤ 2). In total, we define 3 descendant nodes (defined by a branching constraint) as follows:

Node(1) ≡ ν(x 1 ) ≥ 3 ,

Node(2) ≡ ν(x 1 , x 2 ) ≥ 2 , Node(3) ≡ ν(x 1 , x 2 ) ≥ 2 .
Observe that the above solution is not feasible in any of Node [START_REF] Barnhart | Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems[END_REF], Node [START_REF] Barnhart | Branchand-Price: Column Generation for Huge Integer Programs[END_REF], or Node [START_REF] Belov | A Node-Flow Model for the 1D Stock Cutting: Robust Branch-Cut-and-Price[END_REF], which illustrates that this non-binary scheme can be stronger. However, the solution spaces associated with each node are not disjoint: for instance, solutions with ν(

x 1 , x 2 ) ≥ 2 can also arise in node 2, if ν(x 1 ) ≥ 4, or, in node 1, if ν(x 1 , x 2 ) = 0.
Nevertheless, as we see in this example, the identical solutions that could arise at several tree nodes would be solutions that deviated largely from the current solution and hence would probably yield a significant increase in the dual bound.

The general scheme is characterized by a generic definition of successor nodes:

Definition 3 Let ν be the master LP solution at the current node and S be the "component bound sequence" (see Definition 2) that has been selected for branching. For p = 1, . . . , |S| -1, let S p be the subsequence composed of the first p component bounds of S and

L p = ν(S p ) ∈ IN. Let L |S| = ⌈ ν(S)⌉
be the round-up value of column class G(S), while S 0 =<> and L

0 = ν(G) = R. Let G p = G(S p ) for p = 0, . . . , |S|. Observe that L 0 ≥ L 1 ≥ L 2 ≥ . . . ≥ L |S| are nonincreasing integer values, while G = G 0 ⊇ G 1 ⊇ G 2 ⊇ . . . ⊇ G |S| = G(S). Let G p = G p-1 \ G p = G(S p-1 , ẍ[p] ) for p = 1, . . . , |S|, where ẍ[p] = 1 -ẍ[p]
is the complement of the p th component bound of S. Then, the |S| +1 "successor nodes" are defined as follows: for p = 1, . . . , |S|, the branching constraint defining node p is:

Node(p) ≡ ν(G p-1 \ G p ) ≥ L p-1 -L p + 1 ; ( 27
)
while node |S| + 1 is defined by:

Node(|S| + 1) ≡ ν(G |S| ) ≥ L |S| . ( 28
)
Figure 2 illustrates branching at a node for which the branching sequence, S, involves 4 component bounds: |S| = 4, yielding 5 descendant nodes. The node numbers refer to the associated node definitions [START_REF]User guide and Reference Manual[END_REF](28). The definition of the strip (see Definition 1) associated with each nested column class could, for instance, take the form illustrated in Figure 3: vertical lines define the boundaries of the strips associated with nested column classes and their complement. The disjunctive branching constraint can be understood as follows: in an integer solution either the value of class G 4 is increased to the next integer value, i.e., ν(G 4 ) ≥ L 4 (the width of the G 4 -strip in Figure 3 must increase), or it is rounded down, i.e., ν(G 4 ) < L 4 (the width of the G 4 -strip decreases) and some other strip of Figure 3 must have an increased value, i.e., either ν(G The dotted nodes that appear in Figure 2 are not explicitly defined in our scheme, i.e., constraints ν(G p ) < L p on the branches leading to the dotted nodes are not strictly enforced. The subtrees hanging from those branches include solutions that do not satisfy these constraints because our scheme does not define a partition of the solution space. However, all integer solutions that do not belong to the left subtree satisfy the constraint on the right branch: Lemma 1 The only integer solutions, ν, that are not represented in any of the nodes l = p, . . . , |S| + 1 are those for which ν(G p ) < L p .

4 ) = ν(G 3 \ G 4 ) ≥ L 3 -L 4 + 1, or ν(G 3 ) < L 3 , or both. Similarly, the case ν(G 3 ) < L 3 decomposes recursively into ν(G 2 \ G 3 ) ≥ L 2 -L 3 + 1, or ν(G 1 \ G 2 ) ≥ L 1 -L 2 + 1, or ν(Q \ G 1 ) ≥ L 0 -L 1 + 1,
Proof: We show this by induction. For p = |S| + 1, the result is trivial. Let us derive the result for any p ≤ |S|, assuming the result holds for p + 1. Take an integer solution, ν, that does not satisfy any of the branching constraints defining node l = p, . . . , |S| + 1. By the induction hypothesis, we must have ν(G p+1 ) < L p+1 and hence ν(G p+1 ) ≤ L p+1 -1. Moreover, as ν must violate the branching constraint defining Node(p), we have ν(

G p \ G p+1 ) ≤ L p -L p+1 . As ν(G p ) = ν(G p \ G p+1 ) + ν(G p+1 ), the two previous inequalities imply ν(G p ) ≤ L p -1 < L p .
Although our branching can yield up to n + 1 branches, Lemma 1 shows that nodes 1, . . . , p -1 only serve the purpose of enumerating integer solution in which ν(G p ) < L p . This shall be exploited in Sections 6 and 9 to show how the scheme simplifies in practice. Let us now show that the branching scheme yields a valid separation that cuts off the current fractional solution and eliminates no integer solution.

ν(G 4 ) ≥ L 4 ν(G 4 ) ≥ L 4 ν(G 3 ) ≥ L 3 ν(G 2 ) ≥ L 2 ν(G 1 ) ≥ L 1 ν(G 4 ) < L 4 ν(G 3 ) < L 3 ν(G 2 ) < L 2 ν(G 1 ) < L 1 ν(G 0 ) < L 0
G k = G k-1 \ G k and L k = L k-1 -L k + 1. G 0 G 1 G 1 G 2 G 2 G 3 G 3 G 4 G 4

Proposition 2

The descendant nodes, Node(1), . . ., Node(|S| + 1), of Node(0) define a valid separation scheme, i.e., (i) the fractional solution ν of Node(0) is not feasible in any of the descendant nodes; (ii) any integer solution to Node(0) is feasible in at least one of the descendant nodes.

Proof: By construction, the current solution ν violates some of the branching constraints in each descendant node. It remains to ensure that no integer solution has been lost in the process. All integer solutions use R columns in total (counting multiple copies of the same column). Clearly, integer solutions that use at least

L |S|-1 columns in class G(S |S|-1 ) shall use either at least L |S| columns in class G(S |S| ) or use at least L |S|-1 -L |S| + 1 in the complementary class, G |S|-1 \ G |S| ,
or both. Other integer solutions use strictly less than L |S|-1 columns in class G |S|-1 . In the latter case, the complementary class, G \ G |S|-1 , must hold a least R -L |S|-1 + 1 columns, i.e., one more than in the current solution ν. The complementary class, G \ G |S|-1 , can be partitioned into G p-1 \ G p for p = 1, . . . , |S| -1:

G \ G |S|-1 = ∪ p=1,...,|S|-1 (G p-1 \ G p
) and these classes are disjoint. Thus, the case where the value of the complementary set, G \ G |S|-1 , must increase by one unit can be decomposed into |S| -1 subcases depending on which subset of the partition sees its value increased by one unit compared to the current solution ν. These subcases are defined by Node(1) to Node(|S| -1).

Maintaining a nested separation scheme beyond the root node

Assume that the current branch-and-price node is defined by branching constraints, ν(S k ) ≥ L k , for k = 1, . . . , K, where the associated classes, G k = G(S k ), define a nested partition of G. We show how to eliminate a current fractional master solution, ν, while maintaining a nested partition of G. Next, we observe that, in practice, many of the successor nodes of Definition 3 can be eliminated by a dominance rule. Then, we derive a key property of our scheme: each branching constraint implies primal progress in reaching integrality that can be measured in the space of the original variables. We begin by making several observations that characterize basic properties of a branching scheme based on a nested partition of the column set.

Observation 1

In the nested collection of component sets and associated bounds, {(S k , L k )} k=1,...,K , that defines a branch-and-price node, no two (S k , L k ) are identical.

Indeed, at the stage where a branching constraint, ν(S) ≥ L, was added, it had to cut off the current fractional master solution, ν, and therefore, either S = S k held for all previously defined S k , or else S = S k and L = ⌈ ν(S k )⌉ > L k for some previously defined branching constraint k.

Observation 2 At a given branch-and-price node, the branching constraints define a collection of nested column classes. Therefore, the inclusion relations between the classes can be represented in a tree where ascendancy represents inclusion.

Example 4 Let n = 4 and R = 10. Assume that the current branching constraints are:

ν(x 2 , x 3 , x 4 ) ≥ 1 , (29) ν(x 2 , x 3 , x 4 , x 1 ) ≥ 1 , (30) ν(x 2 , x 3 , x 1 ) ≥ 1 , (31) ν(x 2 , x 1 ) ≥ 4 , (32) ν(x 2 , x 1 , x 4 ) ≥ 2 , (33) ν(x 2 , x 1 ) ≥ 3 , (34) ν(x 2 , x 1 , x 3 , x 4 ) ≥ 1 . ( 35
)
The associated tree of column classes is given in Figure 4. Definition 4 Given a collection {G k } k=1,...,K of nested column classes, we define the associated "tree of column classes" as follows. The root node is associated with G. The leaf nodes represent classes G l that have no subclass in the collection, i.e., G j ⊂ G l for all j = 1, . . ., K with j = l. The node associated with G l hangs from that associated with G j , if G l ⊂ G j and there is no k such that G l ⊂ G k ⊂ G j . In that case, G l is a "direct successor" of G j and G j a "direct predecessor" of G l . More generally, we say that class G l is a "predecessor" of G j if G l ⊃ G j , and G l is a "successor" of G j if G l ⊂ G j . The set of column classes that are direct successors of G l is denoted dsucc(l); the direct predecessor is denoted d pred(l); the set of all predecessors (resp. successors) of G l is denoted pred(l) (resp. succ(l)).

G G(x 2 , x 3 , x 4 ) G(x 2 , x 3 , x 4 , x 1 ) G(x 2 , x 3 , x 1 ) G(x 2 , x 1 ) G(x 2 , x 1 , x 4 ) G(x 2 , x 1 ) G(x 2 , x 1 , x 3 , x 4 )
Observation 3 At a given branch-and-price node, the branching constraints induce a specific ordering of the columns.

Because the collection of column classes {G k } k=1,...,K defines a nested partition of G, all the associated component bound sequences S k , k = 1, . . . , K, must start with a bound on the same component (as illustrated in Example 4): 0 x 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 x 2 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 x 3 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 x 4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

G l ⊂ G j ⇔ S j ⊂ S l ⇔ ẍ[p] (S l ) = ẍ[p] (S
The ordering induced by the nested branching sequences is g 8 1 9

2 3 10 11 4 6 5 7 12 13 14 15 νg 1 0 0

3 4 1 4 0 1 1 1 1 1 1 3 2 1 2 0 x 2 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 x 3 1 1 1 0 0 0 0 x 1 1 1 1 1 0 0 0 0 x 4 1 0 0 x 1 1 1 0 0 x 4 1 1 0 0 x 3 1 1 0 0 x 1 0 1 0 x 4 1 0 1 0 x 3 1 0 1 0 x 4 1 0 1 0
Definition 5 Given a nested collection of component bound sequences {S k } k=1,...,K , the so-called "induced lexicographic order" (ILO) is the ordering defined by sorting the columns, g ∈ G, using the operator of Table 3 called with parameters C = {S k } k=1,...K , S =<>, I = {1, . . . , n}, and p = 1.

Table 3: Definition of the operator g 1 ≺ (C, S, I, p) g 2 .

1. If C = / 0, return x g 1 I ≺ x g 2 I where x g I stands for the characteristic vector of column g restricted to its components i ∈ I and x a ≺ x b is the standard lexicographic operator that returns true if x a is before x b in lexicographic order and false otherwise.

2. Let i be the component such that ẍ[p] = ẍi in all S k ∈ C.

If x

g 1 i = x g 2 i = 1, return g 1 ≺ (C(< S, x i >), < S, x i >, I \ {i}, p + 1) g 2 ; 4. If x g 1 i = x g 2 i = 0, return g 1 ≺ (C(< S, x i >), < S, x i >, I \ {i}, p + 1) g 2 ;
5. return true if (x

g 1 i > x g 2 i
) and false otherwise.

In the sequel, we always assume that columns are sorted using the ILO. To simplify the notation, the precedence relation g 1 ≺ g 2 is now meant to say g 1 precedes g 2 in the ILO. Furthermore, any reference to the mapping procedure of Table 1 assumes an ILO sorting of the columns.

The procedure to separate a fractional master solution, ν, can now be easily described. To achieve a nested partition of the column set, separation must be done either by further partitioning a class G k of the current collection {G k } k=1,...,K or its complementary class, G k , or by resetting the bound on an existing class, G k . Intuitively, a candidate component sequence on which to branch is identified by taking the set of fractional columns down the tree of column classes and checking the value of column classes for fractionality, as illustrated in Figure 5. Three cases may arise as outlined in Table 4. Formally, separation proceeds as follows. Let i be the first component present in all previous branching sequences S k , k = 1, . . . , K, i.e., ẍ [START_REF] Barnhart | Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems[END_REF] is either

G a: ν(x 1 ) ∈ IN ? c: partition G(x 1 ) G(x 1 , x 2 ) b: ν(x 1 , x 2 ) ∈ IN ? c: partition G(x 1 , x 2 )
x i or x i in all S k . Let F = {g : νg -⌊ νg ⌋ > 0} = / 0 and ν(x i ) = ∑ q∈F:x g i =1 ( νg -⌊ νg ⌋). If ν(x i ) ∈ IN, we can branch on S =< x i >.
Otherwise, we recursively explore both sets of fractional columns F(< x i >) , F(< x i >) (if not empty) in search of a set S on which to branch. When no more previous branching sequence dictates the next component, we call the subroutine Separate of Table 2. The complete separation procedure is presented in Table 5. As above, C stands for the set of component bound sequences associated with branching constraints defining the current node, S is the component bound sequence defining the current column class, p denotes the next position to be considered in the sequences of C, C(S) is the subset of sequences starting with S, I is the set of components that are candidate for further partitioning of the current column class, and record gathers the set of possible branching sequences. Its use is illustrated in Example 6.

Example 6 (Example 5 continued) It is more convenient to follow the separation procedure in the second table of Example 5 that represents the master LP solution sorted in ILO. Note that ν(F) = 3.

The future branching sequence, S, must start with x 2 or x 2 . Partitioning according to component 2 splits the set of fractional columns, with ν(F(x 2 )) = 1 and ν(F(x 2 )) = 2. Component 3 does not allow us to partition F(x 2 ) further since all the fractional columns of G(x 2 ) have x 3 = 1; neither does component 1. Thus, ν(F(x 2 , x 3 , x 1 )) = 1 must be further split using routine Separate which returns S 1 =< x 2 , x 3 , x 1 , x 4 >. On the other hand, set F(x 2 ) cannot be partitioned further with component 1, but component 3 yields a fractional value subset. Thus, another possible branching sequence is S 2 =< x 2 , x 1 , x 3 >. One of these two branching sequences is selected according to branching priorities.

Let us consider the complexity of the separation procedure of Table 5. The routine Explore is called recursively and, on each leaf of the tree of recursive calls to Explore, routine Separate is called (c) Let α i = ∑ g∈F x g i νg and f = α i -⌊α i ⌋.

(d) Check whether class G(< S, x i >) has fractional value:

If f > 0, add the pair (< S, x i >, f ) to record and return.

(e) Recursively explore the first subclass of columns, G(< S, x i >):

If α i > 0, Explore(C(< S, x i >), p + 1, F(< S, x i >), I \ {i}, < S, x i >, record).
(f) Recursively explore the second subclass of columns, G(< S, x i >):

If α i < ν(F), Explore(C(< S, x i >), p + 1, F(< S, x i >), I \ {i}, < S, x i >, record).
3. Select a branching sequence S in record according to branching priorities on its last component.

recursively. However, the overall depth of the tree of recursive calls is bounded by the number of components, n, and the overall number of leaf nodes in the tree of recursive calls to Explore and Separate is bounded by |F|, since the fractional column set is partitioned at each stage and we only explore non-empty subsets. The work done in a call to Explore is in O(|F|) while that in a call to Separate is O(n|F|). Hence, the overall complexity of the procedure is O(n 2 |F| 2 ) as it was at the root node. Here too, one can reduce the complexity by exploring only the smallest value subset of fractional columns (selecting step (e) or (f)). However, exploring both sides often allows us to identify a branching sequence S with fewer component bounds (as illustrated in Example 5) or higher branching priority.

In practice, the branching sequence, S, is in most cases obtained by adding a single component bound to a previously defined set S k associated with an active branching constraint, whether S k is associated with a leaf node class or not. Case b of Table 4 often consists in resetting the bound of a class whose parent class defines an active branching constraint. Exploiting Lemma 1 in these situations yields a restriction in the number of successor nodes to only two nodes. More generally, Proposition 3 The set of descendant nodes defined in [START_REF]User guide and Reference Manual[END_REF](28) can be restricted to only nodes: k, . . . , |S|+ 1, where S is the sequence chosen for branching to eliminate the current fractional solution, ν, and k is the size of the largest subsequence S k of S for which a previously defined branching constraint

ν(G k ) ≥ L k is active, i.e., L k = ν(G k ).
The proof is a straightforward application of Lemma 1: if constraint ν(G k ) ≥ L k is enforced, no integer solution exists with ν(G k ) < L k , and hence, there is no need to enumerate descendant nodes whose only purpose was to consider integer solutions with ν(G k ) < L k . Moreover, one can further prune the enumeration tree by dominance: Observation 4 A branch-and-price node, N 1 , defined by a branching constraint ν(G k ) ≥ L k needs not be generated if it has an ancestor node, N 0 , whose direct successor, N 2 , is defined by the same constraint.

Indeed, in such case, integer solutions satisfying all branching constraints defined at node N 0 and constraint ν(G k ) ≥ L k are already enumerated in node N 2 . Thus, Proposition 3 and Observation 4 explain why in practice the branch-and-bound tree can be close to be binary.

To conclude this section, we analyse the impact of our branching constraints in the variable space of the original formulation. We begin by an informal illustration. Returning to Example 3, we indicate the progress in reaching primal integrality that is made implicitly with each new branching constraint.

Example 7 (Example 3 continued) Assume a fractional solution ν and associated column class values

ν(x 1 , x 2 ), ν(x 1 , x 2
) and ν(x 1 ) given by: νg 0 1 2 1 1 2 0 0 1 1 0 0 1 2 0 1 2 0 0 x 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 x 2 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 x 3 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 x 4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

(x 1 ) (x 1 ) (x 1 , x 2 ) (x 1 , x 2 ) 1.5 1.5 2
Let xr for r = 1, . . ., 5 be the associated solution obtained from the mapping procedure of Table 1.

Observe that for r = 1 vector xr is entirely determined from columns of class G(x 1 , x 2 ); for r = 3, from columns of class G(x 1 , x 2 ); for r = 4 and 5 from columns of class G(x 1 ); while for r = 2, xr is partially derived from columns of class G(x 1 , x 2 ) and partially from columns of class G(x 1 , x 2 ).

Now let us see the consequence of branching constraints on the projected solutions xr . Branching induces modification of the widths of the "strips" (see Definition 1) associated with the different column classes:

• In Node(1), ν(x 1 ) ≥ 3 implies that three xr vectors resulting from the mapping of Table 1 after branching will be derived from the columns of class G(x 1 ) and hence xr 1 = 0 for at least 3 rindices (while before branching we had xr 1 = 0 for only 2 r-indices). We say that component x r 1 is now "covered" (or fixed) for 3 r-indices.

• In Node(3), ν(x 1 , x 2 ) ≥ 2 ⇒ xr 1 = xr 2 = 1 for at least 2 r-indices (while before branching we had xr 1 = xr 2 = 1 for a single index r). We say that x r 1 and x r 2 are now "covered" for 2 r-indices.

• In Node(2), we would expect that constraint ν(x 1 , x 2 ) ≥ 2 implies xr 1 = 1 and xr 2 = 0 for at least 2 r-indices (while at the ancestor node xr 1 = 1 and xr 2 = 0 for a single index r). But class G(x 1 , x 2 ) that precedes class G(x 1 , x 2 ) in the lexicographic order can take a fractional value. If it does so, the "strip" of width 2 associated with class G(x 1 , x 2 ) would not coincide exactly with two x r vectors in the mapped solution. We say that the G(x 1 , x 2 )-strip is " floating" over 2 r-indices.

A more formal presentation requires the definition of what we call a "frame" for each branching constraint ν(S) ≥ L. Following up on Definition 1, the branching constraint can be seen intuitively as imposing a minimum width L to a G(S)-strip (remember that columns of G(S) are consecutive in the ILO sorting). This strip can be later subdivided if branching constraints are introduced on subsets of class G(S). Nevertheless, the branching constraint ν(S) ≥ L already fixes part of the x solution obtained through the mapping of Table 1: the contribution of the columns of the strip to the definition of x r vectors is fixed for all i ∈ S. Hence, we refine the concept of a strip by introducing a frame that can be understood as a strip on a specific selection of consecutive lines i ∈ S in the table representing a master solution in ILO.

Definition 6 Let S be a component bound sequence and L ∈ IN be the associated width. Then, the "(S, L)-strip" relative to a master solution ν is made of the first columns of G(S) up to value L in the table representing the master solution in ILO: it is a G(S)-strip of width L. It is precisely defined by an interval of cumulative values of columns in the ILO sequence:

V (S, L) = [ ∑ g: g≺G(S) νg , ∑ g: g≺G(S) νg + L) .

The interval is closed on the left and open on the right. The notation g ≺ G(S) says that column g is prior to those of G(S) in the ILO. An "(S, L)-frame" is the restriction of an "(S, L)-strip" to a selection of consecutive lines i ∈ S.

We say that a component x r i of the x solution obtained through the procedure of Table 1 is "covered" by the (S, L)-frame if i ∈ S and (r -1) ∈ V (S, L) (in other words, the strip of width 1 that is associated with xr begins in the (S, L)-strip). Thus, an (S, L)-frame covers L |S| components x r i .

Example ------------------------------

1 1 2 1 2 1 4 1 4 1 2 1 1 1 1 1 1 1 2 1 2 --- --------- ------------------- ----------------- x 2 1 1 1 1 1 1 0 0 0 0 0 0 0 0 x 3 1 1 0 0 0 0 x 1 1 1 1 1 0 0 0 0 -
x 4 1 0 x 1 1 1 1 0 x 4 1 1 0 0 x 3 1 1 1 0 ---- --------- ------- x 1 0 0 x 4 1 1 0 0 x 3 1 0 1 0 x 4 1 0 0 1 --- -- r = 1 r = 2 r = 3 r = 4 r = 5 r = 6 r = 7 r = 8 r = 9 r = 10
Components x r i are covered by the (< x 2 , x 3 , x 4 >, 1)-frame for r = 1 and i ∈ {2, 3, 4}; there are covered by the (< x 2 , x 3 , x 4 , x 1 >, 1)-frame for r = 1 and i ∈ {2, 3, 4, 1}, by the (< x 2 , x 3 , x 1 >, 1)frame for r = 3 and i ∈ {2, 3, 1}, by the (< x 2 , x 1 >, 4)-frame for r ∈ {4, 5, 6, 7} and i ∈ {2, 1} by the (< x 2 , x 1 , x 4 >, 2)-frame for r ∈ {4, 5} and i ∈ {2, 1, 4} by the (< x 2 , x 1 >, 3)-frame for r ∈ {8, 9, 10} and i ∈ {2, 1}, and by the (< x 2 , x 1 , x 3 , x 4 >, 1)-frame for r = 8 and i ∈ {2, 1, 3, 4}. Although the (S, L)-frames are not disjoint, the (S, L)-strips are nested. A component can be covered by multiple frames.

To formalize the impact of branching constraint, ν(S) ≥ L, on the x solution obtained through the mapping of a master solution, ν, note that:

Observation 5 If the columns preceding those defining an (S, L)-frame in the ILO have a total value that is integer, i.e., if v = ∑ g: g≺G(S) νg ∈ IN, then interval V (S, L) has integer extreme points and each component x r i "covered" by the (S, L)-frame has integer value in the x solution obtained through the mapping of Table 1. More precisely, xr

i = 1 if x i ∈ S and xr i = 0 if x i ∈ S ∀i ∈ S, r = v + 1, . . . , v + L.
If v ∈ IN, the (S, L)-frame boundaries define strips that encompass exactly L consecutive x r vectors.

Thus, the (S, L)-frame associated with branching constraint ν(S) ≥ L can be understood as defining a set of x r i components that are potentially fixed to an integer value in the mapped x solution. However, the frame is "floating" around, i.e., the specific r-indices for which this fixing shall occur may change. The boundaries of the frame fall precisely in between r-indices only when ILO preceding columns sum up to an integer value. Allowing such "floating" is a way to avoid the symmetry in r. Nevertheless, the integrality of the associated x solution shall be achieved at some stage: Proposition 4 Consider a branch-and-price node defined by a nested collection of component sets and associated bounds {(S k , L k )} k=1,...,K and a master solution ν. If, in the x solution derived through the mapping of ν as defined in Table 1, every x r i component is "covered" by some (S k , L k )-frame for i = 1, . . . , n and r = 1, . . . , R, then the x solution obtained through the mapping of Table 1

is integer.

Proof: We prove that if the x solution derived through the mapping of Table 1 is fractional, there exists an x r i component that is not covered by any (S, L)-frame. By Proposition 1, if the mapped x solution is fractional, then the master solution ν must be fractional. Let g 1 be the first column in the ILO with fractional value: 0 < λ r g 1 < 1 for r = ∑ g≺g 1 νg + ⌈ νg 1 ⌉. Let g 2 be the first column in ILO such that g 1 ≺ g 2 and λ r g 2 > 0. Let i be the first index in the index ordering underlying the ILO for which x

g 1 i = x g 2 i . Then, xr i ∈ {0, 1}.
Assume by contradiction that component x r i is covered by an (S, L)-frame associated with some branching constraint of the nested collection defining the current node. By Definition 6, this means that i ∈ S and (r -1) ∈ V (S, L). Let i be the p th component for which a bound is defined in sequence S: S =< ẍ [START_REF] Barnhart | Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems[END_REF] , . . . , ẍ[|S|] >, ẍ[p] = x i or x i , and p ≤ |S|. Now observe that by definition of g 1 , ∑ g≺g 1 νg ∈ IN. Thus, by definition of r, column g 1 is the first column of the r th -strip. I.e., column g 1 is found at position (r -1) in the ILO: ∑ g≺g 1 νg ≤ r -1 and

∑ g≺g 1 νg + νg 1 > r -1. Therefore, if x r
i is covered by an (S, L)-frame, we must have g 1 ∈ G(S). This implies that the first p component bounds of S are satisfied by the characteristic vector x g 1 . But, by definition of i,

x g 1 i = x g 2 i . As i ∈ S, g 2 ∈ G(S). Because g 1 ∈ G(S)
is the first column with fractional value in the ILO and g 2 ∈ G(S) is the first column with positive value following g 1 in the ILO, the (S, L)-frame must have its right boundary at value ∑ g≺g 2 ν g ∈ IN. This is a contradiction. Indeed, the right boundary of the (S, L)-frame should have been at an integer value since its left boundary is at an integer value and L ∈ IN. Hence, no (S, L)-frame can cover x r i .

Although a component x r i can be covered by several frames, the nested definition of branching constraints guarantees that each (S k , L k )-frame that covers an x r i imposes the same bound on x r i . More specifically:

Observation 6 When the x solution derived through the mapping of Table 1 is integer, each x r i component that is covered by an (S, L)-frame has a value in x that is prescribed by the associated component bound in S.

This observation results from Proposition 1 and Observation 5. Indeed, x being integer implies that ∑ g: g≺G(S) νg ∈ IN, for all (S, L)-frames.

To guarantee that progress is made in reaching primal integrality in the x-space with each new branching constraint, we need to show that each frame yields coverage of at least one "new" x r i component. This property is only implicit as we cannot exhibit a fixed pair (i, r) for which x r i is covered by the new branching constraint.

Definition 7

The "representative" of an (S, L)-frame is the covered x r i component such that i is the last component of S in the sense of Definition 2, and r is the largest index such as (r -1) ∈ V (S, L), where V (S, L) is the interval of Definition 6.

In other words, the "representative" of an (S, L)-frame is the "bottom-right" component from amongst all the x r i that are covered by this frame. We can show that a given x r i component can be the representative of only one frame: Proposition 5 Consider a branch-and-price node defined by a nested collection of component sets and associated bounds, {(S k , L k )} k=1,...,K , and any feasible solution, ν, to the master LP at that node. In the associated x solution, obtained through the mapping procedure of Table 1, a given x r i component can be the "representative" of at most one (S k , L k )-frame.

Proof: Assume by contradiction that component x r i is the representative of two distinct frames: the (S 1 , L 1 ) and the (S 2 , L 2 )-frame. The fact that component x r i is covered by both frames implies that (r -1) ∈ V (S 1 , L 1 ) ∩ V (S 2 , L 2 ). Take the column g with νg > 0 that lies at width (r -1) in the G-strip of columns sequenced in ILO, i.e., ∑ γ≺g νγ ≤ r -1 and

∑ γ≺g νγ + νg > r -1. As (r -1) ∈ V (S 1 , L 1 ) ∩ V (S 2 , L 2 ), we must have g ∈ G(S 1 ) ∩ G(S 2
). Hence, the component bounds defining S 1 and S 2 must be set to the value found in x g . Moreover, as i is the last component of both S 1 and S 2 , in the sense of Definition 2, we must have |S 1 | = |S 2 |, and thus S 1 = S 2 . Now, as the G(S 1 )-strip and the G(S 2 )-strip start at the same point in the ILO table, and as r is the furthest right index for both the (S 1 , L 1 ) and the (S 2 , L 2 )-frame, we must have L 1 = L 2 . Thus, both frames must be identical in contradiction to our assumption. Thus, although frames may overlap, Proposition 5 gives us a way to show that the number of covered x r i components increases in each branch. Intuitively, each (S, L)-frame is unique and has its own "representative". Hence, each frame can be given credit for ensuring the covering of at least its "bottom-right" component. Observation 6 says that an x r i component that is covered is implicitly fixed to a binary value. In that sense, each branching constraint implicitly fixes at least one x r i component to its integer value in the mapped solution obtained through the procedure of Table 1. Building on this intuition, we can show formally that the scheme ends up with an integer solution after adding at most n R branching constraints. What is more, even though the branching tree is not binary, we can show that the number of leaf nodes is bounded by 2 nR . Proposition 6 With the proposed branching scheme, the depth of the branch-and-price tree is bounded by n R and the number of leaf nodes is bounded by 2 nR .

Proof: Each branching constraint defining a node is different (see Observation 1) and defines its own (S, L)-frame relative to the current master LP solution that covers L |S| components of the x solution obtained through the procedure of Table 1 (see Definition 6), including its "bottom-right representative". By Proposition 5, any x r i component can be the representative of at most one frame. Hence, by the pigeon hole principle, each x r i component must be "covered" after at most n R branches. Once each x r i component is covered, the mapped x solution is integer (by Proposition 4) and so is the associated master solution ν (by Proposition 1). Thus, we have shown that after at most n R branches, we get an integer solution. Now, Observation 6 tells us that, in this integer solution, each x r i component takes the value that is prescribed by the S associated with the covering frame: xr i = 1 if x i ∈ S and xr i = 0 if x i ∈ S. Thus, there are 2 possible values for each of the n R components and hence at most 2 n R leaf nodes in the branch-and-price tree.

Solving the master after branching

At a given branch-and-price node, the master LP takes the form:

min ∑ g∈G c x g ν g (36) [M(node)] ∑ g∈G A x g ν g ≥ a (π) (37)
∑ g∈G ν g = R (σ 0 ) (38)
∑

g∈G k ν g ≥ L k (σ k ) ∀k = 1, . . . , K (39)
ν g ≥ 0 ∀g ∈ G (40)
where constraints ∑ g∈G k ν g ≥ L k are branching constraints and (π, σ ) denotes the dual solution.

As underlined in Observation 1, each branching constraint is different. However, the collection {(S k , L k )} k=1,...,K could include (S 1 , L 1 ) and (S 2 , L 2 ) with S 1 = S 2 but L 1 < L 2 (such (S 2 , L 2 ) can result from case b of Table 4). Then, branching constraint ν(S 2 ) ≥ L 2 clearly dominates ν(S 1 ) ≥ L 1 and the latter can be deleted from the formulation. Hence, in the sequel we assume that each branch-and-price node is defined by the nested collection of component sets and associated bounds, {(S k , L k )} k=1,...,K where no two of the associated branching constraints, ν(S k ) ≥ L k , concern the same column class, G k = G(S k ). Even then, some branching constraints may be dominated by others:

Definition 8 We say that branching constraint ν(S k ) ≥ L k is "redundant" if ∑ l∈dsucc(k) L l ≥ L k (41)
(using the notation of Definition 4). The "marginal lower bound" imposed on a column class G k by branching constraint ν(S k ) ≥ L k is defined as

L k = L k -∑ l∈dsucc(k) L l .

It is strictly positive if and only if the branching constraint is non-redundant.

In example 4, illustrated in Figure 4, branching constraint (29) is redundant: its marginal lower bound is zero.

Observe that redundant branching constraints will remain so at descendant nodes. Hence, in the sequel, we assume that redundant branching constraints have been eliminated from the set of branching constraints defining the current branch-and-price node. These simplifications allow us to derive a useful property: Proposition 7 The number of non-redundant branching constraints at a branch-and-price node is at most R; otherwise, the node problem is infeasible.

Proof: Assume a branch-and-price node defined by the collection {(S k , L k )} k=1,...,K . The nonredundant branching constraints can be equivalently reformulated as

ν(C k ) ≥ L k for k = 1, . . ., K, where class C k ⊆ G is defined as, C k := (G k \ (∪ i∈dsucc(k) G i )),
) implies ν(G) ≤ R. Hence, the system ν(C k ) ≥ L k ≥ 1 for k = 1, . . . , K, ν(G) ≤ R, is infeasible if K > R (this statement
formalizes what is known as the "pigeon hole principle").

After elimination of redundant branching constraints, the master program, [M(node)], is solved by column generation using a pricing procedure that relies only on the oracle of the root node. To each non-redundant branching constraint, ν(S k ) ≥ L k , k = 1, . . ., K, we associate a subproblem, [SP k ], to price the columns of G k :

[SP k ] ζ k (π) := min{(c -πA)x : x ∈ X k } , (42)
where

X k := {x ∈ {0, 1} n : B x ≥ b, ẍi = 1 ∀i ∈ S k }. While [SP 0
] is defined by [START_REF] Ryan | An integer programming approach to scheduling[END_REF], or equivalently (42) with X 0 := X . Each of these pricing subproblems can be solved with the oracle provided for pricing problem [START_REF] Ryan | An integer programming approach to scheduling[END_REF]: additional constraints consist only in fixing the value of some binary variables.

If pricing problem [SP k ] is infeasible (i.e., X k = / 0), let ζ k (π) = ∞.
The column generation procedure can be carried out by solving each pricing problem (42), for k = 0, . . ., K, and returning columns that have negative reduced costs, i.e., returning x k := argmin ζ k (π), if ζ k (π) -∑ l∈pred(k) σ l < 0 (using the notation of Definition 4). If none can be found, the current master LP value is optimal.

Observe however that pricing subproblems (42) are not independent. Solving pricing problem l over a class G l ⊃ G j is solving a relaxation of problem j since the objective functions of both problems are identical:

Observation 7 If G l ⊃ G j (i.e., S l ⊂ S j ), ζ l (π) ≤ ζ j (π) (i.e., ζ l (π) defines a dual bound for [SP j ]).
If the solution to [SP l ], seen as a relaxation of [SP j ], is feasible for [SP j ], then it is optimal for it:

Observation 8 If x l := argmin ζ l (π) and x l ∈ G j ⊂ G l , then x l = argmin ζ j (π).
To exploit the relationships that exist between pricing subproblems, [SP k ], column generation can proceed by enumerating subproblems following a breadth first search in the associated tree of column classes of Definition 4. Then, one can interrupt the procedure as soon as a negative reduced cost column is found and still have a dual bound on the reduced cost of unsolved subproblems. Indeed, for the unsolved pricing subproblems, a dual bound is provided by the value of any of their predecessor in the column class tree that has been solved. Such a procedure is outlined in Table 6. As the procedure stops at the first identified negative reduced cost column, the order in which subproblems are treated is important (we use a heuristic rule to break ties in the sorting of step 1, giving priority to subproblem SP k with the largest

L k σ k ).
Table 6: The column generation procedure. (Notations pred(k), d pred(k), dsucc(k) are from Definition 4; x k denotes the solution of subproblem [SP k ], i.e., x k = argmin ζ k (π).)

1. Sort subproblems, SP k , following the partial order defined by the precedence relation between the associated column classes in the tree representation of Definition 4.

2. For each pricing subproblem SP k in the sorted list, do

(a) If x d pred(k) ∈ G k , continue (x d pred(k) also solves SP k ). (b) If ζ d pred(k) (π) -∑ j∈pred(k) σ j -σ k ≥ 0, continue (SP k shall not yield a negative reduced cost column). (c) Compute ζ k (π) and x k . (d) If ζ k (π) -∑ j∈pred(k) σ j -σ k < 0, return
x k and Stop (x k yields a negative reduced cost column).

(e) If x k is feasible for any SP l with l ∈ dsucc(k), let x l = x k . If, moreover, ζ k (π) -∑ j∈pred(l) σ j -σ l < 0, return x l and Stop (x l yields a negative reduced cost column).

Lagrangian dual bounds

At each iteration of the column generation procedure, a valid dual bound on the master solution can be obtained by Lagrangian relaxation. Dualizing constraints (37) yields

π a + min{ ∑ g∈G (c -π A) x g ν g : ∑ g∈G ν g = R; ∑ g∈G k ν g ≥ L k , k = 1, . . . , K; ν g ≥ 0, g ∈ G} . (43)
Because column classes are nested, this problem admits a closed form solution.

Proposition 8

The solution of problem ( 43) is

θ (π) := π a + K ∑ k=0 L k ζ k (π) (44)
where G 0 = G, L 0 = R, and L k are the marginal lower bounds of Definition 8.

Proof:

The result follows from Observation 7 that implies ∑ g∈G k ν * g = L k ∀k in an optimal solution ν * to (43). More specifically, ν *

g = L k for g ∈ G k such that x g = argmin ζ k (π).
Observe that a Lagrangian dual bound can be computed even if the column generation procedure falls short of solving every pricing subproblems SP k defined by (42). Replacing ζ k (π) by a dual bound, ζ k (π), on SP k in (44) yields a valid dual bound for [M(node)]. Observation 7 points naturally to a pricing subproblem dual bound, ζ k (π) = ζ l (π), obtained when pricing on a predecessor class, l ∈ pred(k). Thus, provided that we enumerate the pricing subproblems following a breadth first search in the associated tree of column classes, an approximation of θ (π) can easily be computed at any stage of the column generation procedure: θ (π)

:= π a + ∑ k∈G L k G ζ k (π)
, where G is the set of solved subproblems and

L k G = L k -∑ l∈dsucc(k)∩G L l .
An important property of our branching scheme is that branching constraints are enforced in the subproblem, which yields stronger dual bounds than when they are enforced in the master and hence dualized.

Proposition 9 Upon completion of the column generation procedure, the dual bound (44) yields the value of a Lagrangian dual problem whose primal formulation is

min{ ∑ r cx r : ∑ r Ax r ≥ a, x r ∈ conv(X k ) for r = ρ k-1 , . . . , ρ k -1, k = 0, . . . , K} (45)
where ρ -1 = 1, and ρ k = ρ k-1 + L k for k = 0, . . . , K.

Proof: Note that formulation [M(node)] given in (36-40) is equivalent to the disaggregated master:

min{ K ∑ k=0 ρ k -1 ∑ r=ρ k-1 ∑ g∈G k c x g λ r g : K ∑ k=0 ρ k -1 ∑ r=ρ k-1 ∑ q∈G k A x g λ r g ≥ a; ∑ g∈G k λ r g = 1 ∀k, r = ρ k-1 , . . . , ρ k -1; λ r g ≥ 0 ∀r, q} . (46)
By Geoffrion [START_REF] Geoffrion | Lagrangian relaxation for integer programming[END_REF], (46) has an optimal LP value equal to that of (45).

Observation 9

The Lagrangian dual problem value given by ( 45) is tighter than the bound given by [START_REF] Thienel | ABACUS -A Branch-And-CUt System[END_REF] for which the dualized branching constraints are included in ∑ r A x r ≥ a.

Preprocessing at a branch-and-price node

The first preprocessing operation at a node consists in deleting redundant branching constraints: keep at most one constraint per class G k (that with the largest L k ); then delete constraints with no strictly positive marginal lower bounds, i.e., with L k ≤ 0. The remaining constraints must satisfy

∑ K k=1 L k ≤ R,
otherwise the node is pruned by infeasibility. For the rest of this section, we include in the collection of branching constraints, the master convexity constraint [START_REF] Parker | A column generation algorithm for brandwidth packing[END_REF] with index k = 0, letting G 0 = G, S 0 be the empty sequence, and

L 0 = R -∑ k∈dsucc(0) L k .
Observe that constraints defined by the collection {(S k , L k )} k=0,...,K induce bounds on the value of aggregate subproblem variables defined in [START_REF] Vanderbeck | Computational Study of a Column Generation algorithm for Bin Packing and Cutting Stock Problems[END_REF]:

(∑ k:S k ∋x i L k ) and (∑ k:S k ∋x i L k ) define respectively
a lower and an upper bound on the value of aggregate variable x i . One must check that these bounds are compatible with the bounds induced by constraints (3) and ( 5). The latter are denoted by gl i and gu i (for global lower and upper bounds):

gl i ≤ ∑ r x r i ≤ gu i i = 1, . . ., n . (47)
The current node master problem [M(node)] is infeasible if

∑ k:S k ∋x i L k > gu i or (48) ∑ k:S k ∋x i L k < gl i (49)
for some i.

On the other hand, if the branching constraints imply that the global upper bound for component i is reached, i.e., if

∑ k:S k ∋x i L k = gu i , (50)
then the classes where component i is not fixed, {k : i ∈ S k }, can be augmented with component bound restriction x i = 0. This restriction takes the form of implied branching constraints: given a component i satisfying (50), we define a new branching constraint,

ν(S k , x i ) ≥ L k - ∑ l∈dsucc(k):S l ∋x i L l , (51)
for all k : S k ∋ i (the notation dsucc(.) is from Definition 4). Observe that constraint (51) makes branching constraint k redundant and hence it simply replaces it. Also note that this operation preserves the nested partition property. Indeed, once all branching constraints k : S k ∋ i are processed in this way, all the redefined branching sequences S k for k = 1, . . ., K include a component bound on i (i.e., either x i or x i ). Thus, this component can be brought in the first position in all sequences and this guarantees that the branching constraints still define a nested partition of the solution space.

Reciprocally, if the global lower bound on a component i can only be met by setting

x g i = 1 in all columns of classes, k : S k ∋ i, i.e., if ∑ k:S k ∋ x i L k = gl i , then, branching constraints indexed by k : S k ∋ i can be reset as ν(S k , x i ) ≥ L k - ∑ l∈dsucc(k):S l ∋x i L l (52)
and this component is placed in first position in all sequences. We refer to such preprocessing as "further specification of column classes".

Another form of preprocessing consists in "deleting columns" that are no longer needed. Note that when class G is redundant, i.e., when ∑ k∈dsucc(root) L k = R, columns in G \ ∪ k∈dsucc(root) G k can be deleted from the formulation. Such preprocessing can be generalized to any class k such that

∑ l∈dsucc(k) L l = U k , ( 53
)
where U k is a valid upper bound on class k value. Then, columns of G k \ ∪ l∈dsucc(k) G l can be deleted.

The upper bound U k can be set for instance to min{R -

∑ l:l =k,l ∈succ(k) L l , min i:x i ∈S k {gu i - ∑ l:l =k,l ∈succ(k),S l ∋x i L l }, min i:x i ∈S k {R - ∑ l:l =k,l ∈succ(k),S l ∋x i L l -gl i } } .
Note that, as L k ≤ U k , (53) implies that L k ≤ 0, i.e., class G k is associated with a redundant branching constraint. Hence, in our pricing procedure, we will not generate columns from class G k \ ∪ l∈dsucc(k) G l , but we shall only consider its active subclasses, G l for l ∈ succ(k).

The set partitioning special case

When the master program is a set partitioning problem of the form [START_REF] Vanderbeck | Exact Algorithm for minimising the number of setups in the onedimensional cutting stock problem[END_REF], preprocessing is particularly effective as global bounds (47) are tight: gl i = gu i = 1 ∀i. Example 9 illustrates this on the bin packing problem.

Example 9

The bin packing problem takes the form [START_REF] Vanderbeck | Exact Algorithm for minimising the number of setups in the onedimensional cutting stock problem[END_REF] where G is the set of solutions to a binary knapsack problem:

X = {x ∈ {0, 1} n : ∑ i w i x i ≤ W } . ( 54
)
Let n = 5, w = (6, 4, 3, 2, 7), W = 10 and R = 3. The generators are: g 1 2 3 4 5 6 7 8 9 10 11 12 13 14 x 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 x 2 1 0 0 1 1 1 1 0 0 0 0 0 0 0 x 3 0 1 0 1 1 0 0 1 1 1 0 0 0 0 x 4 0 0 1 1 0 1 0 1 0 0 1 1 0 0 x 5 0 0 0 0 0 0 0 0 1 0 1 0 1 0

The master LP solution is 7 3

with ν1 = 2 3 , ν3 = ν4 = 1 3 , ν9 = 2 3 , ν11 = 1 3 , ν14 = 2 3 .
Then, branching on S =< x 1 , x 2 > yields 3 nodes: 49) for i = 1). Now, let us examine Node(3) (the preprocessing of Node(2) being symmetric). Preprocessing detects that, as item 1 is entirely covered by columns of class G(x 1 , x 2 ), we can add an implied branching constraint ν(x 1 ) ≥ R -1 = 2. Similarly item 2 is entirely covered by class G(x 1 , x 2 ). Thus, the branching constraints are redefined as ν(x 2 , x 1 ) ≥ 1 and ν(x 2 , x 1 ) ≥ 2. Then, class G becomes redundant and columns 2 to 7 can be deleted. Now, the master solution at Node(3) is 5 2 with ν1 = 1, ν8 = ν9 = ν11 = ν14 = 1 2 . Assume that for separation we choose S =< x 2 , x 1 , x 3 , x 4 >. Although |S| = 4, only three successor nodes need to be defined according to Proposition 3. Indeed, Node (3.1) and (3.2) would only aim at enumerating solutions where ν(x 2 , x 1 ) < 2 which contradicts the previous constraint ν(x 2 , x 1 ) ≥ 2. Hence, there remain

Node(1) ≡ ν(x 1 ) ≥ 3 ; Node(2) ≡ ν(x 1 , x 2 ) ≥ 1 ; Node(3) ≡ ν(x 1 , x 2 ) ≥ 1 .

Preprocessing allows us to prune Node(1) by infeasibility (by (

Node(3.3)      ν(x 2 , x 1 ) ≥ 1 ν(x 2 , x 1 ) ≥ 2 ν(x 2 , x 1 , x 3 ) ≥ 2 ; Node(3.4)      ν(x 2 , x 1 ) ≥ 1 ν(x 2 , x 1 ) ≥ 2 ν(x 2 , x 1 , x 3 , x 4 ) ≥ 1 ; Node(3.5)      ν(x 2 , x 1 ) ≥ 1 ν(x 2 , x 1 ) ≥ 2 ν(x 2 , x 1 , x 3 , x 4 ) ≥ 1 .
In Node (3.3), the second constraint is made redundant by the third. Applying (52), the constraints become ν(x 3 , x 2 , x 1 ) ≥ 1 and ν(x 3 , x 2 , x 1 ) ≥ 2. The former constraint makes the problem infeasible, as G(x 3 , x 2 , x 1 ) = / 0. In Node (3.4), preprocessing leads to redefining the branching constraints as ν(x 3 , x 2 , x 1 ) ≥ 1, ν(x 3 , x 2 , x 1 ) ≥ 1 and ν(x 3 , x 2 , x 1 , x 4 ) ≥ 1. While, in Node (3.5) Indeed, for all X k used in the expression of (45), we have X k ⊆ X (X 0 needs not be considered since Proposition 10 says that class G is redundant) and therefore ζ (π) ≤ ζ k (π) and conv(X k ) ⊆ conv( X) for all k.

Extensions

The above presentation of our branching scheme assumes a pure binary subproblem, and a master convexity constraint of the form ∑ g∈G ν g = R. Extensions are possible beyond these assumptions.

First consider the case where subsystems are general mixed integer programs. Then, the mapping of Table 1 becomes a useful tool to check whether a master solution implicitly defines an integer solution for the original formulation: the mapped solution x could define an integer solution even though ν was fractional. The lexicographic ordering remains well defined in the presence of non-binary integer variables or continuous variables. Column classes are defined by integer bounds on the integer variables, e.g., x i ≤ ⌊α⌋ or x i ≥ ⌈α⌉. In the mixed integer case, it is indeed sufficient to impose integrality condition on integer subproblem variables (see [START_REF] Vanderbeck | A Generic View of Dantzig-Wolfe Decomposition in Mixed Integer Programming[END_REF]). A "component bound sequence" S, is a sorted list of triplets including the index of the integer component, the sense of the inequality (upper or lower bound), and the value of the bound. The extension of routine "Separate" of Table 2 implies choosing a bound value for a fractional mapped component x i (a balanced partition of the column set can be achieved by selecting the median value of those encountered in fractional columns); moreover, one must leave the index i as a potential component for further separation in the recursive calls to "Separate". For the preprocessing of Section 9, the lower and upper bounds on aggregate variables take the form In the case of convexity constraints of the form L ≤ ∑ g∈G ν g ≤ U , one needs to check whether ν(G) is fractional. If so, branching starts by fixing the number of columns used in the solution. Then, in Definition 3, the branching scheme based on component sequence S must include an extra node defined by a branching constraint of the form ν(G) ≤ L 0 -1, which yields |S| + 2 descendant nodes in total. The separation routine of Table 2 shall then return class G as the branching set as long as ν(G) ∈ IN. Standard disjunctive branching on class G implicitly serves the purpose of enumerating different possible values for R. As Proposition 2 holds for each of those R, the result extends to the case of convexity constraints of the form L ≤ ∑ g∈G ν g ≤ U .

(∑ k b k i L k ) and (∑ k b k i L k ),

Numerical Testing

The proposed branching scheme is implemented in our generic branch-and-price code prototype, called BaPCod [START_REF] Vanderbeck | BaPCod -A generic Branch-And-Price Code[END_REF]. The current implementation is relatively basic: it does not include all the preprocessing features of Section 9 and does not exploit computation done at previous branch-and-price nodes (column class tree, ILO sorting, and the like are computed from scratch). Computing times also include important overhead for several validity checks such as previous existence of generated columns. Tests on the cutting stock problem (CSP) and its special case, the bin packing problem (BPP) have been carried out on a PC bi-pro dual-core Intel(R) Xeon(R) X5460 3.16GHz with 16GB of RAM under Scientific Linux 5.0. This experimentation illustrates the fact that our proposal is not just a theoretic scheme, but one that behaves relatively well in the computational practice. In particular, our results show that (i) our non-binary branching tree does not grow too large in practice (as predicted by our theoretical arguments) when compare to a more "standard" binary scheme, (ii) that the routines used for the separation of fractional solutions are not too cumbersome (although our rough implementation becomes time consuming on large problems), and (iii) that the increase in the number of calls to the pricing oracles is significant, but the resulting increase in overall time spent in the oracle does not grow in the same proportion since these extra subproblems are easier (this is not reflected in our numerical results because the reported time spent in the pricing procedure includes overhead for managing the tree of subproblems).

To benchmark our results, we compare them with the closest alternative branching scheme that could be used for the CSP and the BPP. Of course, the efficiency of a branching scheme is very sensitive to parametrization (branching priorities and directions). We did not attempt to optimize the parametrization, but we use the same framework for all comparisons. Moreover, we do not make any use of primal heuristics and rely only on the branching scheme to produce integer solutions. A full blown comparison/competition between the branching schemes proposed in the literature for these problems would require competitive implementations using the same framework, parameter tuning and combination with primal heuristics. This is beyond the scope of this paper. Our numerical experiment only aims at demonstrating the practical viability of our theoretical proposal.

The standard column generation formulation for the bin packing problem is given in Example 9. Its generalization to cutting stock problem involves integer right-hand-sides d i ∈ IN for the master constraint and a bounded integer knapsack as pricing problem:

max{ ∑ i π i x i : ∑ i w i x i ≤ W ; 0 ≤ x i ≤ u i ∀i, x ∈ IN n } (63)
where u i = min{d i , W w i }. The subproblem can be transformed into a binary problem with class bound [START_REF] Vanderbeck | Extending Dantzig's Bound to the Bounded Multi-Class Binary Knapsack Problem[END_REF]:

max{ ∑ i n i ∑ j=1 π i 2 j x i j : ∑ i n i ∑ j=1 w i 2 j x i j ≤ W, n i ∑ j=1 2 j x i j ≤ u i ∀i, x i j ∈ {0, 1}∀i j} (64)
where x i j = 1 iff the binary component of multiplicity 2 j associated with item i is selected, and n i = ⌊log 2 u i ⌋ + 1. If one uses the latter extended formulation, one can branch using standard binary disjunctive branching constraint of the form

∑ g∈G x g i j ν g ≤ ⌊α⌋ or ∑ g∈G x g i j ν g ≥ ⌈α⌉ . (65)
Constraints (65) enforce the integrality of the values of aggregate variables x i j . They induce modified item costs, π i j = π i 2 j . Problem (64) can be solved using the branch-and-bound algorithm of [START_REF] Vanderbeck | Extending Dantzig's Bound to the Bounded Multi-Class Binary Knapsack Problem[END_REF] that can handle item costs π i j = π i 2 j (the algorithm is a generalization of the standard branch-and-bound approach of Horowitz and Sahni [START_REF] Horowitz | Computing partitions with applications to the knapsack problem[END_REF] for the 0-1 knapsack).

We compare the branching scheme of this paper to branching rule (65) that was initially tested in [START_REF] Vanderbeck | Computational Study of a Column Generation algorithm for Bin Packing and Cutting Stock Problems[END_REF]. In theory, this rule alone does not suffice to obtain an integer solution; but experimentally it does for some instances. When it does not, [START_REF] Vanderbeck | Computational Study of a Column Generation algorithm for Bin Packing and Cutting Stock Problems[END_REF] completes it by more complex rules of the generic scheme of [START_REF] Vanderbeck | On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm[END_REF], but these lead to pricing problem modifications. Here, we shall simply stop the algorithm when no more branching constraints of the form (65) can be found even though the solution might still be fractional. The size of the branch-and-price tree obtained so far defines a lower bound on what would be the size of the complete tree. When (65) suffices to achieve integrality, our comparative results show that the size of branch-and-price tree obtained with the newly proposed scheme is of the same order of magnitude. The same remark holds for computing times. Table 7 presents our numerical results for the CSP. We compare three branching schemes. (i) We use branching rule (65), which we denote AG. Notation AG refers to branching on the aggregate value of the original variables. (ii) We apply the scheme of the present paper, setting component bounds on binary variables x i j from the above 0-1 form (64) of the knapsack subproblem, which we denote CS(x i j ). Notation CS refers to Component bound Sequence. (iii) We apply our new scheme setting component bounds directly on integer variables x i , which we denote CS(x i ) (we implemented the extension of the branching scheme to the non-binary case as described in Section 11). We use the same oracle (the branch-and-bound algorithm of [START_REF] Vanderbeck | Extending Dantzig's Bound to the Bounded Multi-Class Binary Knapsack Problem[END_REF]) in all three cases, setting the knapsack pricing problem in the form (64) although we could use a standard binary or integer knapsack solver when using the scheme of the present paper. The master is initialized with artificial columns (vectors of the canonical basis associated with the item covering constraints) in all cases. Note that, for the CSP, the master formulation does not include convexity constraint [START_REF] Parker | A column generation algorithm for brandwidth packing[END_REF]. Hence, we have implemented the generalization of our branching scheme by which we first branch on ν(G) if the latter is fractional. The only feasible branch is the round-up branch, where

∑ g∈G ν g ≥ R = ⌈Z M LP ⌉ 1 .
For our test we use the randomly generated instances of [START_REF] Vanderbeck | Computational Study of a Column Generation algorithm for Bin Packing and Cutting Stock Problems[END_REF]. There are 6 classes of instances characterized by the item weight distribution and the average item demand . In all cases, the knapsack capacity is set to W = 10000. There are 20 instances per class with n = 50 items (the data are available on http://hal.inria.fr/inria-00311274/fr/). Class 5, that involves medium size items, is the hardest for branching. For this class, we increase the number of items up to n = 200, with d = 50, to show how the performance of our scheme evolves with the instance size. The associated results are average over 10 random instances for n ∈ [60, 100] and 5 instances for n > 100. In all these tests, when selecting variables for branching, priority is given to the component i with largest width weighted by its fractional part and bound value, i.e., priority i = w i * (x i -⌊x i ⌋) * ⌈x i ⌉. The branch-and-price tree is searched using depth first priority amongst node with the minimum dual bound.

Table 7 presents the average results for each class or size. The table reports the branching rule used (br-rule), the number of nodes (nod) in the branch-and-price tree, its depth (dep), the best dual bound (DB), the number of calls to the oracle (#Sp), the number of columns generated (#Col), the time spent in solving the master (tMAST) with Xpress-MP LP solver [START_REF]User guide and Reference Manual[END_REF], the time spent in the pricing procedure of Table 6 (tSP), the time spent for separation in subroutine Explore (tEX), the overall time (tTotal), and the number of instances solved to integer optimality out of 20, or 10 when n > 50, or 5 when n > 100 (this number is in bold face when some instances could not be solved to optimality). Time units are ticks (1 tick = 1 100 of a second). The comparison between branching rule CS and AG is somewhat biased by the fact that under AG the hardest problems have not been solved to integer optimality. Nevertheless, it seems to indicate that the size of the AG branch-and-price tree is at least of the same order of magnitude as that with CS(x i ) branching. Comparing CS(x i j ) to CS(x i ) shows that the extension of our new scheme to the integer case gives rise to a scheme with good practical performance. The size of the branch-and-price tree varies more widely from one instance to the next one under CS(x i j ): in the case n = 100, the node limit of 10000 was reached for 2 instances out of 10. We tested CS(x i ) on larger instances. The average tree size is not strictly increasing with n because of the variations that arise from one instance to the next.

On pure bin packing instances (when d i = 1 ∀i), the above branching rules CS(x i j ) and CS(x i ) are the same, since x i ∈ {0, 1} in the knapsack subproblem, while AG does not permit any cutting of fractional solutions. The only branching scheme proposed in the literature for the BPP that does not require any specific oracle is the approach of [START_REF] Villeneuve | On Compact Formulations for Integer Programs Solved by Column Generation[END_REF], but it suffers from a symmetry drawback. Instead, we reformulate the BPP as a Facility Location (FL) problem:

min{ n ∑ i=1 x ii : n ∑ i=1 x i j = 1 ∀ j, n ∑ j=1
w j x i j ≤ W x ii , x i j ∈ {0, 1} ∀(i, j)} , where x i j = 1 if item j is in the same bin as item i (it is only defined if i ≤ j) and x ii = 1 if a bin labelled by item i (seen as a facility) is open. The master is set up in the form [START_REF] Gendreau | Vehicle Routing with Time Windows and Split Deliveries[END_REF] with n binary knapsack subproblems of decreasing size. Branching is then performed on the value of aggregate variables x i j of this extended formulation. This approach is denoted by FL. To the best of our knowledge, the FL approach has not been tested in previous work reported in the literature. Computational tests are carried out under the same framework as for the CSP (same initialization, no primal heuristics, depth first search amongst nodes with minimum dual bound). Table 8 reports average comparative results on 10 randomly generated instances for n = 100 to n = 250, 5 randomly generated instances for n = 300, and 3 randomly generated instances for n = 350. The item width is drawn uniformly in [500, 2500] and W = 10000 (class 5); all items are different. The comparison between the CS scheme and the FL approach shows that the new scheme yields a significant reduction in tree size, number of subproblems that are solved and computing time.

Conclusion

We have detailed a generic branching scheme for use when applying a Dantzig-Wolfe decomposition approach to a problem with identical subsystems. The pricing problem after branching decomposes into independent subproblems associated with each column class, each of which can be solved with the oracle provided for the pricing problem of the root node. The scheme relies on four novel features: (i) a dynamic nested partition of the generator set, (ii) an implicit grouping of subsytems to avoid individual r-indices that yield symmetry, (iii) an exclusive use of branching constraints that enforce lower bounds on column classes to guarantee a polynomial number of active column classes (the branching disjunction may require more than two branches), and (iv) a tree-search enumeration of active pricing subproblems that may permit pruning or early termination. The proposed branching scheme is shown to have good theoretical properties both in terms of achieving integrality (as each branching constraint amounts to implicitly fixing a bound on some variable of the original formulation) and in terms of improving dual bounds (the Lagrangian dual bounds are shown to be equivalent

Notes

1 There is a technical remark regarding our theoretical result on the size of the branch-and-price tree: we proved that the depth of the tree is polynomial in n and R, but, for the CSP, R is not polynomial in the input size. Thus, the so-called original formulation in its form (2-6) is not compact neither. These considerations remain theoretical. In fact, the number of different cutting patterns used in an optimum solution, which we may denote R ′ , is polynomial in the input size as proven in [START_REF] Eisenbrand | Carathéodory Bounds for Integer Cones[END_REF]. R ′ is much smaller than R when item demands d i are large. To satisfy the theoretical need for a polynomial depth of the branch-and-bound tree, we could use an alternative original formulation that is compact and an associated Dantzig-Wolfe reformulation with a polynomial number of columns R ′ , where a column is defined by a cutting pattern and its multiplicity in the solution [START_REF] Vanderbeck | Exact Algorithm for minimising the number of setups in the onedimensional cutting stock problem[END_REF]. However, even if we use the traditional formulation (that of Example 9 with integer right-hand-sides d i ∈ IN), the depth of the branch-and-price tree will be experimentally in O(nR ′ ). There are typically O(R ′ ) non-zero variables in master solution and non-zero ν g have value much larger than 1. Hence, the (S, L)-frames defined through branching tend to have a large width and ensure the covering of several x r i components at a time (and implicitly fix them to an integer value).

  which are the different ways in which the value of the complementary class G \ G 3 can increase its value in an integer solution.

Figure 2 :

 2 Figure 2: Example of implicit branching tree when |S| = 4: Gk = G k-1 \ G k and L k = L k-1 -L k + 1.

Figure 3 :

 3 Figure 3: Example of a partitioning of columns into nested classes when |S| = 4: each strip bounded by vertical lines has a width that represents the value ν( Ĝ) of the associated class Ĝ.

Figure 4 :

 4 Figure 4: Tree of column classes for Example 4.

Example 5 ( 1

 51 j ) for p = 1, . . . , |S j |. The order induced by the collection of component bound sequences, {S k } k=1,...,K , consists in sorting columns primarily according to the components in the order in which they appear in the sequences defining the column classes to which the columns belong. Beyond the component order prescribed by component sequences S k , one uses a standard lexicographic order. Table3presents a comparison operator that implicitly defines the ordering induced by a nested collection of branching sequences. Its parameters are defined as follows: C denotes a set of nested branching sequences, S denotes the sequence of component bounds already tested, I denotes the set of components that have not been fixed by a component bound so far, and p denotes the next position in branching sequences of C that needs to be considered. C(S) denotes the subset of sequences starting with S, i.e., C(S) = {S k ∈ C : S ⊆ S k }. Column g 1 precedes column g 2 in the induced order if the operator g 1 ≺ (C, S, I, p) g 2 returns true for C = {S k } k=1,...K , S =<>, I = {1, . . . , n}, and p = 1. Here is an example of its application: Example 4 continued) Assume that the node is defined by branching constraints (29-35) and that the current fractional master solution is g

Figure 5 :

 5 Figure 5: Testing the fractionality of column subsets in Node(3) of Example 3 to identify a branching set.

Table 5 :

 5 Separation of a fractional master solution at a node other than the root 1. Let F = {g : νg -⌊ νg ⌋ > 0}, I = {1, . . . , n}, S =<>, record= / 0, p = 1, and C = {S k } k=1,...K . 2. Explore(C, p, F, I, S, record) (a) If C = / 0, return Separate(F , I, S, record). (b) Let i be the component such that x [p] = ẍi in all S k ∈ C.

where b k i and b k i

 k define respectively the value of the lower and upper bounds on x i in column class k. When the class defines no component bound on x i , the default bound values (5) are used.

  d i : for class 1 w ∼ U [1, 7500], d i ∼ U [1, 100], and hence d = 50; for class 2, w ∼ U [1, 5000] and d = 50, for class 3: w ∼ U [1, 2500] and d = 50; for class 4a: w ∼ U [500, 5000] and d = 50; for class 4b, w ∼ U [500, 5000], d i ∼ U [1, 200], and hence d = 100; for class 5 w ∼ U [500, 2500] and d = 50

Table 4 :

 4 Cases arising when separating a fractional master solution assuming a current collection of column classes {G k } k=1,...,K . An intermediate class, Ĝ, with G l ⊂ Ĝ ⊂ G j for some j and l ∈ {1, . . . , k} is identified as having fractional value; then one can branch on the associated sequence Ŝ. An existing class, G l , has fractional value; then one can branch on S l which implies resetting the associated L l bound. An existing leaf class or the complementary class to any intermediate class, is partitioned further by applying the procedure Separate of Table2to the fractional columns of this class; this yields a fractional value class on which to branch.

	case a: case b: case c:

  On the bottom of the table are represented the boundaries of the R strips of width 1 associated with the xr vectors.

	g	8	9	2 2	3	11	4	6	5	7	12	13 13	14
	λ r g

8 (Examples 4 and 5 continued) The table below illustrates the frames associated with branching constraints (29-35) for a different master solution, ν, represented in ILO. It shows only the columns with νg > 0 and duplicates the columns that lie over several slices (associated with different index r). The bold face x g

i components are those contributing to the definition of x r i components that are "covered" by these frames.

  and L k is the marginal lower bound which according to Definition 8 must be strictly positive, i.e., L k ≥ 1 for k = 1, . . ., K. Observe that classes {C k } k=1,...,K are disjoint (because classes {G k } k=1,...,K are nested and all different). Master constraint (12

  , they take the form Observation 10 Under Ryan and Foster's scheme, intermediate dual bounds at a branch-and-price node take the form θ RF (π) = π a + R ζ (π)

					(61)
	where ζ (π) is the solution of the modified subproblem and the Lagrangian dual bound has value
	equal to	min{ ∑ r	r c x r : ∑	A x r ≥ a, x r ∈ conv( X) for r = 1, . . ., R},	(62)
	where X is the polyhedron of the modified subproblem.
	Observation 11 Assuming an "equivalent" set of branching constraints ("equivalence" is only loosely
	defined by way of Example 10), intermediate bounds (44) dominate (61) and the Lagrangian dual
	bound (45) dominates (62).

Table 7 :

 7 Comparative results for Cutting Stock Problems use of a resource constrained shortest path oracle.

	inst-size/class br-rule	nod	dep	DB	#Sp #col tMAST	tSP	tEX	tTotal opt
		AG	45	30	992.3	165	132	27	36		104 12
	n = 50, C1	CS(x i j )	33	30	992.3	185	135	13	42	0	91 20
		CS(x i )	36	35 992.35	153	137	13	37	1	85 20
		AG	343	149	635.5	586	180	419	138		980	3
	n = 50, C2	CS(x i j )	148	143	635.5	535	249	67	405	29	929 20
		CS(x i )	140	137	635.5	356	232	84	202	20	610 20
		AG	911	245 317.05	3217	333	2144	291		6207	1
	n = 50, C3	CS(x i j )	277	243 317.05	4778	718	256	3538	92	5672 20
		CS(x i )	270	260 317.05	3825	742	303	1525	87	3715 20
		AG	93	65	690.9	180	146	76	144		317	7
	n = 50, C4a CS(x i j )	82	79	690.9	221	170	37	251	9	428 20
		CS(x i )	74	72	690.9	231	169	38	237	7	391 20
		AG	119	86 1381.1	184	148	83	216		426 14
	n = 50, C4b CS(x i j )	114	91 1381.1	229	161	39	309	12	566 20
		CS(x i )	100	98 1381.1	187	160	38	263	10	459 20
		AG	305	204	372.6	617	277	450	98		960	0
	n = 50, C5	CS(x i j )	455	190	372.6	3584	521	300	2911	116	6318 20
		CS(x i )	260	245	372.6	5060	649	355	2392	82	4460 20
		AG	401	269	450.4	669	340	701	154		1514	0
	n = 60, C5	CS(x i j )	251	235	450.4	4075	673	304	5740	105	7879 10
		CS(x i )	321	308	450.4	7110	811	527	3485	173	7451 10
		AG	436	304	525.8	722	414	952	193		1995	0
	n = 70, C5	CS(x i j )	340	296	525.8	6692	811	492	9210	231	13393 10
		CS(x i )	346	341	525.8	5530	923	662	6598	246	11577 10
		AG	453	312	609.8	801	481	1275	268		2568	0
	n = 80, C5	CS(x i j )	378	337	609.8	6504	996	789	14127	315	20452 10
		CS(x i )	417	389	609.8	15128 1173	1308	10726	396	19166 10
		AG	521	370	681.8	982	558	1695	369		3411	0
	n = 90, C5	CS(x i j ) 1113	377	681.8	14142 1184	1601	22651	923	51938 10
		CS(x i )	504	481	681.8	17875 1430	1902	11562	681	26225 10
		AG	560	391	764.3	991	617	2268	454		4309	0
	n = 100, C5 CS(x i j ) 1946	430	764.3	36212 1335	4245	40968	2589 141981	8
		CS(x i )	496	489	764.3	20084 1637	2230	19401	874	36268 10
	n = 120, C5 CS(x i )	605	588	925.4	21925 2123	3767	30854	1452	59691	5
	n = 140, C5 CS(x i )	997	777 1095.2 146900 3158	8778	67536	4030 185442	5
	n = 160, C5 CS(x i ) 1186	912 1252.4 112044 3681	9475	81810	5551 205453	5
	n = 180, C5 CS(x i ) 1227 1106 1395.6 283865 4451	16215 105542	9658 356423	5
	n = 200, C5 CS(x i ) 1036 1025 1558.6 111334 4109	14273	94214 11375 305741	5

Acknowledgments

We are very grateful to Ph. Meurdesoif, P. Pesneau, Y. Pochet, E. Uchoa and B. Vignac for their comments on the early versions of this work and to A. Miller for his great help in improving the final form. We express deep thanks to the anonymous referees and the associated editor for their constructive remarks that have had a significant influence on the revision of this paper and for their patience in mentioning typos. A special thank goes to R. Butel, the engineer who set up the platform for our computational tests. A Xpress-MP license was granted to us by Fair Isaac in the context of the Dash's Academic Partner Program.

ν(x 4 , x 3 , x 2 , x 1 ) ≥ 1, ν(x 4 , x 3 , x 2 , x 1 ) ≥ 1 and ν(x 4 , x 3 , x 2 , x 1 ) ≥ 1. Then, Node (3.4) and Node (3.5) have both an integer master LP solution.

Thus, for set partitioning problems, the branching scheme takes a simpler form: Proposition 10 When the master program is a set partitioning problem of the form [START_REF] Vanderbeck | Exact Algorithm for minimising the number of setups in the onedimensional cutting stock problem[END_REF], our branching scheme has the following properties (after preprocessing): (i) L k = 1 for all branching constraints k such that S k includes a "setting-to-one bound", i.e., for all k : S k ∋ x i for some i.

(ii) The tree of column classes has depth 1, with K -1 classes that involve at least one "setting-toone bound" (each of these classes has its own set of "setting-to-one bounds") and one class, say G 1 , that involves only "setting-to-zero bounds"; more specifically, G 1 = G({x i :

(iv) A fractional solution ν satisfies all branching constraints at equality, i.e., ν(G k ) = L k for all k.

Hence, eliminating it requires further splitting an existing column class.

(v) When further splitting a column class that involves a "setting-to-one-bound", only one more "setting-to-one-bound" is needed to identify a set S on which to branch and there are only two feasible successor nodes.

(vi) When further splitting a class that involves "setting-to-zero-bounds" only (G 1 in our notation), identifying a set S on which to branch requires at most two "setting-to-one-bounds" and there are at most three successor nodes.

Proof: (i) if x i ∈ S k , then ν(S k ) ≤ gu i = 1. Thus, the only feasible strictly positive bound is L k = 1.

(ii) A class that involves a setting-to-one-bound cannot have a non-redundant predecessor class whose definition also involves setting-to-one-bounds, because both would have bound L k = 1. If x i ∈ S k , then, as L k = gu i = 1, x i is added to all other class definitions. In particular adding bounds x i to class G yields G 1 . By construction, G 1 is the only class that does not involves a setting-to-one-bound and G 1 has no successor.

(iii) is a direct consequence of (ii).

(iv) In a fractional solution to the master, all column classes have integer value because L k is both a lower bound and an upper bound on the class (even for class G 1 ).

(v) Assume ∃k :

Proposition 3 implies that only two successor nodes need to be defined.

0 for all k = 2, . . ., K or not. In the latter case, one could branch as in case (iv). But one can also split G 1 : a single setting-to-one-bound, x i , suffices to define a set S =< S 1 , x i > on which to branch, as one can simply select some component i in I(G 1 ) ∩ I(G k ) for some k. In the former case where I(G 1 ) ∩ I(G k ) = / 0 for all k = 2, . . ., K, we have ν(S 1 , x i ) = 1 for any i ∈ I(G 1 ). But, as all columns are different, ∃ j ∈ I(G 1 ), j = i : 0 < ν(S 1 , x i , x j ) < 1. Choose S =< S 1 , x i , x j > for such pair (i, j). By Proposition 3, descendant nodes 1, . . ., |S| -2 need not be generated as they are enumerating solutions where ν(G 1 ) < L 1 .

With the above characterization, our branching scheme for set partitioning like problems can be compared to the specialized scheme of Ryan and Foster. Our scheme yields 2 or 3 successor nodes while, in Ryan and Foster's scheme, the branch-and-price tree is binary. However, the depth of our tree is O(n R) while that of Ryan and Foster's scheme is O(n 2 ) (note that R ≤ n). Columns can be deleted after branching in both schemes. The main difference therefore is that the pricing problem is solved by enumerating the active subproblems in our scheme while, under Ryan and Foster's scheme, a modified subproblem is solved that can become intractable because of the extra constraints resulting from branching. Moreover, our intermediate Lagrangian bounds (44) can lead to a stronger Lagrangian dual bound than under Ryan and Foster's scheme because we impose tighter restrictions on the pricing problem. This is illustrated in Example 10 and informally stated in Observation 11.

Example 10 Assume that we are at a branch-and-bound node defined under Ryan and Foster's scheme by branching constraints

Constraints (55-56) are enforced by adding x 1 = x 2 and x 2 = x 3 in the subproblem while constraint (57) amounts to adding x 4 + x 5 ≤ 1 in the subproblem. The modified subproblem polyhedron is

Note that constraint (57) is equivalent to enforcing ν(x 4 , x 5 ) ≥ 1 or symmetrically, ν(x 4 , x 5 ) ≥ 1.

Under our scheme the "equivalent" node problem could be defined by branching constraints:

(assuming that successive branching sequences were

Then, we would have 3 subproblems with respective polyhedron to solving an LP over a polyhedron where both sets of subproblem constraints and branching constraints are convexified). The worst case size of the branch-and-price tree is not worse than if one had implemented branching in the compact space of the original variables.

Computational testing on cutting stock and bin packing problems seems to indicate that the proposed scheme is a practical way to get to integrality while not modifying the structure of the pricing problem and avoiding symmetry. Observe that every previous approach for these problems required either modification of the pricing problem or the use of an extended variable space (which require in turn a specific pricing problem solver). These computations also illustrate that the generalization of the proposed scheme to the case of a non-binary integer subproblem and generalized master convexity constraints works fine.

Our generic scheme assumes that adding bounds on the subproblem variables does not impair its solution. In some applications the oracle cannot handle bounds on the subproblem variables and fixing some variables may destroy the subproblem structure (as fixing an arbitrary arc in a constrained shortest path subproblem). However, there might be ad-hoc ways to get around this issue by being more prescriptive for the selection of branching set. For instance, the so called "path-splitting" branching rule used for multi-commodity flow in [START_REF] Barnhart | Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems[END_REF] or for the Vehicle Routing Problems with split delivery in [START_REF] Gendreau | Vehicle Routing with Time Windows and Split Deliveries[END_REF] can be understood as a special case of our scheme where one branches on a subset of binary variables associated with arcs where the sequence of arcs that are fixed to 1 must form an elementary path (this restriction is enforced at the stage of separating a fractional solution). Branching constraints that bound the number of routes that use a common starting path are consistent with the