Intersection cuts for nonlinear integer programming: convexification techniques for structured sets

We study the generalization of split, k-branch split, and intersection cuts from mixed integer linear programming to the realm of mixed integer nonlinear programming. Constructing such cuts requires calculating the convex hull of the difference between a convex set and an open set with a simple geometric structure. We introduce two techniques to give precise characterizations of such convex hulls and use them to construct split, k-branch split, and intersection cuts for several classes of non-polyhedral sets. In particular, we give simple formulas for split cuts for essentially all convex sets described by a single conic quadratic inequality. We also give simple formulas for k-branch split cuts and some general intersection cuts for a wide variety of convex quadratic sets.

1. We allow \(\pi =0_n\) to consider disjunctions that only affect \(t\).

2. For instance, (13) implies \(\sqrt{\left( ax+b\right) ^2} \le \left( c-d\right) x+e\) for all \(\left( x,-x\right) \in Q_0\).

3. After our original submission, it was brought to our attention that reduction of the infinite number of inequalities to a single quadratic inequality can also be directly deduced from the formulas for such linear inequalities given in [12, 13].

We thank the review team including an anonymous associate editor and two referees for their thoughtful and constructive comments, which significantly improved the exposition of the paper. This research was partially supported by the National Science Foundation under Grant CMMI-1030662 and by the Office of Naval Research under Grant N000141110724.

Authors and Affiliations

1. Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, PA, 15261, USA

   Sina Modaresi

2. Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA, 15213, USA

   Mustafa R. Kılınç

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

   Juan Pablo Vielma

Corresponding author

Correspondence to Juan Pablo Vielma.

Appendix

Here we provide the omitted proofs.

Proof of Lemma 1

We show the equivalent version of the lemma given by

1. (i)

   If \(s \in \left\{ \pi _0, \pi _1\right\} \), then \(\left| as +b\right| =(\left| s\right| ^p + \left| l\right| ^p)^{1/p}\) and

2. (ii)

   if \(s \notin \left( \pi _0, \pi _1\right) \), then \(\left| as +b\right| \le (\left| s\right| ^p + \left| l\right| ^p)^{1/p}\).

Let \(f(s):{=}a s +b\) and \(g(s):{=}(\left| s\right| ^p + \left| l\right| ^p)^{1/p}\). By definition of \(a\) and \(b\) we have that \(f( \pi _i)=g(\pi _i)\) for \(i\in \left\{ 0,1\right\} \). Indeed, \(f(s)\) is the (affine) linear interpolation of \(g(s)\) through \(z=\pi _0\) and \(z = \pi _1\). Convexity of \(g(s)\) then implies \(f(s)\le g(s)\) for all \(s\notin \left( \pi _0, \pi _1\right) \). If \(\left| \pi _0\right| =\left| \pi _1\right| \), then \(\left| as +b\right| =f(s)\) and the result follows directly. If \(\left| \pi _0\right| \ne \left| \pi _1\right| \), one can check that \(\left| as +b\right| =f(s)\) for \(s\in \left[ \pi _0, \pi _1\right] \) and hence (i) holds. For (ii) it suffices to show that \(-as-b\le g(s)\) for all \(s\in {\mathbb {R}}\). To show this we first assume \(a>0\) and hence \(\pi _1>0\) (case \(a<0\) is analogous). Because \(f(s)\) is affine and \(f( \pi _i)=g(\pi _i)\) for \(i\in \left\{ 0,1\right\} \), by a sub-differential version of the mean value theorem we have that there exists \(\bar{s}\in (\pi _0,\pi _1)\) such that \(a \in \partial g(\bar{s})\). Then, by symmetry of \(g(s)\) and its convexity, we have that \(g(s)\ge g(-\bar{s})-a(s+\bar{s}) = - as + g(-\bar{s})-a\bar{s}\) for \(s \in {\mathbb {R}}\). The result then follows by noting that \( g(-\bar{s})-a\bar{s}\ge -b\) for all \(\bar{s}\in (\pi _0,\pi _1)\) because \(g(s)-as \ge 0\) for all \(s \in {\mathbb {R}}\) and \(-b\le 0\). \(\square \)

Proof of Lemma 3

We first prove the second case \(\pi \notin L^\perp \). The left to right containment follows from \(B \setminus {{\mathrm{int}}}\left( F\right) \subseteq B\) and convexity of \(B\). To show the right to left containment, let \(\overline{x}\in B\) such that \(\pi ^T \overline{x}\in \left( \pi _0,\pi _1\right) \) and \(u \in L\). Note that \(\pi \notin L^\perp \) implies \(\pi ^T u \ne 0\). Let \(x^i :{=}\overline{x}+ \lambda _i u\) for \(i \in \left\{ 0,1\right\} \), where \(\lambda _i = \frac{\pi _i - \pi ^T \overline{x}}{\pi ^T u}\), and let \(\beta \in (0,1)\) be such that \(\pi ^T \overline{x}= \beta \pi _0 + \left( 1-\beta \right) \pi _1\). Because \(u \in L\) and since \(\pi ^T x^i = \pi _i\), we have \(x^i \in B \setminus {{\mathrm{int}}}\left( F\right) \) for \(i \in \left\{ 0,1\right\} \). The results then follows by noting that \(\overline{x}= \beta x^0 + \left( 1-\beta \right) x^1\).

We prove the first case by showing that

Note that (34) and (36) follow from the assumptions. To show the left to right containment in (35), let \(\overline{x}\in {{\mathrm{conv}}}\left( \left( B_0 + L\right) \setminus {{\mathrm{int}}}\left( F\right) \right) \). There exist \(y^i \in B_0\), \(u^i \in L\) for \(i \in \left\{ 0,1\right\} \), and \(\beta \in [0,1]\) such that for \(x^i :{=}y^i + u^i\), we have \(x^i \notin {{\mathrm{int}}}\left( F\right) \) and \(\overline{x}= \beta x^0 + \left( 1-\beta \right) x^1\). Note that \(\pi \in L^\perp \) and \(x^i \notin {{\mathrm{int}}}\left( F\right) \) imply \(y^i \notin {{\mathrm{int}}}\left( F\right) \) for \(i \in \left\{ 0,1\right\} \). The result then follows from noting that \(\beta y^0 + \left( 1-\beta \right) y^1 \in {{\mathrm{conv}}}\left( B_0 \setminus {{\mathrm{int}}}\left( F\right) \right) \) and \(\beta u^0 + \left( 1-\beta \right) u^1 \in L\).

To show the right to left containment in (35), let \(\overline{x}\in {{\mathrm{conv}}}\left( B_0 \setminus {{\mathrm{int}}}\left( F\right) \right) + L\). There exist \(u \in L\), \(y^i \in B_0 \setminus {{\mathrm{int}}}\left( F\right) \) for \(i \in \left\{ 0,1\right\} \), and \(\beta \in [0,1]\) such that \(\overline{x}= \beta y^0 + \left( 1-\beta \right) y^1 + u\). If \(\beta \in \left\{ 0,1\right\} \), the result follows by noting that \(\pi \in L^\perp \) and \(y^0,y^1 \notin {{\mathrm{int}}}\left( F\right) \) imply \(\overline{x}\notin {{\mathrm{int}}}\left( F\right) \). Assume \(\beta \in \left( 0,1\right) \) and let \(x^0 :{=}y^0 + \frac{u}{2\beta }\) and \(x^1 :{=}y^1 + \frac{u}{2\left( 1-\beta \right) }\). The result then follows by noting that \(x^i \in B_0+L \setminus {{\mathrm{int}}}\left( F\right) \) for \(i \in \left\{ 0,1\right\} \) and \(\overline{x}= \beta x^0 + \left( 1-\beta \right) x^1\). \(\square \)

Proof of Proposition 9

We first prove the last case using Proposition 1. Using Lemma 2, we have

Now consider the following two cases.

Case 1 Assume that \(\left\| \pi \right\| _2 \ne 0\). To prove the right to left containment in (2a), let \((\overline{x}, \overline{t}) \in C \cap {{\mathrm{bd}}}\left( F\right) \). We need to show that

Replacing \(\overline{t}\) with \((\pi _i - \pi ^T \overline{x})/\hat{\pi }\) for \(i \in \left\{ 0,1\right\} \), one can check that (38) follows from the definition of \(b, c, d,\) and e. To prove the left to right containment in (2a), let \((\overline{x}, \overline{t}) \in Q_0 \cap {{\mathrm{bd}}}\left( F\right) \). We only need to show that \(c \pi ^T \overline{x}+ d\overline{t}+ e \ge 0\). Since \(d = c \hat{\pi }\), we can equivalently show that \(c (\pi ^T \overline{x}+ \hat{\pi }\overline{t}) \ge -e\), which after a few simplifications, can be written as

(39) follows from noting that \(\min \{\hat{\pi }(\pi ^Tx + \hat{\pi }t) \,:\, (x, t) \in Q_0\} = -\frac{\left\| \pi \right\| _2^2}{4}\).

To show (2b), let \(\left( \overline{x},\overline{t}\right) \in Q_0 \setminus {{\mathrm{int}}}\left( F\right) \). Proving \(c \pi ^T \overline{x}+ d\overline{t}+ e \ge 0\) is similar as before. We only need to show that \((\overline{x}, \overline{t})\) satisfies the quadratic inequality in (37), which we prove by showing that

One can check that proving (40) is equivalent to showing that

which follows from \(\pi ^T \overline{x}+ \hat{\pi }\overline{t}\notin (\pi _0, \pi _1)\). Note that \(C\) is a conic set with apex \(\left( x^*,t^*\right) = (\frac{-b}{\left\| \pi \right\| _2^2} \pi ,\frac{bc-e}{d})\). Furthermore,

Hence, if \(\hat{\pi }< 0\), then \(\left( \pi ,\hat{\pi }\right) ^T \left( x^*,t^*\right) \ge \frac{-\left\| \pi \right\| _2^2}{4\hat{\pi }} \ge \pi _1\) and if \(\hat{\pi }> 0\), then \(\left( \pi ,\hat{\pi }\right) ^T \left( x^*,t^*\right) \le \frac{-\left\| \pi \right\| _2^2}{4\hat{\pi }} \le \pi _0\). Friends condition (3) then follows from Proposition 4.

Case 2 If \(\left\| \pi \right\| _2 = 0\), \(C\) is simplified to \(C = \left\{ (\right\} x,t) \in {\mathbb {R}}^{n+1}\,:\, \left\| x\right\| _2^2 \le \left( dt+e\right) ^2, \) \( dt+e \ge 0 \).

Interpolation condition (2a) follows from noting that \(\left( d \overline{t}+ b\right) ^2 = \overline{t}\). Non-negativity of \(d, e\), and \(t\) also imply \(d \overline{t}+ e \ge 0\). Proving (2b) is equivalent to showing that

which follows from \(\hat{\pi }\overline{t}\notin (\pi _0, \pi _1)\). Note that \(C\) is a conic set with apex \(\left( x^*,t^*\right) = \left( 0,\frac{-e}{d}\right) \). Furthermore, \(\left( \pi ,\hat{\pi }\right) ^T \left( x^*,t^*\right) = -e/c\). As shown in Case 1, we have \(\left( \pi ,\hat{\pi }\right) ^T \left( x^*,t^*\right) \notin \left( \pi _0,\pi _1\right) \). Friends condition (3) then follows from Proposition 4.

To prove the other cases, let \(S_0 :{=}\{(x,t) \in Q_0\,:\, \pi ^Tx+\hat{\pi }t \le \pi _0\}\) and \(S_1 :{=}\) \( \{(x,t) \in Q_0\,:\, \pi ^Tx+\hat{\pi }t \ge \pi _1\}\). Consider the first case where \(\hat{\pi }> 0\) and \(\pi _1 \le \frac{-\left\| \pi \right\| _2^2}{4\hat{\pi }}\). We prove the result by showing that \(S_0 = \emptyset \) and \(S_1 = Q_0\). If \(\left\| \pi \right\| _2 = 0\), the result follows from non-negativity of \(t\). Now assume that \(\left\| \pi \right\| _2 \ne 0\). We prove \(S_0 = \emptyset \) by showing that \((\pi ^T x)^2/\left\| \pi \right\| _2^2 > (\pi _0 - \pi ^T x)/\hat{\pi }\) for \(x\in {\mathbb {R}}^n\). This follows from noting that for \(y \in {\mathbb {R}}\), the quadratic equation \(\frac{y^2}{\left\| \pi \right\| _2^2} = \frac{\pi _0 - y}{\hat{\pi }}\) does not have any solution. To prove \(S_1 = Q_0\), we show that \(\pi ^T x + \hat{\pi }t \ge \pi _1\) is a valid inequality for \(Q_0\). This comes from the fact that the quadratic equation \(\frac{y^2}{\left\| \pi \right\| _2^2} = \frac{\pi _1 - y}{\hat{\pi }}\) has at most a single solution and we thus have \((\pi _1 - \pi ^T x)/\hat{\pi } \le (\pi ^T x)^2/\left\| \pi \right\| _2^2 \le t\) for \(x \in {\mathbb {R}}^n\). The proof for the case \(\hat{\pi }< 0\) and \(\frac{-\left\| \pi \right\| _2^2}{4\hat{\pi }} \le \pi _0\) is analogous and follows by noting that \(S_0 = Q_0\) and \(S_1 = \emptyset \).

We prove the second case where \(\hat{\pi }> 0\) and \(\pi _0 < \frac{-\left\| \pi \right\| _2^2}{4\hat{\pi }} < \pi _1\) by showing that \(S_0 = \emptyset , S_1 \subsetneq Q_0\), and \(S_1 \ne \emptyset \). Proving \(S_0 = \emptyset \) is analogous to the previous case. We have \(S_1 \subsetneq Q_0\) since \(\left( \bar{x}, \overline{t}\right) = (\frac{- \pi }{2 \hat{\pi }}, \frac{\left\| \pi \right\| _2^2}{4 \hat{\pi }^2}) \in Q_0\), but \(\left( \bar{x}, \overline{t}\right) \notin S_1\). To prove \(S_1 \ne \emptyset \), one can check that for any \(\bar{x} \in {\mathbb {R}}^n\) and \(\overline{t}= {{\mathrm{max}}}\{\left\| \overline{x}\right\| _2^2, \frac{\pi _1 - \pi ^T \bar{x}}{\hat{\pi }}\}\), \(\left( \bar{x}, \overline{t}\right) \in S_1\). The proof of the third case is analogous and follows by noting that \(S_1 = \emptyset , S_0 \subsetneq Q_0\), and \(S_0 \ne \emptyset \). \(\square \)

Proof of Proposition 10

We first prove the last case using Proposition 1. Note that \(\hat{\pi }\ne 0\) and \(\hat{\pi }\in (-\left\| \pi \right\| _2, \left\| \pi \right\| _2)\) imply \(\left\| \pi \right\| _2 \ne 0\). Using Lemma 2, we have

Observe that \(d>0\). Similarly to the proof of Proposition 9, one can show that interpolation condition (2) holds by the definition of \(a, b, c, d\), and \(e\). If \(\left| \pi _0 \right| = \left| \pi _1 \right| \), then \(u = (\pi ,\frac{-c \left\| \pi \right\| _2^2}{d}) \in {{\mathrm{lin}}}\left( C\right) \) and friends condition (3) follows from Proposition 2. If \(\left| \pi _0 \right| \ne \left| \pi _1 \right| \), then \(C\) is a conic set with apex \(\left( x^*,t^*\right) = (\frac{-b}{a \left\| \pi \right\| _2^2} \pi ,\frac{bc-ae}{ad})\). Furthermore, \(\left( \pi ,\hat{\pi }\right) ^T \left( x^*,t^*\right) = \frac{2 \pi _0\pi _1}{\pi _0 + \pi _1}\). If \(\pi _0 + \pi _1 <0\), then we have \(\frac{2 \pi _0\pi _1}{\pi _0 + \pi _1} \ge \pi _1\), and if \(\pi _0 + \pi _1 >0\), then we have \(\frac{2 \pi _0\pi _1}{\pi _0 + \pi _1} \le \pi _0\). Friends condition (3) then follows from Proposition 4.

To prove the first case \(0 \notin \left( \pi _0, \pi _1\right) \), we only need to show that friends condition (3) holds. This follows from Proposition 4 by noting that \(K_0\) is a conic set whose apex is the origin.

To prove the other cases, let \(S_0 :{=}\{(x,t) \in K_0\,:\, \pi ^Tx+\hat{\pi }t \le \pi _0\}\) and \(S_1 :{=} \{(x,t) \in K_0\,:\, \pi ^Tx+\hat{\pi }t \ge \pi _1\}\). Consider the second case \(0 \in \left( \pi _0,\pi _1\right) \) and \(\hat{\pi } \le -\left\| \pi \right\| _2\). We prove the result by showing that \(S_1 = \emptyset \), \(S_0 \subsetneq K_0\), and \(S_0 \ne \emptyset \). If \(\left\| \pi \right\| _2 = 0\), the result follows from non-negativity of \(t\). Now assume that \(\left\| \pi \right\| _2 \ne 0\). We prove \(S_1 = \emptyset \) by showing that \((\pi ^T x)^2/\left\| \pi \right\| _2^2 > (\pi _1 - \pi ^T x)^2/\hat{\pi }^2\). Note that non-negativity of \(t\), \(\hat{\pi }< 0\), and \(\pi ^T x + \hat{\pi } t \ge \pi _1\) imply \(\pi ^T x \ge \pi _1 > 0\). One can see that \(-\pi ^T x < \pi _1 - \pi ^T x < \pi ^T x\), where the first inequality comes from the fact that \(\pi _1 > 0\), and the second inequality follows from \(\pi _1 \le \pi ^T x\) and \(- \pi ^T x < 0\). Thus, \((\pi ^T x)^2 > (\pi _1 - \pi ^T x)^2\) and the result follows by noting that \(\frac{1}{\left\| \pi \right\| _2^2} \ge \frac{1}{\hat{\pi }^2}\). We have \(S_0 \subsetneq K_0\) since \(\left( \bar{x}, \overline{t}\right) = \left( {0_n}, 0\right) \in K_0\), but \(\left( \bar{x}, \overline{t}\right) \notin S_0\). To prove \(S_0 \ne \emptyset \), one can check that for any \(\bar{x} \in {\mathbb {R}}^n\) and \(\overline{t}= {{\mathrm{max}}}\{\left\| \overline{x}\right\| _2, \frac{\pi _0 - \pi ^T \bar{x}}{\hat{\pi }}\}\), \(\left( \bar{x}, \overline{t}\right) \in S_0\). The proof of the third case \(0 \in \left( \pi _0,\pi _1\right) \) and \(\hat{\pi } \ge \left\| \pi \right\| _2\) is analogous and follows by noting that \(S_0 = \emptyset \), \(S_1 \subsetneq K_0\), and \(S_1 \ne \emptyset \). \(\square \)

Reprints and permissions