Sequence Independent Lifting for the Set of Submodular Maximization Problem

Abstract

We study the polyhedral structure of a mixed 0-1 set arising in the submodular maximization problem, given by $P = \{(w,x)\in \mathbb {R}\times \{0,1\}^n: w\le f(x), x\in \mathcal {X}\}$, where submodular function f(x) is represented by a concave function composed with a linear function, and $\mathcal {X}$ is the feasible region of binary variables x. For $\mathcal {X}= \{0,1\}^n$, two families of facet-defining inequalities are proposed for the convex hull of P through restriction and lifting using submodular inequalities. When $\mathcal {X}$ is a partition matroid, we propose a new class of facet-defining inequalities for the convex hull of P through multidimensional sequence independent lifting. Our results enable us to unify and generalize the existing results on valid inequalities for the mixed 0-1 knapsack. Finally, we perform some preliminary computational experiments to illustrate the superiority of our facet-defining inequalities.

Appendices

A Proof of Theorem 1

Lemma 1

Let $z \in [A_{k}, A_{k+1}]$ for some $k\ge 1$. Then for any $\varDelta \ge 0$ and $z + \varDelta \le A_{k+1}$, we have

$$\begin{aligned} \phi (z+\varDelta ) - \phi (z) \le \phi (z - \sum _{j = \ell }^{k+1} a_j + \varDelta ) - \phi (z - \sum _{j = \ell }^{k+1} a_j) \quad \forall \ell = 2,\ldots , k+1. \end{aligned}$$

Proof

It suffices to show the statement holds for $\ell = k+1$. Since $z \in [A_k, A_{k+1}]$ and $z+\varDelta \le A_{k+1}$, then $z-a_{k+1} \in [A_{k-1}, A_{k}]$ and $z+\varDelta -a_{k+1}\le A_k$. Therefore,

$$\begin{aligned} \phi (z+\varDelta ) - \phi (z)&= g(\varOmega +v_k - a_k+ \varDelta ) - g(\varOmega +v_k-a_k) \\&\le g(\varOmega + v_{k-1} -a_{k+1}+ \varDelta ) - g(\varOmega + v_{k-1} -a_{k+1}) \\&= \phi (z - a_{k+1} + \varDelta ) - \phi (z - a_{k+1}), \end{aligned}$$

where $\varOmega = z - A_{k-1}$, the inequality follows from $v_{k-1} + a_k \le v_k+a_{k+1}$ and the concavity of g (i.e., $g(z_0+\varDelta ) - g(z_0) \ge g(z_1 + \varDelta ) - g(z_1)$ if $z_0\le z_1$ and $\varDelta \ge 0$).    $\square$

Lemma 2

Let $\varDelta \in [0, a_{k+1}]$ for some $k\ge 0$. Then for any $z \ge A_{k}$, we have

$$\begin{aligned} \phi (A_{k} + \varDelta ) - \phi (A_{k}) \ge \phi (z + \varDelta ) - \phi (z). \end{aligned}$$

Proof

Suppose $z \in [A_{k_1}, A_{k_1+1}]$ and $z + \varDelta \in [A_{k_2}, A_{k_2+1}]$, where $k \le k_1 \le k_2$. We establish the result for each $k_2 - k_1$ by induction.

• If $k_2 = k_1$, then based on Lemma 1, we have

  $$\begin{aligned} \phi (z + \varDelta ) - \phi (z)&\le \phi (z - \sum _{j=k+2}^{k_1+1} a_j+\varDelta ) - \phi (z - \sum _{j=k+2}^{k_1+1} a_j) \\&= g(\varOmega + v_k + \varDelta )- g(\varOmega + v_k) \\&\le g(v_k+\varDelta ) - g(v_k) = \phi (A_{k} +\varDelta ) - \phi (A_{k}), \end{aligned}$$

  where $\varOmega = z-A_k-\sum _{j=k+2}^{k_1+1} a_j$, the second inequality follows from $a_{k+1} \ge a_{k_1+1}$ and $\varOmega = z - A_k - \sum _{j=k+2}^{k_1+1} a_j \ge z -A_k - \sum _{j=k+1}^{k_1} a_j \ge 0$.

• If the statement holds for $k_2 - k_1 = m$, then we show that the statement also holds for $k_2 - k_1 = m+1$. Let $\varDelta ' = A_{k_1+1} - z$, then $\varDelta \ge \varDelta '$. Since $\varDelta \in [0, a_{k+1}]$ and $A_{k_1+1} - \sum _{j=k+2}^{k_1+1} a_j = A_{k+1} \ge A_{k} + \varDelta$, we have

  $$\begin{aligned} \phi (A_{k} + \varDelta ) - \phi (A_{k} + \varDelta - \varDelta ')&\ge \phi (A_{k+1}) - \phi (A_{k+1} - \varDelta ') \\&= \phi (A_{k_1+1} -\sum _{j=k+2}^{k_1+1} a_j) - \phi (z - \sum _{j=k+2}^{k_1+1} a_j) \\&\ge \phi (A_{k_1+1}) - \phi (z), \end{aligned}$$

  where the first inequality follows from that $\phi$ is concave on $[A_k, A_{k+1}]$. Let $z' = A_{k_1+1}$, then $z' \in [A_{k_1+1}, A_{k_1+2}]$. Since $k_2 - (k_1 + 1)= m$, by the induction hypothesis, we have

  $$\begin{aligned} \phi (A_{k} + \varDelta - \varDelta ') - \phi (A_{k}) \ge \phi (z' + \varDelta - \varDelta ') - \phi (z') = \phi (z+\varDelta ) - \phi (A_{k_1+1}). \end{aligned}$$

  Summing the above two inequalities, we obtain the desired inequality.    $\square$

Proof

(Theorem 1). To show that $\phi$ is subadditive on $[0, +\infty )$, it is sufficient to prove that the inequality $\phi (z) - \phi (0) \ge \phi (z+\varDelta ) - \phi (\varDelta )$ holds for any $z, \varDelta \ge 0$.

First, by Lemma 2, we have that for any $\varDelta \ge 0$,

$$\begin{aligned} \phi (A_{j+1}) - \phi (A_{j}) \ge \phi (A_{j+1}+\varDelta ) - \phi (A_{j}+\varDelta ) \quad \forall j = 0, 1, \ldots . \end{aligned}$$

(11)

Suppose $z\in [A_{k}, A_{k+1}]$ for some k and let $\varDelta ' = z - A_{k} \in [0, a_{k+1}]$. By Lemma 2 we have

$$\begin{aligned} \phi (A_{k} + \varDelta ') - \phi (A_{k}) \ge \phi (z+\varDelta ) - \phi (z+\varDelta - \varDelta '). \end{aligned}$$

(12)

Note that $A_k+\varDelta ' = z$ and $z+\varDelta - \varDelta ' = A_k+ \varDelta$. Summing equations (11) over all $j=0, 1,\ldots , k-1$ and (12), yields the desired result.    $\square$

B Proof Sketch of Theorem 4

We first give the explicit formula to compute $\gamma (z, T)$.

Lemma 3

Suppose $T = \{\ell _1, \ldots , \ell _{|T|}\} \subseteq S$ such that $\ell _1< \cdots < \ell _{|T|}$. Denote $A_k = \sum _{j=1}^k a_j$ for $k\in S$ and $A_0 = 0$. Denote $A^T_t = a(T) - \sum _{j=1}^{t} a_{\ell _j}$ for $t=1,\ldots , |T|$, and $A^T_0 = a(T)$, $\ell _0 = 0$. There have three cases to consider: (i) if $0 \le z \le a(T)$, then $\gamma (z, T) = g(a(S) - a(T) +z) + \sum _{j\in T} \rho _j(S\setminus j) -f(S).$ (ii) if $A_{k} + A^T_{t} \le z \le A_{k+1}+A_{t}^T$ for $k = \ell _{t}, \ldots , \ell _{t+1} -2$ and $t = 0, 1, \ldots , |T|-1$, then $\gamma (z, T) = g(a(S) - A_{k+1} - A^T_{t} + z) + \sum _{j \in [k]\cup \{\ell _j\}_{j=t+1}^{|T|} } \rho _j(S\setminus j) - g(a(S)-a_{k+1}).$ (iii) if $z \ge A_{\ell _{|T|}}$, then $\gamma (z, T) = \gamma _0(z)$.

To establish the proof of Theorem 4, our basic idea is to exploit (8) in Proposition 3. To show (8), we first establish that inequalities similar in spirit to (8) hold for $\gamma (z, T)$ in Lemmas 4 and 5. Then we use the fact that $\gamma {\left( {\begin{array}{c}z\\ \mathbf {u}\end{array}}\right) }$ can be computed through (10) and $\gamma (z, T)$ to complete the proof of Theorem 4.

Lemma 4

For any $T\subseteq S$, we have $\sum _{j\in T} \gamma (z_j, \{j\}) \ge \gamma (z(T), T), \forall z_j \ge 0.$

Lemma 5

For any $i\in [r]$, we have $\gamma _0(z_0) + \gamma {\left( {\begin{array}{c}z_1\\ \mathbf {e}_i\end{array}}\right) } \ge \gamma {\left( {\begin{array}{c}z_0+z_1\\ \mathbf {e}_i\end{array}}\right) }, \forall z_0, z_1\ge 0.$

Proof (Theorem 4). Let $\varGamma \subseteq \bar{S}$ and $|\varGamma _i| \le d_i$, recall equation (10), we have

$$\begin{aligned}&\sum _{j\in \varGamma }\gamma {\left( {\begin{array}{c}z_j\\ \mathbf {e}_{\sigma (j)}\end{array}}\right) } = \sum _{j\in \varGamma } \max _{T^j} \{ \gamma (z_j, T^j): |T^j| = \max \{0, |S_i|+1-d_i\}, T^j \subseteq S_{\sigma (j)} \} \\&= \max _{\{T^j\}_{j\in \varGamma }} \{ \sum _{j\in \varGamma } \gamma (z_j, T^j): |T^j| = \max \{0, |S_{i}|+1-d_{i}\}, T^j \subseteq S_{\sigma (j)} \} \\&\ge \max _{T\subseteq S} \{ \gamma (z(\varGamma ), T): |T_i| = \max \{0, |S_i|+ |\varGamma _i| -d_i\} \} = \gamma {\left( {\begin{array}{c}z(\varGamma )\\ \sum _{j\in \varGamma } \mathbf {e}_{\sigma (j)} \end{array}}\right) }, \end{aligned}$$

where the inequality is based on Lemmas 4 and 5.    $\square$