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

Abstract

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.

Appendix

Here we provide the omitted proofs.

Proof of Lemma 1

We show the equivalent version of the lemma given by

• (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

• (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

$$\begin{aligned} {{\mathrm{conv}}}\left( B \setminus {{\mathrm{int}}}\left( F\right) \right)&= {{\mathrm{conv}}}\left( \left( B_0 + L\right) \setminus {{\mathrm{int}}}\left( F\right) \right) \end{aligned}$$

(34)

$$\begin{aligned}&= {{\mathrm{conv}}}\left( B_0 \setminus {{\mathrm{int}}}\left( F\right) \right) + L \end{aligned}$$

(35)

$$\begin{aligned}&= \left( B_0 \cap C\right) + L \end{aligned}$$

(36)

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

$$\begin{aligned} C&= \left\{ (x,t) \in {\mathbb {R}}^{n+1}\,:\, \left\| P_\pi ^\perp x\right\| _2^2 \le (c \pi ^T x + d t + e)^2\right. \nonumber \\&\left. \quad - \frac{(\pi ^T x + b)^2}{\left\| \pi \right\| _2^2}, \quad c \pi ^T x + d t + e \ge 0\right\} . \end{aligned}$$

(37)

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

$$\begin{aligned} (c \pi ^T \overline{x}+ d\overline{t}+ e)^2 - \frac{(\pi ^T \overline{x}+ b)^2}{\left\| \pi \right\| _2^2} = \overline{t}- \frac{(\pi ^T \overline{x})^2}{\left\| \pi \right\| _2^2}. \end{aligned}$$

(38)

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

$$\begin{aligned} \hat{\pi }(\pi ^T \overline{x}+ \hat{\pi }\overline{t}) \ge - \left( \left\| \pi \right\| _2^2 + \sqrt{\left\| \pi \right\| _2^2+ 4 \pi _0 \hat{\pi }} \sqrt{\left\| \pi \right\| _2^2+ 4 \pi _1 \hat{\pi }}\right) \Big /{4}. \end{aligned}$$

(39)

(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

$$\begin{aligned} \left( (c \pi ^T \overline{x}+ d\overline{t}+ e)^2 - \frac{(\pi ^T \overline{x}+ b)^2}{\left\| \pi \right\| _2^2}\right) - \left( \overline{t}- \frac{(\pi ^T \overline{x})^2}{\left\| \pi \right\| _2^2}\right) \ge 0. \end{aligned}$$

(40)

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

$$\begin{aligned} \frac{f^2 (\pi ^T \overline{x}+ \hat{\pi }\overline{t}- \pi _0) (\pi ^T \overline{x}+ \hat{\pi }\overline{t}- \pi _1)}{2 \left( \pi _1 - \pi _0\right) ^2 \hat{\pi }^2} \ge 0, \end{aligned}$$

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,

$$\begin{aligned} \left( \pi ,\hat{\pi }\right) ^T \left( x^*,t^*\right) = -e/c = \frac{-\left\| \pi \right\| _2^2}{4\hat{\pi }} - \frac{\sqrt{\left\| \pi \right\| _2^2 + 4 \pi _0 \hat{\pi }} \sqrt{\left\| \pi \right\| _2^2 + 4 \pi _1 \hat{\pi }}}{4\hat{\pi }}. \end{aligned}$$

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

$$\begin{aligned} \frac{f^2 \left( \hat{\pi }\overline{t}- \pi _0\right) \left( \hat{\pi }\overline{t}- \pi _1\right) }{2 \left( \pi _1 - \pi _0\right) ^2 \hat{\pi }^2} \ge 0, \end{aligned}$$

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

$$\begin{aligned} C&= \left\{ (x,t) \in {\mathbb {R}}^{n+1}\,:\, \left\| P_\pi ^\perp x\right\| _2^2 \le (c \pi ^T x + d t + e)^2 - \frac{(a\pi ^T x + b)^2}{\left\| \pi \right\| _2^2},\right. \nonumber \\&\left. \quad c \pi ^T x + d t + e \ge 0\right\} . \end{aligned}$$

(41)

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$