Extended formulations in mixed integer conic quadratic programming

In this paper we consider the use of extended formulations in LP-based algorithms for mixed integer conic quadratic programming (MICQP). Extended formulations have been used by Vielma et al. (INFORMS J Comput 20: 438–450, 2008) and Hijazi et al. (Comput Optim Appl 52: 537–558, 2012) to construct algorithms for MICQP that can provide a significant computational advantage. The first approach is based on an extended or lifted polyhedral relaxation of the Lorentz cone by Ben-Tal and Nemirovski (Math Oper Res 26(2): 193–205 2001) that is extremely economical, but whose approximation quality cannot be iteratively improved. The second is based on a lifted polyhedral relaxation of the euclidean ball that can be constructed using techniques introduced by Tawarmalani and Sahinidis (Math Programm 103(2): 225–249, 2005). This relaxation is less economical, but its approximation quality can be iteratively improved. Unfortunately, while the approach of Vielma, Ahmed and Nemhauser is applicable for general MICQP problems, the approach of Hijazi, Bonami and Ouorou can only be used for MICQP problems with convex quadratic constraints. In this paper we show how a homogenization procedure can be combined with the technique by Tawarmalani and Sahinidis to adapt the extended formulation used by Hijazi, Bonami and Ouorou to a class of conic mixed integer programming problems that include general MICQP problems. We then compare the effectiveness of this new extended formulation against traditional and extended formulation-based algorithms for MICQP. We find that this new formulation can be used to improve various LP-based algorithms. In particular, the formulation provides an easy-to-implement procedure that, in our benchmarks, significantly improved the performance of commercial MICQP solvers.

1. Or more precisely, \({\mathcal {N}}:=\left\{ N_{i,k}\,:\, i\in \{1,\ldots ,\lfloor r_k/2 \rfloor \},\,k\in \left\{ 0,\ldots ,K-1\right\} \right\} \) where \(N_{i,k}={\widehat{N}}^2_s\) for each i, k.

2. After removing redundant variables through the equalities of the formulation.

3. For instance, one can check that \(\left\{ y\in {\mathbb {R}}^2\,:\, {{\mathrm{Proj}}}_{\left( 1,y\right) }\left( {\widehat{N}}^2_s\right) \right\} \) is a regular \(2^s\) polygon.

4. Note that the complete description of each rotated two-dimensional conic quadratic constraints is \(y_j^2 \le w_j y_0\) and \(0\le y_0\).

5. Remember that, while \(\widehat{{\mathbf {C}}}\) does not explicitly include \(y_0\ge 0\), any point in \(\widehat{{\mathbf {C}}}\) satisfies this constraint under the assumptions of Proposition 4 (e.g. see proof of Lemma 2 in Appendix A).

We thank the review team for their thoughtful and constructive comments, which improved the exposition of the paper. Support for Juan Pablo Vielma was provided by the National Science Foundation under grant CMMI-1351619, support for Miles Lubin was provided by the DOE Computational Science Graduate Fellowship under grant DE-FG02-97ER25308 and support for Joey Huchette was provided by the National Science Foundation Graduate Research Fellowship under grant 1122374.

Authors and Affiliations

1. Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA

   Juan Pablo Vielma

2. Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA

   Iain Dunning, Joey Huchette & Miles Lubin

Corresponding author

Correspondence to Juan Pablo Vielma.

Appendix A: Proof of Proposition 4

To prove Proposition 4 we begin with the following lemma, which gives a characterization of the homogenization of a convex set described by nonlinear constraints.

Lemma 1

Let \(f:{\mathbb {R}}^d\rightarrow {\mathbb {R}}\) be a closed convex function such that \(\lim _{\left||x\right||_2\rightarrow \infty } \frac{f(x)}{\left||x\right||_2}=\infty \) so that the closure of the perspective function of f is given by

If \({\mathbf {C}}:=\left\{ y\in {\mathbb {R}}^d\,:\, f(y)\le 1\right\} \), then

Proof

Let \({\mathbf {D}}:=\left\{ \left( y_0,y\right) \in {\mathbb {R}}^{d+1}\,:\, \left( cl{\tilde{f}}\right) (y_0,y)\le y_0\right\} \). We have \(\left\{ 1\right\} \times {\mathbf {C}}\subseteq {\mathbf {D}}\) and \({\mathbf {D}}\) is a convex cone because \(\left( cl{\tilde{f}}\right) (y_0,y)\) is a homogeneous function, so \({{\mathrm{cone}}}\left( \left\{ 1\right\} \times {\mathbf {C}}\right) \subseteq {\mathbf {D}}\).

For the reverse inclusion, let \(\left( y_0,y\right) \in {\mathbf {D}}\). If \(y_0=0\) then \(y=0\) and hence \(\left( y_0,y\right) \in {{\mathrm{cone}}}\left( \left\{ 1\right\} \times {\mathbf {C}}\right) \). If \(y_0>0\) then \(\left( y_0,y\right) /y_0\in \left\{ 1\right\} \times {\mathbf {C}}\) and hence \(\left( y_0,y\right) \in {{\mathrm{cone}}}\left( \left\{ 1\right\} \times {\mathbf {C}}\right) \). \(\square \)

The final ingredient for the proof of Proposition 4 is the following lemma that shows how to translate the polyhedral approximation for univariate functions to their homogenization.

Lemma 2

Let \(f:{\mathbb {R}}\rightarrow {\mathbb {R}}\) be a closed convex differentiable function such that \(\lim _{x\rightarrow \infty } \frac{f(x)}{\left| x\right| }=\infty \). Then

Furthermore, \(\left( y_0,y,w\right) \in {{\mathrm{epi}}}\left( cl{\tilde{f}}\right) \) if and only if either \(y_0=y=0\le w\) or if \(y_0> 0\) and

for \(\gamma \left( y_0,y\right) \) defined in Corollary 2.

Proof

First note that \({\mathbf {D}}:=\big \{\left( y_0,y,w\right) \in {\mathbb {R}}^3\,:\, \left( f\left( \gamma \right) -\gamma f'\left( \gamma \right) \right) y_0 + f'\left( \gamma \right) y \le w \quad \forall \gamma \in {\mathbb {R}}\big \}\) is a closed convex cone, \({{\mathrm{epi}}}\left( cl{\tilde{f}}\right) ={\overline{{{\mathrm{cone}}}}}\left( \left\{ 1\right\} \times {{\mathrm{epi}}}\left( f\right) \right) \) and

Then \(\left\{ 1\right\} \times {{\mathrm{epi}}}\left( f\right) \subseteq {\mathbf {D}}\) implies \({{\mathrm{epi}}}\left( cl{\tilde{f}}\right) \subseteq {\mathbf {D}}\).

For the reverse inclusion, let \(\left( y_0,y,w\right) \in {\mathbf {D}}\). We first show that \(y_0\ge 0\), by assuming \(y_0<0\) and reaching a contradiction. For this we consider cases \(y\ne 0\) and \(y=0\) separately. For both cases note that \(\lim _{x\rightarrow \infty } \frac{f(x)}{\left| x\right| }=\infty \) implies that \(\lim _{x\rightarrow +\infty } f'(x)=+\infty \) and \(\lim _{x\rightarrow -\infty } f'(x)=-\infty \).

For case \(y\ne 0\), note that if \(y_0<0\), then \(y_0 f(0)\le y_0\left( f\left( \gamma \right) -\gamma f'\left( \gamma \right) \right) \) for all \(\gamma \in {\mathbb {R}}\) by convexity of f. Hence, if \(\left( y_0,y,w\right) \in {\mathbf {D}}\) and \(y_0<0\) then

for all \(\gamma \in {\mathbb {R}}\). Taking limit for \(\gamma \rightarrow \infty \) when \(y>0\) and for \(\gamma \rightarrow -\infty \) when \(y<0\) in (25) we arrive at a contradiction with \(w<\infty \).

For case \(y=0\), note that by convexity of f and the mean value theorem we have that \(f\left( \gamma \right) -\gamma f'\left( \gamma \right) \le f\left( \gamma _0\right) - f'\left( \gamma \right) \gamma _0\) for any \(0<\gamma _0<\gamma \). Then, \(\lim _{\gamma \rightarrow \infty } f\left( \gamma \right) -\gamma f'\left( \gamma \right) =-\infty \). Now, if \(\left( y_0,y,w\right) \in {\mathbf {D}}\) and \(y=0\) then

for all \(\gamma \in {\mathbb {R}}\). Then, if \(y_0<0\), by taking limit for \(\gamma \rightarrow \infty \) in (26) we again arrive at a contradiction with \(w<\infty \).

We now show that any \(\left( y_0,y,w\right) \in {\mathbf {D}}\) with \(y_0\ge 0\) also belongs to \({{\mathrm{epi}}}\left( cl{\tilde{f}}\right) \). We divide the proof into cases \(y_0=0\) and \(y_0>0\).

For case, \(y_0=0\), note that \(\left( y_0,y,w\right) \in {\mathbf {D}}\) implies \(f'\left( \gamma \right) y \le w\) for all \(\gamma \in {\mathbb {R}}\). Taking limit for \(\gamma \rightarrow \infty \) when \(y>0 \) and for \(\gamma \rightarrow -\infty \) when \(y<0\), we conclude that \(y=0\) and \(w\ge 0\). Hence, \(\left( y_0,y,w\right) \in {{\mathrm{epi}}}\left( cl{\tilde{f}}\right) \).

For case, \(y_0>0\) we can check that \(\left( y,w\right) /y_0\in {{\mathrm{epi}}}\left( f\right) \) and then \(\left( y_0,y,w\right) /y_0\in \left\{ 1\right\} \times {{\mathrm{epi}}}\left( f\right) \). Hence, \(\left( y_0,y,w\right) \in {{\mathrm{cone}}}\left( \left\{ 1\right\} \times {{\mathrm{epi}}}\left( f\right) \right) \subseteq {{\mathrm{epi}}}\left( cl{\tilde{f}}\right) \).

For the final statement, it suffices to prove that \(\left( y_0,y,w\right) \in {{\mathrm{epi}}}\left( cl{\tilde{f}}\right) \) if \(y_0>0\) and \(\left( y_0,y,w\right) \) satisfies (24). For this note that, if the last two conditions hold, then \(\left( y,w\right) /y_0\in {{\mathrm{epi}}}\left( f\right) \), which we have already shown implies \(\left( y_0,y,w\right) \in {{\mathrm{epi}}}\left( cl{\tilde{f}}\right) \).

\(\square \)

Combining these lemmas we obtain the following straightforward proof of Proposition 4.

Proof

(of Proposition 4) Let \(f(y)=\sum _{j=1}^d f_j(y_j)\). Then (11) follows by noting that by Lemma 1 we have \({{\mathrm{cone}}}\left( \left\{ 1\right\} \times {\mathbf {C}}\right) =\left\{ \left( y_0,y\right) \in {\mathbb {R}}^{d+1}\,:\, \left( cl{\tilde{f}}\right) (y_0,y)\le y_0\right\} \) and by the definition of perspective function we have \(\left( cl{\tilde{f}}\right) (y_0,y)=\sum _{j=1}^d \left( cl\tilde{f_j}\right) (y_0,y_j)\). All other statements are directly from Lemma 2 and from Proposition 3 by fixing \(y_0=1\). \(\square \)

Appendix B: Additional graphs and tables

1.1 Appendix B.1: Summary statistics for solve times

Tables 1, 2, 3, 4, 5, 6, 7 and 8 show some summary statistics for the solve times for the different algorithms and instances. These statistics include the minimum, average and maximum solve times, together with their standard deviation. The tables also include the number of each solver was the fastest (wins) and the number of times a solver has a solution time that was within 1 and 10 % of the fastest solver (1 and 10 % win).

1.2 B. 2 Summary statistics for solution quality

Tables 9, 10, 11, 12, 13, 14, 15 and 16 present summary statistics for the maximum violation of constraints (1c) by the optimal solution returned by the solver. This value is calculated as

where \({\bar{x}}\) is the optimal solution.

1.3 B.3 Additional graphs

Figure 6 compares the performance of the three dynamic lifted polyhedral relaxations in their nonlinear reformulation version (CPLEXSepLP, GurobiSepLP, CPLEXTowerLP, GurobiTowerLP, CPLEXTowerSepLP, GurobiTowerSepLP). We also include as a reference the NLP-based algorithms CPLEXCP and GurobiCP (Tables 14, 15, 16).

LiftedLP Our final set of charts compare the branch- and cut-based LiftedLP algorithms (LiftedLP, CPLEXSepLazy and GurobiSepLazy) with the separable dynamic lifted polyhedral relaxation in its nonlinear reformulation version (CPLEXSepLP and GurobiSepLP). To minimize the complexity of the graphics we divide the comparison into two parts. In Fig. 7 we compare the branch-based algorithm with the separable reformulations and in Fig. 8 we compare the cut-based algorithms with the separable reformulations.

From Fig. 7 we see that the separable reformulations provide an advantage over the branch-based LiftedLP algorithm for all instances. However, this advantage becomes smaller as the problems sizes increase and the LiftedLP algorithm can provide an advantage in some instances (e.g Table 7 shows the algorithms is the fastest in 10 % of the robust instances for \(n=200\)). Figure 8 shows a similar behavior for the cut-based algorithms.

Solution times for dynamic lifted polyhedral relaxations solved by standard LP-based algorithms (s)

Full size image

Solution times for the branch-based LiftedLP algorithm and best LP-based (separable re-formulation) algorithms (s)

Full size image

Solution times for the cut-based LiftedLP algorithms and best LP-based (separable re-formulation) algorithms (s)

Full size image

Reprints and permissions