The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design

Abstract

In this paper, we present a state-of-the-art branch-and-cut (B&C) algorithm for the multicommodity capacitated fixed charge network design problem (MCND). This algorithm combines bounding and branching procedures inspired by the latest developments in mixed-integer programming (MIP) software tools. Several filtering methods that exploit the structure of the MCND are also developed and embedded within the B&C algorithm. These filtering methods apply inference techniques to forbid combinations of values for some variables. This can take the form of adding cuts, reducing the domains of the variables, or fixing the values of the variables. Our experiments on a large set of randomly generated instances show that an appropriate selection of filtering techniques allows the B&C algorithm to perform better than the variant of the algorithm without filtering. These experiments also show that the B&C algorithm, with or without filtering, is competitive with a state-of-the-art MIP solver.

1 Introduction

We present a branch-and-cut algorithm (B&C) to solve the multicommodity capacitated fixed charge network design problem (MCND), following the development of a specialized cutting-plane method described in Chouman et al. (2017). In this last paper, several valid inequalities, separation routines and modeling alternatives are presented and analyzed, the cutting-plane procedure being embedded within a state-of-the-art mixed-integer programming (MIP) solver. In the present paper, our aim is to develop a B&C method tailored for the problem that includes not only the cuts and separation routines from Chouman et al. (2017), but also filtering methods that exploit the structural properties of the problem. In general, such filtering methods apply inference techniques to forbid combinations of values for some variables, and proceed by adding cuts, reducing the domains of the variables, or fixing the values of the variables. Filtering methods are widely used in constraint programming (Hooker 2002), while in MIP, they arise within preprocessing routines (Savelsbergh 1994) and domain reduction tests based on reduced cost information. As such, filtering methods are an integral part of state-of-the-art MIP solvers (Atamtürk and Savelsbergh 2005).

To the best of our knowledge, along with the cutting-plane approach (Chouman et al. 2017) that constitutes the foundation for this work, the present paper is one of the few attempts at solving optimally the MCND, following earlier contributions based on Benders decomposition (Costa et al. 2009, 2012), column generation (Gendron and Larose 2014) and Lagrangian relaxation approaches (Crainic et al. 1999, 2001; Gendron and Crainic 1994; Holmberg and Yuan 2000; Kliewer and Timajev 2005; Sellmann et al. 2002). Heuristic methods have also been proposed for computing feasible solutions (Crainic et al. 2000, 2004; Crainic and Gendreau 2002; Ghamlouche et al. 2003, 2004; Hewitt et al. 2010; Katayama et al. 2009; Rodríguez-Martín and Salazar-González 2010). Typically, instances with few commodities (say, in the order of 10) can be solved to optimality in reasonable time by state-of-the-art MIP solvers, while instances with many commodities (more than 100) are very hard to solve to optimality (in Chouman et al. (2017), an average gap of 1.93% is reported for 57 difficult instances that are still unsolved after 2 hours of computing time). However, even for these instances, very good (often optimal) upper bounds are obtained by the cited heuristic methods. In our developments, we will therefore focus on the exact solution of these difficult large-scale instances, assuming that near-optimal solutions are readily available.

While a B&C algorithm is often the method of choice for the exact solution of network design problems similar to the MCND (Aardal 1998; Aardal et al. 1995; Atamtürk 2002; Atamtürk and Rajan 2002; Barahona 1996; Bienstock et al. 1998; Bienstock and Günlük 1996; Gabrel et al. 1999; Günlük 1999; Leung and Magnanti 1989; Magnanti et al. 1993, 1995; Ortega and Wolsey 2003; Raack et al. 2011), there are no systematic studies regarding the behavior and performance of filtering methods in B&C algorithms for network design problems. Our main goal is to address this issue. We proceed by first presenting the basic features of the B&C algorithm we propose for the MCND, i.e., bounding and branching procedures inspired by Chouman et al. (2017) and by the latest developments in MIP software tools (Achterberg et al. 2005; Atamtürk and Savelsbergh 2005). We then develop a number of filtering methods that exploit the structure of the MCND and analyze their performance using the proposed B&C algorithm.

Our contributions are threefold:

• We develop a tailored B&C algorithm for the MCND. The implementation of this algorithm combines the cutting-plane method from Chouman et al. (2017) with an adaptation of the reliability branching rule introduced in Achterberg et al. (2005).

• We develop several filtering methods that are embedded within the B&C algorithm. These filtering methods are based either on duality arguments or on the detection of infeasible solutions. With the exception of the classical LP-based reduced cost fixing technique, they all exploit the structure of the MCND. Hence, to the best of our knowledge, state-of-the-art MIP solvers do not perform these filtering methods.

• By performing experiments on a set of 196 randomly generated instances used in other studies on the MCND, we show the efficiency and the effectiveness of both the B&C algorithm and the filtering methods. Specifically, our computational results illustrate that an appropriate selection of filtering techniques and their associated parameters provides notable improvements over the B&C algorithm without filtering. Furthermore, we also show that the B&C algorithm, with or without filtering, is competitive with a state-of-the-art MIP solver.

The paper is organized as follows. Section 2 presents the main features of the B&C algorithm, namely the valid inequalities and their separation routines, the cutting-plane procedure and the branching rule. Section 3 describes the filtering methods, while Sect. 4 summarizes the overall B&C algorithm. In Sect. 5, we present the results of extensive computational experiments on a large set of instances. Section 6 summarizes our findings and discusses avenues for future research.

2 Main features of the branch-and-cut algorithm

We describe the MCND and the formulation used within the B&C algorithm in Sect. 2.1. In Sect. 2.2, we present the valid inequalities and the separation routines performed at every node of the B&C tree by the cutting-plane procedure. The latter is summarized in Sect. 2.3, while the branching rule used in the B&C algorithm is described in Sect. 2.4.

2.1 Problem formulation

Given a directed network $G=(V,A)$, with V the set of nodes and A the set of arcs, we let K be the set of commodities, each commodity k having one origin, O(k), and one destination, D(k), with a demand $d^k>0$ between the two nodes. We associate with each arc (i, j) the per unit routing cost $c_{ij}\ge 0$, the fixed cost $f_{ij}\ge 0$, and the capacity $u_{ij}>0$. We assume that capacities and demands take integer values. Two types of variables are used to formulate the MCND: the continuous flow variable $x_{ij}^k$, which represents the flow of commodity k on arc (i, j), and the binary design variable $y_{ij}$, which equals 1 when arc (i, j) is used, and 0, otherwise. Given these definitions, the MCND can be formulated as follows:

$$\begin{aligned} Z= & {} \min \sum _{k \in K} \sum _{(i,j) \in A} c_{ij} x_{ij}^{k} + \sum _{(i,j) \in A} f_{ij} y_{ij} \end{aligned}$$

(1)

$$\begin{aligned} \sum _{j \in V^{+}_i} x_{ij}^{k} - \sum _{j \in V^{-}_i} x_{ji}^{k}= & {} \left\{ \begin{array}{rl} d^k ,&{} \quad \text{ if } \; i = O(k), \\ - d^k ,&{} \quad \text{ if } \; i = D(k), \quad i \in V, k \in K, \\ 0 , &{} \quad \text{ otherwise }, \end{array} \right. \end{aligned}$$

(2)

$$\begin{aligned} \sum _{k \in K} x_{ij}^{k}\le & {} u_{ij} y_{ij}, \quad (i,j) \in A , \end{aligned}$$

(3)

$$\begin{aligned} 0\le & {} x_{ij}^{k} \le b_{ij}^k , \quad (i,j) \in A , k \in K, \end{aligned}$$

(4)

$$\begin{aligned} y_{ij}\in & {} \{ 0,1 \}, \quad (i,j) \in A, \end{aligned}$$

(5)

where $b_{ij}^k = \min \{u_{ij},d^k\}$, $V^{+}_i = \{ j \in V | (i,j) \in A\}$ and $V^{-}_i = \{ j \in V |(j,i) \in A\}$. Constraints (2) represent the flow conservation equations for each node and each commodity. Relations (3) ensure that the flow on each arc does not exceed its capacity; they also play the role of forcing constraints, since they ensure that no flow is allowed on an arc unless the fixed cost on the arc is incurred. Constraints (4) and (5) define the domains of the flow and design variables, respectively. Note that $b_{ij}^k$ can be any valid upper bound on the amount of flow of commodity k on arc (i, j). The model can thus integrate commodity-dependent capacities, although we only assume a capacity $u_{ij}$ on each arc (i, j) that binds the flow of all commodities on the arc. Similarly, we assume that the routing costs do not depend on the commodities, although it would be easy to handle commodity-dependent costs in our model.

To characterize the status of the binary design variables at each node of the B&C tree, $A_1$ and $A_0$ denote the sets of open and closed arcs, respectively, i.e., the arcs fixed to 1 and to 0 by branching and variable fixing; $A_{01}=A\setminus (A_1 \cup A_0)$ denotes the set of free arcs. The restricted problem considered at each node then consists of model (1)–(5) to which we add the constraints $y_{ij} = 0, \, (i,j)\in A_0$, and $y_{ij} = 1, \, (i,j)\in A_1$. The cutting-plane procedure strengthens the linear programming (LP) relaxation of this restricted problem by adding inequalities that are valid for model (1)–(5), but violated by the solution of the current LP relaxation. These inequalities are presented next.

2.2 Valid inequalities and separation

Our cutting-plane procedure exploits the valid inequalities that are shown to be the most useful in Chouman et al. (2017). We use two classes of valid inequalities, the strong and knapsack inequalities, which are described in the next subsections, along with their respective separation algorithms. Chouman et al. (2017) also use flow cover/pack inequalities (Atamtürk 2001; Gu et al. 1999b; Louveaux and Wolsey 2007; Padberg et al. 1985; Roy and Wolsey 1987). Although these inequalities are effective in improving the lower bounds, they provide similar bound improvements, on most instances, than the combination of strong and knapsack inequalities. Since their separation is significantly more expensive computationally, we have decided not to use them in our cutting-plane procedure.

2.2.1 Strong inequalities

The following inequalities, in a similar way as constraints (3), play the role of forcing constraints, since they also forbid any flow to circulate on an arc that is not part of the selected design:

$$\begin{aligned} x_{ij}^k \le b_{ij}^k y_{ij} , \quad (i,j) \in A, k \in K. \end{aligned}$$

(6)

Adding these so-called strong inequalities to the model significantly improves the quality of the LP relaxation lower bound (Chouman et al. 2017; Crainic et al. 1999; Gendron and Crainic 1994). Adding a priori all these inequalities to the LP relaxation yields very large models that frequently exhibit degeneracy. We add them in a dynamic way, identifying only those that are violated by the solution of the current LP relaxation. Their separation is trivial, as it suffices to scan each arc and each commodity to identify all violated inequalities.

2.2.2 Knapsack inequalities

Assuming $S \subset V$ is a non-empty subset of V and $\bar{S} = V \backslash S$ is its complement, we note the corresponding cutset $(S,\bar{S})=\{(i,j)\in A\;|\;i\in S,j\in \bar{S}\}$ and its associated commodity subset $K(S,\bar{S})=\{k\in K\;|\;O(k)\in S, \, D(k)\in \bar{S}\}$. We then have the following valid inequality, which is obtained by combining the flow conservation equations (2) with the capacity constraints (3):

$$\begin{aligned} \sum _{(i,j) \in (S,\bar{S})} u_{ij} y_{ij} \ge d_{(S,\bar{S})}, \end{aligned}$$

(7)

where $d_{(S,\bar{S})}=\sum _{k \in K(S,\bar{S})} d^k$. This inequality simply states that there should be enough capacity on the arcs of the cutset $(S,\bar{S})$ to satisfy the total demand that must flow from S to $\bar{S}$. By complementing the y variables, i.e., replacing $y_{ij}$ by $1-y_{ij}$, the cutset inequality reduces to a 0-1 knapsack structure.

The well-known cover inequalities for the 0-1 knapsack structure (Balas 1975; Hammer et al. 1975; Wolsey 1975) are based on the following definition: $C \subseteq (S,\bar{S})$ is a cover if the total capacity of the arcs in $(S,\bar{S}) {\setminus } C$ does not cover the demand, i.e., $\sum _{(i,j) \in (S,\bar{S}) \setminus C} u_{ij} < d_{(S,\bar{S})}$. For every cover $C \subseteq (S,\bar{S})$, the following cover inequality is valid for the MCND:

$$\begin{aligned} \sum _{(i,j) \in C} y_{ij} \ge 1. \end{aligned}$$

(8)

In addition to the cover inequalities, we use the so-called minimum cardinality inequalities Martello and Toth (1997). To define these inequalities, we assume the capacities of the arcs in $(S, \bar{S})$ are sorted in non-increasing order: $u_{a(t)} \ge u_{a(t+1)}$, where $a(t)\in (S,\bar{S}), \, t=1,...,|(S, \bar{S})|$ ($u_{a(t+1)}=u_{a(t)}$). This allows us to compute the least number of arcs in $(S, \bar{S})$ that must be opened in any feasible solution: $l_{(S,\bar{S})} = \max \; \{ h \;|\; \sum _{t=1,...,h} u_{a(t)} < d_{(S,\bar{S})} \} +1$. We then derive the minimum cardinality inequality:

$$\begin{aligned} \sum _{(i,j) \in (S,\bar{S})} y_{ij} \ge l_{(S,\bar{S})}. \end{aligned}$$

(9)

The generation of knapsack inequalities is based on single-node cutsets, i.e., for each cutset $(S, \bar{S})$, S is an origin or $\bar{S}$ is a destination for at least one commodity. Methods to generate cutsets $(S, \bar{S})$ with $|S|>1$ are developed and tested in Chouman et al. (2017), where it is observed that, for most instances, the single-node cutsets are responsible for most of the lower bound improvement.

For each single-node cutset, we try to generate one violated cover inequality and one violated minimum cardinality inequality. Initially, some y variables are fixed to either 0 or 1, using the LP relaxation solution. Two different variable fixing strategies are used, depending on the type of inequality we try to generate, cover or minimum cardinality (details can be found in Chouman et al. (2017)). Thus, we obtain in this way two restricted cutsets, one that is used to derive a cover inequality, the other to generate a minimum cardinality inequality. The cover inequality is obtained by the separation routine described in Chouman et al. (2017); Gu et al. (1998, 1999a). To generate the minimum cardinality inequality, we simply sort the arcs in the corresponding restricted cutset and then derive the minimum number of arcs to be opened. For each of the two inequalities thus obtained, a sequential lifting procedure is applied to obtain an inequality that is valid for the original cutset, and therefore also for the MCND. The same lifting procedure is used for the two inequalities, cover and minimum cardinality. If any of the resulting valid inequalities is violated by the solution of the current LP relaxation solution, it is added to the LP relaxation.

2.3 Cutting-plane procedure

As explained above, the cutting-plane procedure is a simpler variant of the method described in Chouman et al. (2017), since it generates strong and knapsack inequalities, but no flow cover/pack inequalities. At each node of the B&C tree, it starts by solving the LP relaxation of the current formulation, defined by the current status of the arcs, open, closed or free, and by the cuts added so far. Subsequently, it alternates between the generation of cuts and the solution of the current LP relaxation.

The cutting-plane procedure performs the following steps, where $Z^*$ is the objective value of the best known feasible solution and $\delta$ is a parameter that measures the minimum bound improvement between two consecutive LPs that is required to continue the procedure (we use $\delta = 0.1$ as in Chouman et al. (2017)):

• 1. $Z^l_{last} \leftarrow 0$.

• 2. Solve the LP relaxation; let $Z^l$ be the LP optimal value ($Z^l=+\,\infty$ if the LP is infeasible), and $\bar{y}$ the LP design solution.

• 3. If $\bar{y}$ is integral or $Z^l\ge Z^*$ or $Z^l - Z^l_{last} \le \delta$, then stop.

• 4. Try to generate cuts.

• 5. If some cuts are found, then $Z^l_{last} \leftarrow Z^l$ and go to 2.

The B&C algorithm manages two types of cuts: global cuts, which are valid at any node of the B&C tree, and local cuts, which are valid only at the current node and at all its descendants. When a node is handled immediately after its parent, the LP relaxation is simply reoptimized after taking into account the additions made by branching and filtering. When a node is obtained from backtracking in the B&C tree, the LP relaxation is built by considering the LP solution from its parent and by adding global and local cuts violated by this solution.

The strong inequalities are generated at all nodes and managed as global cuts. The knapsack inequalities are generated only at the root node and are therefore managed as global cuts. Other global and local cuts are generated by the filtering methods described in Sect. 3.

2.4 Branching rule

When branching is performed, the set of free arcs with fractional $\bar{y}$ values, denoted $\bar{A}_{01}$, is non-empty, i.e., $\bar{A}_{01} = \{(i,j)\in A_{01}| 0<\bar{y}_{ij}<1\}\ne \emptyset$. In a classical way, the branching rule selects one arc from this set, say $a^*\in \bar{A}_{01}$, and generates the 0-child and the 1-child defined by removing $a^*$ from $A_{01}$ and by adding it to $A_0$ and to $A_1$, respectively. To select $a^*$, we use a variant of reliability branching (Achterberg et al. 2005), a rule that combines the strengths of two other branching rules, pseudo-cost branching and strong branching.

To define these different branching rules, we use the following notation. When branching on an arc a, we define the increase in the LP bounds from the parent node to the 0-child and the 1-child as $\Delta ^0_a$ and $\Delta ^1_a$, respectively. We also define the corresponding per unit increase in the LP bounds from the parent to its children as follows: $\rho ^h_a = \frac{\Delta ^h_a}{g^h_a}$, $h=0,1$, where $g^0_a = \bar{y}_a$ and $g^1_a= 1-\bar{y}_a$. Assume that, after branching on arc a, the increase in the LP bounds from the parent node to the 0-child and the 1-child have been computed $n_a^0$ and $n_a^1$ times; we can then define the average per unit increase in the LP bounds from the parent node to its children as $\bar{\rho }^h_a$, $h=0,1$ (i.e., the average value of $\rho ^h_a$ over the $n_a^h$ times arc a has been selected for branching and the increase in the LP bound from the parent to its h-child has been computed).

Pseudo-cost branching (Benichou et al. 1971) is based on computing and storing the values $\bar{\rho }^h_a$, $h=0,1$, for each arc a. This branching rule selects the free arc $a^*$ such that

$$\begin{aligned} a^* = \mathrm {arg} \max _{a\in \bar{A}_{01}}\{ \min (g_a^0 \bar{\rho }_a^0, g_a^1 \bar{\rho }_a^1) \}. \end{aligned}$$

In this formula, $g_a^h \bar{\rho }_a^h$, $h=0,1$, represent estimates of the increase in the LP bounds from the current node to the children that would be obtained by selecting arc a for branching. Initially, no values of LP bound increases, i.e., $\Delta _a^h$, $h=0,1$, are available; hence, we simply set $\bar{\rho }_a^h= 1$, $h=0,1$, for each arc a. The selected arc is then the one with the most fractional value $\bar{y}_a$, i.e., with $\bar{y}_a$ closest to 0.5.

An alternative is strong branching (Applegate et al. 1995), which is based on computing estimates of the LP bound increases $\Delta _a^h$, $h=0,1$, prior to branching. This rule amounts to look at the effect of selecting arc a by adding to the current LP relaxation the constraints $y_a=0$ and $y_a=1$ in order to evaluate $\Delta _a^0$ and $\Delta _a^1$, respectively. This is performed by reoptimizing the current LP relaxation with the added constraint through a few iterations of the dual simplex method. The strong branching rule then selects the free arc $a^*$ such that

$$\begin{aligned} a^* = \mathrm {arg} \max _{a\in \bar{A}_{01}}\{ \min (\Delta _a^0, \Delta _a^1) \}. \end{aligned}$$

The idea behind reliability branching (Achterberg et al. 2005) is to perform strong branching at the beginning of the exploration to obtain reliable LP bound increase estimates and then to switch to pseudo-cost branching for the rest of the exploration. More precisely, assuming a free arc $a^*$ is selected by the pseudo-cost branching rule, if $\min (n_{a^*}^0,n_{a^*}^1) < \eta$, where $\eta \ge 0$ is a parameter, then the pseudo-costs associated with arc $a^*$ are considered unreliable, and the pseudo-cost estimates are replaced by the strong branching estimates of LP bound increases. When $\eta = 0$, reliability branching reduces to pseudo-cost branching, while if $\eta = +\,\infty$, reliability branching reduces to strong branching.

Our implementation of reliability branching works as follows. We first select the free arc $a^* \in \bar{A}_{01}$ according to the pseudo-cost branching rule. If $a^*$ is not reliable, i.e., $\min (n_{a^*}^0,n_{a^*}^1) < \eta$, then the arcs $a\in \bar{A}_{01}$ with unreliable pseudo-costs are sorted in non-increasing order of $\min (g_a^0 \bar{\rho }_a^0, g_a^1 \bar{\rho }_a^1)$. Using that particular order, we keep as a candidate for branching the arc $a^*$ that achieves so far the maximum of $\min (\Delta _a^0, \Delta _a^1)$, where $\Delta _a^h$, $h=0,1$, are computed with the dual simplex method (limited to 100 iterations). If that candidate is not updated for $\lambda$ successive attempts, we select $a^*$ for branching. The branching procedure thus performs the following steps (we use $\eta = 8$ and $\lambda = 4$ as in Achterberg et al. (2005)):

• 1. $a^* \leftarrow \mathrm {arg} \max _{a\in \bar{A}_{01}}\{ \min (g_a^0 \bar{\rho }_a^0, g_a^1 \bar{\rho }_a^1) \}$.

• 2. If $\min (n_{a^*}^0,n_{a^*}^1) \ge \eta$, then stop.

• 3. Let $m\leftarrow 0$, $s^* \leftarrow 0$ and sort the arcs of $(\bar{A}_{01}\cap \{a\in A|\min (n_a^0,n_a^1)< \eta \})$ in non-increasing order of $\min (g_a^0 \bar{\rho }_a^0, g_a^1 \bar{\rho }_a^1)$.

• 4. For all $a\in (\bar{A}_{01}\cap \{a\in A|\min (n_a^0,n_a^1)< \eta \})$ (sorted):

  • (a) $m\leftarrow m+1$.

  • (b) Compute $\Delta _a^0$ and update $n_a^0$ and $\bar{\rho }_a^0$ (unless the LP is infeasible); if $Z^l+\Delta _a^0 \ge Z^*$, then fix arc a to value 1, i.e., transfer a from $A_{01}$ to $A_1$.

  • (c) If arc a has not been fixed to value 1 in the previous step, then compute $\Delta _a^1$ and update $n_a^1$ and $\bar{\rho }_a^1$; if $Z^l+\Delta _a^1 \ge Z^*$, then fix arc a to value 0, i.e., transfer a from $A_{01}$ to $A_0$.

  • (d) If arc a has not been fixed to value 0 or 1 in the previous steps and if $\min (\Delta _a^0,\Delta _a^1) > s^*$, then $a^*\leftarrow a$, $s^*\leftarrow \min (\Delta _a^0,\Delta _a^1)$ and $m\leftarrow 0$.

  • (e) If $m\ge \lambda$, then stop.

Note that a filtering method is already embedded into the strong branching loop in steps (4b) and (4c). In both steps, we use the fact that $Z^l + \Delta _a^h$ is a lower bound on the restriction of the MCND defined by $y_a = h$, $h=0,1$. Therefore, if this lower bound exceeds the best known upper $Z^*$ on the optimal value of the MCND, we can fix variable $y_a$ to the value $1 - h$. We see other examples of similar filtering methods in the next section.

3 Filtering methods

Filtering methods are applied at every node of the B&C tree. The general idea is to exclude solutions that cannot be optimal, given the current status of the design variables, i.e., the partition of the set of arcs into $A_{0}$, $A_{1}$ and $A_{01}$. The solutions are excluded through the addition of cuts that are generally local (i.e., valid only for the node and its descendants), but that can be global in some cases. Special types of cuts are worth noting: bound reduction consists in decreasing (increasing) the upper (lower) bound on a single variable, while variable fixing, a special case of bound reduction, assigns a value to a single variable (such cuts are heavily used in the field of constraint programming).

A common approach in filtering methods is to deduce from the addition of a constraint $\mathcal {C}$ the impossibility of finding an optimal solution that satisfies simultaneously $\mathcal {C}$ and the constraints that define the current B&C node. Hence, constraint $\lnot \mathcal {C}$, the complement of $\mathcal {C}$, can be added to cut all solutions that satisfy $\mathcal {C}$. To infer that the addition of $\mathcal {C}$ cannot lead to an optimal solution, we generally compute a lower bound $Z^l(\mathcal {C})$ on the optimal value of the restricted problem derived from the addition of $\mathcal {C}$. If $Z^l(\mathcal {C}) \ge Z^*$, where $Z^*$ is the value of the best known feasible solution, we can conclude that no optimal solution can be found when constraint $\mathcal {C}$ is added. A particular case of this test arises when we can deduce that no feasible solution can be obtained when $\mathcal {C}$ is added, since this case can be reduced to $Z^l(\mathcal {C}) = +\,\infty$.

Thus, to perform efficient and effective filtering methods, we: (1) derive lower bounds that are quickly computed based on duality arguments; (2) investigate sources of infeasibility to try to detect them as early as possible when exploring the B&C tree. The next three sections are dedicated to duality-based filtering techniques: the LP-based reduced cost fixing, the Lagrangian-based reduced cost fixing and the reduced cost bound reduction, which are presented in Sects. 3.1, 3.2, and 3.3, respectively. Then, we describe three feasibility-based filtering techniques: the generation of combinatorial Benders cuts, the connectivity-based filtering procedure, and the capacity-based filtering methods, which are presented in Sects. 3.4, 3.5, and 3.6, respectively.

3.1 LP-based reduced cost fixing

The reduced costs $\overline{f}_{ij}$ derived from the LP relaxation can be used to perform variable fixing. Indeed, for each non-basic variable $y_{ij}$ at value $\overline{y}_{ij}\in \{0,1\}$ and such that $(i,j)\in A_{01}$, we have $\overline{f}_{ij}\le 0$ if $\overline{y}_{ij}=1$, and $\overline{f}_{ij}\ge 0$ if $\overline{y}_{ij}=0$. If we add the constraint $y_{ij}=(1-\overline{y}_{ij})$, then $Z^l + |\overline{f}_{ij}|$ is a lower bound on the optimal value of the resulting problem, using standard LP duality theory. Therefore, if $Z^l + |\overline{f}_{ij}| \ge Z^*$, then we can fix $y_{ij}$ to value $\overline{y}_{ij}$. These tests are carried out immediately after performing the cutting-plane procedure by scanning all non-basic design variables. This filtering technique is common to all general purpose LP-based B&C algorithms and is performed by state-of-the-art MIP solvers. The next filtering method, however, exploits the particular structure of the MCND.

3.2 Lagrangian-based reduced cost fixing

At any node of the B&C tree, characterized by the sets $A_0$, $A_1$ and $A_{01}$, we consider the Lagrangian relaxation of the flow conservation equations, known as the knapsack relaxation (Gendron and Crainic 1994). Our objective is to use reduced costs derived from this Lagrangian relaxation to perform variable fixing, with the potential of delivering results that are different than those obtained when performing LP-based reduced cost fixing. More precisely, we consider the Lagrangian relaxation with respect to the formulation restricted by $A_0$, $A_1$, $A_{01}$, and defined by (1)–(5), plus the strong inequalities (6). Denoting $\pi =(\pi _i^k)_{i\in V}^{k\in K}$ the vector of Lagrange multipliers associated with the flow conservation equations, we then obtain the following Lagrangian subproblem:

$$\begin{aligned} Z^l_{LR}= & {} \sum _{k\in K}(\pi _{D(k)}^k- \pi _{O(k)}^k)d^k \\&+ \min \sum _{(i,j)\in A_{01}\cup A_1} \left\{ \sum _{k\in K}(c_{ij} + \pi _i^k - \pi _j^k) x_{ij}^k + f_{ij}y_{ij} \right\} \\ \sum _{k \in K} x_{ij}^{k}\le & {} u_{ij} y_{ij}, \quad (i,j) \in A_{01}\cup A_1 , \\ 0\le & {} x_{ij}^{k} \le b_{ij}^k y_{ij}, \quad (i,j) \in A_{01}\cup A_1 , k \in K, \\ y_{ij}= & {} 1, \quad (i,j)\in A_1, \\ y_{ij}\in & {} \{0,1\} , \quad (i,j) \in A_{01}. \end{aligned}$$

This problem can be solved by first considering, for each arc $(i,j)\in A_{01}\cup A_1$, the following continuous knapsack problem:

$$\begin{aligned} v_{ij} = \min \left\{ \sum _{k\in K} {\tilde{c}}_{ij}^k x_{ij}^k \;| \; \sum _{k\in K} x_{ij}^k \le u_{ij}; \; 0\le x_{ij}^k \le b_{ij}^k, \; k\in K\right\} , \end{aligned}$$

where ${\tilde{c}}_{ij}^k=c_{ij} + \pi _i^k - \pi _j^k$, $k\in K$. Indeed, it is easy to show that the Lagrangian subproblem can be reformulated as follows:

$$\begin{aligned} Z^l_{LR} = \sum _{k\in K}(\pi _{D(k)}^k - \pi _{O(k)}^k)d^k + \sum _{(i,j)\in A_1} {\tilde{f}}_{ij} + \sum _{(i,j)\in A_{01}} \min \{ {\tilde{f}}_{ij}y_{ij} \; | \; y_{ij} \in \{0,1\} \}, \end{aligned}$$

where ${\tilde{f}}_{ij} = v_{ij} + f_{ij}$, $(i,j)\in A_{01}\cup A_1$. An optimal solution to the subproblem for each arc $(i,j)\in A_{01}$ is given by ${\tilde{y}}_{ij} = 1$, if ${\tilde{f}}_{ij} < 0$, and ${\tilde{y}}_{ij} = 0$, otherwise.

Clearly, $Z^l_{LR}$ is a lower bound on the optimal value at the current node. Therefore, if $Z^l_{LR}\ge Z^*$, the current node can be fathomed. Furthermore, it is easy to derive variable fixing rules by using the quantity ${\tilde{f}}_{ij}$, which can be interpreted as a Lagrangian reduced cost associated with $y_{ij}$. Indeed, for each $(i,j)\in A_{01}$, it is immediate to see that $Z^l_{LR} + |{\tilde{f}}_{ij}|$ is a lower bound on the restricted problem obtained by adding the constraint $y_{ij} = 1 - {\tilde{y}}_{ij}$. Consequently, if $Z^l_{LR} + |{\tilde{f}}_{ij}| \ge Z^*$, then we can fix $y_{ij}$ to value ${\tilde{y}}_{ij}$.

The Lagrangian subproblem is solved after performing LP-based reduced cost fixing. The Lagrange multipliers are fixed to the values of the dual variables associated with the flow conservation equations that are obtained after performing the cutting-plane procedure. Note that the knapsack relaxation has been used to compute lower bounds in branch-and-bound algorithms for the MCND (Holmberg and Yuan 2000; Kliewer and Timajev 2005; Sellmann et al. 2002), where non-differentiable optimization, i.e., subgradient and bundle, methods were used to compute near-optimal Lagrange multipliers. The difference here is that we use the knapsack relaxation only to improve filtering at each node of the B&C tree and thus as a complement to the cutting-plane procedure, rather than as the main lower bounding method.

3.3 Flow upper bound reduction

We can use the LP-based reduced costs of the flow variables $x_{ij}^k$, $\overline{c}_{ij}^k$, to perform bound reduction on these variables. The basic idea is the following: assume we add the constraint $x_{ij}^k > a_{ij}^k$ to the LP relaxation and that the resulting lower bound exceeds $Z^*$. We can then conclude that the constraint $x_{ij}^k \le a_{ij}^k$ is valid. In order to compute $a_{ij}^k$, we use the following result.

Proposition 1

Let $\overline{x}_{ij}^k$ be the value of variable $x_{ij}^k$ in the optimal solution to the LP relaxation. If $\overline{x}_{ij}^k=0$, $\overline{c}_{ij}^k> 0$ and $Z^l+\overline{f}_{ij}(1-\overline{y}_{ij})+\overline{c}_{ij}^kb_{ij}^k > Z^*$, we have $x_{ij}^k\le a_{ij}^k <b_{ij}^k$, where

$$\begin{aligned} a_{ij}^k = \frac{Z^* - Z^l - \overline{f}_{ij}(1-\overline{y}_{ij})}{\overline{c}_{ij}^k}. \end{aligned}$$

Proof

We consider two cases. First, let us assume that $0<\overline{y}_{ij} \le 1$, which implies $\overline{f}_{ij}(1-\overline{y}_{ij})=0$. We note that, if $0<\overline{x}_{ij}^k <b_{ij}^k$, then $\overline{c}_{ij}^k = 0$ and, in this case, the LP relaxation lower bound remains the same when we increase $x_{ij}^k$ further. Therefore, for the LP relaxation lower bound to increase and exceed $Z^*$ when we add the constraint $x_{ij}^k > a_{ij}^k$, we must have $\overline{x}_{ij}^k=0$, $\overline{c}_{ij}^k>0$ and $Z^l+\overline{c}_{ij}^kb_{ij}^k > Z^*$. Since any optimal solution must satisfy $Z^l+\overline{c}_{ij}^kx_{ij}^k \le Z^*$, we conclude that $x_{ij}^k\le a_{ij}^k <b_{ij}^k$, where

$$\begin{aligned} a_{ij}^k = \frac{Z^* - Z^l}{\overline{c}_{ij}^k}. \end{aligned}$$

Next, we consider the case where $\overline{y}_{ij} = 0$. Then, we necessarily have $\overline{x}_{ij}^k = 0$ and $\overline{f}_{ij}\ge 0$. This means that, if we add the constraint $x_{ij}^k > a_{ij}^k$, the LP relaxation lower bound will exceed $Z^*$ only if $Z^l+ \overline{f}_{ij}+\overline{c}_{ij}^kb_{ij}^k > Z^u$. Since any optimal solution must satisfy $Z^l+ \overline{f}_{ij}+\overline{c}_{ij}^kx_{ij}^k \le Z^*$ and assuming $\overline{c}_{ij}^k> 0$, we have $x_{ij}^k\le a_{ij}^k <b_{ij}^k$, where

$$\begin{aligned} a_{ij}^k = \frac{Z^* - Z^l - \overline{f}_{ij}}{\overline{c}_{ij}^k}. \end{aligned}$$

$\square$

Similarly, we can use the solution to the knapsack relaxation to reduce the upper bounds on the flow variables, as shown in the following Proposition, the proof of which is omitted, as it is similar to that of Proposition 1.

Proposition 2

Let ${\tilde{x}}_{ij}^k$ be the value of variable $x_{ij}^k$ in the optimal solution to the Lagrangian subproblem. If ${\tilde{x}}_{ij}^k=0$, ${\tilde{c}}_{ij}^k> 0$ and $Z^l_{LR}+{\tilde{f}}_{ij}(1-{\tilde{y}}_{ij})+{\tilde{c}}_{ij}^kb_{ij}^k > Z^*$, we have $x_{ij}^k\le a_{ij}^k <b_{ij}^k$, where

$$\begin{aligned} a_{ij}^k = \frac{Z^* - Z^l_{LR} - {\tilde{f}}_{ij}(1-{\tilde{y}}_{ij})}{{\tilde{c}}_{ij}^k}. \end{aligned}$$

We use these results as follows. After performing LP-based reduced cost fixing, we look for flow variables $x_{ij}^k$ that verify the condition for reducing their upper bound $b_{ij}^k$ to $a_{ij}^k$. We do the same after carrying out Lagrangian-based reduced cost fixing. New upper bounds are then used at the current node and all its descendants. The upper bounds are stored at each node, in order to initialize them for the child node that is activated when backtracking is performed. In this way, when looking for violated strong inequalities in the cutting-plane procedure, we use the local cuts $x_{ij}^k \le a_{ij}^k y_{ij}$ instead of $x_{ij}^k \le b_{ij}^k y_{ij}$.

In the next section, we derive another type of cuts, this time by investigating the structure of feasible solutions. Contrary to the cuts obtained by flow upper bound reduction, these cuts are global, i.e., they apply at every node of the B&C tree.

3.4 Combinatorial Benders cuts

At every node of the B&C tree, feasible solutions must satisfy the following multicommodity flow system, noted MF:

$$\begin{aligned} \sum _{j \in V^{+}_i} x_{ij}^{k} - \sum _{j \in V^{-}_i} x_{ji}^{k}= & {} \left\{ \begin{array}{rl} d^k ,&{} \quad \text{ if } \; i = O(k), \\ - d^k ,&{} \quad \text{ if } \; i = D(k), \quad i \in V, k \in K, \\ 0 , &{} \quad \text{ otherwise }, \end{array} \right. \end{aligned}$$

(10)

$$\begin{aligned} \sum _{k \in K} x_{ij}^{k}\le & {} u_{ij}, \quad (i,j) \in A_{01}\cup A_1 , \end{aligned}$$

(11)

$$\begin{aligned} \sum _{k \in K} x_{ij}^{k}= & {} 0, \quad (i,j) \in A_0, \end{aligned}$$

(12)

$$\begin{aligned} x_{ij}^{k}\ge & {} 0 , \quad (i,j) \in A , k \in K. \end{aligned}$$

(13)

In particular, any feasible solution generated by the cutting-plane procedure at the current node satisfies this system. We exploit the structure of MF in two ways.

First, we note that when MF is infeasible, we can derive a cut that prevents this infeasible design configuration, i.e., subset $A_0$, to be generated again; this cut is generated whenever the cutting-plane procedure returns an infeasible LP relaxation (it is also generated in capacity-based filtering, see Sect. 3.6).

Proposition 3

If MF is infeasible, then the following inequality is valid for the MCND:

$$\begin{aligned} \sum _{(i,j)\in A_0} y_{ij} \ge 1. \end{aligned}$$

(14)

Inequality (14) is a combinatorial Benders cut (Codato and Fischetti 2006), which has the general form $\sum _{(i,j)\in A_1} (1-y_{ij}) + \sum _{(i,j)\in A_0} y_{ij} \ge 1$ that can be strengthened to (14), since only closed arcs can induce an infeasible subproblem. A different inequality can be derived from LP duality arguments, giving rise to classical Benders cuts, which have been studied for the MCND Costa et al. (2009, 2012). In our B&C algorithm, combinatorial Benders cuts are stored as global cuts. Their violation is verified after the cutting-plane procedure has been completed. In case violated combinatorial Benders cuts are found, the cutting-plane procedure is restarted.

At each node of the B&C tree, combinatorial Benders cuts are also used in simple operations that attempt to detect infeasibility just before calling the cutting-plane procedure. These node-based preprocessing operations work as follows. Assuming the current design configuration is given by $A_{0}^{\prime }$, $A_{1}^{\prime }$ and $A_{01}^{\prime }$, we define the design vector $y^{\prime }$ as $y^{\prime }_{ij} = 0$, if $(i,j)\in A_{0}^{\prime }$, and $y^{\prime }_{ij} = 1$, otherwise. We scan the set of combinatorial Benders cuts generated so far and for each of them, associated with a set $A_0$, we verify: (1) if $\sum _{(i,j)\in A_0} y^{\prime }_{ij} < 1$, which is equivalent to the condition $A_0 \subseteq A_{0}^{\prime }$, in which case the node can be fathomed; (2) if $\sum _{(i,j)\in A_0} y^{\prime }_{ij} = 1$, which is equivalent to the condition $|A_0 \cap A_{01}^{\prime }| \le 1$, in which case if all the arcs in $A_0$ are fixed to 0, except one, then that arc must be fixed to 1. Similar node-based preprocessing operations can be applied to lifted knapsack inequalities generated by the cutting-plane procedure and stored in the global cut pool (the details are obvious and therefore omitted).

A second approach to exploiting the structure of MF consists in developing filtering methods aiming to detect as early as possible any infeasibility that might occur as a result of closing too many arcs. Two sources of infeasibility can be identified: first, for some commodity k, there is no longer any path connecting O(k) to D(k), which gives rise to connectivity-based filtering; second, the overall capacity is not sufficient to satisfy the demand for at least one commodity, which yields capacity-based filtering.

3.5 Connectivity-based filtering

As mentioned above, the current node can be fathomed when we can identify at least one commodity k such that there is no path between O(k) and D(k). In addition to detecting this type of infeasibility prior to the call to the cutting-plane procedure, we also fix flow and design variables based on simple connectivity tests. Indeed, when, for some commodity k, an arc (i, j) does not belong to any path between O(k) and D(k), the upper bound $b_{ij}^k$ associated with variable $x_{ij}^k$ can be fixed to 0. Similarly, when, for some commodity k, an arc (i, j) belongs to all paths between O(k) and D(k), the lower bound associated with variable $x_{ij}^k$ can be fixed to $d^k$ (unless $b_{ij}^k < d^k$, in which case the current node can be fathomed; this case can happen as a result of flow upper bound reduction that can decrease the upper bound $b_{ij}^k$, see Sect. 3.3). In addition, an arc (i, j) can be closed when it does not belong to any path between O(k) and D(k) for all commodities k. Conversely, an arc (i, j) can be opened when it belongs to all paths between O(k) and D(k) for at least one commodity k. This last test prevents the occurrence of infeasible subproblems due to a lack of connectivity.

These tests can be easily performed using graph-traversal algorithms. Indeed, to every node $i\in V$, we associate the commodity subsets $K_i^+=\{k\in K\; |\; i=O(k)\}$ and $K_i^-=\{k\in K\; | \;i=D(k)\}$. Starting from every node i, we perform complete forward and backward traversals of the graph. Each arc $a\in A_{01}\cup A_1$ has two sets of labels $p_a^k$ and $m_a^k$, for each commodity k; each label is initialized with value 0. Whenever we encounter an arc a during the forward traversal from node i, we set the label $p_a^k$ of each commodity k in $K_i^+$ to value 1. Likewise, when performing the backward traversal starting at node i, the label $m_a^k$ of each arc a for commodity $k\in K_i^-$ is set to value 1. After completing forward and backward traversals (each being performed in linear time) for all nodes, a final pass through all arcs is performed. For each arc $a\in A_{01}\cup A_1$ and commodity $k\in K$, two cases can happen: (1) $p_a^k = m_a^k = 1$, in which case arc a belongs to some path between O(k) and D(k); (2) $p_a^k = 0$ or $m_a^k=0$, which implies that arc a does not belong to any path between O(k) and D(k). This information suffices to perform the fathoming and filtering tests outlined above. In particular, to determine that an arc $a=(i,j)$ belongs to all paths between O(k) and D(k) for commodity k, (i, j) must satisfy case (1), while any other outgoing arc from i must verify case (2).

Connectivity-based filtering is called only when some arcs have been closed since the last time it was performed. It is also performed at the root node of the B&C tree in order to simplify the problem instance.

3.6 Capacity-based filtering

This filtering method solves the following linear program, denoted MC and obtained from system MF:

$$\begin{aligned} Z^l_{MC}=\sum _{(i,j)\in A_1}f_{ij} + \min \sum _{k \in K} \left\{ \sum _{(i,j) \in A_{01}} (c_{ij} + f_{ij}/u_{ij}) x_{ij}^{k} + \sum _{(i,j)\in A_1}c_{ij}x_{ij}^k \right\} \end{aligned}$$

(15)

subject to constraints (10) to (13). This linear multicommodity flow problem is a relaxation of any LP generated during the cutting-plane procedure. Indeed, it is equivalent to the LP relaxation of the MCND without any strong or knapsack inequality added, the so-called weak relaxation (Gendron and Crainic 1994). To see why, simply note that each design variable $y_{ij}$ appears in only one capacity constraint in the weak relaxation. As a consequence, since $f_{ij}\ge 0$, there must be an optimal solution such that $y_{ij} = \sum _{k\in K}x_{ij}^k/u_{ij}$ for each arc $(i,j)\in A_{01}$. By substituting $y_{ij}$ using this equation, we obtain the above linear multicommodity flow problem. Hence, MC provides a lower bound $Z^l_{MC}$ on the optimal value at the current node, which is often significantly weaker than the cutting-plane lower bound $Z^l$, except when the current node is located deep in the B&C tree.

Capacity-based filtering starts by solving MC. If it is infeasible, the current node can be fathomed. Also, using Proposition 3, we can generate a combinatorial Benders cut, which is stored in the global cut pool. Otherwise, if MC is feasible, we denote by $\widehat{x}$ an optimal solution. We first verify if $Z^l_{MC} \ge Z^*$, in which case the current node can be fathomed. Then, for each free arc $(i,j)\in A_{01}$ such that $\sum _{k\in K} \widehat{x}_{ij}^k > (1-\epsilon )u_{ij}$, where $\epsilon \in (0,1)$ is a parameter, we solve MC with the additional constraint $\sum _{k\in K} x_{ij}^k = 0$. If the resulting problem is infeasible, then we can conclude that arc (i, j) must necessarily be opened in any optimal solution to the MCND. If the resulting problem is feasible, thus providing a lower bound $Z^l_{MC}(i,j)$, then we verify if $Z^l_{MC}(i,j) \ge Z^*$, in which case we can conclude again that arc (i, j) must be opened in any optimal solution to the MCND.

To fully understand this filtering procedure, several remarks are in order. First, it is useless to test a free arc $(i,j)\in A_{01}$ such that $\sum _{k\in K} \widehat{x}_{ij}^k =0$, since in that case, arc (i, j) cannot be opened by the procedure. Second, this type of filtering achieves success mostly for free arcs that fully use their capacity in $\widehat{x}$. Hence, $\epsilon$ must be small (we use $\epsilon = 0.01$ in our tests). Third, it is possible to implement a similar filtering procedure that attempts to close free arcs with no flow circulating on them in solution $\widehat{x}$. Indeed, we tested this procedure, but given the weakness of the lower bound, its impact was very limited. Fourth, capacity-based filtering can succeed only when many arcs are fixed to 0. Hence, we perform it only when the number of closed arcs is large enough, i.e., if $|A_0| > \gamma |A|$, where $\gamma \in [0,1]$ is a parameter (in Sect. 5, we show results for $\gamma =$ 0.85, 0.9 and 0.95). Fifth, capacity-based filtering is called only when some arcs have been closed since the last time it was performed, because only arcs that are closed can incur infeasibility. Sixth, capacity-based filtering complements connectivity-based filtering and is therefore performed immediately after.

4 Overview of the branch-and-cut algorithm

This section summarizes the overall B&C algorithm. Before providing the details of the algorithm in Sect. 4.3, we first explain how upper bounds are computed during the course of the algorithm. This is the topic of Sect. 4.1, while in Sect. 4.2, we explain how we search the B&C tree.

4.1 Computation of upper bounds

As mentioned in Introduction, very good upper bounds are obtained by the heuristic methods proposed in the literature (Crainic et al. 2000, 2004; Crainic and Gendreau 2002; Ghamlouche et al. 2003, 2004; Hewitt et al. 2010; Katayama et al. 2009; Rodríguez-Martín and Salazar-González 2010). In our tests, reported in Sect. 5, we use as initial upper bound the value $(1+\xi )\times Z$, where Z is the best known upper bound on the optimal value (which is the optimal value for most tested instances) and $\xi$ is a small number (we use $\xi = 0.00001$). Apart from the fact that it is realistic to assume that a very good initial upper bound is known, this setting allows to test the capacity of the B&C algorithm and the different filtering methods to focus only on lower bound improvement and optimality proof. Nevertheless, the B&C algorithm has the ability to compute upper bounds and to prove optimality, even if its initial upper bound is $+\,\infty$. We now show how these upper bounds are computed during the course of the algorithm.

The following (the proof of which is omitted, as it is trivial) states that we can derive an upper bound on the optimal value of the MCND from any feasible solution to the multicommodity flow system MF, presented in Sect. 3.4.

Proposition 4

For any feasible solution $\widehat{x}$ to MF,

$$\begin{aligned} Z(\widehat{x})=\sum _{k \in K} \sum _{(i,j) \in A} c_{ij} \widehat{x}_{ij}^{k} + \sum _{(i,j)\in A}f_{ij} \left\lceil \sum _{k\in K}\widehat{x}_{ij}^k/u_{ij} \right\rceil \end{aligned}$$

is an upper bound on the optimal value Z of the MCND.

Corollary 5

At any iteration of the cutting-plane procedure, if the LP relaxation is feasible, then

$$\begin{aligned} Z(\bar{y}) = Z^l + \sum _{(i,j)\in A}f_{ij} (\lceil \bar{y}_{ij} \rceil -\bar{y}_{ij}) \end{aligned}$$

is an upper bound on the optimal value Z of the MCND.

Proof

First, we note that any solution $(\overline{x},\overline{y})$ generated during the cutting-plane procedure satisfies the multicommodity flow system MF. In addition, we have $\bar{y}_{ij} \ge \sum _{k\in K}\overline{x}_{ij}^k/u_{ij}$, for each $(i,j)\in A$. By applying the previous proposition, we obtain an upper bound on the optimal value of the MCND:

$$\begin{aligned} Z(\overline{x})= & {} \sum _{k \in K} \sum _{(i,j) \in A} c_{ij} \overline{x}_{ij}^{k} + \sum _{(i,j)\in A}f_{ij}\lceil \sum _{k\in K}\overline{x}_{ij}^k/u_{ij}\rceil \\\le & {} \sum _{k \in K} \sum _{(i,j) \in A} c_{ij} \overline{x}_{ij}^{k} + \sum _{(i,j)\in A}f_{ij}\lceil \overline{y}_{ij}\rceil \\= & {} Z^l + \sum _{(i,j)\in A}f_{ij} (\lceil \overline{y}_{ij} \rceil -\overline{y}_{ij}). \end{aligned}$$

$\square$

The last result is used to quickly compute an upper bound after performing the cutting-plane procedure. In particular, this bound has a nice interpretation when $\overline{y}$ is integral: in that case, $Z(\overline{y}) = Z^l$ and the lower bound test $Z^l \ge Z^*$ suffices to fathom the node. In addition, Proposition 4 is exploited when performing the capacity-based filtering method. Details are given below in the algorithm statement.

4.2 Tree search

We use a hybrid search strategy that combines the depth-first and best-first approaches. After branching, the next node to evaluate is the child that gives the smallest estimated lower bound increase among the two generated children, in order to mimic a best-first approach. When a strong branching evaluation has just been performed to select a branching arc $a^*$, this corresponds to the child that attains the value $\min (\Delta _{a^*}^0, \Delta _{a^*}^1)$. When, instead, the branching arc $a^*$ is selected by a pseudo-cost estimate, the next child to evaluate is the one that achieves the value $\min (g_{a^*}^0 \bar{\rho }_{a^*}^0, g_{a^*}^1 \bar{\rho }_{a^*}^1)$. The other child is stored in the node pool and will eventually be evaluated when backtracking is performed. When a newly generated node is stored in the node pool, we keep in memory its lower bound estimate, which is equal to the lower bound of its parent plus the estimated lower bound increase computed by the branching rule. When backtracking, we select the node that has the smallest lower bound estimate among all the nodes in the node pool.

4.3 Statement of the algorithm

We now outline the algorithm, the steps being commented below:

• 1. Initialize the upper bound $Z^*$, the node pool $\mathcal L$ and the current node as the root node ($\mathcal L \leftarrow \emptyset$ and $A_{01} \leftarrow A$).

• 2. Evaluation: Evaluate the current node:

  • (a) Determine LP-fix, LR-fix, Flow, Benders, Conn, Cap.

  • (b) If Conn, perform connectivity-based filtering; if the network at the current node is not connected, go to step 4 (Backtrack).

  • (c) If Cap, perform capacity-based filtering:

    • i. Solve MC.

    • ii. If MC is infeasible: if Benders, generate a combinatorial Benders cut; go to step 4.

    • iii. Let $\widehat{x}$ be an optimal solution to MC; compute an upper bound $Z(\widehat{x})$; if $Z(\widehat{x})< Z^*$, $Z^* \leftarrow Z(\widehat{x})$.

    • iv. If $Z^l_{MC}\ge Z^*$, go to step 4.

    • v. For each $(i,j)\in A_{01}$ such that $\sum _{k\in K} \widehat{x}_{ij}^k > (1-\epsilon )u_{ij}$, solve MC with the added constraint $\sum _{k\in K} \widehat{x}_{ij}^k = 0$; if $Z^l_{MC}(i,j) \ge Z^*$, open arc (i, j).

  • (d) Apply the cutting-plane procedure to solve the LP relaxation.

  • (e) If the LP relaxation is infeasible: if Benders, generate a combinatorial Benders cut; go to step 4.

  • (f) Let $(\overline{x}, \overline{y})$ be an optimal solution to the LP relaxation; compute an upper bound $Z(\overline{y}) = Z^l + \sum _{(i,j)\in A} f_{ij}(\lceil \overline{y}_{ij}\rceil - \overline{y}_{ij})$; if $Z(\overline{y}) < Z^*$, $Z^* \leftarrow Z(\overline{y})$.

  • (g) If $Z^l \ge Z^*$, go to step 4.

  • (h) If Benders, try to add violated combinatorial Benders cuts; if cuts were generated, go to step 2d.

  • (i) If LP-fix, perform LP-based reduced cost fixing.

  • (j) If Flow, perform LP-based flow upper bound reduction.

  • (k) If LR-fix or Flow:

    • i. Compute the Lagrangian relaxation bound $Z^l_{LR}$.

    • ii. If $Z^l_{LR} \ge Z^*$, go to step 4.

    • iii. If LR-fix, perform LR-based reduced cost fixing.

    • iv. If Flow, perform LR-based flow upper bound reduction.

• 3. Branching: Perform branching to generate two child nodes; select one child as the next current node to evaluate; insert the other into $\mathcal L$; Go to step 2.

• 4. Backtracking: If $\mathcal L = \emptyset$, stop the algorithm; otherwise, select from $\mathcal L$ the next current node to evaluate and go to step 2.

In step 1, the upper bound is initialized as described in Sect. 4.1. The node pool $\mathcal L$ is also initialized, and the first current node is the root node. Step 2 is the main procedure to be performed at every node of the B&C tree. The details of that step are further commented below. Step 3 performs the reliability branching rule presented in Sect. 2.4. The next current node is selected among the two children according to the rule described in Sect. 4.2. Step 4 verifies the stopping condition $\mathcal L = \emptyset$ and, if it is not satisfied, it performs backtracking as discussed in Sect. 4.2. We also stop the algorithm when a time limit has been reached. Finally, the best global lower bound, $Z^l_+$, is stored and updated in an obvious way. This lower bound on the optimal value of the MCND is used to compute the final gap, $100\times (Z^* - Z^l_+)/Z^*$, when the B&C algorithm is stopped by the time limit.

Step 2a determines the values of six parameters that are used to trigger the filtering methods at the current node. Each of these parameters is set to False if we do not want to activate the corresponding filtering method. Otherwise, a parameter value is set to True depending on the conditions that allow the execution of the filtering method, conditions that are described in the corresponding section. The parameters are LP-fix, LR-fix, Flow, Benders, Conn, Cap, which correspond to the following filtering methods, respectively: LP-based reduced cost fixing (Sect. 3.1 and step 2i), LR-based reduced cost fixing (Sect. 3.2 and step 2k), flow upper bound reduction (Sect. 3.3 and steps 2j and 2(k)iv), combinatorial Benders cuts (Sect. 3.4 and steps 2(c)ii, 2e and 2h), connectivity-based filtering (Sect. 3.5 and step 2b) and capacity-based filtering (Sect. 3.6 and step 2c). The cutting-plane procedure performed at step 2d follows the developments in Sect. 2.3. Finally, the computation and update of upper bounds, steps 2(c)iii and 2f, correspond to Sect. 4.1.

5 Computational results

This section presents computational results obtained by the B&C algorithm on a publicly available set of 196 instances (the so-called Canad instances, see Frangioni (2017)) used in several papers on the MCND, for instance (Ghamlouche et al. 2003; Hewitt et al. 2010; Kliewer and Timajev 2005), and described in detail in Crainic et al. (2001). These problem instances consist of general networks with one commodity per origin-destination pair and no parallel arcs. Associated with each arc are three positive quantities: the capacity, the routing cost, and the fixed cost. These instances are characterized by various degrees of capacity tightness, with regard to the total demand, and importance of the fixed cost, with respect to the routing cost.

The instances are divided into three classes. Class I [the “C” instances in Frangioni (2017)] consists of 31 problem instances with many commodities compared to the number of nodes, while Class II [the “C+” instances in Frangioni (2017)] contains 12 problem instances with few commodities compared to the number of nodes. Class III [the “R” instances in Frangioni (2017)] is divided into two categories, A and B, each containing nine sets of nine problem instances each. Each set is characterized by the numbers of nodes, arcs, and commodities, which are the same for the nine instances, and by instance-specific levels of capacity tightness and importance of the fixed cost. Class III-A (instances “R01” to “R09”) contains 72 small size problem instances with 10 nodes (nine infeasible instances have been discarded), while Class III-B (instances “R10” to “R18”) contains 81 medium to large size instances with 20 nodes. Table 1 gives the size of the instances in each class.

Table 1 Classes and problem dimensions (number of instances within parentheses)

The B&C algorithm was implemented in C++ with the OOBB library (Crainic et al. 2009), using CPLEX version 12.6.1.0 as the LP solver. The code was compiled with g++ 4.8.1 and performed on an Intel Xeon ES-2609 v2 operating at 2,50 GHz, in single-threaded mode. All instances were solved with a time limit of 10 hours, which allows to divide the set of instances according to their difficulty, while at the same time to study trends in the evolution of the lower bounds for the most difficult instances, still unsolved after that time limit (we come back to this issue at the end of Sect. 5.1). The following measures are used to evaluate the performance of the B&C algorithm: (1) CPU time in seconds; (2) number of generated B&C nodes; (3) relative gap in percentage computed as Gap = $100 \times (Z^* - Z^l_+)/Z^*$.

We first present the results obtained with different configurations of the filtering parameters in Sect. 5.1. Then, in Sect. 5.2, we compare the B&C variant including filtering with CPLEX and with other variants having limited filtering or no filtering at all. In both sections, we divide the instances into two classes: 148 instances solved by all parameter configurations within the time limit of 10 hours (for which Gap = 0), called solved instances, and 45 instances unsolved by any of the parameter configurations after the time limit of 10 hours (for which Gap > 0), called unsolved instances. The remaining three instances are solved by some parameter configurations, but unsolved by others. To simplify the analysis, we did not include them in the tables of results presented in Sects. 5.1 and 5.2. Appendix presents detailed results of each of the 196 instances in the data set, including these three instances, for the “best” parameter configuration identified in Sect. 5.1.

5.1 Impact of the filtering methods

This section presents tables of results for different configurations of the filtering parameters, separating the analysis for each set of configurations into two tables, one for the solved instances and one for the unsolved instances. For the solved instances, we report only the CPU time in seconds and the number of nodes, Columns “CPU” and “Nodes,” respectively, since Gap = 0 for all these instances. For the unsolved instances, we show only the number of nodes and the relative gap in percentage, Column “Gap,” since the CPU time limit was attained for all these instances. Note that the value “Nodes” has different meanings, depending on the class of instances: for solved instances, a smaller number of nodes is to be preferred and is often correlated with a smaller CPU time, while for unsolved instances, a larger number of nodes is to be preferred and is often correlated with a smaller gap.

In each table, the first column gives the name of the class of instances, I, II, III-A or III-B, and the number of instances on which the average performance measures are computed. Both arithmetic means and shifted geometric means are reported for each performance measure. Shifted geometric means are now widely used for analyzing the performance of MIP solvers, since a geometric mean prevents hard instances close to the CPU time limit from having a huge impact on the measures, while the shift reduces the effect of very easy instances. For both “CPU” and “Nodes,” we use a shift of 100, while for “Gap,” the shift is set to 0.001%. The second column in each table identifies the filtering parameters activated in each configuration. The next columns give the mean values for the performance measures, first the arithmetic means, “Arithmetic,” then the shifted geometric means, “Shifted geom.”

Tables 2 and 3 show the results obtained on solved and unsolved instances, respectively, for four parameter configurations. We compare the configuration with no filtering with three duality-based filtering configurations: LP-based reduced cost fixing is activated in all three configurations, while LR-based reduced cost fixing is activated in two of the configurations and flow upper bound reduction is activated in only one configuration.

Table 2 Results with duality-based filtering on solved instances

Table 3 Results with duality-based filtering on unsolved instances

Before analyzing the results reported in Tables 2 and 3, it is important to note that, when any of the three duality-based filtering configurations is used, two instances unsolved by the configuration with no filtering (one more in each of Classes I and III-B) are solved within the time limit of 10 hours, so that the number of solved instances increases from 149 (with no filtering) to 151. This is already a clear indication of the positive effect of LP-based reduced cost fixing. The two additional solved instances are not reported in any of the two tables, so that the comparison for both classes of instances, solved and unsolved, relies on the same instances and the performance measures retain the same meaning.

The results in Table 2 show that, when more filtering is performed, the number of nodes is generally reduced. In general, the most significant reduction in the number of nodes is observed for LP-based reduced cost fixing. These reductions in the number of nodes always translate into reductions in the CPU time. In general, the results in Tables 2 and 3 indicate that LP-based reduced cost fixing has a clear positive impact on the overall performance. The impact of the other duality-based filtering techniques is less clear, but we note that both the LR-based reduced cost fixing and the flow upper bound reduction allow to reduce the final gap for some hard instances in Class III-B. Thus, for the remaining tested parameter configurations, we activate LP-fix, LR-fix, and Flow.

Tables 4 and 5 show the results obtained by performing feasibility-based filtering, in addition to duality-based filtering. More specifically, we display the results obtained with three parameter configurations, obtained by activating Benders and Conn in isolation and in conjunction. To facilitate the comparison, we report the results when these parameters are not activated, which are also displayed in Tables 2 and 3. The same instances are used, 148 solved ones and 45 unsolved ones. The remaining three instances in the set of 196 instances are solved by the two configurations that use Benders cuts, but one of these three instances (in Class II) is no more solved when using connectivity-based filtering. However, the final gap for this instance is 0.07%, which is negligible. We can thus consider that the four configurations reported in Tables 4 and 5 are performing equally well in terms of the total number of solved instances within the limit of 10 hours of CPU time.

Table 4 Results with feasibility-based filtering on solved instances

Table 5 Results with feasibility-based filtering on unsolved instances

The results in Table 4 show that the addition of Benders cuts has a negligible impact on all instances. In contrast, connectivity-based filtering generally has a positive impact, especially on Class III-B instances. Overall, the best configuration is obtained by activating only connectivity-based filtering, with notable reductions in the CPU time on Class III-B instances. The results in Table 5 show decreases in the gap for all configurations that include feasibility-based filtering, except for Class III-B for which lower gaps are obtained only when Conn alone is activated, while higher gaps are observed when Benders is activated. The results in Tables 4 and 5 point to the general conclusions that the addition of combinatorial Benders cuts might have a positive impact for some instances, but that better results are obtained when connectivity-based filtering is used alone, without activating Benders.

Tables 6 and 7 show the results obtained when the parameter Cap is activated, in addition to LP-fix, LR-fix, Flow and Conn. We report the results with three values of the parameter $\gamma$, which controls when capacity-based filtering is performed depending on the proportion of design variables fixed to 0: $\gamma = 0.85, 0.90, 0.95$ (values around $\gamma = 0.90$ generally give the best results, according to preliminary experiments). To ease the comparison, we also report the results when Cap is not activated, which are already shown in Tables 4 and 5. The same instances are also used, 148 solved ones and 45 unsolved ones.

Table 6 Results with capacity-based filtering on solved instances

Table 7 Results with capacity-based filtering on unsolved instances

The results in Table 6 show that capacity-based filtering (with the tested values of $\gamma$) has a marginal impact on both the number of nodes and the CPU time. In preliminary experiments, we have observed significant variations in the CPU time for smaller values of $\gamma$, but this behavior is highly instance-dependent and, thus, difficult to generalize to obtain consistent improvements. The results in Table 7 confirm that capacity-based filtering (with the tested values of $\gamma$) has a marginal impact on the performance of the algorithm. Overall, the results in Tables 6 and 7 point to the conclusion that capacity-based filtering, with appropriate values of the parameter $\gamma$, has a marginal effect on the overall performance of the algorithm. When $\gamma = 0.95$, we note, however, that slight improvements are obtained on most instances, with reductions in the CPU time for solved instances (in Classes I and III-B) and reductions in the gap for unsolved instances (in Class III-B). For the remaining tests, we thus activate Cap with $\gamma = 0.95$.

Note that we have performed additional tests where we modify the order in which the configurations are tested [a systematic approach could have been used, e.g., the fractional design-of-experiments described in Adenso-Diaz and Laguna (2006)]. The results are consistent with the following observations: (1) Duality-based filtering (including Flow) should be performed in all cases; (2) connectivity-based filtering must be performed in all cases and Benders cuts should be avoided; (3) capacity-based filtering generally has a marginally positive impact when it is performed in deep regions of the search tree (i.e., with values of $\gamma$ around 0.9). The sequential way in which we have presented the configuration testing has been adopted to facilitate the exposition.

Fig. 1

Gap vs CPU(h), one instance per class I: c58; II: c100_400_30_F_L; III-B: r17.6

Before comparing the different B&C variants, we look at the evolution of the lower bounds over the course of the algorithm. Figure 1 shows the evolution of gaps with respect to CPU times (in hours) on three difficult instances, each taken from a different class. The name of each instance comes from Frangioni (2017), which also specifies their dimensions |V|, |A|, |K|: c58 in Class I has size 30,700,100; c100_400_30_F_L in Class II has size 100,400,30; r17.6 in Class III-B has size 20,320,100. Note that these three instances are representative of the behavior over the whole set of unsolved instances. To obtain the gap evolution curves shown in Fig. 1, we ran the B&C algorithm by reporting the gap after each hour. We used the following configuration of filtering parameters, based on our observations: LP-Fix, LR-Fix, Flow, Conn and Cap ($\gamma =0.95$). The gap evolution curve for each of the three instances exhibits a convex shape, indicating that the gap diminishes relatively quickly at the beginning and relatively slowly as we approach the time limit. On all unsolved instances, including the three representative ones, the gap decreases by less than 2%, sometimes by less than 1%, as can be seen for Class I instance c58 on the graph. It is interesting to note that Class II instance c100_400_30_F_L is almost solved after 10 hours, with a final gap smaller than 0.1%. In general, however, even though 10 hours is a long time to be given to the B&C algorithm, most difficult instances are still far from being solved when the time limit is attained.

5.2 Comparison between branch-and-cut variants

In this section, we summarize the performances of three variants of the B&C algorithm: with no filtering, identified as “B&C”; with only the “classical” reduced cost fixing techniques LP-Fix and LR-Fix, “B&C&Fix”; and with the best identified configuration of filtering parameters, “B&C&Filter,” which activates, in addition to LP-Fix and LR-Fix, Flow, Conn, and Cap ($\gamma =0.95$). We use the same set of instances as before, 148 solved and 45 unsolved instances, so these results can be found already in the previous tables, but they are easier to read in Tables 8 and 9, which show the results on solved and unsolved instances, respectively. In addition, these two tables show the results obtained with CPLEX on the strong formulation, defined by (1)–(5), with the addition of the strong inequalities (6). Since for many instances, there are too many strong inequalities to add all of them a priori, they are declared as user cuts, which allows CPLEX to generate them dynamically, within its own branch-and-cut algorithm. In preliminary experiments, this approach was shown to be superior to the alternative that consists in solving the so-called weak formulation defined by (1)–(5) by CPLEX, i.e., the strong inequalities are not given to CPLEX. CPLEX is performed with default parameters, with two exceptions: we give as initial incumbent value the same upper bound provided to the B&C and we deactivate the heuristic features of CPLEX. Since CPLEX does not solve the same instances as the three B&C variants, we also count: (1) the number of instances that CPLEX does not solve among those that are solved by the B&C variants, reported with a “–” sign in column “Instances” of Table 8; (2) the number of instances that CPLEX solves among those that are unsolved by the B&C variants, reported with a “+” sign in column “Instances” of Table 9.

Table 8 Comparison with CPLEX on solved instances

Table 9 Comparison with CPLEX on unsolved instances

The results in Tables 8 and 9 show that the filtering methods have a notable impact on the performance of the B&C algorithm for all classes of instances. On the solved instances, reductions in the CPU time are observed: 50%, 51%, 25% and 41% reductions in the arithmetic means are obtained on Classes I, II, III-A, and III-B, respectively, with corresponding reductions of 23%, 16%, 17%, and 26% in the shifted geometric means. Among the filtering techniques, reduced cost fixing is responsible for a major part of these improvements, with reductions in the CPU time of 45%, 38%, 25% and 35% in the arithmetic means on Classes I, II, III-A and III-B, respectively, with corresponding reductions of 22%, 12%, 17% and 20% in the shifted geometric means. On unsolved instances, the arithmetic means of the gaps are reduced by 0.04% and 0.16% on Classes I and III-B, respectively, with corresponding reductions of 0.05% and 0.27% in the shifted geometric means. The reductions in the gap are generally correlated with increases in the number of nodes that can be explored within the time limit of 10 hours of CPU time: 25% and 29% increases in the arithmetic means of the number of nodes are obtained on Classes I and III-B, respectively, with corresponding increases of 29% and 52% in the shifted geometric means.

These results also show that the three B&C variants outperform CPLEX on Classes I and III-B, while the opposite is true for Class II. These observations are consistent with the results presented in Chouman et al. (2017), where it was already shown that the strong inequalities are particularly useful for instances with many commodities, such as those found in Classes I and III-B, while other types of cuts, namely flow cover/pack inequalities, are more effective for instances with few commodities, such as those in Class II. As our B&C algorithm relies mostly on strong inequalities, while CPLEX generates flow cover inequalities (among other types of cuts), these comparative results are consistent with those presented in Chouman et al. (2017). The appendix gives the detailed results, for each of the 196 instances in the data set, of the comparison between CPLEX and B&C&Filter. Overall, B&C&Filter solves 19 instances more than CPLEX on instances in Classes I and III-B (B&C&Filter solves two of the three instances not considered in Tables 8 and 9), while CPLEX solves one instance more than B&C&Filter on instances of Class II. On the unsolved instances in Classes I and III-B, the gap is also significantly smaller with B&C&Filter, compared with the gap obtained by CPLEX.

6 Conclusion

We have presented a B&C algorithm for the MCND that combines the cutting-plane method from Chouman et al. (2017), an adaptation of the reliability branching rule Achterberg et al. (2005), and a series of filtering methods taking advantage of the structure of the MCND. Our experiments on a large set of randomly generated instances have demonstrated the efficiency and the effectiveness of both the B&C algorithm and the filtering methods. In particular, these experiments have shown that an appropriate selection of filtering techniques allows the B&C algorithm to perform better than the variant of the algorithm without filtering. These experiments have confirmed that the B&C algorithm, with or without filtering, is competitive with a state-of-the-art MIP solver, especially for instances with many commodities (typically more than 100).

The filtering methods exploit the particular structure of the MCND. It would be interesting to adapt them to other exact algorithms for the MCND (see the references in Introduction). In particular, the feasibility-based filtering techniques (combinatorial Benders cuts, connectivity-based and capacity-based filtering) do not depend on the cutting-plane method and can be used in any enumerative algorithm. In contrast, the duality-based filtering techniques (reduced cost bound reduction, LP-based and Lagrangian-based reduced cost fixing) depend on the cutting-plane procedure, but could be adapted in the context of column generation and Lagrangian relaxation methods. The implementation of these different bounding methods under the same interface for enumerative algorithms, including adaptations of the filtering and branching procedures presented here, would allow a fair comparison of the exact approaches proposed so far for the MCND. Finally, another avenue of research would be to adapt the filtering methods to other difficult network design problems.

Appendix: Detailed results for CPLEX and B&C&Filter

Tables 10, 11, 12, 13, 14, and 15 give the detailed results for the 196 instances in the data set. The name of each instance, “Instance,” is taken from Frangioni (2017), which also specifies the dimensions of each instance. The performance measures are defined in Sect. 5. The lines “Arithm” and “ShiftG” at the end of a table provide the arithmetic and the shifted geometric means over all instances in the corresponding Class. Each instance name in bold corresponds to an instance solved by B&C&Filter, but not by CPLEX. Each instance name in italics shows an instance solved by CPLEX, but not by B&C&Filter.

Table 10 CPLEX and B&C&Filter on Class I instances

Table 11 CPLEX and B&C&Filter on Class II instances

Table 12 CPLEX and B&C&Filter on Class III-A instances (1)

Table 13 CPLEX and B&C&Filter on Class III-A instances (2)

Table 14 CPLEX and B&C&Filter on Class III-B instances (1)

Table 15 CPLEX and B&C&Filter on Class III-B instances (2)