An exact separation algorithm for unsplittable flow capacitated network design arc-set polyhedron

In this paper, we concentrate on generating cutting planes for the unsplittable capacitated network design problem. We use the unsplittable flow arc-set polyhedron of the considered problem as a substructure and generate cutting planes by solving the separation problem over it. To relieve the computational burden, we show that, in some special cases, a closed form of the separation problem can be derived. For the general case, a brute-force algorithm, called exact separation algorithm, is employed in solving the separation problem of the considered polyhedron such that the constructed inequality guarantees to be facet-defining. Furthermore, a new technique is presented to accelerate the exact separation algorithm, which significantly decreases the number of iterations in the algorithm. Finally, a comprehensive computational study on the unsplittable capacitated network design problem is presented to demonstrate the effectiveness of the proposed algorithm.

1. Shifted geometric mean, 10s for average time and 100 for average nodes [1].

Authors and Affiliations

1. LSEC, ICMSEC, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China

   Liang Chen, Mu-Ming Yang & Yu-Hong Dai

2. School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, China

   Liang Chen, Mu-Ming Yang & Yu-Hong Dai

3. School of Mathematics and Statistics/Beijing Key Laboratory on MCAACI, Beijing Institute of Technology, Beijing, China

   Wei-Kun Chen

Corresponding author

Correspondence to Wei-Kun Chen.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Wei-Kun Chen was supported by Beijing Institute of Technology Research Fund Program for Young Scholars (Nos. 3170011181905 and 3170011182012). Yu-Hong Dai was partly supported by the Chinese NSF grants (Nos. 11631013, 11991020, 12021001, 11991021, and 11971372) and Beijing Academy of Artificial Intelligence (BAAI)

Appendix

Lemma 2

Suppose that \(T=\{1\}\) and inequality (6) with \(\beta _1 = 1\) is a facet-defining inequality of polyhedron P. For each \( q \in Q \), if \( a_q \le b_1 \), then \( 0 \le \alpha _q \le 1 \).

Proof

Combining with \(a_q\le b_1\), \(\beta _1 = 1\), and Proposition 4, we have the statement.\(\square \)

Lemma 3

Given \( ({\bar{x}}, {\bar{y}}_1) \in {[0,1]}^{|Q|} \times {\mathbb {R}}_+ \), the linear programming problem

has an optimal solution \( (\varvec{e^d}, -r) \) where r and d are defined in (16) and (17), respectively.

Proof

By simple calculation, point \((\varvec{e^d}, -r)\) is a feasible solution of problem (37) with the objective value being \( {\bar{x}}_d -{\bar{y}}_1 +r \). It is optimal since

\(\square \)

Proof of Proposition 5

Proof

From the definition of r in (16), we have \( (\varvec{0},r) \in X \). This, combined with assumption (ii) and condition (18), implies that

It is obvious that the vertices of polyhedron P, i.e., \(\mathrm{conv }\,(X)\), are points \((\varvec{0},r)\) and \((x,r+1)\) for all \(x\in \{0,1\}^{|Q|}\) with \(x\ne \varvec{0}\). Particularly, in problem (12), the vertex \( ({\varvec{e}},r+1) \) corresponds to the constraint

By removing the constraints that are dominated by (38) and using Lemma 2 and Theorem 1, problem (12) is further equivalent to problem (37). Hence, by Lemma 3, in this case, point \((\varvec{e^d}, -r)\) is optimal for problem (12), which corresponds to the inequality \(x_d \le y_1 -r\) of polyhedron P. Furthermore, inequality \(x_d \le y_1 -r\) is facet-defining for polyhedron P since the \(|Q|+1\) affinely independent points \(({\varvec{0}},r)\), \((\varvec{e^d},r+1)\), and \((\varvec{e^d} + \varvec{e^q} ,r+1)\) for each \(q\in Q\backslash \{d\}\) are on the face \(\{(x,y_1)\in P: x_d = y_1-r\}\). \(\square \)

Lemma 4

Let r and d be the values defined in (16) and (17), respectively, and \( ({\bar{x}}, {\bar{y}}_1) \in {[0,1]}^{|Q|} \times {\mathbb {R}}_+ \). Consider the following linear programming problem

The following results hold.

1. (a)

   If \( |Q| \le 2\), one of the optimal solutions of problem (12) is \(({\varvec{e}}, -r)\);

2. (b)

   If \( |Q| \ge 3 \), one of the optimal solutions of problem (12) is

   $$\begin{aligned} \left\{ \begin{aligned}&(\varvec{e^{d}}, -r),&\text {if}\ \frac{\sum _{q\in Q}{\bar{x}}_q}{|Q|-1} \le {\bar{x}}_d;\\&\left( \frac{1}{|Q|-1}{\varvec{e}}, -r\right) ,&\text {if}\ {\bar{x}}_d < \frac{\sum _{q\in Q}{\bar{x}}_q}{|Q|-1}\le 1;\\&({\varvec{e}},-r+|Q|-2),&\text {if}\ \frac{\sum _{q\in Q}{\bar{x}}_q}{|Q|-1}> 1. \end{aligned} \right. \end{aligned}$$

Proof

If \(|Q| \le 2\), by removing the redundant constraints that are dominated by \( -r -\gamma \le 0 \) and \( \alpha _q \le 1\), \( q \in Q \), problem (39) is equivalent to

Clearly, \(({\varvec{e}}, -r)\) is an optimal solution. This proves case (a) in the statement.

Next, we consider the case \(|Q|\ge 3\). Since the coefficient of \(\gamma \) in the objective function in problem (39) is \(-1\), optimality of problem (39) requires that \(\gamma \) must be equal to \(-r\), or \( \sum _{q\in Q\backslash \{q'\}}\alpha _q - (r+1)\) for some \(q' \in Q \). We have the following two cases.

1. 1.

   \(\gamma = -r \). By eliminating the variable \(\gamma \), problem (39) reduces to

   $$\begin{aligned} \max _{\alpha }\left\{ \sum _{q \in Q} {\bar{x}}_q\alpha _q- {\bar{y}}_1 +r: \sum _{q\in Q\backslash \{{\bar{q}}\}}\alpha _q \le 1,~\forall ~ {\bar{q}}\in Q, ~ 0\le \alpha _q \le 1,~ \forall ~ q \in Q \right\} . \end{aligned}$$

   From the linear programming theory, there are at least |Q| constraints in the above problem being active at the basic optimal solution.

2. 1.1

   If \(\sum _{q\in Q\backslash \{{\bar{q}}\}}\alpha _q = 1\) for all \( {\bar{q}}\in Q \), we have \(\alpha _q =\frac{1}{|Q|-1}\) for all \( q \in Q\), and \((\frac{1}{|Q|-1}\varvec{e}, -r)\) is an optimal solution of problem (39).

3. 1.2

   Otherwise, we have \( \alpha _{q'} = 0 \) or \( \alpha _{q'} = 1 \) for some \( q' \in Q \). In any case, there must exist some \( q'' \in Q \) such that \( \alpha _{q''} = 0 \). Together with \( \sum _{q\in Q\backslash \{q''\}} \alpha _q \le 1 \), it can be easily verified that \((\varvec{e^d}, -r)\) is an optimal solution of problem (39).

4. 2.

   \(\gamma = \sum _{q\in Q\backslash \{q'\}}\alpha _q - (r+1) \) for some \( q'\in Q \). By eliminating the variable \(\gamma \), problem (39) reduces to

   $$\begin{aligned}&\max _{\alpha } \left\{ -\sum _{q\in Q\backslash \{q'\}}(1-{\bar{x}}_q)\alpha _q+{\bar{x}}_{q'}\alpha _{q'} - {\bar{y}}_1 + ( r+1):\sum _{q\in Q\backslash \{q'\}}\alpha _q \ge 1, \right. \nonumber \\&\qquad \qquad \qquad \alpha _{q} \ge \alpha _{q'},\ \forall ~q\in Q \backslash \{q'\}, ~0\le \alpha _q \le 1, ~\forall ~ q \in Q \left. \right\} . \end{aligned}$$

   (40)
5. 2.1.

   If \(\alpha _{q'} = 0\), the constraints \(\alpha _{q} \ge \alpha _{q'},\ q \in Q \backslash \{q'\}\), are redundant. This implies that \((\varvec{e^{d'}}, -r)\) is an optimal solution of problem (40) where \(d' \in \mathrm{argmax}\,_{q\in Q \backslash \{q'\}}\{ {\bar{x}}_q \}\). We note that by the definition of d in (17), the objective value of problem (39) at point \((\varvec{e^{d'}}, -r)\) cannot be better than that at point \((\varvec{e^d}, -r)\).

6. 2.2.

   If \(\alpha _{q'} = 1\), we have \(\alpha _q=1,\) for all \(q\in Q\backslash \{q'\}\). Then \((\varvec{e}, -r+|Q|-2)\) is an optimal solution of problem (40).

7. 2.3.

   If \(0< \alpha _{q'} < 1\), we have \(\alpha _q \ge \alpha _{q'} > 0\) for all \(q \in Q \backslash \{q'\}\). There exists a basic optimal solution such that at least |Q| constraints in problem (40) are active. By a simple analysis, the active constraints must be \(\sum _{q\in Q\backslash \{q'\}}\alpha _q = 1 \) and \(\alpha _{q}=\alpha _{q'}\) for all \(q\in Q\backslash \{q'\}\). This implies \(\alpha _q =\frac{1}{|Q|-1}\) for all \(q \in Q\), and hence \((\frac{1}{|Q|-1}\varvec{e}, -r)\) is an optimal solution of problem (39).

   In summary, for problem (39), there are three potentially optimal solutions \((\varvec{e^d}, -r)\), \((\frac{1}{|Q|-1}\varvec{e}, -r)\), and \((\varvec{e}, -r+|Q|-2)\) with the objective value \( {\bar{x}}_d - {\bar{y}}_1 +r \), \(\frac{1}{|Q| -1} \sum _{q \in Q}{\bar{x}}_q - {\bar{y}}_1 + r\), and \( \sum _{q \in Q}{\bar{x}}_q - {\bar{y}}_1 + r - |Q| + 2 \), respectively. Finally, comparing these three values, we have case (b) in the statement. This completes the proof.

\(\square \)

Proof of Proposition 6

Proof

From the definition of r in (16), we have \( (\varvec{0},r) \in X \). This, together with assumption (ii) and condition (19), implies that

The vertices of polyhedron P, i.e., \( \mathrm{conv }\,(X) \), are \((\varvec{0},r)\), \((x,r+1)\) for all \(x\in \{0,1\}^{|Q|}\) with \(x\ne \varvec{0}\) and \(x\ne \varvec{e}\), and \((\varvec{e},r+2)\). Similar to the proof in Proposition 5, by removing redundant constraints and using Lemma 2 and Theorem 1, problem (12) reduces to problem (39). Hence, if \(|Q| \le 2\), by Lemma 4, the optimal solution \(({\varvec{e}}, -r)\) of problem (39) corresponds to the inequality \(\sum _{q \in Q} x_q \le y_1-r\) of polyhedron P. The associated face \(\{(x,y)\in P: \sum _{q \in Q} x_q= y_1-r\}\) contains \( |Q| + 1 \) affinely independent points: \(({\varvec{0}},r)\) and \((\varvec{e^q},r+1)\) for each \( q \in Q \), which shows that inequality \(\sum _{q \in Q} x_q \le y_1-r\) defines a facet of polyhedron P. This proves case (a) in the statement.

Analogously, if \(|Q| \ge 3\), by Lemma 4, points \((\varvec{e^d}, -r)\), \((\frac{1}{|Q|-1}\varvec{e}, -r)\), and \((\varvec{e}, -r +|Q|-2)\) are three potentially optimal solutions for problem (39) which correspond to inequalities \(x_{d}\le y_1-r\), \(\frac{1}{|Q|-1}\sum _{q \in Q} x_q\le y_1 -r\), and \(\sum _{q\in Q}x_q\le y_1-r+|Q|-2\), respectively. To prove that each of the three inequalities defines a facet of polyhedron P, we list the \(|Q|+1\) affinely independent points in polyhedron P fulfilling them at equality in the following.

Thus, we have case (b) in the statement. This completes the proof. \(\square \)

Proof of Proposition 7

Proof

From the definition of r in (16), we have \( (\varvec{0},r \varvec{f^1}) \in X \). Combining with assumptions (ii), (iii), and condition (18), we can write set X as:

Clearly, if \(r=0\), the vertices of polyhedron P, i.e., \(\mathrm{conv }\,(X)\), are \((\varvec{0},r\varvec{f^1})\), \((x,(r+1)\varvec{f^1})\) for all \(x\in \{0,1\}^{|Q|}\) with \(x\ne \varvec{0}\), and \((x,\varvec{f^t})\) for all \(x\in \{0,1\}^{|Q|}\) with \(x \ne {\varvec{0}}\) and \(t\in T\backslash \{1\}\). If \(r>0\), the additional vertices of polyhedron P are \(({\varvec{0}},\varvec{f^t})\) for all \(t\in T\backslash \{1\}\). Similar to the proof in Proposition 5, by removing redundant constraints and using Lemma 2 and Theorem 1, problem (12) reduces to

We now relax the bound constraints \(\beta _t \ge 0\) for all \(t\in T\backslash \{1\}\) in problem (41). Then as the objective coefficient of \(\beta _t\) in problem (41) is \(-{\bar{y}}_t \le 0\), we have \(\beta _t = \sum _{q \in Q}\alpha _q -\gamma \) for all \(t\in T\backslash \{1\}\) in the relaxation problem. Substituting them into the objective function and dividing the objective function by the positive value \( 1-\sum _{t\in T\backslash \{1\}}{\bar{y}}_t \), we obtain an equivalent relaxation problem:

If, for some \( q\in Q\), variable \( \alpha _q \)’s objective coefficient \(\frac{{\bar{x}}_q- \sum _{t\in T\backslash \{1\}}{\bar{y}}_t}{1-\sum _{t\in T\backslash \{1\}}{\bar{y}}_t} \le 0\), then there must exist an optimal solution of problem (42) such that \(\alpha _q = 0\). Hence, we can remove the variables \( \alpha _q \) with nonpositive objective coefficients (\( q\in Q\backslash \tilde{Q} \) where \(\tilde{Q}\) is defined in (20)) from problem (42) and concentrate on the equivalent form of problem (42):

We have two following cases.

1. 1.

   \(\tilde{Q} = \varnothing \). It can be easily verified that point \( (\alpha , \gamma )= ({\varvec{0}}, -r) \) is optimal for problem (42). Together with \( \beta _t =\sum _{q \in Q}\alpha _q -\gamma = r \ge 0 \) for all \( t \in T \backslash \{1\} \), we know that \(({\varvec{0}}, \varvec{f^1} + r\sum _{t \in T \backslash \{1\}} \varvec{f^t}, -r)\) is an optimal solution for problem (41) corresponding to the inequality \( 0 \le y_1 + r\sum _{t\in T \backslash \{1\}}y_t-r \) of polyhedron P. Moreover, the inequality defines a facet of polyhedron P since the \(|Q|+|T|\) affinely independent points \(({\varvec{0}},r\varvec{f^1})\), \(({\varvec{0}},\varvec{f^t})\) for each \(t\in T\backslash \{1\}\), and \((\varvec{e^q},\varvec{f^{t'}})\) for each \(q\in Q\) and some \( t' \in T \backslash \{1\} \), are on the face \(\{(x,y)\in P: 0 = y_1 + r\sum _{t\in T \backslash \{1\}}y_t-r\}\).

2. 2.

   \(\tilde{Q} \ne \varnothing \). Notice that problem (42) are a form of problem (37) and hence by Lemma 3, point \( (\alpha , \gamma ) = (\varvec{e^d}, -r) \) is optimal for problem (42) where d is defined in (17). Furthermore, for all \( t \in T\), we have \( \beta _t =\sum _{q \in Q}\alpha _q -\gamma = r+1 \ge 0 \) showing that \((\varvec{e^{d}}, \varvec{f^1} + (r+1)\sum _{t \in T \backslash \{1\}} \varvec{f^t}, -r)\) is an optimal solution of problem (41) which corresponds to the inequality \( x_d \le y_1 + (r+1)\sum _{t\in T \backslash \{1\}}y_t-r \) for P. Finally, the \(|Q|+|T|\) affinely independent points \(({\varvec{0}},r\varvec{f^1})\), \((\varvec{e^d},(r+1)\varvec{f^1})\), \((\varvec{e^d} + \varvec{e^q},(r+1)\varvec{f^1})\) for each \(q\in Q \backslash \{d\}\), and \((\varvec{e^{d}},\varvec{f^t})\) for each \(t\in T\backslash \{1\}\) are on the face \(\{(x,y)\in P: x_d = y_1 + (r+1)\sum _{t\in T \backslash \{1\}}y_t-r\}\), which implies that the inequality \(x_d \le y_1 + (r+1)\sum _{t\in T \backslash \{1\}}y_t-r\) is facet-defining for polyhedron P.

\(\square \)

Proof of Proposition 8

Proof

From the definition of r in (16), we have \( (\varvec{0},r\varvec{f^1}) \in X \). It follows from assumptions (ii), (iii) and condition (19) that the set X can be equivalently written as:

Clear, if \(r=0\), the vertices of polyhedron P, i.e., \( \mathrm{conv }\,(X) \), are \((\varvec{0},r\varvec{f^1})\), \((x,(r+1)\varvec{f^1})\) for all \(x\in \{0,1\}^{|Q|}\) with \(x\ne \varvec{0}\) and \(x\ne \varvec{e}\), \((\varvec{e}, (r+2)\varvec{f^1})\), and \((x,\varvec{f^t})\) for all \(x\in \{0,1\}^{|Q|}\) with \(x \ne {\varvec{0}}\) and for all \(t\in T\backslash \{1\}\). If \(r>0\), the additional vertices of polyhedron P are \(({\varvec{0}},\varvec{f^t})\) for all \(t\in T\backslash \{1\}\). Similar to the proof in Proposition 5, by removing redundant constraints and using Lemma 2 and Theorem 1, problem (12) reduces to

We now consider the relaxation of problem (44) obtained by relaxing the bound constraints \(\beta _t \ge 0\) for all \(t\in T\backslash \{1\}\). As the objective coefficient of \(\beta _t\) in problem (44) is \(-{\bar{y}}_t \le 0\), we can set \(\beta _t = \sum _{q \in Q}\alpha _q -\gamma \) for all \(t\in T\backslash \{1\}\) in the relaxation problem. In analogy to the proof in Proposition 7, substituting them into the objective function and dividing the objective function by the positive value \( 1-\sum _{t\in T\backslash \{1\}}{\bar{y}}_t \), this relaxation problem reduces to:

1. 1)

   \(\tilde{Q}\ne Q\). For \( q \in Q \backslash \tilde{Q} \) where \(\tilde{Q}\) is defined in (20), since \(\frac{{\bar{x}}_q- \sum _{t\in T\backslash \{1\}}{\bar{y}}_t}{1-\sum _{t\in T\backslash \{1\}}{\bar{y}}_t} < 0 \), we can set \( \alpha _q = 0 \) in problem (45). This, together with \( \alpha _q \ge 0\) for all \( q \in \tilde{Q} \), implies that the |Q| constraints \( \sum _{q \in {Q}\backslash \{{\bar{q}}\} }\alpha _q - (r+1) -\gamma \le 0 \), for all \( {\bar{q}}\in Q \), in problem (45), can be reduced to a single constraint \( \sum _{q \in \tilde{Q}}\alpha _q - (r+1) -\gamma \le 0 \) since they are either equivalent to or dominated by this constraint. Therefore, in this case, problem (45) reduces to problem (43), and repeating 1) and 2) in the proof of Proposition 7, we have cases (a) and (b) in the statement.

2. 2)

   \(\tilde{Q} = Q\) and \(|Q| \le 2\). By Lemma 4, point \(({\varvec{e}}, -r) \) is optimal for problem (45). For each \( t \in T\backslash \{1\}\), we have \( \beta _t =\sum _{q \in Q}\alpha _q -\gamma = r+|Q| \ge 0 \) showing that \(({\varvec{e}}, \varvec{f^1} + (r+|Q|)\sum _{t \in T \backslash \{1\}} \varvec{f^t}, -r)\) is an optimal solution of problem (44) corresponding to the inequality \(\sum _{q\in Q}x_q \le y_1 + (r+|Q|)\sum _{t\in T \backslash \{1\}}y_t-r \) for polyhedron P. Moreover, to show that it is facet-defining for polyhedron P, we list the \(|Q|+|T|\) affinely independent points in polyhedron P satisfying it on equality: \(({\varvec{0}},r \varvec{f^1})\), \((\varvec{e^q},(r+1) \varvec{f^1})\) for each \( q \in Q \), and \(({\varvec{e}}, \varvec{{f}^t})\) for each \( t \in T \backslash \{1\} \). Thus, we have case (c) in the statement.

3. 3)

   \(\tilde{Q} = Q\) and \(|Q| \ge 3\). By Lemma 4, one of the three points \((\varvec{e^d}, -r)\), \((\frac{1}{|Q|-1}{\varvec{e}}, -r)\), and \(({\varvec{e}}, -r+|Q|-2)\) are optimal for problem (45). Using these three points to compute \( \beta _t =\sum _{q \in Q}\alpha _q -\gamma \), for all \(t\in T\backslash \{1\}\), we have \(\beta _t= r+1\), \(r+\frac{|Q|}{|Q|-1}\), and \( r+2 \), respectively. In all three cases, we have \( \beta _t \ge 0 \) for all \( t \in T \backslash \{1\} \) and hence one of the three points \((\varvec{e^d},\varvec{f^1}+(r+1)\sum _{t\in T\backslash \{1\}}\varvec{f^t}, -r)\), \((\frac{1}{|Q|-1}{\varvec{e}}, \varvec{f^1}+(r+\frac{|Q|}{|Q|-1})\sum _{t\in T\backslash \{1\}}\varvec{f^t},-r)\), and \(({\varvec{e}},\varvec{f^1}+(r+2)\sum _{t\in T\backslash \{1\}}\varvec{f^t}\), \(-r+|Q|-2)\) must be optimal for problem (44). Finally, the following table shows that the associated inequalities define facets of polyhedron P.

Thus, we have case (d) in the statement. This completes the proof. \(\square \)

Reprints and permissions