Solving Bin Packing Problems Using VRPSolver Models

Abstract

We propose branch-cut-and-price algorithms for the classic bin packing problem and also for the following related problems: vector packing, variable sized bin packing, and variable sized bin packing with optional items. The algorithms are defined as models for VRPSolver, a generic solver for vehicle routing problems. In that way, a simple parameterization enables the use of several branch-cut-and-price advanced elements: automatic stabilization by smoothing, limited-memory rank-1 cuts, enumeration, hierarchical strong branching, and limited discrepancy search diving heuristics. As an original theoretical contribution, we prove that the branching over accumulated resource consumption (Gélinas et al, Ann Oper Res 61(1):91–109, 1995) that does not increase the difficulty of the pricing subproblem is sufficient for those bin packing models. Extensive computational results on instances from the literature show that the VRPSolver models have a performance that is very robust over all those problems, being often superior to the existing exact algorithms on the hardest instances. Several instances could be solved to optimality for the first time.

1 Introduction

Bin packing problems are among the most classic combinatorial optimization problems, being discussed since the 1930s [22]. The problems addressed in this paper can be defined as follows:

• Bin packing problem (BPP) Let $I = \{1,\ldots ,\mathcal {I}\}$ be a set of $\mathcal {I}$ items and assume an unlimited quantity of identical bins with integer positive capacity Q. Each i ∈ I has an integer positive weight w_i ≤ Q. The goal is finding a packing using the minimum number of bins, such that the total weight of the items in a bin does not exceed its capacity.

• Vector packing problem (VPP) Let $I= \{1,\ldots ,\mathcal {I}\}$ be a set of items and D a set of dimensions. Assume an unlimited quantity of identical bins with integer positive weight capacities Q^d, d ∈ D. Each i ∈ I has integer non-negative weights ${w_{i}^{d}} \leq Q^{d}$, d ∈ D. The goal is to pack all items into the minimum possible number of bins, such that, for each dimension, the total weight of the items in a bin does not exceed its capacity.

• Variable sized bin packing problem (VSBPP) Let $I= \{1,\ldots ,\mathcal {I}\}$ be a set of $\mathcal {I}$ items and $K = \{1,\ldots ,\mathcal {K}\}$ a set of $\mathcal {K}$ bin types. There are u_k bins of type k ∈ K available, each one having positive integer capacity Q_k and positive integer cost c_k. Each i ∈ I has integer positive weight $w_{i} \leq Q_{max} = \max \limits _{k \in K} Q_{k}$. The goal is to pack all items into a least costly set of bins, considering the availability of each bin type and such that the total weight of the items in a bin does not exceed its capacity.

• Variable sized bin packing problem with optional items (VSBPPOI) Same as before, except that each item i ∈ I is associated to a positive integer penalty p_i for not packing it. The goal is to find a packing minimizing the costs of the used bins plus the penalties for the non-packed items.

There is a vast literature on those problems, specially for the classic BPP. A comprehensive survey on exact methods for BPP, including an original comparative computational study, was published in 2016 by Delorme et al. [11]. After that, other exact algorithms for BPP were proposed in [10, 42]. Recent exact algorithms for VPP were presented in [6, 19, 43]. The best exact algorithms for VSBPP are those in [1, 4, 17, 23]. The VSBPPOI was less studied, and the best exact algorithms for it were presented in [4].

Big advances in the exact solution of vehicle routing problems (VRPs) by branch-cut-and-price (BCP) algorithms have been accomplished in recent years, as surveyed in [9]. A milestone was certainly the branch-cut-and-price (BCP) algorithm of [24] that could solve capacitated VRP (CVRP) instances with up to 360 customers, a large improvement upon the previous record of 150 customers. That BCP exploits many algorithmic elements introduced by several authors, combining and enhancing them. Improvements of the same magnitude were later obtained for several other variants, like VRP with time windows (VRPTW) [25] and heterogeneous fleet VRP (HFVRP) [28]. Unhappily, designing and coding each one of those complex and sophisticated BCPs have been a highly demanding task, measured on several work-months of a skilled team. VRPSolver [31] is a software that contains a state-of-the-art BCP algorithm for a very generic model that encompasses most VRP variants found in the literature. Algorithms for particular problems are obtained by defining certain elements in the generic model (using a Julia language interface), in the so-called specific problem VRPSolver models. Experiments with VRPSolver models on ten of the most classic VRP variants, including CVRP, VRPTW, and HFVRP, show a performance that is competitive or even superior to best specific algorithms for each one of those variants.

This work proposes VRPSolver models for the abovementioned bin packing variants and investigates the performance of the resulting BCP algorithms. As will be shown, even though bin packing problems are not VRPs, VRPSolver can be a quite effective tool for solving them. This is not completely unexpected. Some of the most recent algorithms for bin packing problems, like those in Heßler et al. [19] and Wei et al. [42], are BCP algorithms that clearly borrow ideas from VRP literature. In particular, those algorithms also solve the pricing subproblem as a resource constrained shortest paths problem, using a labeling algorithm, as is usual on VRP.

The theoretical novelty of this paper is related to the branching scheme over accumulated resource consumption by Gélinas et al. [15]. The scheme was originally proposed in the context of an algorithm for a time constrained VRP, but it can be applied in any situation where the pricing subproblem is a resource constrained shortest path and is implemented in VRPSolver. It has the very nice feature of not increasing the pricing complexity in any child node. So, we adopted it in our bin packing VRPSolver models. In principle, we believed that an additional branching scheme, like Ryan and Foster [34] (that makes pricing subproblems harder), would be needed after all accumulated consumption branching alternatives were exhausted. Happily, we could prove that this is not necessary.

This paper is organized as follows. Section 2 reviews the generic VRPSolver model, used to define the specific models given in Section 3. Section 4 contains the proof that the branching on accumulated resource consumption, used in all models, is sufficient. Section 5 presents computational results and comparisons with existing algorithms in the literature. Finally, some additional analyses of the results and future perspectives are provided in Section 6.

2 Reviewing the Generic VRPSolver Model

The generic VRPSolver model is a special Mixed Integer Program (MIP) that contains variables associated to resource constrained paths over directed, not necessarily simple, graphs defined by the user. As the number of such variables is usually huge, they are dynamically priced by solving resource constrained shortest path (RCSP) problems [20]. Since the integrality of some variables need to be enforced, the MIP is solved by a branch-and-price (BP) algorithm. If cuts are also separated, the resulting algorithm becomes a branch-cut-and-price (BCP). In particular, if the so-called packing sets are defined, Limited-Memory Rank-1 cuts are automatically separated. This section reviews the VRPSolver model. Some advanced features not used in this paper are omitted, readers interested in knowing them may refer to this detailed reference [30].

2.1 Path Generator Graph

All models in this paper use a single path generator graph. So, we simplify the explanation by assuming that the user defines a single graph G = (V,A). She/he should also define: (1) two special vertices in V, v_source and v_sink; (2) a set R of resources, together with their arc consumptions and accumulated consumption intervals. For each r ∈ R and a ∈ A, q_a,r is the consumption of resource r in arc a and [l_a,r,u_a,r] is its accumulated resource consumption interval. A path p = (v_source = v₀,a₁,v₁,…,a_n− 1,v_n− 1,a_n,v_n = v_sink) in G is said to be resource constrained if, for every r ∈ R, the accumulated resource consumption $S^{p}_{j,r}$ at visit j, 0 ≤ j ≤ n, where $S^{p}_{0,r}=0$ and $S^{p}_{j,r}=\max \limits \{l_{a_{j},r},S^{p}_{j-1,r}+q_{a_{j},r}\}$, does not exceed $u_{a_{j},r}$. We remark that the previous definition allows resources to be disposed in order to satisfy the lower bounds l_a,r on accumulated consumption of an arc a; on the other hand, upper bounds u_a,r are strict. An example of a situation where resources can be disposed would be in the VRP with time windows problem, where a vehicle can arrive early at a customer and wait (i.e., dispose some time resource) until the opening of its time window. Let P denote the set of all resource constrained paths in G. For all a ∈ A and p ∈ P, let ${h_{a}^{p}}$ indicate how many times arc a appears in path p.

2.2 Formulation and Mapping

The MIP model is defined by the user as follows. There are variables x_j, 1 ≤ j ≤ n₁, and variables y_s, 1 ≤ s ≤ n₂. The first $\bar {n}_{1}$ x variables and the first $\bar {n}_{2}$ y variables are defined to be integer. Equations 1a and 1b define a general objective function and m general constraints over those variables, respectively. For each variable x_j, 1 ≤ j ≤ n₁, $M(x_{j}) \subseteq A$ defines its mapping into a non-empty subset of the arcs. Mappings do not need to be disjoint; the same arc can mapped to more than one variable x_j. Define M^− 1(a) as {j|1 ≤ j ≤ n₁;a ∈ M(x_j)}. As not all arcs need to belong to some mapping, some M^− 1 sets may be empty. For each path p ∈ P, let λ_p be a non-negative integer variable. The relation between variables x and λ is given by Eq. 1c. The values L and U are given lower and upper bounds on the number of paths in a solution.

$$ \begin{array}{@{}rcl@{}} \text{Min} & \sum\limits_{j =1}^{n_{1}} c_{j} x_{j} + \sum\limits_{s =1}^{n_{2}} f_{s} y_{s} & \end{array} $$

(1a)

$$ \begin{array}{@{}rcl@{}} \text{S.t.} & \sum\limits_{j =1}^{n_{1}} \alpha_{ij} x_{j} + \sum\limits_{s =1}^{n_{2}} \beta_{is} y_{s} \geq d_{i}, & i=1,\ldots,m, \end{array} $$

(1b)

$$ \begin{array}{@{}rcl@{}} & x_{j} = \sum\limits_{p \in P} \left( \sum\limits_{a \in M(x_{j})} {h_{a}^{p}} \right) \lambda_{p}, \quad & j=1\ldots,n_{1}, \end{array} $$

(1c)

$$ \begin{array}{@{}rcl@{}} & L \leq \sum\limits_{p \in P} \lambda_{p} \leq U, & \end{array} $$

(1d)

$$ \begin{array}{@{}rcl@{}} & \lambda_{p} \in \mathbb{Z}_{+}, & p \in P, \end{array} $$

(1e)

$$ \begin{array}{@{}rcl@{}} & x_{j} \in \mathbb{Z}, y_{s} \in \mathbb{Z}, & j = 1,\ldots,\bar{n}_{1}, s = 1,\ldots,\bar{n}_{2}. \end{array} $$

(1f)

A feasible solution to Formulation (1) is composed of a set of paths, each path p ∈ P with multiplicity λ_p in the solution, and perhaps additional decisions represented by the values assigned to variables y_s, s = 1,…,n₂. Hence, modelling a problem as Eq. 1 requires it to contain structures that can be cast into paths in a properly defined graph. It is preferable that such a graph has polynomial size. Then, resources should be created to model “intrapath” constraints while global “interpath” constraints, and the objective function, should be modelled as Eq. 1b and Eq. 1a, respectively. Note that the values of x_j, $j = 1,\dots ,n_{1}$, are completely defined as a function of the path variables, through the mappings. Thus, these variables are only created for allowing expressing (1a) and (1b).

Eliminating the x variables and relaxing the integrality constraints, the following LP, corresponding to the root node of the BP algorithm, is obtained:

$$ \begin{array}{@{}rcl@{}} \text{Min} & \underset{p \in P}{\sum} \left( \sum\limits_{j =1}^{n_{1}} c_{j} \underset{a \in M(x_{j})}{\sum} {h_{a}^{p}} \right) \lambda_{p} + \sum\limits_{s =1}^{n_{2}} f_{s} y_{s} & \end{array} $$

(2a)

$$ \begin{array}{@{}rcl@{}} \text{S.t.} & \underset{p \in P}{\sum} \left( \sum\limits_{j =1}^{n_{1}} \alpha_{ij} \underset{a \in M(x_{j})}{\sum} {h_{a}^{p}} \right) \lambda_{p} + \sum\limits_{s =1}^{n_{2}} \beta_{is} y_{s} \geq d_{i}, \quad & i=1,\ldots,m, \end{array} $$

(2b)

$$ \begin{array}{@{}rcl@{}} & L \leq \underset{p \in P}{\sum} \lambda_{p} \leq U, & \end{array} $$

(2c)

$$ \begin{array}{@{}rcl@{}} & \lambda_{p} \geq 0, & p \in P. \end{array} $$

(2d)

Master LP (2) is solved by column generation. Let π_i, 1 ≤ i ≤ m, denote the dual variables of Constraints (2b), ν₊ and ν₋, are the dual variables of Constraints (2c). The reduced cost of an arc a ∈ A is defined as:

$$ \bar{c}_{a} = \underset{j \in M^{-1}(a)}{\sum} c_{j} - \sum\limits_{i =1}^{m} \underset{j \in M^{-1}(a)}{\sum} \alpha_{ij} \pi_{i}. $$

The reduced cost of a path p = (v₀,a₁,v₁,…,a_n− 1,v_n− 1,a_n,v_n) ∈ P is:

$$ \bar{c}(p) = \sum\limits_{j =1}^{n} \bar{c}_{a_{j}} - \nu_{+} - \nu_{-}. $$

So, the pricing subproblems correspond to finding a path p ∈ P with a minimum reduced cost. The above scheme assumes that no additional cuts are being added to the formulation. The interested reader may consult [24] on how cuts can be handled.

2.3 Packing Sets and Some Advanced Algorithmic Elements

Let ${\mathcal B} \subset 2^{A}$ be a collection of mutually disjoint subsets of A such that the constraints:

$$ \underset{a \in B}{\sum} \underset{p \in P}{\sum} {h_{a}^{p}} \lambda_{p} \leq 1, \quad B \in {\mathcal B}, $$

(3)

are satisfied by at least one optimal solution (x^∗,y^∗,λ^∗) of Formulation (1). This means that the arcs in each $B \in \mathcal B$ can appear at most once in all paths p ∈ P that are part of some optimal solution. In those conditions, we say that ${\mathcal B}$ defines a collection of packing sets. The definition of a proper ${\mathcal B}$ should be done by the user as part of the modeling.

The information given by the packing sets is used by VRPSolver to improve the solution of Eq. 1, switching from a basic BP algorithm to an advanced BCP. The following algorithmic elements based on packing sets are used to solve the models described in this article.

2.3.1 Limited-Memory Rank-1 Cuts

The Rank-1 Cuts (R1Cs) [27] are a generalization of the Subset Row Cuts proposed by Jepsen et al [21]. In the VRPSolver context, they are further generalized as follows. Consider a collection of packing sets ${\mathcal B}$ and non-negative multipliers ρ_B for each $B \in {\mathcal B}$. A Chvátal-Gomory rounding of constraints (3) yields:

$$ \underset{p \in P}{\sum} \left\lfloor \underset{B \in {\mathcal B}}{\sum} \rho_{B} \underset{a \in B}{\sum} {h_{a}^{p}} \right \rfloor \lambda_{p} \leq \left\lfloor \underset{B \in {\mathcal B}}{\sum} \rho_{B} \right \rfloor. $$

(4)

R1Cs are potentially strong, but each added cut makes the pricing subproblems significantly harder. The limited memory technique [26] is essential for mitigating that negative impact.

2.3.2 Path Enumeration

The path enumeration technique was proposed by Baldacci et al. [3], and later improved by Contardo and Martinelli [8]. It consists in trying to enumerate into a table all paths in P that can possibly be part of an improving solution. After a successful enumeration, the corresponding pricing subproblem can be solved by inspection, saving time. If the enumeration has already succeeded and the total number of paths in the tables is not too large (say, less than 10,000), the overall problem may be finished by a standard MIP solver, which often saves a lot of time.

From time to time, VRPSolver tries to enumerate all paths p without more than one arc in the same packing set, and with reduced cost $\bar {c}(p)$ smaller than the current gap UB − LB, where UB is the best known integer solution cost, and LB the value of the current linear relaxation. Moreover, if two paths p and p^′ lead to variables λ_p and $\lambda _{p}^{\prime }$ with identical coefficients in Eq. 2b–2c, the one with the larger cost is dropped.

2.3.3 Branching

Branching over x and y variables (or over linear expressions defined over them) is simple and does not change the structure of the pricing subproblem. In many models, this is sufficient for correctness. For example, in a capacitated VRP model where x_ij variables indicate whether a vehicle travels from point i to point j (like in [31]), if all x variables are integer then they correspond to a correct solution, there is no need to even check the integrality of the λ variables. However, there are models, including all in this paper, where this does not happen and constraints (1e) need to be explicitly enforced. Branching over individual λ variables should be avoided due to a big negative impact in the pricing and also due to highly unbalanced branch trees [40].

VRPSolver has the option of branching using a generalization of the Ryan and Foster rule [34]. Choose two distinct sets B and $B^{\prime }$ in ${\mathscr{B}}$. Let $P(B,B^{\prime }) \subseteq P$ be the subset of the paths that contain arcs in both B and $B^{\prime }$. The branch is over the value of ${\sum }_{p \in P(B,B^{\prime })} \lambda _{p}$. The branch trees are much more balanced. However, Ryan and Foster branching scheme changes the structure of the pricing subproblem, sometimes increasing a lot of its difficulty.

VRPSolver also implements a branching scheme similar to the one proposed by Gélinas et al. [15] for time constrained routing problems. It can be described as follows. Assume that all consumptions and accumulated consumption intervals are integer. For a chosen $B \in {\mathcal B}$, r ∈ R and for a certain threshold value t^∗: in the left child make u_a,r = t^∗− 1, for all a ∈ B; in the right child make l_a,r = t^∗, for all a ∈ B. In other words, the branch is over the accumulated consumption of resource r on arcs in B. This branching has the nice feature of not increasing the pricing difficulty. However, it is not sufficient for general Formulation (1) since some fractional λ solutions can not be eliminated by it. The main theoretical contribution of this paper (in Section 4) is a proof that the branching scheme over accumulated resource consumption is sufficient for the proposed bin packing models.

3 VRPSolver Models for Bin Packing problems

Now, we present the specific VRPSolver models corresponding to each of the problems addressed in this paper.

3.1 Vector Packing (VPP)/Bin Packing (BPP)

The following model is valid for the VPP: the classic BPP corresponds to the case where |D| = 1:

The path generator graph is depicted in Fig. 1. For each item i ∈ I, there is an arc a_i+ with consumptions ${w_{i}^{d}}$, d ∈ D, and another arc a_i− with zero consumptions. It can be seen that there is a one-to-one correspondence between resource constrained paths in P and solutions of the |D|-dimensional binary knapsack problem defined by $\{ z \in \{0,1\}^{\mathcal {I}} : {\sum }_{i \in I} {w_{i}^{d}} {z_{i}^{d}} \leq Q^{d}, d \in D\}$, that also correspond to the possible ways of packing items into a bin. Variables x_i, i ∈ I, indicate if item i is packed. As all items must be packed, they are fixed to 1 in Eq. 5b. Each variable x_i is mapped to arc a_i+. So, Constraints (5b) are equivalent to saying that the solution should contain exactly one path in P passing by each arc a_i+. Variable x₀ is mapped to both a₁₊ and a₁₋. As every path in P passes by exactly one of those arcs, x₀ is put in the objective function (5a) for counting the number of used paths (bins).

Fig. 1

Path generator graph for VPP/BPP

Consider the BPP instance with ${\mathcal I}=4$, w₁ = 7, w₂ = 8, w₃ = 9, w₄ = 11, and Q = 17. The set P has 8 paths: p₁ = (a₁₋,a₂₋,a₃₋,a₄₋), p₂ = (a₁₊,a₂₋,a₃₋,a₄₋), p₃ = (a₁₋,a₂₊,a₃₋,a₄₋), p₄ = (a₁₋,a₂₋,a₃₊,a₄₋), p₅ = (a₁₋,a₂₋,a₃₋,a₄₊), p₆ = (a₁₊,a₂₊,a₃₋,a₄₋), p₇ = (a₁₊,a₂₋,a₃₊,a₄₋), p₈ = (a₁₋,a₂₊,a₃₊,a₄₋). The complete formulation (corresponding to Formulation (1)) for that instance is:

$$ \begin{array}{@{}rcl@{}} \text{Min} && x_{0} \end{array} $$

(6a)

$$ \begin{array}{@{}rcl@{}} \text{S.t.} && x_{1} = 1, \end{array} $$

(6b)

$$ \begin{array}{@{}rcl@{}} && x_{2} = 1, \end{array} $$

(6c)

$$ \begin{array}{@{}rcl@{}} && x_{3} = 1, \end{array} $$

(6d)

$$ \begin{array}{@{}rcl@{}} && x_{4} = 1, \end{array} $$

(6e)

$$ \begin{array}{@{}rcl@{}} && x_{0} = \lambda_{1} + \lambda_{2} + \lambda_{3} + \lambda_{4} + \lambda_{5} + \lambda_{6} + \lambda_{7} + \lambda_{8}, \end{array} $$

(6f)

$$ \begin{array}{@{}rcl@{}} && x_{1} = \lambda_{2} + \lambda_{6} + \lambda_{7}, \end{array} $$

(6g)

$$ \begin{array}{@{}rcl@{}} && x_{2} = \lambda_{3} + \lambda_{6} + \lambda_{8}, \end{array} $$

(6h)

$$ \begin{array}{@{}rcl@{}} && x_{3} = \lambda_{4} + \lambda_{7} + \lambda_{8}, \end{array} $$

(6i)

$$ \begin{array}{@{}rcl@{}} && x_{4} = \lambda_{5}, \end{array} $$

(6j)

$$ \begin{array}{@{}rcl@{}} && 0 \leq \lambda_{1} + \lambda_{2} + \lambda_{3} + \lambda_{4} + \lambda_{5} + \lambda_{6} + \lambda_{7} + \lambda_{8}, \end{array} $$

(6k)

$$ \begin{array}{@{}rcl@{}} && \lambda \in \mathbb{Z}_{+}^{8} \end{array} $$

(6l)

A possible optimal solution to Eq. 6 would have λ₄ = λ₅ = λ₆ = 1 (the corresponding paths are depicted in Fig. 2) and the remaining λ variables equal to zero.

Eliminating the x variables and relaxing the integrality, the master LP (corresponding to Eq. 2) that should be solved by column generation is obtained:

$$ \begin{array}{@{}rcl@{}} \text{Min} && \lambda_{1} + \lambda_{2} + \lambda_{3} + \lambda_{4} + \lambda_{5} + \lambda_{6} + \lambda_{7} + \lambda_{8} \end{array} $$

(7a)

$$ \begin{array}{@{}rcl@{}} \text{S.t.} && \lambda_{2} + \lambda_{6} + \lambda_{7} = 1, \end{array} $$

(7b)

$$ \begin{array}{@{}rcl@{}} && \lambda_{3} + \lambda_{6} + \lambda_{8} = 1, \end{array} $$

(7c)

$$ \begin{array}{@{}rcl@{}} && \lambda_{4} + \lambda_{7} + \lambda_{8} = 1, \end{array} $$

(7d)

$$ \begin{array}{@{}rcl@{}} && \lambda_{5} = 1, \end{array} $$

(7e)

$$ \begin{array}{@{}rcl@{}} && \lambda \geq 0 \end{array} $$

(7f)

Fig. 2

Paths used on an integer solution of Eq. 3.1. The arc consumptions and the accumulated resource consumption at the end of each path are also indicated

3.2 Variable Sized Bin Packing with Optional Items (VSBPPOI)

We present the model for the more general VSBPPOI; the model for the VSBPP without optional items is easily obtained by setting sufficiently large penalties or by removing some variables from the model.

The path generator graph is depicted in Fig. 3. The graph differs from that in the previous BPP/VPP model by having one more vertex and extra arcs a_k, k ∈ K. The paths in P passing by an arc a_k are associated to the possible packings in bin type k. Each variable x_i, i ∈ I, mapped to arc a_i+, indicates if item i is packed. Unlike in the previous model, those variables are not fixed to 1. Each variable z_k, k ∈ K, mapped to arc a_k, counts how many bins of type k are used in the solution. Variables s are not mapped.

Fig. 3

Path generator graph for VSBPPOI with three bin types

The expression ${\sum }_{i\in I} s_{i}$ corresponds to the number of items that are not packed. Branching on the value of that expression can only be applied on VSBPPOI instances. The expression ${\sum }_{k\in K}\frac {c_{k}}{g}z_{k}$ is proportional to the total cost of the bins used in the solution. On VSBPP instances (without optional items), branching down on the value of this expression yields an infeasible left child node; in the right child the node lower bound is certainly increased at least to the next multiple of g. The rounding up of lower bounds to the next multiple of the greatest common divisor of the bin costs is standard in published VSBPP algorithms. Even on VSBPPOI instances, where the left child is feasible, this branching is usually quite good in increasing lower bounds.

4 Branching over Accumulated Resource Consumption

The classic lower bound for the BPP by Gilmore and Gomory [16] is obtained by column generation, solving binary knapsack problems in the pricing. The problem is (weakly) NP-hard, but there are some advanced knapsack algorithms that perform very well in practice [32]. However, implementing a BP algorithm over Gilmore and Gomory can be tricky.

Branching directly over the variables of the model (as done in [5]) leads to very unbalanced search trees, fixing a variable corresponding to a certain packing of items to a bin to 1 is strong, but fixing it to 0 is much less likely to move the lower bounds. Moreover, fixing variables to 0 change the structure of the pricing, each fixing making it harder.

Another alternative, first used in [39], is to apply Ryan and Foster scheme [34], choosing a pair of items i and j. In the left child, i and j should be packed in the same bin. This does not change the pricing structure; the items are simply merged into a single item. In the right child, i and j can not be packed in the same bin. This changes the structure of the pricing that becomes a binary knapsack with conflicts, which is a strongly NP-hard problem.

The BPP model presented in Section 3.1 is equivalent to Gilmore and Gomory model; however, VRPSolver uses the resource constrained shortest path problem as pricing subproblem. RCSPs are solved using a labeling algorithm (see [35] for details), which is a dynamic programming where reachable states are represented as labels. The practical efficiency of a labeling algorithm depends on the concept of dominance. Let L₁ and L₂ be the labels corresponding to partial paths p₁ and p₂ in G, starting in v_source and ending at the same vertex v of V. If the accumulated resource consumption of p₁ is not larger than the accumulated resource consumption of p₂ (for all r ∈ R) and the reduced cost of p₁ is smaller than the reduced cost of p₂, then label L₂ is dominated by L₁ and can be removed. This dominance rule is correct because every extension of p₂ into a complete path in P, if applied to p₁, would produce a complete path in P with a smaller reduced cost. We remark that the “smaller-consumption-is-better” rule works because the RCSP definition permits resources to be disposed, if this is needed to satisfy lower bounds on accumulated consumption.

A potential advantage of solving the pricing subproblem as a RCSP is that the branching over accumulated resource consumption, which never changes the pricing structure, can be used. That branching scheme was proposed by Gélinas et al. [15] for time constrained routing problems. However, the authors did not prove its sufficiency. In fact, they proposed using a second branching scheme for the cases when the current fractional solution could not be eliminated by branching over accumulated resource consumption in both children nodes. The main theoretical result of this work is Theorem 1. For the sake of simplicity, it is stated only for BPP. However, we will show later that the sufficiency result also holds for all models in Section 3.

Definition 1

A branching is effective if it cuts the current fractional solution in both child nodes.

Definition 2

A branching scheme is sufficient if, given a fractional solution, it provides either an effective branching or a polynomial algorithm to convert that fractional solution into an integer solution with the same cost.

Consider as example the instance described in Section 3.1 and its linear relaxation (7), having solution λ₅ = 1, λ₆ = λ₇ = λ₈ = 0.5, the remaining variables with value zero. The accumulated resource consumptions for the paths associated to the fractional variables are as follows: $S^{p_{6}}_{1,1}=7$, $S^{p_{6}}_{2,1}=S^{p_{6}}_{3,1}=S^{p_{6}}_{4,1}=15$, $S^{p_{7}}_{1,1}=S^{p_{7}}_{2,1}=7$, $S^{p_{7}}_{3,1}=S^{p_{7}}_{4,1}=16$, $S^{p_{8}}_{1,1}=0$, $S^{p_{8}}_{2,1}=8$, $S^{p_{8}}_{3,1}=S^{p_{8}}_{4,1}=17$. It is not possible to branch effectively over item 3, corresponding to arc a₃₊. This arc appears in paths p₇ and p₈. Choosing t^∗ = 17, we would have intervals [0,16] and [17,17] for the accumulated resource consumption of arc a₃₊ in the left and right child nodes, respectively. The first interval would indeed eliminate p₈, but the second would eliminate neither p₇ (because 1 unit of resource can be dropped to make $S^{p_{7}}_{3,1}=17$) nor p₈. On the other hand, it is possible to branch effectively over item 2. Choosing t^∗ = 10 would give intervals [0,9] and [10,17] for a₂₊. The first interval would eliminate p₆, while the second would eliminate p₈. So, the fractional solution would be cut in both branches.

Lemma 1

Suppose that one sets tight intervals on accumulated resource consumption for all items, that is, $l_{a_{i+},1} = u_{a_{i+},1}, i \in I$. The linear relaxation of the BPP model (corresponding to Eq. 2) restricted to the paths in P that respect those tight intervals has an optimal integer solution.

Proof

Define the following Minimum Cost Flow Circulation (MCFC) problem over graph $H=(\{0,\ldots ,2{\mathcal {I}}+1\},F)$, where $F = \{(0,2i-1),(2i-1,2i),(2i,2{\mathcal {I}}+1 : i \in I\} \cup \{ (2i_{1}, 2i_{2}-1) : i_{1}, i_{2} \in I, i_{1} < i_{2}, l_{a_{i_{1}+}} + w_{i_{2}} \leq l_{a_{i_{2}+}} \} \cup \{(2{\mathcal {I}}+1,0)\}$. All arcs in F cost zero, except by $(2{\mathcal {I}}+1,0)$ that costs 1. The flow f_a in each arc a ∈ F can assume any non-negative value, except by arcs in {(2i − 1,2i) : i ∈ I} where the flow is fixed to 1. Let z(MCFC) be the optimal solution value of MCFC. Let $BPP_{LP}(P^{\prime })$ be the linear relaxation of the BPP model restricted to $P^{\prime }$, the subset of P formed by the paths that respect the tight intervals. Let $z(BPP_{LP}(P^{\prime }))$ be its optimal solution value.

There is a one-to-one correspondence between paths in $P^{\prime }$ and cycles in F. Let $\bar {\lambda }$ be an optimal solution (integer or fractional) of $BPP_{LP}(P^{\prime })$. Start with zero flow for all arcs in F. For each $p \in P^{\prime }$, add the value $\bar {\lambda }_{p}$ to the flow of all arcs of the cycle in F corresponding to p. The resulting flow is a solution of MCFC with value $z(BPP_{LP}(P^{\prime }))$. Conversely, a cycle decomposition of an optimal solution of MCFC yields a solution of $BPP_{LP}(P^{\prime })$ with value z(MCFC). So, $z(BPP_{LP}(P^{\prime }))=z(MCFC)$. Moreover, the Flow Integrality Theorem asserts that MCFC has an optimal solution where all flows are integers. That integer solution will yield an optimal integer solution for $BPP_{LP}(P^{\prime })$. □

In order to exemplify Lemma 1, consider the same BPP instance from Section 3.1 and suppose that intervals are set to [8,8], [8,8], [17,17], and [14,14], for items 1, 2, 3, and 4, respectively. Graph H is depicted in Fig. 4, $P^{\prime } = P \setminus \{p_{6}\}$, and $z(BPP_{LP}(P^{\prime }))=z(MCFC) =3$. A minimum cost integer flow circulation is has arcs f₀₁, f₁₂, f₂₅, f₅₆, f₆₉, f₀₃, f₃₄, f₄₉, f₀₇, f₇₈, and f₈₉ with value 1 and f₉₀ = 3. This flow corresponds to an integer solution having λ₃ = λ₅ = λ₇ = 1.

Fig. 4

Example of a network obtained from a BPP instance with tight consumption bounds

Theorem 1

The branching scheme over accumulated resource consumption is sufficient for the VRPSolver Model for BPP.

Proof

In this context, a branching over an item i ∈ I and threshold value t^∗ is effective if there exists a pair of paths p₁ and p₂ passing by a_i+, where $\lambda _{p_{1}}$ and $\lambda _{p_{2}}$ have positive value in the current fractional relaxation, and such that if $u_{a_{i+},1}$ is set to t^∗− 1 (left child) then p₁ remains feasible but p₂ not; if $l_{a_{i+},1}$ is set to t^∗ (right child) then p₂ remains feasible but p₁ not. Assume that there is no effective branching. This means for each item i ∈ I and for every threshold t^∗, all paths (including, of course, the paths that do not pass by a_i+) with positive fractional variable would remain feasible either in the left or in the right child. Consider some i ∈ I, and let $t^{**}_{i}$ be the maximum threshold such that all those paths would remain feasible in the right child, threshold $t^{**}_{i} +1$ would make all those paths to be feasible in the left child. This means that all paths with positive fractional value are feasible for both intervals $[0,t^{**}_{i}]$ and $[t^{**}_{i},Q]$ on the accumulated consumption of a_i+, so they are all feasible for tight interval $[t^{**}_{i},t^{**}_{i}]$. Repeating the reasoning for each i ∈ I, one at a time, we can conclude that all paths with positive fractional value would remain feasible even if all intervals are tightened to $[t^{**}_{i},t^{**}_{i}]$. Then, by Lemma 1, the current fractional solution has the same cost of an optimal integer solution. In fact, in order to obtain that solution itself it may be necessary to solve (in polynomial time) the MCFC instance defined in the proof of Lemma 1. □

We now sketch how to adapt the above proof for obtaining similar sufficiency results for the other variants considered.

• The branching scheme over accumulated resource consumption is also sufficient for the more generic VRPSolver Model for VPP. The reasoning in Lemma 1 and Theorem 1 remains essentially the same, showing that a fractional solution without an effective branching would also be a solution to a restricted problem where the intervals on accumulated consumption associated to each item i ∈ I are tight for each resource d ∈ D.

• The same branching scheme also suffices for the VRPSolver Model for VSBPP. The proof only differs in Lemma 1, where graph H would have vertex-set $\{0,\ldots ,2{\mathcal {I}}+\mathcal {K}\}$ and arc-set $F = \{(0,2i-1),(2i-1,2i) : i \in I\} \cup \{ (2i,2{\mathcal {I}}+k) : k \in K, i \in I, l_{a_{i+},1} \leq Q_{k} \} \cup \{ (2i_{1}, 2i_{2}) : i_{1}, i_{2} \in I, i_{1} < i_{2}, l_{a_{i_{1}+},1} + w_{i_{2}} \leq l_{a_{i_{2}+},1} \} \cup \{(2{\mathcal {I}}+k,0) : k \in K\}$. Arcs $(2{\mathcal {I}}+k,0)$, k ∈ K would have flow capacity u_k and cost c_k.

• Finally, the branching scheme for the VRPSolver Model for VSBBPOI of branching over z variables and over accumulated resource consumption is sufficient. This is true because if all z variables are integer, then the same proof used for the VSBPP guarantees the existence of an effective branching over accumulated resource, unless the current fractional solution can be converted into an integer solution with the same cost.

5 Computational Experiments

The models presented in Section 3 were implemented on VRPSolver [30, 31], available for free academic use at https://vrpsolver.math.u-bordeaux.fr. VRPSolver solves RCSP pricing subproblems with the bucket graph-based labeling algorithm proposed in [35] and applies automatic dual price smoothing stabilization [29]. The precise version of VRPSolver used in the experiments was v.0.3, built on top of BapCod v.047b. CPLEX 12.8 is used for solving linear programs and MIPs. The experiments were run on a 2 Deca-core Ivy-Bridge Haswell Intel Xeon E5-2680 v3 server running at 2.50 GHz. The 128 GB of available RAM was shared between 8 copies of the algorithm running in parallel on the server. Each instance is solved by one copy of the algorithm using a single thread.

5.1 Bin Packing Problem

For the experiments on the BPP, we use the hardest (according to [11]) classes of literature instances: “Falkenauer T” [13], “Wäscher” [41], “Hard28” [37], as well as “AI” and “ANI” instances recently proposed in [11].

The default parameterization of VRPSolver (see [30]) is changed in the following way:

• The number of buckets per vertex is set to 200, and iit is not dynamically adjusted.

• The bidirectional variant of the labeling algorithm is applied when solving the pricing both heuristically and exactly.

• At most, 100 columns are generated at every iteration of column generation.

• When applying the path enumeration technique, the number of enumerated paths is limited to 2 ⋅ 10⁶, i.e., path enumeration is interrupted if this number is exceeded.

• The node is finished by the MIP solver if the number of enumeration paths is less or equal to 10⁵.

• 3- and 4-row limited-memory rank-1 cuts are separated, i.e., they are obtained by Chvátal-Gomory rounding of 3 and 4 constraints (3), respectively.

• The cut generation tailing-off threshold is set to 5, i.e., the cut generation is stopped when the primal-dual gap is decreased by less than 2% after 5 cut separation rounds.

• The safe lower bound technique similar to the one proposed in [18] is applied to assure the validity of the column generation bound.

• At most, 20 branching candidates are considered during the strong branching.

For each instance, we use initial primal bound which is equal to the rounded up value of the column generation lower bound plus 1 unit. There is a long-standing conjecture that the optimal solution value of a BPP instance is never larger than this. Solutions with these objective values are easily obtainable by simple heuristics. The pure diving heuristic [36] is used to improve initial primal bound. It is executed at every node of the search tree unless its depth is greater that 10.

We compare the results of VRPSolver with the best approaches in the literature. These are the following:

BelSch06:

Branch-cut-and-price algorithm proposed in [5] and executed at an Intel Xeon 3.10 GHz processor in [11]

DelIori20:

Enhanced pseudo-polynomial formulation proposed in [10], also executed at an Intel Xeon 3.10 GHz processor,

WLBL20:

Branch-cut-and-price algorithm proposed in [42] and executed at an Intel Xeon E5-1603 2.80 GHz.

The results are shown in Table 1. In the first column, the name of the dataset is given. The second column gives the number of items in the instances of this dataset. Then for each algorithm, we show the number of instances solved within the time limit and the average solution time. The time limit is 10 min for the first three classes of instances, and 1 h for instances in classes AI and ANI. For unsolved instances, the solution time is set to the time limit. We mark in italics the best results for each dataset, considering first the number of solved instances and then the average time in case of ties.

Table 1 Comparison of VRPSolver with best approaches from the literature on BPP instances

It can be seen that VRPSolver is able to solve more instances to optimality than any other algorithm. However, the average solution time is significantly worse than competitors for the first three classes of instances. For the two most difficult classes AI and ANI, our approach clearly showed the best results. Algorithm WLBL20 is close to VRPSolver both in terms of the number of solved instances and the solution time in seconds. This is not surprising as WLBL20 is a branch-cut-and-price algorithm similar to the one used in VRPSolver, but with a specialized implementation. The main differences are that VRPSolver (i) uses bi-directional labeling algorithm for the pricing problem, (ii) employs stabilization and enumeration, and (iii) uses 3- and 4-row limited-memory rank-1 cuts, whereas WLB uses only 3-row full-memory cuts, and (iv) uses branching over accumulated resource consumption instead of Ryan and Foster branching.

The bottleneck of our algorithm for solving instances of classes AI and ANI with 600 items or more is the LP solver numerical tolerance. For such instances, sometimes, a column added to the master problem does not enter in the basis, in spite of having a negative reduced cost according to the current optimal dual solution provided by CPLEX. This may happen even if the reduced cost tolerance in CPLEX is set to its minimum value 10^− 9. In those cases, the column generation procedure is stopped and the safe Lagrangean bound is used. The safe bound is only a little weaker than the potential bound that would be obtained by solving the master LP to the end. Yet, this may make a lot of difference. It is quite frequent on those hard BPP instances that the lower bound of a node is very close to be one unit away from the primal upper bound. The use of a slightly worse lower bound may be enough to prevent the pruning of that node.

In Table 2, we compare branching over accumulated resource consumption and Ryan and Foster branching. The comparison is done on classes of instances for which average number of nodes is greater than 1, i.e., branching is needed for at least one instance in the class. It can be seen that one can solve more instances when employing the branching over accumulated resource consumption, and the average solution time is also decreased. The main reason is that Ryan and Foster branching is “non-robust.” Additional binary resources should be added to the resource constrained shortest path pricing problem to take into account Ryan and Foster branching constraints. Thus, the pricing problem takes significantly more time to be solved, and fewer nodes can be explored within the time limit.

Table 2 Comparison of branching strategies

The first linear relaxation of the BPP model (corresponding to Eq. 2 ), before cuts are added or branching is performed, is equivalent to Gilmore and Gomory relaxation and can be solved using a knapsack algorithm in the pricing. Table 3 presents a comparison of solving that first relaxation by using the VRPSolver RCSP labeling algorithm in the pricing with the use of a high-performance specialized algorithm for the binary knapsack problem. For the latter, we have chosen the algorithm by Pisinger [33]. We skip instances with 1000 items as for some of these instances, the column generation algorithm did not converge in 1 h when the pricing is solved by the labeling algorithm. The first two columns are as in the previous tables. Then in next columns, for each algorithm, we show the average solution time, average number column generation iterations, and the average number of generated columns. As can be seen, using a specialized algorithm for the knapsack problem makes that column generation procedure two to four times faster. The number of iterations is larger as at most one column per iteration is generated. When using the labeling algorithm, at most 100 columns are generated on every iteration. However, each iteration, including the solution of a larger LP, is much more expensive.

Table 3 Comparison of pricing algorithms for solving the first linear relaxation

In spite of being less efficient for the first column generation, the use of the labeling algorithm for the RCSP in the overall branch-cut-and-price algorithm still has many advantages, allowing the use of important algorithmic elements: rank-1 cuts, path enumeration, and branching over accumulated resource consumption. However, a hybrid pricing strategy that uses Pisinger’s code for the first column generation, while the subproblem structure is still a knapsack, would indeed save some time. In some cases, the saving would be significant. For example, for the AI instances with 201 items, the average total time would decrease from 17 to 6 s. We preferred not do that in our main experiments because the publicly available version of the VRPSolver does not have the feature of using external algorithms for the pricing, so its users would not be able to reproduce the reported results.

Another note concerns the set-partitioning constraints (5b) and (8b). It could be advantageous to define set-covering constraints of format x_i ≥ 1 instead, so the dual variables would never be negative. However, our preliminary experiments showed that the solution time of the first column generation would be reduced by only 10–20%, due to the fact that VRPSolver already uses a strong stabilization mechanism. No gains were observed in the remainder of the algorithm, after cuts, enumeration, diving heuristics, or branching starts to be performed. Thus, the overall improvements were not significant. We prefer to keep the set-partitioning constraints because they are more intuitive to the average VRPSolver user. For similar reasons, the dual cuts from [38] do not improve results significantly and were not used in the reported experiments.

A last note concerns the item ordering in the path generator graph (see Fig. 1). In our tests, the items followed the order in which they appear in the original instance files, sorted in non-increasing order of weights. We have experimented with two different orders: a random order and the alternating order, in which the first item (the one with largest weight) goes first in the graph, the second item (the second largest weight goes last in the graph), the third item goes second in the graph, and so on. These experiments show that the item ordering does not have any significant impact on the results. The reason is that the number of non-dominated labels in the exact labeling algorithm during the first column generation convergence is close to $\mathcal {I}.Q$, the number of states in the standard dynamic programming algorithm for the binary knapsack problem. Therefore, there is no sparsity to be explored by changing the order of items.

5.2 Vector Packing Problem

For the experiments on the VPP, we use classic 2-dimensional instances generated in [7]. These instances have from 25 to 200 items. We have also used the 20-dimensional instances obtained in [6] by aggregating ten 2-dimensional ones. The parameterization of VRPSolver is similar to the one used for the BPP instances except by the following changes.

• The number of buckets per vertex is set to 2000 in the labeling algorithm.

• A labeling heuristic is used for the heuristic pricing in which each bucket contains at most 8 non-dominated labels.

• Rank-1 cuts are not generated.

• When applying the path enumeration technique, the number of labels is limited to 10⁵. If this number is exceeded, the path enumeration is interrupted.

We do not use initial upper bounds. In order to obtain primal solutions, the diving heuristic embedded in VRPSolver is used only at the root node, with Limited Discrepancy Search [36] having parameterization χ^depth = 2, χ^disc = 3, which ensures that at most 10 dives are performed.

We compare the results of VRPSolver with the best results in the literature. These are the following:

BraPed16:

Graph compression and arc-flow model-based approach proposed in [6] and executed at a Quad-Core Intel Xeon 2.66 GHz processor,

HesGscIrn18:

Stabilized branch-and-price algorithm, using a labeling algorithm for RCSP in the pricing, proposed in [19] and executed at an Intel i7-5930k 3.5GHz processor.

WLLH20:

Branch-and-price algorithm proposed in [43] only for the 2-dimensional case, using a specially tailored 2-D binary knapsack algorithm for the pricing subproblem, executed at an Intel i7-6700 3.40GHz processor.

Table 4 Comparison of VRPSolver with best approaches from the literature on the vector packing instances with 2 dimensions

In Table 4, we present the results for classes of 2-dimensional instances for which the average VRPSolver solution time was more than 10 s. In the first column, the data class is given. The second column gives the number of items in the instances. Then, for each algorithm, we show the number of instances solved within the 1-h time limit and the average solution time in seconds. For unsolved instances, the solution time is set to the time limit.

VRPSolver clearly outperforms approaches BraPed16 and HesGscIrn18. The most recent algorithm WLLH20 is by far the fastest in almost all instances. However, VRPSolver solved the largest number of instances, including 3 open instances in class 9 with 200 items. In [43], another algorithm could solve 5 instances in class 9 with 200 items. It can be seen in Table 4 that the other classes of instances are “easy,” in the sense that all their instances are solvable in root node, without need for cutting or branching.

Table 5 Comparison of VRPSolver with best approaches from the literature on the vector packing instances with 20 dimensions

Table 6 Comparison of VRPSolver with the approach from [4] on the variable size bin packing instances in classes 0, 1, and 2

In Table 5, we present the results for 20-dimensional instances for which the VRPSolver solution time was more than 10 s. In the first column, the data class is given. The second column gives to the number of items. Then, for each algorithm, we give the solution time. The instance is solved to optimality if the time is less than 3600 s. VRPSolver is the fastest approach for the instances shown, and it solved the largest number of instances to optimality, including one open instance. All instances are solved at the root node without branching. For non-solved instances, the column generation procedure did not converge in 1 h due to a large difficulty of the pricing problem.

As for the BPP, we have experimented with different orders of items. Contrary to the bin packing, item order has an impact on the solution time when solving VPP instances. However, this impact was not radical during our preliminary experiments. Moreover, we do not have any good prediction mechanism based on the instance data to decide which order is better and which one is worse. Therefore, for the final experiments, we use the same order in which items appear in original instances.

5.3 Variable Sized Bin Packing Problem

For the experiments on the VSBPP, we use classic instances generated according to the procedure described in Monaci [23]. In addition, we use instances of VSBPPOI proposed in [4]. These instances are obtained by modification of instances from [23]. There are 4 classes of instances: class 0, class 1, class 2, and class 3. In instances in class 0, all items are compulsory. These instances are generated in the same way as the original Monaci instances. In instances in classes 1 and 2, all items are optional. Instances in the first three classes contain from 25 to 500 items. In instances in class 3, there is a mixture of compulsory and optional items. This class contains only instances with 500 items. All instances have been generated in [4].

The parameterization of VRPSolver is similar to the one used for the bin packing instances except the following changes.

• When applying the path enumeration technique, the number of enumerated paths is limited to 2 ⋅ 10⁶, and the number of generated labels is limited to 2 ⋅ 10⁵.

• The node is finished by the MIP solver if the number of enumerated paths is less or equal to 5000.

We do not use initial upper bounds, but feasible solutions are obtained by the heuristic with Limited Discrepancy Search heuristic [36] with the same parameterization as for the vector packing instances. We compare the results of VRPSolver with those obtained by the branch-and-price algorithm proposed in [4], which we denote as BCPT14, executed at a Pentium IV 3.0 GHz processor.

In Table 6, we present the results for the instance classes 0, 1, and 2. In the first column, the data class is given. The second and third columns give the number of bin types and the number of items. Then for each algorithm, we show the number of instances solved within the 1-h time limit, the average solution time in seconds, and the average number of nodes. For unsolved instances, the solution time is set to the time limit.

VRPSolver clearly outperforms the approach BCPT14, both in terms of the solution time and the number of solved instances. Note that instances in class 0 with only compulsory items seem to be solved much more efficiently by the older approaches proposed in [1] (all 300 instances solved, all average times less than 1 s) and in [17] (only two unsolved instances). We did not include their results in Table 6 because those authors used similarly generated instances, not the original instances of [23]. Anyway, it seems that the branch-cut-and-price in [1] for the multiple length (assumes that the cost of a bin type is given by its capacity) cutting stock problem is particularly better for that kind of instances due to their cutting stock structure. Monaci’s generation scheme creates instances with only 20 to 100 distinct weights. Solving such instances using a bin packing code like the one in BCPT14 and in our VRPSolver model leads to unnecessary large LPs and symmetry in the branching.

Table 7 Comparison of VRPSolver with the approach from [4] on the variable size bin packing instances in class 3

In Table 7, we present the results for the instance class 3 with 500 items. In the first column, the percentage of compulsory items. Other columns are the same as in Table 6. One can see again that VRPSolver clearly outperforms the approach BCPT14.

6 Conclusions

This paper proposes branch-cut-and-price algorithms for the bin packing problem and for some of its well-studied variants, defined as VRPSolver models. This is quite convenient, each model is coded in about 50 lines of Julia language using the package JuMP.jl [12]. Here, we do not count the lines of code for reading the instance data and for solution output. The bulk of the implementation effort is the tuning of some VRPSolver parameters (important but not critical, running the proposed model using VRPSolver default values would still obtain results not much worse than the competing algorithm). As far as we know, that set of models provides the most generic existing exact code for bin packing variants. Moreover, the code is freely available for academic purposes.

The computational experiments on the classic BPP indicate that:

• VRPSolver branch-cut-and-price algorithm seems to be an excellent alternative for instances that are really hard for existing exact methods, either because they are primal-hard or dual-hard. Primal-hard instances are those where an optimal solution is quite difficult to find, either by combinatorial heuristics (like [2]), by LP rounding or by diving methods. However, once an optimal solution is solution found, it is immediately proved to be optimal by Gilmore and Gomory bound. Those instances have the so-called Integer Round Up Property (IRUP). For example, AI instances are primal-hard. Dual-hard instances are those where finding an optimal solution is relatively easy, but Gilmore and Gomory bound is not enough to prove its optimality, cutting and/or branching is required. For example, ANI BPP instances are dual-hard. Interestingly, there are no BPP instances in the literature that are primal-and-dual-hard.

• On the other hand, on instances that are not so difficult, specialized methods may be faster, sometimes much faster. In fact, Alvim et al. [2] mention that for a significant number of BPP instances greedy heuristics (like first-fit decreasing or best-fit decreasing) find solutions that can proven to be optimal using fast lower bounding procedures (like those in [14])

A similar behavior can be observed in the experiments with the other bin packing variants: the VRPSolver branch-cut-and-price algorithms are likely to outperform existing specialized methods on harder instances. This is explained by the fact that some advanced features in VRPSolver, like limited-memory rank-1 cuts, enumeration, hierarchical strong branching over accumulated resource consumption, and limited discrepancy search diving heuristics, are more likely to make a difference on those harder instances.

As a final remark, we believe that the robust results obtained by the VRPSolver models over all those bin packing variants encourage future attempts of using that tool for solving other families of problems, not only for vehicle routing.