Relaxations and Cutting Planes for Linear Programs with Complementarity Constraints

Alberto Del Pia [email protected] Wisconsin Institute for Discovery, University of Wisconsin-Madison Jeff Linderoth [email protected] Haoran Zhu Corresponding author, [email protected]

Abstract

We study relaxations for linear programs with complementarity constraints, especially instances whose complementary pairs of variables are not independent. Our formulation is based on identifying vertex covers of the conflict graph of the instance and generalizes the extended reformulation-linearization technique of Nguyen, Richard, and Tawarmalani to instances with general complementarity conditions between variables. We demonstrate how to obtain strong cutting planes for our formulation from both the stable set polytope and the boolean quadric polytope associated with a complete bipartite graph. Through an extensive computational study for three types of practical problems, we assess the performance of our proposed linear relaxation and new cutting-planes in terms of the optimality gap closed.

Key words: Complementarity constraints; Cutting-planes; Convex hull; Disjunctive programming; Boolean quadric polytope

1 Introduction

In this paper we study the linear programming problem with complementarity constraints (LPCC) of the following form:

\displaystyle\begin{split}\text{maximize}\quad&\boldsymbol{a}^{\mathsf{T}}\boldsymbol{x}+\boldsymbol{b}^{\mathsf{T}}\boldsymbol{y}\\ \text{subject to}\quad&A\textbf{{x}}+B\textbf{{y}}\leq\textbf{{d}},\\ &0\leq\textbf{{y}}\leq\textbf{1}_{n},\\ &y_{i}\cdot y_{j}=0\quad\forall\{i,j\}\in E.\end{split}

(LPCC)

Here $A\in{\mathbb{R}}^{m\times p},B\in{\mathbb{R}}^{m\times n},\textbf{{a}}\in{\mathbb{R}}^{p},\textbf{{b}}\in{\mathbb{R}}^{n},\textbf{{d}}\in{\mathbb{R}}^{m}$ for $m,n,p\in{\mathbb{N}}$ , and $\textbf{1}_{n}$ denotes the $n$ -dimensional vector with all components having value one. We assume that finite upper bounds on the variables y are given, so it is without loss of generality that we may scale their upper bounds to be $\textbf{1}_{n}$ . The set $E$ consists of unordered pairs of elements in $[n]:=\{1,\ldots,n\}$ , and we denote by $G=([n],E)$ the so-called conflict graph of (LPCC). Throughout the paper we assume that $G$ is simple, so it contains no loops or parallel edges. We denote by $P^{\perp}$ the feasible region of (LPCC), and by

P=\{(\textbf{{x}},\textbf{{y}})\in{\mathbb{R}}^{p+n}\mid A\textbf{{x}}+B\textbf{{y}}\leq\textbf{{d}},0\leq\textbf{{y}}\leq\textbf{1}_{n}\}

the linear programming (LP) relaxation of $P^{\perp}$ .

The conditions $y_{i}\cdot y_{j}=0,\{i,j\}\in E,$ known as complementarity constraints, are a special case of Special Ordered Sets of type 1 (SOS1) [7], which is a set of variables in which at most one may take a non-zero value. Practical problems involving complementarity constraints arise extensively in business, engineering, and economics, and we refer the reader to [16] for a detailed survey of applications. In many applications of LPCC, its associated conflict graph is 1-regular, i.e., every variable $y_{i},i\in[n]$ is contained in exactly one complementarity constraint. An important example of this case arises from imposing optimality conditions on decisions in a multi-level setting. In other applications, however, the conflict graph $G$ is more general. For example, consider scheduling a set of jobs $[n]$ , where each job $i\in[n]$ has processing times $a_{i}$ and benefit $c_{i}$ . The goal is to optimally select a subset $I\subseteq[n]$ of jobs to complete in a given time limit $b$ , where jobs may be partially executed, and certain pairs of jobs may not both be selected. This problem, known as the continuous knapsack problem with conflicts, can be formulated as an LPCC:

\max\big{\{}\textbf{{c}}^{\mathsf{T}}\textbf{{y}}\mid\textbf{{a}}^{\mathsf{T}}\textbf{{y}}\leq b,0\leq\textbf{{y}}\leq\textbf{1}_{n},\ y_{i}\cdot y_{j}=0\ \forall\{i,j\}\in E\big{\}}.

In this paper, we propose a new extended formulation for $\mathop{\rm conv}(P^{\perp})$ whose natural relaxation is strong, and we demonstrate additional cutting-planes to strengthen the relaxation. We call a set $\mathcal{R}$ an extended relaxation for a set $X$ in ${\mathbb{R}}^{n}$ if $\mathop{\rm dim}(\mathcal{R})>n$ and $X\subseteq\operatorname{proj}_{{\mathbb{R}}^{n}}\mathcal{R}$ . A recent paper by Nguyen et al. [27] is closely related to our research. The authors propose an extension of the well-known reformulation-linearization technique (RLT) of Sherali and Adams [32], coined ERLT, to the LPCC with a 1-regular conflict graph, and show that the resulting extended relaxation is stronger. As we will see in Section 2.2, when the conflict graph is 1-regular, our extended relaxation coincides with the relaxation given by the first-level ERLT. The paper [27] also describes the standard, iterative, multi-level process to strengthen ERLT. From a computational perspective, the first level ERLT relaxation is the most relevant, and throughout this paper, when we reference the ERLT relaxation, we mean the first-level ERLT.

For (LPCC) with a 1-regular conflict graph, many approaches have been given for strengthening the LP relaxation. Ibaraki [21] applies the work of Balas [4] to obtain a family of cutting-planes that can be derived from the simplex tableau of the linear programming relaxation of LPCC, and an improvement to these cuts is proposed by Sherali et al. [31] using disjunctive programming techniques. Jeroslow [24] gave a finite sequential procedure for generating all valid inequalities of the feasible set when every variable appears in some complementarity constraint. Moreover, Hu et al. [19, 20] studied the complementarity constraints arising from KKT conditions for linear programming problems with quadratic objective, and proposed a Benders type approach for solving the resulting LPCC. When the complementarity constraints are a collection of disjoint SOS1, the corresponding conflict graph is the union of a set of cliques. In this case, de Farias et al. [10, 11, 12] analyzed the polyhedral properties of the feasible sets that arise in this scenario and derived cutting-planes by a sequential lifting procedure of cover inequalities. Moreover, with the setting, Del Pia et al. [14] studied how to derive strong cutting-planes from another complementary concept of cover called “pack”. Most existing research for the case of a general conflict graphs focuses on integer programming [1, 2, 3, 18, 26, 30]. Recently, Fischer and Pfetsch [17] investigated a branch-and-cut algorithm to solve LPCC with a general conflict graph and demonstrated its effectiveness by an extensive computational study.

The structure of this paper is as follows: In Section 2, using concepts of vertex cover in graph theory and motivated by the disjunctive formulation, we present an extended relaxation for $\mathop{\rm conv}(P^{\perp})$ . We show that for the special case where the conflict graph $G$ is 1-regular, our extended relaxation coincides with the ERLT relaxation introduced by Nguyen et al. [27]. In particular, from the disjunctive perspective of our formulation and the idealness of Balas’ disjunctive formulation, we are able to derive Theorem 2 and Theorem 3 in [27]. In Section 3, we study a sub-structure that arises from our proposed extended formulation, and we show that all valid inequalities for a particular Boolean Quadric Polytope (BQP) [28] associated with a complete bipartite graph, can be added as cutting-planes to our extended relaxation proposed in the previous section. In Section 4, we conduct an extensive numerical study over a series of randomly generated problems and illustrate that when combined with the cutting-planes from Section 3, our extended relaxation is able to significantly close the optimality gap, compared to some other benchmark linear relaxations. We give concluding remarks in Section 5.

Notation. Throughout this paper, vectors are written in bold, e.g., $\textbf{{x}}=(x_{1},\ldots,x_{p})^{\mathsf{T}}$ , and matrices are written in capital letters. The notation $M_{i}$ is used to denote the $i$ -th row of a matrix $M\in{\mathbb{R}}^{m\times n}$ , for $i\in[m]$ . For a given vector $\textbf{{x}}\in{\mathbb{R}}^{n}$ and set $S\subseteq[n]$ , we use the common notation $\textbf{{x}}(S):=\sum_{i\in S}x_{i}$ . For a node $i\in[n]$ of the conflict graph $G$ , the notation $\delta(i)$ refers to the set of nodes in $G$ adjacent to $i$ , and for any $T\subseteq[n]$ , we define $\delta(T):=\cup_{i\in T}\delta(i)$ . The notation $\textbf{1}_{n}$ denotes the $n$ -dimensional vector with all components 1, and the orthogonal projection of a set $X$ onto the space of x-variables is given by $\operatorname{proj}_{\textbf{{x}}}X.$ The set of all subsets of a given set $S$ is denoted as $2^{S}$ .

2 A Vertex cover-based extended relaxation

In this section, we introduce a new extended relaxation for (LPCC) that generalizes the ERLT procedure [27] to the case of complementarity conditions forming an arbitrary conflict graph. The extension relies on the concept of vertex covers.

Definition 1.

A vertex cover of a graph $G=([n],E)$ is a subset $C$ of $[n]$ such that for every edge $\{i,j\}\in E$ , at least one among $i$ and $j$ is in $C$ . A minimum vertex cover is a vertex cover with the smallest size.

The following lemma follows directly from the definition of a vertex cover.

Lemma 1.

Let $\textbf{{y}}\in{\mathbb{R}}^{n}$ and let $C$ be a vertex cover of $G=([n],E)$ . Then y satisfies the complementarity constraints of (LPCC) if and only if for any $i\in C$ , either $y_{i}=0$ or $y_{j}=0$ for every $j\in\delta(i)$ .

Proof.

First, assume $y$ satisfies the complementarity constraints $y_{i}\cdot y_{j}=0$ for all $\{i,j\}\in E$ , and assume that $y_{i^{\prime}}\neq 0$ for some $i^{\prime}\in C$ . Then we must have $y_{j}=0$ for any $j\in\delta(i^{\prime})$ .

On the other hand, assume that for any $i\in C$ , either $y_{i}=0$ or $y_{j}=0$ for every $j\in\delta(i)$ . Take an arbitrary edge $\{i^{\prime},j^{\prime}\}\in E$ . Since $C$ is a vertex cover, either $i^{\prime}\in C$ or $j^{\prime}\in C$ . Suppose without loss of generality that $i^{\prime}\in C$ . Then by assumption we obtain that either $y_{i^{\prime}}=0$ or $y_{j}=0$ for every $j\in\delta(i^{\prime})$ . Since $j^{\prime}\in\delta(i^{\prime})$ , it follows that $y_{i^{\prime}}\cdot y_{j^{\prime}}=0$ . ∎

Our extended relaxation is based on the notion of a (feasible) cover partition.

Definition 2.

We say that $\mathcal{T}\subseteq 2^{[n]}$ is a cover partition of $G$ if $\cup_{T\in\mathcal{T}}T$ is a vertex cover of $G$ , and $T_{1}\cap T_{2}=\emptyset$ for any $T_{1},T_{2}\in\mathcal{T}$ . A cover partition $\mathcal{T}$ of $G$ is a feasible cover partition if for any $T\in\mathcal{T}$ and any $i\in T$ , we have $\delta(i)=\delta(T)$ .

For notational convenience, for any set $T\subseteq[n]$ , define the sets

	$\displaystyle H_{T}$	$\displaystyle:=\{(\textbf{{x}},\textbf{{y}})\in{\mathbb{R}}^{p+n}\mid y_{i}=0\ \forall i\in T\}\mbox{ and}$
	$\displaystyle\bar{H}_{T}$	$\displaystyle:=\{(\textbf{{x}},\textbf{{y}})\in{\mathbb{R}}^{p+n}\mid y_{j}=0\ \forall j\in\delta(T)\}.$

From Section 1, it follows that if $C$ is a vertex cover of the conflict graph $G$ of (LPCC), then $P^{\perp}=P\cap_{i\in C}(H_{\{i\}}\cup\bar{H}_{\{i\}})$ . If $\mathcal{T}$ is a feasible cover partition of $G$ , then because for any $T\in\mathcal{T}$ and $i,j\in T,\bar{H}_{i}=\bar{H}_{j}=\bar{H}_{T}$ , we have that $\cap_{i\in C}(H_{\{i\}}\cup\bar{H}_{\{i\}})=\cap_{T\in\mathcal{T}}(H_{T}\cup\bar{H}_{T})$ . Thus, we have the following chain of equalities:

P^{\perp}=P\cap_{i\in C}(H_{\{i\}}\cup\bar{H}_{\{i\}})=P\cap_{T\in\mathcal{T}}(H_{T}\cup\bar{H}_{T})=\bigcap_{T\in\mathcal{T}}\big{(}(P\cap H_{T})\cup(P\cap\bar{H}_{T})\big{)}.

(1)

Hence for a feasible cover partition $\mathcal{T}$ , one natural convex relaxation for $P^{\perp}$ is

\bigcap_{T\in\mathcal{T}}\mathop{\rm conv}\big{(}(P\cap H_{T})\cup(P\cap\bar{H}_{T})\big{)}.

In the remainder of the paper, we always assume that $\mathcal{T}$ is a feasible cover partition. We first notes that this relaxation is a polyhedron.

Observation 1.

For any $P\subseteq{\mathbb{R}}^{p}\times[0,1]^{n}$ and $T\subseteq[n],\mathop{\rm conv}\big{(}(P\cap H_{T})\cup(P\cap\bar{H}_{T})\big{)}$ is a polyhedron.

Proof.

Since $P\subseteq{\mathbb{R}}^{p}\times[0,1]^{n}$ and the hyperplanes defining $H_{T}$ and $\bar{H}_{T}$ only involve $y$ variables, the recession cone of the both polyhedra $P\cap H_{T}$ and $P\cap\bar{H}_{T}$ is $\{(\textbf{{x}},\boldsymbol{0})\mid A\textbf{{x}}\leq\boldsymbol{0}\}$ . It is well-known (see, e.g., [9]) that if the polyhedra share the same recession cone, the convex hull of the union of the polyhedra is polyhedral. ∎

A consequence of Section 1 is that (unlike in [27]), we need not assume $P^{\perp}$ is compact. From Section 1 and Balas’ classical results on disjunctive programming [6, 5], for each $T\subseteq[n]$ , $\mathop{\rm conv}\big{(}(P\cap H_{T})\cup(P\cap\bar{H}_{T})\big{)}$ has the following extended formulation:

	$\displaystyle A\boldsymbol{u_{T}}+B\boldsymbol{v_{T}}\leq\textbf{{d}}q_{T}$		(2)
	$\displaystyle A\boldsymbol{\bar{u}_{T}}+B\boldsymbol{\bar{v}_{T}}\leq\textbf{{d}}\bar{q}_{T}$		(3)
	$\displaystyle\bar{v}_{T,i}=0\ \forall i\in T,\ v_{T,j}=0\ \forall j\in\delta(T)$		(4)
	$\displaystyle 0\leq\boldsymbol{v_{T}}\leq q_{T}\cdot\textbf{1}_{n},\ 0\leq\boldsymbol{\bar{v}_{T}}\leq\bar{q}_{T}\cdot\textbf{1}_{n}$		(5)
	$\displaystyle\boldsymbol{\bar{u}_{T}}+\boldsymbol{u_{T}}=\textbf{{x}},\ \boldsymbol{\bar{v}_{T}}+\boldsymbol{v_{T}}=\textbf{{y}}$		(6)
	$\displaystyle\bar{q}_{T}+q_{T}=1,\ q_{T},\bar{q}_{T}\geq 0,$		(7)

where $\boldsymbol{u_{T}}\in{\mathbb{R}}^{p}$ , $\boldsymbol{\bar{u}_{T}}\in{\mathbb{R}}^{p}$ , $\boldsymbol{v_{T}}\in{\mathbb{R}}^{n}$ , $\boldsymbol{\bar{v}_{T}}\in{\mathbb{R}}^{n}$ are vectors of variables, and $q_{T}$ and $\bar{q}_{T}$ are scalar variables. For a given feasible cover partition $\mathcal{T}$ , by enumerating the extended formulations for each $T\in\mathcal{T}$ , we obtain a relaxation for $P^{\perp}$ in the extended space ${\mathbb{R}}^{p+n+2|\mathcal{T}|+2|\mathcal{T}|p+2|\mathcal{T}|n}$ . We call this extended relaxation the vertex-cover-based extended relaxation of $P^{\perp}$ :

\mathcal{E}_{\mathcal{T}}(P):=\big{\{}(\textbf{{x}},\textbf{{y}},\textbf{{q}},\bar{\textbf{{q}}},\textbf{{u}},\bar{\textbf{{u}}},\textbf{{v}},\bar{\textbf{{v}}})\in{\mathbb{R}}^{p+n+2|\mathcal{T}|+2|\mathcal{T}|p+2|\mathcal{T}|n}\mid\eqref{eq: balas 1}-\eqref{eq: balas 6}\ \forall T\in\mathcal{T}\big{\}}.

Here we should remark that $\mathcal{E}_{\mathcal{T}}(P)$ only depends on the linear constraints of the polyhedron $P$ and the feasible cover partition $\mathcal{T}$ . Due to the natural connection between $\mathcal{E}_{\mathcal{T}}(P)$ and the disjunctive formulation of $\mathop{\rm conv}\big{(}(P\cap H_{T})\cup(P\cap\bar{H}_{T})\big{)}$ with $T\in\mathcal{T}$ , we naturally have the following result.

Theorem 1.

Let $Q\subseteq{\mathbb{R}}^{p}\times[0,1]^{n}$ be a polyhedron such that $P^{\perp}\subseteq Q$ , and let $\mathcal{T}$ be a feasible cover partition of the conflict graph $G$ . Then for each $T\in\mathcal{T}$ ,

\mathop{\rm conv}(P^{\perp})\subseteq\operatorname{proj}_{\textbf{{x}},\textbf{{y}}}\mathcal{E}_{\mathcal{T}}(Q)\subseteq\mathop{\rm conv}\big{(}(Q\cap H_{T})\cup(Q\cap\bar{H}_{T})\big{)}.

Proof.

The set $\mathcal{E}_{\mathcal{T}}(Q)$ is constructed by enumerating Balas’ disjunctive formulation of $\mathop{\rm conv}\big{(}(Q\cap H_{T})\cup(Q\cap\bar{H}_{T})\big{)}$ for each $T\in\mathcal{T}$ , so the second subset relation holds trivially. To show the first subset relation, since $\operatorname{proj}_{\textbf{{x}},\textbf{{y}}}\mathcal{E}_{\mathcal{T}}(Q)$ is a convex set, we need only need to show $P^{\perp}\subseteq\operatorname{proj}_{\textbf{{x}},\textbf{{y}}}\mathcal{E}_{\mathcal{T}}(Q)$ , so we will show that for any $(\textbf{{x}},\textbf{{y}})\in P^{\perp}$ , there exists $(\textbf{{q}},\bar{\textbf{{q}}},\textbf{{u}},\bar{\textbf{{u}}},\textbf{{v}},\bar{\textbf{{v}}})\in{\mathbb{R}}^{2|\mathcal{T}|+2|\mathcal{T}|p+2|\mathcal{T}|n}$ such that $(\textbf{{x}},\textbf{{y}},\textbf{{q}},\bar{\textbf{{q}}},\textbf{{u}},\bar{\textbf{{u}}},\textbf{{v}},\bar{\textbf{{v}}})\in\mathcal{E}_{\mathcal{T}}(Q)$ . Given $(\textbf{{x}},\textbf{{y}})\in P^{\perp}$ , for each $T\in\mathcal{T}$ , let

q_{T}:=\begin{cases}0&\text{if }\textbf{{y}}(T)+\textbf{{y}}(\delta(T))=0\\ \frac{\textbf{{y}}(T)}{\textbf{{y}}(T)+\textbf{{y}}(\delta(T))}&\text{otherwise,}\end{cases}\qquad

$\bar{q}_{T}:=1-q_{T},\textbf{{u}}_{T}:=q_{T}\cdot\textbf{{x}},\bar{\textbf{{u}}}_{T}:=\bar{q}_{T}\cdot\textbf{{x}},\textbf{{v}}_{T}:=q_{T}\cdot\textbf{{y}},\bar{\textbf{{v}}}_{T}:=\bar{q}_{T}\cdot\textbf{{y}}$ . Since $(\textbf{{x}},\textbf{{y}})\in P^{\perp}\subseteq Q$ , by the definition of $(\textbf{{u}},\bar{\textbf{{u}}},\textbf{{v}},\bar{\textbf{{v}}})$ , the corresponding constraints (2) and (3) with respect to $Q$ are naturally satisfied. Now we check constraint (4). Since $\mathcal{T}$ is a feasible cover partition, for any $T\in\mathcal{T}$ and $i\in T$ , $\delta(i)=\delta(T)$ Also, since y satisfies the complementarity constraints, for any $i\in T$ , either $y_{i}=0$ or $\textbf{{y}}(\delta(i))=\textbf{{y}}(\delta(T))=0$ . Hence, either $\textbf{{y}}(T)=0$ or $\textbf{{y}}(\delta(T))=0$ . In the first case, $q_{T}$ is defined to be 0, and equations of (4) hold; In the second case, $q_{T}=\mathbbm{1}\{\textbf{{y}}(T)>0\}$ and (4) holds. It is easy to verify that the remaining constraints (5)-(7) are also satisfied by $(\textbf{{x}},\textbf{{y}},\textbf{{q}},\bar{\textbf{{q}}},\textbf{{u}},\bar{\textbf{{u}}},\textbf{{v}},\bar{\textbf{{v}}})$ for any $T\in\mathcal{T}$ . ∎

We define $\mathcal{R}_{\mathcal{T}}(P):=\operatorname{proj}_{\textbf{{x}},\textbf{{y}}}\mathcal{E}_{\mathcal{T}}(P)$ to be the linear relaxation of $P^{\perp}$ in the original space of variables. Furthermore, for any $t\in{\mathbb{N}}$ and $t\geq 2$ , we recursively define $\mathcal{R}_{\mathcal{T}}^{t}(P)=\mathcal{R}_{\mathcal{T}}(\mathcal{R}_{\mathcal{T}}^{t-1}(P))$ , where $\mathcal{R}_{\mathcal{T}}^{1}(P):=\mathcal{R}_{\mathcal{T}}(P)$ . We obtain the following theorem.

Theorem 2.

Let $\mathcal{T}$ be a feasible cover partition of $G$ . For any $k\in[|\mathcal{T}|]$ , and for any collection of $k$ distinct elements $T_{1},\ldots,T_{k}$ of $\mathcal{T}$ ,

\mathop{\rm conv}(P^{\perp})\subseteq\mathcal{R}_{\mathcal{T}}^{k}(P)\subseteq\mathop{\rm conv}\big{(}\bigcap_{j=1}^{k}(P\cap H_{T_{j}})\cup(P\cap\bar{H}_{T_{j}})\big{)}.

(8)

Proof.

The proof is by induction. When $k=1$ , this result reduces to Section 1 by picking $Q=P$ . Assume now that the result holds for $k\leq\kappa-1$ , where $\kappa\in[|\mathcal{T}|]$ and consider the case $k=\kappa$ . Let $Q=\mathcal{R}_{\mathcal{T}}^{\kappa-1}(P)$ , and $H=\cap_{j=1}^{\kappa-1}(H_{T_{j}}\cup\bar{H}_{T_{j}})$ . By the inductive hypothesis, we have:

\mathop{\rm conv}(P^{\perp})\subseteq Q\subseteq\mathop{\rm conv}\big{(}\bigcap_{j=1}^{\kappa-1}(P\cap H_{T_{j}})\cup(P\cap\bar{H}_{T_{j}})\big{)}=\mathop{\rm conv}(P\cap H).

(9)

Applying Section 1 for $Q$ and $T_{\kappa}\in\mathcal{T}$ , we have

\mathop{\rm conv}(P^{\perp})\subseteq\mathcal{R}_{\mathcal{T}}(Q)\subseteq\mathop{\rm conv}\big{(}(Q\cap H_{T_{\kappa}})\cup(Q\cap\bar{H}_{T_{\kappa}})\big{)}.

(10)

Combining (9) and (10), we obtain

	$\displaystyle\mathop{\rm conv}(P^{\perp})$	$\displaystyle\subseteq\mathcal{R}_{\mathcal{T}}^{\kappa}(P)=\mathcal{R}_{\mathcal{T}}(Q)$
		$\displaystyle\subseteq\mathop{\rm conv}\big{(}(\mathop{\rm conv}(P\cap H)\cap H_{T_{\kappa}})\cup(\mathop{\rm conv}(P\cap H)\cap\bar{H}_{T_{\kappa}})\big{)}.$

Notice that both $H_{T_{\kappa}}\cap\mathop{\rm conv}(P\cap H)$ and $\bar{H}_{T_{\kappa}}\cap\mathop{\rm conv}(P\cap H)$ are faces of the set $\cap\mathop{\rm conv}(P\cap H)$ , hence we have $\mathop{\rm conv}(P\cap H)\cap H_{T_{\kappa}}=\mathop{\rm conv}(P\cap H\cap H_{T_{\kappa}})$ and $\mathop{\rm conv}(P\cap H)\cap\bar{H}_{T_{\kappa}}=\mathop{\rm conv}(P\cap H\cap\bar{H}_{T_{\kappa}})$ . Therefore:

	$\displaystyle\mathop{\rm conv}(P^{\perp})\subseteq\mathcal{R}_{\mathcal{T}}^{\kappa}(P)$	$\displaystyle\subseteq\mathop{\rm conv}\big{(}\mathop{\rm conv}(P\cap H\cap H_{T_{\kappa}})\cup\mathop{\rm conv}(P\cap H\cap\bar{H}_{T_{\kappa}})\big{)}$
		$\displaystyle=\mathop{\rm conv}\big{(}(P\cap H\cap H_{T_{\kappa}})\cup(P\cap H\cap\bar{H}_{T_{\kappa}})\big{)}$
		$\displaystyle=\mathop{\rm conv}\big{(}\bigcap_{j=1}^{\kappa}(P\cap H_{T_{j}})\cup(P\cap\bar{H}_{T_{j}})\big{)}.$

Hence (8) also holds for $k=\kappa$ , and the proof is complete. ∎

Note that Section 2 implies that $\mathcal{R}_{\mathcal{T}}^{|\mathcal{T}|}(P)=\mathop{\rm conv}(P^{\perp})$ for any feasible cover partition $\mathcal{T}$ of $G$ , which naturally leads to the following definition.

Definition 3.

Let $\mathcal{T}$ be a feasible cover partition for the conflict graph $G$ of (LPCC) whose feasible region is $P^{\perp}$ . The cover-partition rank of $\mathcal{T}$ for $P^{\perp}$ , denoted $r_{\mathcal{T}}(P^{\perp})$ , is the least number $r$ such that $\mathcal{R}_{\mathcal{T}}^{r}(P)=\mathop{\rm conv}(P^{\perp})$ .

An immediate corollary of Section 2 is that the cover-partition rank is upper bounded by the cardinality of the feasible cover partition for any polyhedron $P$ .

Corollary 1.

$r_{\mathcal{T}}(P)\leq|\mathcal{T}|$ .

2.1 Edge-based extended relaxation

From a similar disjunctive perspective as that which motivated the chain of equations (1), a natural relaxation of $\mathop{\rm conv}(P^{\perp})$ contain be obtained using the following relations:

\mathop{\rm conv}(P^{\perp})=\mathop{\rm conv}\big{(}\bigcap_{\{i,j\}\in E}(P\cap H_{i})\cup(P\cap H_{j})\big{)}\subseteq\bigcap_{\{i,j\}\in E}\mathop{\rm conv}\big{(}(P\cap H_{i})\cup(P\cap H_{j})\big{)}.

Therefore, using disjunctive programming, the following linear system provides another extended relaxation of $P^{\perp}$ :

\begin{split}A\boldsymbol{u_{e}}+B\boldsymbol{v_{e}}\leq\textbf{{d}}q_{e},&\quad\forall e\in E\\ A\boldsymbol{\bar{u}_{e}}+B\boldsymbol{\bar{v}_{e}}\leq\textbf{{d}}\bar{q}_{e},&\quad\forall e\in E\\ \bar{v}_{e,i}=0,\ v_{e,j}=0,&\quad\forall e=\{i,j\}\in E\\ 0\leq\boldsymbol{v_{e}}\leq q_{e}\cdot\textbf{1}_{n},\ 0\leq\boldsymbol{\bar{v}_{e}}\leq\bar{q}_{e}\cdot\textbf{1}_{n},&\quad\forall e\in E\\ \boldsymbol{\bar{u}_{e}}+\boldsymbol{u_{e}}=\textbf{{x}},\ \boldsymbol{\bar{v}_{e}}+\boldsymbol{v_{e}}=\textbf{{y}},&\quad\forall e\in E\\ \bar{q}_{e}+q_{e}=1,\ q_{e},\bar{q}_{e}\geq 0,&\quad\forall e\in E.\end{split}

(11)

Let $\mathcal{M}$ denote the set in ${\mathbb{R}}^{p+n+2|E|+2|E|p+2|E|n}$ given by the linear system (11). It can be shown that $\mathcal{M}$ is never a stronger relaxation than the relaxation provided by $\mathcal{E}_{\mathcal{T}}(P)$ with respect to some feasible cover partition $\mathcal{T}$ .

Proposition 1.

Let $\mathcal{T}^{*}=\{\{i\}\mid\{i,j\}\in E\}$ . Then $\mathcal{R}_{\mathcal{T}^{*}}(P)\subseteq\operatorname{proj}_{\textbf{{x}},\textbf{{y}}}\mathcal{M}$ .

Proof.

Arbitrarily pick $(\boldsymbol{x^{*}},\boldsymbol{y^{*}})\in\mathcal{R}_{\mathcal{T}^{*}}(P)=\operatorname{proj}_{\textbf{{x}},\textbf{{y}}}\mathcal{E}_{\mathcal{T}^{*}}(P)$ . There exist variables $(\boldsymbol{q^{*}},\boldsymbol{\bar{q}^{*}},\boldsymbol{u^{*}},\boldsymbol{\bar{u}^{*}},\boldsymbol{v^{*}},\boldsymbol{\bar{v}^{*}})$ such that $(\boldsymbol{x^{*}},\boldsymbol{y^{*}},\boldsymbol{q^{*}},\boldsymbol{\bar{q}^{*}},\boldsymbol{u^{*}},\boldsymbol{\bar{u}^{*}},\boldsymbol{v^{*}},\boldsymbol{\bar{v}^{*}})$ satisfies the following constraints:

\begin{split}A\boldsymbol{u^{*}_{T}}+B\boldsymbol{v^{*}_{T}}\leq\textbf{{d}}q^{*}_{T},&\quad\forall T\in\mathcal{T}^{*}\\ A\boldsymbol{\bar{u}^{*}_{T}}+B\boldsymbol{\bar{v}^{*}_{T}}\leq\textbf{{d}}\bar{q}^{*}_{T},&\quad\forall T\in\mathcal{T}^{*}\\ \bar{v}^{*}_{T,i}=0,\ v^{*}_{T,j}=0\ \forall j\in\delta(i),&\quad\forall T=\{i\}\in\mathcal{T}^{*}\\ 0\leq\boldsymbol{v^{*}_{T}}\leq q^{*}_{T}\cdot\textbf{1}_{n},\ 0\leq\boldsymbol{\bar{v}^{*}_{T}}\leq\bar{q}^{*}_{T}\cdot\textbf{1}_{n},&\quad\forall T\in\mathcal{T}^{*}\\ \boldsymbol{\bar{u}^{*}_{T}}+\boldsymbol{u^{*}_{T}}=\textbf{{x}}^{*},\ \boldsymbol{\bar{v}^{*}_{T}}+\boldsymbol{v^{*}_{T}}=\textbf{{y}}^{*},&\quad\forall T\in\mathcal{T}^{*}\\ \bar{q}^{*}_{T}+q^{*}_{T}=1,\ q^{*}_{T},\bar{q}^{*}_{T}\geq 0,&\quad\forall T\in\mathcal{T}^{*}.\end{split}

(12)

Now, for any $e=\{i,j\}\in E$ , we construct:

q^{\circ}_{e}:=q^{*}_{\{i\}},\ \bar{q}^{\circ}_{e}:=\bar{q}^{*}_{\{i\}},\ \boldsymbol{u^{\circ}_{e}}:=\boldsymbol{u^{*}_{\{i\}}},\ \boldsymbol{\bar{u}^{\circ}_{e}}:=\boldsymbol{\bar{u}^{*}_{\{i\}}},\ \boldsymbol{v^{\circ}_{e}}:=\boldsymbol{v^{*}_{\{i\}}},\ \boldsymbol{\bar{v}^{\circ}_{e}}:=\boldsymbol{\bar{v}^{*}_{\{i\}}}.

Given (12) is simple to check that $(\boldsymbol{x^{*}},\boldsymbol{y^{*}},\boldsymbol{q^{\circ}},\boldsymbol{\bar{q}^{\circ}},\boldsymbol{u^{\circ}},\boldsymbol{\bar{u}^{\circ}},\boldsymbol{v^{\circ}},\boldsymbol{\bar{v}^{\circ}})$ satisfies all the constraints (11). Thus $(\boldsymbol{x^{*}},\boldsymbol{y^{*}})\in\operatorname{proj}_{\textbf{{x}},\textbf{{y}}}\mathcal{M}$ . ∎

Later in Section 4, we will show empirically that $\mathcal{E}_{\mathcal{T}}(P)$ can provide a significantly stronger relaxation than $\mathcal{M}$ . The strength of the relaxation depends on the choice of $\mathcal{T}$ , so an important question is how to select the cover partition. Intuition given by Section 1 suggests that we should choose a feasible cover partition of small cardinality, as the cardinality upper bounds the cover-partition rank. In this case, the simple choice of feasible cover partition $\{\{i\}\mid\{i,j\}\in E\}$ of Proposition 1 is not likely to lead to the strongest relaxation. Moreover, a feasible cover partition $\mathcal{T}$ with cardinality $t$ produces a linear relaxation $\mathcal{E}_{\mathcal{T}}(P)$ with $O(mt+nt+pt)$ linear constraints and $(2+2p+2n)t$ additional variables, so a smaller feasible cover partition will also be more favorable from a computational perspective. In the numerical experiments that we present later in Section 4, we will use the feasible cover partition given by some approximate minimum vertex cover, which can be easily accessed using the Python package NetworkX.

2.2 Equivalence of vertex cover-based extended relaxation and ERLT for 1-regular conflict graph

In this section, we demonstrate that if the conflict graph of complementarity condition $G$ is 1-regular, then the vertex-cover-based extended relaxation $\mathcal{E}_{\mathcal{T}}(P)$ is the same as the relaxation from the Extended Reformulation Linearization Technique (ERLT) proposed by Nguyen et al. [27].

We begin by briefly reviewing the ERLT procedure. Let $Q=\{(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z})\in{\mathbb{R}}^{p+2n}\mid\bar{A}\boldsymbol{x}+\bar{B}\boldsymbol{y}+\bar{C}\boldsymbol{z}\leq\boldsymbol{\bar{d}}\}$ be a given polytope in ${\mathbb{R}}^{n}_{+}$ , where the complementarity constraints are $y_{j}\cdot z_{j}=0$ for any $j\in[n]$ . Given a matrix $F\in{\mathbb{R}}^{m\times n}$ and a subset $K\subseteq[n]$ , we denote by $F^{K}$ the sub-matrix obtained by removing from $F$ all columns with indices not in $K$ , and denote by $F^{-K}$ the sub-matrix obtained by removing from $F$ all columns with indices in $K$ . Using this notation, then applying the ERLT to $Q$ gives the linear description

\begin{split}&\bar{A}\boldsymbol{u_{j}}+\bar{B}^{-\{j\}}\boldsymbol{v_{j}}+\bar{C}^{-\{j\}}\boldsymbol{w_{j}}+\bar{B}^{\{j\}}y_{j}\leq\bar{\textbf{{d}}}q_{j},\ \forall j\in N,\\ &\bar{A}(\boldsymbol{x}-\boldsymbol{u_{j}})+\bar{B}^{-\{j\}}(\boldsymbol{y^{-\{j\}}}-\boldsymbol{v_{j}})+\bar{C}^{-\{j\}}(\boldsymbol{z^{-\{j\}}}-\boldsymbol{w_{j}})+\bar{C}^{\{j\}}z_{j}\leq\bar{\textbf{{d}}}(1-q_{j}),\ \forall j\in N,\end{split}

(13)

in the variables $\boldsymbol{u_{j}}\in{\mathbb{R}}^{p},\boldsymbol{v_{j}}\in{\mathbb{R}}^{n-1},\boldsymbol{w_{j}}\in{\mathbb{R}}^{n-1}$ , and $q_{j}\in{\mathbb{R}}$ for $j\in[n]$ . The primary difference between the original Reformulation Linearization Technique (RLT) for binary mixed integer programs [32] and ERLT is that in RLT we multiply the linear constraints of the problem with binary variables (and their complements) from the existing problem, while in ERLT, auxiliary variables are created, and the original linear constraints are multiplied with these auxiliary variables. After multiplication, the reformulation and linearization steps are the same in RLT and ERLT.

Next, consider the vertex-cover-based relaxation for (LPCC) with a 1-regular conflict graph $G$ . When $G$ is 1-regular, the number of nodes of $G$ is even, and we assume without loss of generality that $G=([2n],E)$ , where $E=\{\{i,i+n\}\mid i\in[n]\}$ . Throughout this section, we define

P^{\perp}_{1r}:=\{(\textbf{{x}},\textbf{{y}})\in{\mathbb{R}}^{p+2n}\mid A\boldsymbol{x}+D\boldsymbol{y}\leq\boldsymbol{d},\ 0\leq\boldsymbol{y}\leq\textbf{1}_{2n},\ y_{i}\cdot y_{n+i}=0\ \forall i\in[n]\}.

Any minimum vertex cover $C$ of $G$ has the property that $|C\cap\{i,n+i\}|=1$ for any $i\in[n]$ , and by symmetry of variables $y_{i}$ and $y_{n+i}$ we may assume without loss of generality that the feasible cover partition is $\mathcal{T}=\{\{1\},\ldots,\{n\}\}$ . Applying the vertex-cover-based extended relaxation procedure and renaming variables, we obtain the following extended relaxation for $P^{\perp}_{1r}$ :

	$\displaystyle A\boldsymbol{u_{i}}+D\boldsymbol{\nu_{i}}\leq\boldsymbol{d}q_{i},\quad\forall i\in[n]$
	$\displaystyle A\boldsymbol{\bar{u}_{i}}+D\boldsymbol{\bar{\nu}_{i}}\leq\boldsymbol{d}\bar{q}_{i},\quad\forall i\in[n]$
	$\displaystyle\bar{\nu}_{i,i}=0,\ \nu_{i,i+n}=0,\quad\forall i\in[n]$
	$\displaystyle 0\leq\boldsymbol{\nu_{i}}\leq q_{i}\cdot\textbf{1}_{2n},\ 0\leq\boldsymbol{\bar{\nu}_{i}}\leq\bar{q}_{i}\cdot\textbf{1}_{2n},\quad\forall i\in[n]$
	$\displaystyle\boldsymbol{\bar{u}_{i}}+\boldsymbol{u_{i}}=\boldsymbol{x},\ \boldsymbol{\bar{\nu}_{i}}+\boldsymbol{\nu_{i}}=\boldsymbol{y},\quad\forall i\in[n]$
	$\displaystyle\bar{q}_{i}+q_{i}=1,\ q_{i},\bar{q}_{i}\geq 0,\quad\forall i\in[n].$

Here $\boldsymbol{u_{i}},\boldsymbol{\bar{u}_{i}}\in{\mathbb{R}}^{n},\boldsymbol{\nu_{i}},\boldsymbol{\bar{\nu}_{i}}\in{\mathbb{R}}^{2n}$ for each $i\in[n]$ . Now we denote $z_{i}:=y_{i+n},v_{i,j}:=\nu_{i,j},\bar{v}_{i,j}:=\bar{\nu}_{i,j},w_{i,j}:=\nu_{i,j+n}$ , and $\bar{w}_{i,j}:=\bar{\nu}_{i,j+n}$ for any $i,j\in[n]$ , and let matrix $D:=(B\mid C)$ , where $B$ denotes the sub-matrix of $D$ given by the first $n$ columns, and $C$ denotes the sub-matrix of $G$ given by the remaining $n$ columns. Then we have

	$\displaystyle A\boldsymbol{u_{i}}+B\boldsymbol{v_{i}}+C\boldsymbol{w_{i}}\leq\boldsymbol{d}q_{i},\quad\forall i\in[n]$		(14)
	$\displaystyle A\boldsymbol{\bar{u}_{i}}+B\boldsymbol{\bar{v}_{i}}+C\boldsymbol{\bar{w}_{i}}\leq\boldsymbol{d}\bar{q}_{i},\quad\forall i\in[n]$		(15)
	$\displaystyle\bar{v}_{i,i}=0,\ w_{i,i}=0,\quad\forall i\in[n]$		(16)
	$\displaystyle 0\leq\boldsymbol{v_{i}},\boldsymbol{w_{i}}\leq q_{i}\cdot\textbf{1}_{n},\ 0\leq\boldsymbol{\bar{v}_{i}},\boldsymbol{\bar{w}_{i}}\leq\bar{q}_{i}\cdot\textbf{1}_{n},\quad\forall i\in[n]$		(17)
	$\displaystyle\boldsymbol{\bar{u}_{i}}+\boldsymbol{u_{i}}=\boldsymbol{x},\ \boldsymbol{\bar{v}_{i}}+\boldsymbol{v_{i}}=\boldsymbol{y_{[n]}},\ \boldsymbol{\bar{w}_{i}}+\boldsymbol{w_{i}}=\boldsymbol{z},\quad\forall i\in[n]$		(18)
	$\displaystyle\bar{q}_{i}+q_{i}=1,\ q_{i},\bar{q}_{i}\geq 0,\quad\forall i\in[n].$		(19)

Here $\boldsymbol{y_{[n]}}=(y_{1},\ldots,y_{n})^{\mathsf{T}}$ , and $\boldsymbol{v_{i}},\boldsymbol{\bar{v}_{i}},\boldsymbol{w_{i}},\boldsymbol{\bar{w}_{i}}\in[0,1]^{n}$ for each $i\in[n]$ . Lastly, for any $i\in[n]$ , by eliminating variables $\bar{v}_{i,i},w_{i,i},\boldsymbol{\bar{u}_{i}},\boldsymbol{\bar{v}_{i}},\boldsymbol{\bar{w}_{i}}$ and $\bar{q}_{i}$ using equations (16), (18) and (19), the above linear system will coincide exactly with the ERLT relaxation (13), demonstrating their equivalence.

By this observation, the ERLT proposed in [27] can be seen as a special case of our vertex-cover-based extended relaxation. More specifically, by the construction of $\mathcal{E}_{\mathcal{T}}(P)$ , we provide a disjunctive perspective for the ERLT procedure. Once consequence of this different perspective is that Theorem 2 in [27] can be deduced from the fact that the disjunctive formulation provides an extended formulation for the convex hull of multiple polyhedra with identical recession cones.

3 Cutting-planes in extended space

In this section, we study how to strengthen the extended relaxation $\mathcal{E}_{\mathcal{T}}(P)$ through cutting planes. First, we strengthen the relaxation by imposing additional valid bilinear equations:

	$\displaystyle\boldsymbol{u_{T}}=q_{T}\cdot\boldsymbol{x},\quad\boldsymbol{\bar{u}_{T}}=\bar{q}_{T}\cdot\boldsymbol{x}$	$\displaystyle\quad\forall T\in\mathcal{T}$		(20)
	$\displaystyle\boldsymbol{v_{T}}=q_{T}\cdot\boldsymbol{y},\quad\boldsymbol{\bar{v}_{T}}=\bar{q}_{T}\cdot\boldsymbol{y}$	$\displaystyle\quad\forall T\in\mathcal{T},$		(21)

and we define the set

\tilde{\mathcal{E}}_{\mathcal{T}}(P):=\big{\{}(\boldsymbol{x},\boldsymbol{y},\boldsymbol{q},\boldsymbol{\bar{q}},\boldsymbol{u},\boldsymbol{\bar{u}},\boldsymbol{v},\boldsymbol{\bar{v}})\mid\eqref{eq: balas 1}-\eqref{eq: balas 6},\eqref{eq: bilinear1},\eqref{eq: bilinear2}\ \forall T\in\mathcal{T}\big{\}}.

(22)

We first show that these bilinear equations are indeed valid by demonstrating that $\tilde{\mathcal{E}}_{\mathcal{T}}(P)$ is an extended formulation for $P^{\perp}$ .

Proposition 2.

$\operatorname{proj}_{\textbf{{x}},\textbf{{y}}}\tilde{\mathcal{E}}_{\mathcal{T}}(P)=P^{\perp}.$

Proof.

First, we show $\operatorname{proj}_{\textbf{{x}},\textbf{{y}}}\tilde{\mathcal{E}}_{\mathcal{T}}(P)\subseteq P^{\perp}.$ Pick $(\boldsymbol{x^{*}},\boldsymbol{y^{*}},\boldsymbol{q^{*}},\boldsymbol{\bar{q}^{*}},\boldsymbol{u^{*}},\boldsymbol{\bar{u}^{*}},\boldsymbol{v^{*}},\boldsymbol{\bar{v}^{*}})\in\tilde{\mathcal{E}}_{\mathcal{T}}(P)$ . From constraints (2), (3), (5), (6), (7), we know $(\boldsymbol{x^{*}},\boldsymbol{y^{*}})\in P$ . Moreover, for each $T\in\mathcal{T}$ , from (4), (20), (21), we have $q^{*}_{T}\cdot y^{*}_{j}=0$ for any $j\in\delta(T)$ , and $\bar{q}^{*}_{T}\cdot y^{*}_{i}=0$ for any $i\in T$ . Since $\bar{q}^{*}_{T}+q^{*}_{T}=1$ by (7), we have either $\bar{q}^{*}_{T}>0$ or $q^{*}_{T}>0$ . These yield that either $\boldsymbol{y^{*}}(\delta(T))=0$ or $\boldsymbol{y^{*}}(T)=0$ , which means $(\boldsymbol{x^{*}},\boldsymbol{y^{*}})\in P^{\perp}$ because of (1).

Now we arbitrarily pick $(\boldsymbol{x^{\prime}},\boldsymbol{y^{\prime}})\in P^{\perp}$ . For each $T\in\mathcal{T}$ , we define $q^{\prime}_{T}=\mathbbm{1}\{\boldsymbol{y^{\prime}}(T)>0\}$ , $\bar{q}^{\prime}_{T}=1-q^{\prime}_{T}$ , and $\boldsymbol{u^{\prime}},\boldsymbol{\bar{u}^{\prime}},\boldsymbol{v^{\prime}},\boldsymbol{\bar{v}^{\prime}}$ are defined by (20) and (21), respectively. In order to show that $(\boldsymbol{x^{\prime}},\boldsymbol{y^{\prime}},\boldsymbol{q^{\prime}},\boldsymbol{\bar{q}^{\prime}},\boldsymbol{u^{\prime}},\boldsymbol{\bar{u}^{\prime}},\boldsymbol{v^{\prime}},\boldsymbol{\bar{v}^{\prime}})\in\tilde{\mathcal{E}}_{\mathcal{T}}(P)$ , it suffices to show that (4) holds for each $T\in\mathcal{T}$ , since all the remaining constraints are naturally satisfied from the construction of $\boldsymbol{u^{\prime}},\boldsymbol{\bar{u}^{\prime}},\boldsymbol{v^{\prime}},\boldsymbol{\bar{v}^{\prime}}$ . For each $T\in\mathcal{T}$ and $i\in T$ ,

\bar{v}^{\prime}_{T,i}=\bar{q}^{\prime}_{T}\cdot y^{\prime}_{i}=(1-\mathbbm{1}\{\boldsymbol{y^{\prime}}(T)>0\})\cdot y^{\prime}_{i}=\mathbbm{1}\{\boldsymbol{y^{\prime}}(T)=0\}\cdot y^{\prime}_{i}=0.

Next we verify that $v^{\prime}_{T,j}=0$ for any $j\in\delta(T)$ . Since $\boldsymbol{y^{\prime}}$ satisfies the complementarity constraints of $P^{\perp}$ , by (1) we know that either $\boldsymbol{y^{\prime}}(T)=0$ or $\boldsymbol{y^{\prime}}(\delta(T))=0$ . If $\boldsymbol{y^{\prime}}(T)=0$ , then $q^{\prime}_{T}=\mathbbm{1}\{\boldsymbol{y^{\prime}}(T)>0\}=0$ , which implies $v^{\prime}_{T,j}=q^{\prime}_{T}\cdot y^{\prime}_{j}=0$ for any $j\in\delta(T)$ ; If $\boldsymbol{y^{\prime}}(\delta(T))=0$ , then $y^{\prime}_{j}=0$ for any $j\in\delta(T)$ , so we have $v^{\prime}_{T,j}=q^{\prime}_{T}\cdot y^{\prime}_{j}=0$ for any $j\in\delta(T)$ . Hence we have shown that $P^{\perp}\subseteq\operatorname{proj}_{\textbf{{x}},\textbf{{y}}}\tilde{\mathcal{E}}_{\mathcal{T}}(P)$ , which completes the proof. ∎

From the disjunctive interpretation of the auxiliary variables in defining $\mathcal{E}_{\mathcal{T}}(P)$ and $\tilde{\mathcal{E}}_{\mathcal{T}}(P)$ , we can further obtain the following proposition. Here for graph $G$ , a clique of $G$ is defined to be a subset of nodes such that every two distinct nodes in the clique are adjacent.

Proposition 3.

Let $\mathcal{T}$ be a feasible cover partition of the conflict graph $G$ , and let $C$ be a clique of $G$ . If $T_{1},\ldots,T_{k}$ are different node sets in $\mathcal{T}$ such that $T_{i}\cap C\neq\emptyset$ for any $i\in[k]$ , then:

\operatorname{proj}_{\textbf{{x}},\textbf{{y}}}\left\{(\boldsymbol{x},\boldsymbol{y},\boldsymbol{q},\boldsymbol{\bar{q}},\boldsymbol{u},\boldsymbol{\bar{u}},\boldsymbol{v},\boldsymbol{\bar{v}})\in\tilde{\mathcal{E}}_{\mathcal{T}}(P)\mid\sum_{i=1}^{k}q_{T_{i}}\leq 1,\sum_{i=1}^{k}\boldsymbol{v_{T_{i}}}\leq\boldsymbol{y}\right\}=P^{\perp}.

Proof.

From Section 2, we only need to show the projection onto $(\textbf{{x}},\textbf{{y}})$ -space of the set defined in the statement of this proposition contains $P^{\perp}$ .

Arbitrarily pick $(\boldsymbol{x^{\prime}},\boldsymbol{y^{\prime}})\in P^{\perp}$ . For each $T\in\mathcal{T}$ , we define $q^{\prime}_{T}=\mathbbm{1}\{\boldsymbol{y^{\prime}}(T)>0\}$ , $\bar{q}^{\prime}_{T}=1-q^{\prime}_{T}$ , and $\boldsymbol{u^{\prime}},\boldsymbol{\bar{u}^{\prime}},\boldsymbol{v^{\prime}},\boldsymbol{\bar{v}^{\prime}}$ are defined by (20) and (21), respectively. It is obvious that $(\boldsymbol{x^{\prime}},\boldsymbol{y^{\prime}},\boldsymbol{q^{\prime}},\boldsymbol{\bar{q}^{\prime}},\boldsymbol{u^{\prime}},\boldsymbol{\bar{u}^{\prime}},\boldsymbol{v^{\prime}},\boldsymbol{\bar{v}^{\prime}})\in\tilde{\mathcal{E}}_{\mathcal{T}}(P)$ . Let $C$ and $T_{1},\ldots,T_{k}\in\mathcal{T}$ be the node sets defined in the statement of this proposition.

First of all, we show that $\sum_{i=1}^{k}q^{\prime}_{T_{i}}\leq 1$ . If $\sum_{i=1}^{k}q^{\prime}_{T_{i}}>1$ , from the definition of $q^{\prime}_{T}=\mathbbm{1}\{\boldsymbol{y^{\prime}}(T)>0\}$ , we know there are $i_{1}\neq i_{2}\in[k]$ such that $\boldsymbol{y^{\prime}}(T_{i_{1}})>0,\boldsymbol{y^{\prime}}(T_{i_{2}})>0$ . Say $y^{\prime}_{j_{1}}>0,y^{\prime}_{j_{2}}>0$ for $j_{1}\in T_{i_{1}},j_{2}\in T_{i_{2}}$ . Since $T_{i_{1}}\cap C\neq\emptyset,T_{i_{2}}\cap C\neq\emptyset$ , and $C$ is a clique, we know there exists $j_{3}\in T_{i_{1}}$ and $j_{4}\in T_{i_{2}}$ , such that $(j_{3},j_{4})$ is an edge in $G$ . Hence $j_{3}\in\delta(j_{4}),j_{4}\in\delta(j_{3})$ . By definition of feasible cover partition, $\delta(T_{i_{1}})=\delta(j_{1})=\delta(j_{3}),\delta(T_{i_{2}})=\delta(j_{2})=\delta(j_{4})$ . Therefore, $j_{3}\in\delta(j_{2})$ , so $j_{2}\in\delta(j_{3})=\delta(j_{1})$ , which means $(j_{1},j_{2})$ is also an edge of $G$ . However, $y^{\prime}_{j_{1}}>0$ , $y^{\prime}_{j_{2}}>0$ , thus we get the contradiction using the complementarity constraints.

Lastly, $\sum_{i=1}^{k}\boldsymbol{v^{\prime}_{T_{i}}}\leq\boldsymbol{y^{\prime}}$ follows immediately from (21) in the definition of $\tilde{\mathcal{E}}_{\mathcal{T}}(P)$ . ∎

In particular, Section 3 implies that all inequalities in Section 3 can be added to the formulation of $\mathcal{E}_{\mathcal{T}}(P)$ to obtain a stronger extended relaxation.

Even though Section 2 shows that $\tilde{\mathcal{E}}_{\mathcal{T}}(P)$ is a formulation of $P^{\perp}$ in an extended space, in general $\mathop{\rm conv}(\tilde{\mathcal{E}}_{\mathcal{T}}(P))$ is not expected to be polyhedral. In order to obtain a polyhedral relaxation of $\mathop{\rm conv}(\tilde{\mathcal{E}}_{\mathcal{T}}(P))$ which is stronger than the previous extended relaxation $\mathcal{E}_{\mathcal{T}}(P)$ , we define $\mathcal{S}_{\mathcal{T}}$ as the set of points $(\boldsymbol{y},\boldsymbol{q},\boldsymbol{\bar{q}},\boldsymbol{v},\boldsymbol{\bar{v}})$ in ${\mathbb{R}}^{n+2|\mathcal{T}|+2|\mathcal{T}|n}$ that satisfy the constraints defining $\tilde{\mathcal{E}}_{\mathcal{T}}(P)$ in (22) which do not involve variables $x,u$ and $\bar{u}$ . Namely

\mathcal{S}_{\mathcal{T}}:=\big{\{}(\boldsymbol{y},\boldsymbol{q},\boldsymbol{\bar{q}},\boldsymbol{v},\boldsymbol{\bar{v}})\mid\eqref{eq: balas 3},\eqref{eq: balas 4},\eqref{eq: balas 6},\eqref{eq: bilinear2}\ \forall T\in\mathcal{T}\big{\}}.

(23)

Here we ignore the equation $\boldsymbol{\bar{v}_{T}}+\boldsymbol{v_{T}}=\boldsymbol{y}$ in (6) since it is induced by (21) and $q_{T}+\bar{q}_{T}=1$ . Note that:

\begin{split}\mathop{\rm conv}(\tilde{\mathcal{E}}_{\mathcal{T}}(P))\subseteq\big{\{}(\boldsymbol{x},\boldsymbol{y},\boldsymbol{q},\boldsymbol{\bar{q}},\boldsymbol{u},\boldsymbol{\bar{u}},\boldsymbol{v},\boldsymbol{\bar{v}})\mid\ &\boldsymbol{x}=\boldsymbol{u_{T}}+\boldsymbol{\bar{u}_{T}},\eqref{eq: balas 1},\eqref{eq: balas 2},\\ &(\boldsymbol{y},\boldsymbol{q},\boldsymbol{\bar{q}},\boldsymbol{v},\boldsymbol{\bar{v}})\in\mathop{\rm conv}(\mathcal{S}_{\mathcal{T}})\ \forall T\in\mathcal{T}\big{\}}.\end{split}

(24)

Obviously, the relaxation of $\mathop{\rm conv}(\tilde{\mathcal{E}}_{\mathcal{T}}(P))$ in (24) is tighter than $\mathcal{E}_{\mathcal{T}}(P)$ . In the next result we show that it is indeed a polyhedral relaxation.

Proposition 4.

The extreme points of $\mathcal{S}_{\mathcal{T}}$ are contained in $\{0,1\}^{n+2|\mathcal{T}|+2|\mathcal{T}|n}$ . Hence the set $\mathop{\rm conv}(\mathcal{S}_{\mathcal{T}})$ is polyhedral.

Proof.

Let $\boldsymbol{p^{*}}=(\boldsymbol{y^{*}},\boldsymbol{q^{*}},\boldsymbol{\bar{q}^{*}},\boldsymbol{v^{*}},\boldsymbol{\bar{v}^{*}})$ be an extreme point of $\mathcal{S}_{\mathcal{T}}$ . It suffices to show that $\boldsymbol{y^{*}}\in\{0,1\}^{n}$ and $\boldsymbol{q^{*}}\in\{0,1\}^{|\mathcal{T}|}$ , since from equations $\bar{q}^{*}_{T}=1-q^{*}_{T},\boldsymbol{v^{*}_{T}}=q^{*}_{T}\cdot\boldsymbol{y^{*}}$ and $\boldsymbol{\bar{v}^{*}_{T}}=\bar{q}^{*}_{T}\cdot\boldsymbol{y^{*}}$ , the integrality of the remaining variables follows.

First, we show $\boldsymbol{y^{*}}\in\{0,1\}^{n}$ . Assume for a contradiction that $0<y^{*}_{\ell}<1$ for some $\ell\in[n]$ . Let $\boldsymbol{p^{0}}=(\boldsymbol{y^{0}},\boldsymbol{q^{0}},\boldsymbol{\bar{q}^{0}},\boldsymbol{v^{0}},\boldsymbol{\bar{v}^{0}})$ be the vector in ${\mathbb{R}}^{n+2|\mathcal{T}|+2|\mathcal{T}|n}$ obtained from $\boldsymbol{p^{*}}$ by setting $y^{0}_{\ell}=0$ and $v^{0}_{T,\ell}=\bar{v}^{0}_{T,\ell}=0$ for any $T\in\mathcal{T}$ . Similarly, let $\boldsymbol{p^{1}}$ be obtained from $\boldsymbol{p^{*}}$ by setting $y^{1}_{\ell}=1$ and $v^{1}_{T,\ell}=q^{*}_{T},\bar{v}^{1}_{T,\ell}=\bar{q}^{*}_{T}$ for any $T\in\mathcal{T}$ .

Now we show that both vectors $\boldsymbol{p^{0}}$ and $\boldsymbol{p^{1}}$ are in $\mathcal{S}_{\mathcal{T}}$ . From the construction of $\boldsymbol{p^{0}}$ and $\boldsymbol{p^{1}}$ , it suffices to check that (4) are satisfied by both $\boldsymbol{p^{0}}$ and $\boldsymbol{p^{1}}$ . Note that $\boldsymbol{p^{0}}\leq\boldsymbol{p^{*}}$ (component-wise), so the fact that $\boldsymbol{p^{*}}$ satisfies (4) directly implies that $\boldsymbol{p^{0}}$ satisfies (4). For $\boldsymbol{p^{1}}$ , we want to check that: for any $T\in\mathcal{T}$ , $\bar{v}^{1}_{T,i}=0\ \forall i\in T$ , and $v^{1}_{T,j}=0\ \forall j\in\delta(T)$ . Since $\boldsymbol{p^{*}}$ satisfies (4), and from the construction of $\boldsymbol{p^{1}}$ , it suffices to check that: $q^{*}_{T}=v^{1}_{T,\ell}=0$ for any $T\in\mathcal{T}$ with $T\cap\delta(\ell)\neq\emptyset$ , and $\bar{q}^{*}_{T}=\bar{v}^{1}_{T,\ell}=0$ for any $T\in\mathcal{T}$ with $\ell\in T$ . Since $\boldsymbol{p^{*}}$ satisfies (4) and $\boldsymbol{v^{*}_{T}}=q^{*}_{T}\cdot\boldsymbol{y^{*}},\boldsymbol{\bar{v}^{*}_{T}}=\bar{q}^{*}_{T}\cdot\boldsymbol{y^{*}}$ for any $T\in\mathcal{T}$ , we obtain that $\bar{v}^{*}_{T,\ell}=\bar{q}^{*}_{T}\cdot y^{*}_{\ell}=0$ for any $T\in\mathcal{T}$ with $\ell\in T$ , and $v^{*}_{T,\ell}=q^{*}_{T}\cdot y^{*}_{\ell}=0$ for any $T\in\mathcal{T}$ with $T\cap\delta(\ell)\neq\emptyset$ . By assumption of $y^{*}_{\ell}>0$ , we get $\bar{q}^{*}_{T}=0$ for any $T\in\mathcal{T}$ with $\ell\in T$ , and $q^{*}_{T}=0$ for any $T\in\mathcal{T}$ with $T\cap\delta(\ell)\neq\emptyset$ . Therefore, we have shown that both $\boldsymbol{p^{0}},\boldsymbol{p^{1}}$ are in $\mathcal{S}_{\mathcal{T}}$ .

Next, we show that $\boldsymbol{p^{*}}$ can be written as the convex combination of $\boldsymbol{p^{0}}$ and $\boldsymbol{p^{1}}$ :

\boldsymbol{p^{*}}=y^{*}_{\ell}\cdot\boldsymbol{p^{1}}+(1-y^{*}_{\ell})\cdot\boldsymbol{p^{0}}.

(25)

From the construction of $\boldsymbol{p^{0}}$ and $\boldsymbol{p^{1}}$ , we only need to consider the components of $y_{\ell}$ and $v_{T,\ell},\bar{v}_{T,\ell}$ for all $T\in\mathcal{T}$ . The $y_{\ell}$ component of (25) is trivial to check. For any $T\in\mathcal{T}$ , we have

	$\displaystyle v^{}_{T,\ell}=y^{}_{\ell}\cdot q^{}_{T}+(1-y^{}_{\ell})\cdot 0=y^{}_{\ell}\cdot v^{1}_{T,\ell}+(1-y^{}_{\ell})\cdot v^{0}_{T,\ell},$
	$\displaystyle\bar{v}^{}_{T,\ell}=y^{}_{\ell}\cdot\bar{q}^{}_{T}+(1-y^{}_{\ell})\cdot 0=y^{}_{\ell}\cdot\bar{v}^{1}_{T,\ell}+(1-y^{}_{\ell})\cdot\bar{v}^{0}_{T,\ell},$

where the first equations of both lines are from the fact that $\boldsymbol{p^{*}}\in\mathcal{S}_{\mathcal{T}}$ , and the second equations are from the definition of $\boldsymbol{p^{0}}$ and $\boldsymbol{p^{1}}$ . We have thereby shown that, if $\boldsymbol{p^{*}}$ has fractional $y$ components, then $\boldsymbol{p^{*}}$ can be written as the convex combination of two different points in $\mathcal{S}_{\mathcal{T}}$ . This contradicts the fact that $\boldsymbol{p^{*}}$ is an extreme point.

Next, we show $\boldsymbol{q^{*}}\in\{0,1\}^{|\mathcal{T}|}$ . Assume for a contradiction that $0<q^{*}_{\tilde{T}}<1$ for some $\tilde{T}\in\mathcal{T}$ . Let $\boldsymbol{p^{2}}=(\boldsymbol{y^{2}},\boldsymbol{q^{2}},\boldsymbol{\bar{q}^{2}},\boldsymbol{v^{2}},\boldsymbol{\bar{v}^{2}})$ be the vector in ${\mathbb{R}}^{n+2|\mathcal{T}|+2|\mathcal{T}|n}$ obtained from $\boldsymbol{p^{*}}$ by setting $q^{2}_{\tilde{T}}=0$ , $\bar{q}^{2}_{\tilde{T}}=1$ , $\boldsymbol{v^{2}_{\tilde{T}}}=0$ , $\boldsymbol{\bar{v}^{2}_{\tilde{T}}}=\boldsymbol{y^{*}}$ . Similarly, let $\boldsymbol{p^{3}}$ be obtained from $\boldsymbol{p^{*}}$ by setting $q^{3}_{\tilde{T}}=1$ , $\bar{q}^{3}_{\tilde{T}}=0$ , $\boldsymbol{v^{3}_{\tilde{T}}}=\boldsymbol{y^{*}}$ , $\boldsymbol{\bar{v}^{3}_{\tilde{T}}}=0$ . Now, we show that $\boldsymbol{p^{2}},\boldsymbol{p^{3}}\in\mathcal{S}_{\mathcal{T}}$ . Here we only have to show that (4) are satisfied by both $\boldsymbol{p^{2}}$ and $\boldsymbol{p^{3}}$ . For $\boldsymbol{p^{2}}$ , we need to show: $\bar{v}^{2}_{\tilde{T},i}=0\ \forall i\in\tilde{T}$ and $v^{2}_{\tilde{T},j}=0$ for any $j\in\delta(T)$ . By definition of $p^{2}$ , we only need to show $y^{*}_{i}=0\ \forall i\in\tilde{T}$ . By assumption of $q^{*}_{\tilde{T}}\in(0,1)$ , we also have $\bar{q}^{*}_{\tilde{T}}\in(0,1)$ . Since (4) and (21) imply $\bar{v}^{*}_{\tilde{T},i}=\bar{q}^{*}_{\tilde{T}}\cdot y^{*}_{i}=0$ , for any $i\in\tilde{T}$ we have $y^{*}_{i}=0$ for any $i\in\tilde{T}$ . Hence we have shown $\boldsymbol{p^{2}}\in\mathcal{S}_{\mathcal{T}}$ . Similarly, we can obtain $\boldsymbol{p^{3}}\in\mathcal{S}_{\mathcal{T}}$ . Lastly, we show that:

\boldsymbol{p^{*}}=q^{*}_{\tilde{T}}\cdot\boldsymbol{p^{3}}+(1-q^{*}_{\tilde{T}})\cdot\boldsymbol{p^{2}}.

(26)

From the definition of $\boldsymbol{p^{2}}$ and $\boldsymbol{p^{3}}$ , we only need to consider the components of $q_{\tilde{T}},\bar{q}_{\tilde{T}},v_{\tilde{T},j},\bar{v}_{\tilde{T},j}$ for any $j\in[n]$ . The $q_{\tilde{T}},\bar{q}_{\tilde{T}}$ components of (26) are trivial to check. For any $j\in[n]$ , we have

	$\displaystyle v^{}_{\tilde{T},j}=q^{}_{\tilde{T}}\cdot y^{}_{j}+(1-q^{}_{\tilde{T}})\cdot 0=q^{}_{\tilde{T}}\cdot v^{3}_{\tilde{T},j}+(1-q^{}_{\tilde{T}})\cdot v^{2}_{\tilde{T},j},$
	$\displaystyle\bar{v}^{}_{\tilde{T},j}=q^{}_{\tilde{T}}\cdot 0+\bar{q}^{}_{\tilde{T}}\cdot y^{}_{j}=q^{}_{\tilde{T}}\cdot\bar{v}^{3}_{\tilde{T},j}+(1-q^{}_{\tilde{T}})\cdot\bar{v}^{2}_{\tilde{T},j},$

where the first equations of both lines are from the fact that $\boldsymbol{p^{*}}\in\mathcal{S}_{\mathcal{T}}$ , and the second equations are from the definition of $\boldsymbol{p^{2}}$ and $\boldsymbol{p^{3}}$ . Therefore, $\boldsymbol{p^{*}}$ can be written as the convex combination of two different points in $\mathcal{S}_{\mathcal{T}}$ , which contradicts the fact that $\boldsymbol{p^{*}}$ is an extreme point. ∎

According to Section 4, the convex hull of $\mathcal{S}_{\mathcal{T}}$ in (23) can be rewritten as:

\mathop{\rm conv}(\big{\{}(\boldsymbol{y},\boldsymbol{q},\boldsymbol{\bar{q}},\boldsymbol{v},\boldsymbol{\bar{v}})\in\{0,1\}^{n+2|\mathcal{T}|+2|\mathcal{T}|n}\mid\eqref{eq: balas 3},\eqref{eq: balas 6},\eqref{eq: bilinear2}\ \forall T\in\mathcal{T}\big{\}}).

(27)

Here constraints (5) are redundant hence they have been removed.

For the purpose of studying quadratic 0-1 programming problems, Padberg [28] proposed the boolean quadric polytope (BQP), which is a polytope in a higher dimensional space that results from the linearization of the quadratic terms. In particular, the BQP with respect to the complete bipartite graph that can be bipartitioned into $2|\mathcal{T}|$ and $n$ nodes is defined as

\mathcal{BQP}_{2|\mathcal{T}|,n}:=\mathop{\rm conv}(\{(\boldsymbol{y},\boldsymbol{q},\boldsymbol{\bar{q}},\boldsymbol{v},\boldsymbol{\bar{v}})\in\{0,1\}^{n+2|\mathcal{T}|+2|\mathcal{T}|n}\mid\eqref{eq: bilinear2}\ \forall T\in\mathcal{T}\}).

In fact, this special case of BQP corresponding to a complete bipartite graph is also called bipartite BQP, and its structural properties have been recently studied in [33]. Using this definition, by (27), we have the following relaxation for $\mathop{\rm conv}(\mathcal{S}_{\mathcal{T}}):$

\begin{split}\mathop{\rm conv}(\mathcal{S}_{\mathcal{T}})\subseteq&\mathop{\rm conv}(\{(\boldsymbol{y},\boldsymbol{q},\boldsymbol{\bar{q}},\boldsymbol{v},\boldsymbol{\bar{v}})\in\{0,1\}^{n+2|\mathcal{T}|+2|\mathcal{T}|n}\mid\eqref{eq: bilinear2}\ \forall T\in\mathcal{T}\})\\ &\cap\{(\boldsymbol{y},\boldsymbol{q},\boldsymbol{\bar{q}},\boldsymbol{v},\boldsymbol{\bar{v}})\mid\eqref{eq: balas 3},\eqref{eq: balas 6}\ \forall T\in\mathcal{T},\boldsymbol{\bar{v}_{T}}+\boldsymbol{v_{T}}=\boldsymbol{y}\}\\ =&\{(\boldsymbol{y},\boldsymbol{q},\boldsymbol{\bar{q}},\boldsymbol{v},\boldsymbol{\bar{v}})\in\mathcal{BQP}_{2|\mathcal{T}|,n}\mid\eqref{eq: balas 3},\eqref{eq: balas 6}\ \forall T\in\mathcal{T},\boldsymbol{\bar{v}_{T}}+\boldsymbol{v_{T}}=\boldsymbol{y}\}.\end{split}

(28)

Here we also include the equations $\boldsymbol{\bar{v}_{T}}+\boldsymbol{v_{T}}=\boldsymbol{y}$ for all $T\in\mathcal{T}$ , since they are obviously valid for $\mathcal{S}_{\mathcal{T}}$ . Interestingly, the next theorem shows that, the relaxation given in (28) is in fact a formulation of $\mathop{\rm conv}(\mathcal{S}_{\mathcal{T}})$ . It is worth mentioning that such result is non-trivial in general, since (7) and $\boldsymbol{\bar{v}_{T}}+\boldsymbol{v_{T}}=\boldsymbol{y}$ are not facial constraints to $\mathcal{BQP}_{2|\mathcal{T}|,n}$ , and equations $\boldsymbol{\bar{v}_{T}}+\boldsymbol{v_{T}}=\boldsymbol{y}$ are redundant in the definition (23) of $\mathcal{S}_{\mathcal{T}}$ , while they are necessary in order for the statement of the next theorem to hold.

Figure 1: In this figure, the original conflict graph

G

is marked in blue, and the complete bipartite graph is marked in red.

\mathcal{T}=\{T_{1},T_{2}\}:=\left\{\{1,2\},\{3\}\right\}

is a feasible cover partition of

G

, each red edge represents the variable

v_{T,i}

\bar{v}_{T,i}

for

T\in\mathcal{T}

and

i\in[4]

, and the dashed red edges therein represent the variables that are set to 0 in (4), which are

\bar{v}_{T_{1},1},\bar{v}_{T_{1},2},\bar{v}_{T_{2},3},v_{T_{1},3},v_{T_{1},4},v_{T_{2},1},v_{T_{2},2}

and

v_{T_{2},4}

Theorem 3.

$\{(\boldsymbol{y},\boldsymbol{q},\boldsymbol{\bar{q}},\boldsymbol{v},\boldsymbol{\bar{v}})\in\mathcal{BQP}_{2|\mathcal{T}|,n}\mid\eqref{eq: balas 3},\eqref{eq: balas 6}\ \forall T\in\mathcal{T},\boldsymbol{\bar{v}_{T}}+\boldsymbol{v_{T}}=\boldsymbol{y}\}=\mathop{\rm conv}(\mathcal{S}_{\mathcal{T}})$ .

Proof.

Because of (28), here we only have to show the other direction: $\{(\boldsymbol{y},\boldsymbol{q},\boldsymbol{\bar{q}},\boldsymbol{v},\boldsymbol{\bar{v}})\in\mathcal{BQP}_{2|\mathcal{T}|,n}\mid\eqref{eq: balas 3},\eqref{eq: balas 6}\ \forall T\in\mathcal{T},\boldsymbol{\bar{v}_{T}}+\boldsymbol{v_{T}}=\boldsymbol{y}\}\subseteq\mathop{\rm conv}(\mathcal{S}_{\mathcal{T}})$ .

Arbitrarily pick $p^{*}=(\boldsymbol{y^{*}},\boldsymbol{q^{*}},\boldsymbol{\bar{q}^{*}},\boldsymbol{v^{*}},\boldsymbol{\bar{v}^{*}})\in\mathcal{BQP}_{2|\mathcal{T}|,n}$ which also satisfies (4), (7), and $\boldsymbol{\bar{v}_{T}}+\boldsymbol{v_{T}}=\boldsymbol{y}$ for every $T\in\mathcal{T}$ . We want to show that $\boldsymbol{p^{*}}\in\mathop{\rm conv}(\mathcal{S}_{\mathcal{T}})$ . Here $\boldsymbol{p^{*}}$ can be written as the convex combination of some binary points in $\mathcal{BQP}_{2|\mathcal{T}|,n}$ :

\boldsymbol{p^{*}}=\sum_{i=1}^{k}\lambda_{i}\boldsymbol{p^{i}},\ \lambda_{i}>0,\ \sum_{i=1}^{k}\lambda_{i}=1,\ \boldsymbol{p^{i}}\in\mathcal{BQP}_{2|\mathcal{T}|,n}\cap\{0,1\}^{n+2|\mathcal{T}|+2|\mathcal{T}|n}.

(29)

Our goal is to show that either all of those $\boldsymbol{p^{i}}$ are contained in $\mathcal{S}_{\mathcal{T}}$ , or there exist some other binary points in $\mathcal{S}_{\mathcal{T}}$ which contain $\boldsymbol{p^{*}}$ in their convex hull.

First of all, since $\boldsymbol{p^{*}}$ satisfies (4) for any $T\in\mathcal{T}$ , and $\boldsymbol{p^{*}}$ can be written as the convex combination in (29), we know that $\boldsymbol{p^{i}}$ satisfies (4) for all $i\in[k]$ . If for any $i\in[k]$ and $T\in\mathcal{T}$ , we also have $q^{i}_{T}+\bar{q}^{i}_{T}=1$ , then we complete the proof, since all of these $\boldsymbol{p^{i}}\in\mathcal{S}_{\mathcal{T}}$ , and $\boldsymbol{p^{*}}=\sum_{i=1}^{k}\lambda_{i}\boldsymbol{p^{i}}\in\mathop{\rm conv}(\mathcal{S}_{\mathcal{T}})$ .

Now, assume equation $q_{\tilde{T}}+\bar{q}_{\tilde{T}}=1$ is not satisfied by all $\{\boldsymbol{p^{i}}\}_{i=1}^{k}$ , for some $\tilde{T}\in\mathcal{T}$ . Since $q_{\tilde{T}}+\bar{q}_{\tilde{T}}=1$ is satisfied by $\boldsymbol{p^{*}}$ , we know there must exist some point $\boldsymbol{p^{r}}$ with $q^{r}_{\tilde{T}}+\bar{q}^{r}_{\tilde{T}}=0$ and some other point $\boldsymbol{p^{s}}$ with $q^{s}_{\tilde{T}}+\bar{q}^{s}_{\tilde{T}}=2$ . Namely, there exist $\{\ell_{i}\}_{i=1}^{a},\{h_{i}\}_{i=1}^{b}\subseteq[k]$ such that $q^{\ell_{i}}_{\tilde{T}}+\bar{q}^{\ell_{i}}_{\tilde{T}}=0$ for all $i\in[a]$ , and $q^{h_{i}}_{\tilde{T}}+\bar{q}^{h_{i}}_{\tilde{T}}=2$ for all $i\in[b]$ . Next, we want to transform $\boldsymbol{p^{\ell_{1}}},\ldots,\boldsymbol{p^{\ell_{a}}},\boldsymbol{p^{h_{1}}},\ldots,\boldsymbol{p^{h_{b}}}$ into some other binary points in $\mathcal{BQP}_{2|\mathcal{T}|,n}$ with $q_{\tilde{T}}+\bar{q}_{\tilde{T}}=1$ . For all points in $\{\boldsymbol{p^{i}}\}_{i=1}^{k}$ with index in $\{\ell_{i}\}_{i=1}^{a}\cup\{h_{i}\}_{i=1}^{b}$ , we replace their $\bar{q}_{\tilde{T}}$ component by $1-\bar{q}_{\tilde{T}}$ , and change those components $\boldsymbol{\bar{v}_{\tilde{T}}}$ correspondingly to make $\boldsymbol{p^{i}}$ remain feasible in $\mathcal{BQP}_{2|\mathcal{T}|,n}$ . We denote the obtained set of binary points by $\{\boldsymbol{\tilde{p}^{i}}\}_{i=1}^{k}$ . Clearly, after such transformation, those new points now all satisfy the equation $q_{\tilde{T}}+\bar{q}_{\tilde{T}}=1$ . Now we verify that $\boldsymbol{p^{*}}$ can still be written as their convex combination, with the same convex combination coefficients: $\boldsymbol{p^{*}}=\sum_{i=1}^{k}\lambda_{i}\boldsymbol{\tilde{p}^{i}}$ . Note that the only components changed in $\sum_{i=1}^{k}\lambda_{i}\boldsymbol{\tilde{p^{i}}}$ from $\sum_{i=1}^{k}\lambda_{i}\boldsymbol{p^{i}}$ are $\bar{q}_{\tilde{T}}$ and $\boldsymbol{\bar{v}_{\tilde{T}}}$ . From the transformation above, the change occurred to component $\bar{q}_{\tilde{T}}$ of $\sum_{i=1}^{k}\lambda_{i}\boldsymbol{\tilde{p}^{i}}$ from $\sum_{i=1}^{k}\lambda_{i}\boldsymbol{p^{i}}$ is: $\sum_{i=1}^{a}\lambda_{\ell_{i}}-\sum_{i=1}^{b}\lambda_{h_{i}}$ . By the fact that $q^{*}_{\tilde{T}}+\bar{q}^{*}_{\tilde{T}}=1$ and $\boldsymbol{p^{*}}=\sum_{i=1}^{k}\lambda_{i}\boldsymbol{p^{i}}$ , we have:

1=1\cdot(1-\sum_{i=1}^{a}\lambda_{\ell_{i}}-\sum_{i=1}^{b}\lambda_{h_{i}})+0\cdot\sum_{i=1}^{a}\lambda_{\ell_{i}}+2\cdot\sum_{i=1}^{b}\lambda_{h_{i}},

which gives us $\sum_{i=1}^{a}\lambda_{\ell_{i}}-\sum_{i=1}^{b}\lambda_{h_{i}}=0$ . So the component $\bar{q}_{\tilde{T}}$ of $\sum_{i=1}^{k}\lambda_{i}\boldsymbol{\tilde{p}^{i}}$ remains unchanged from $\sum_{i=1}^{k}\lambda_{i}\boldsymbol{p^{i}}$ . Similarly, the change occurred to components $\boldsymbol{\bar{v}_{\tilde{T}}}$ of $\sum_{i=1}^{k}\lambda_{i}\boldsymbol{\tilde{p}^{i}}$ from $\sum_{i=1}^{k}\lambda_{i}\boldsymbol{p^{i}}$ is: $\sum_{i=1}^{a}\lambda_{\ell_{i}}\boldsymbol{y^{\ell_{i}}}-\sum_{i=1}^{b}\lambda_{h_{i}}\boldsymbol{y^{h_{i}}}$ , where $\boldsymbol{y^{j}}$ are the $\boldsymbol{y}$ components of point $\boldsymbol{p^{j}}$ for any $j\in[k]$ . According to the fact that $\boldsymbol{y^{*}}=\boldsymbol{v^{*}_{\tilde{T}}}+\boldsymbol{\bar{v}^{*}_{\tilde{T}}}$ and $\boldsymbol{p^{*}}=\sum_{i=1}^{k}\lambda_{i}\boldsymbol{p^{i}}$ , here we have:

\sum_{i=1}^{a}\lambda_{\ell_{i}}\boldsymbol{y^{\ell_{i}}}+\sum_{i\neq\ell_{j}\text{ nor }h_{j}}\lambda_{i}\boldsymbol{y^{i}}+\sum_{i=1}^{b}\lambda_{h_{i}}\boldsymbol{y^{h_{i}}}=\boldsymbol{y^{*}}=\boldsymbol{v^{*}_{\tilde{T}}}+\boldsymbol{\bar{v}^{*}_{\tilde{T}}}=\sum_{i\neq\ell_{j}\text{ nor }h_{j}}\lambda_{i}\boldsymbol{y^{i}}+2\sum_{i=1}^{b}\lambda_{h_{i}}\boldsymbol{y^{h_{i}}}.

This gives us $\sum_{i=1}^{a}\lambda_{\ell_{i}}\boldsymbol{y^{\ell_{i}}}=\sum_{i=1}^{b}\lambda_{h_{i}}\boldsymbol{y^{h_{i}}}$ , which means that the components $\boldsymbol{\bar{v}_{\tilde{T}}}$ of $\sum_{i=1}^{k}\lambda_{i}\boldsymbol{\tilde{p}^{i}}$ remain unchanged from $\sum_{i=1}^{k}\lambda_{i}\boldsymbol{p^{i}}$ . Therefore, $\boldsymbol{p^{*}}=\sum_{i=1}^{k}\lambda_{i}\boldsymbol{p^{i}}=\sum_{i=1}^{k}\lambda_{i}\boldsymbol{\tilde{p}^{i}}$ . The above argument holds for any $T\in\mathcal{T}$ which has $q^{i}_{T}+\bar{q}^{i}_{T}\neq 1$ for some $i\in[k]$ . Eventually, we end up getting $k$ binary points in $\mathcal{S}_{\mathcal{T}}$ that contain $\boldsymbol{p^{*}}$ in their convex hull, hence $\boldsymbol{p^{*}}\in\mathop{\rm conv}(\mathcal{S}_{\mathcal{T}})$ . ∎

From Section 3, in order to fully utilize the cutting-planes provided by $\mathop{\rm conv}(\mathcal{S})$ , one only needs to consider valid inequalities of $\mathcal{BQP}_{2|\mathcal{T}|,n}$ as well as some additional equations in (28). However, it is challenging to enumerate the facets of $\mathcal{BQP}$ even for a very small graph, see [15]. The polyhedral structure of $\mathcal{BQP}$ for a series-parallel or an acyclic graph were studied originally by Padberg [28]. More recently, Sripratak et al. [33] studied valid inequalities for $\mathcal{BQP}$ over a complete bipartite graph, which is particularly interesting for our setting and they coined it as bipartite boolean quadric polytope. In that paper, the authors proposed a few families of valid inequalities, e.g., odd-cycle inequalities, rounded clique inequalities, rounded cut inequalities, etc., among which odd-cycle inequalities are the only family of inequalities that can be facet-defining. Therefore, even though we have a complete characterization of $\mathop{\rm conv}(\mathcal{S})$ in terms of $\mathcal{BQP}_{2|\mathcal{T}|,n}$ , facet-defining inequalities of $\mathcal{BQP}_{2|\mathcal{T}|,n}$ are still generally hard to obtain. Now, we will generate valid inequalities of $\mathop{\rm conv}(\mathcal{S})$ from a different perspective.

It is simple to see that, by studying the sub-system of (LPCC) involving only $y$ variables, we are also able to derive valid inequalities for $P^{\perp}$ . Namely, any valid inequality for the convex set

\mathop{\rm conv}(\{\boldsymbol{y}\in[0,1]^{n}\mid y_{i}\cdot y_{j}=0\ \forall\{i,j\}\in E\})

(30)

can be utilized as a cutting-plane involving only $y$ -variables to strengthen the LP relaxation $P$ . In fact, as we will see in the next result, the convex set (30) is simply the stable set polytope of the graph $G$ , and any valid inequality for such stable set polytope is actually valid for the projection of $\mathop{\rm conv}(\mathcal{S}_{\mathcal{T}})$ .

Proposition 5.

For any graph $G$ and any feasible cover partition $\mathcal{T}$ of $G$ , $\operatorname{proj}_{\boldsymbol{y}}\mathop{\rm conv}(\mathcal{S}_{\mathcal{T}})\subseteq\mathop{\rm conv}(\{\boldsymbol{y}\in[0,1]^{n}\mid y_{i}\cdot y_{j}=0\ \forall\{i,j\}\in E\})=\mathop{\rm conv}(\{\boldsymbol{y}\in\{0,1\}^{n}\mid y_{i}+y_{j}\leq 1\ \forall\{i,j\}\in E\})$ .

Proof.

To show the second equation, it suffices to show that the set (30) has binary extreme points. Let $\boldsymbol{y^{*}}$ be a fractional point of (30), with $y^{*}_{i^{\prime}}\in(0,1)$ . Consider the two points $\boldsymbol{y^{0}}=\boldsymbol{y^{*}}-y^{*}_{i^{\prime}}\cdot\boldsymbol{e^{i^{\prime}}}$ and $\boldsymbol{y^{1}}=\boldsymbol{y^{*}}+(1-y^{*}_{i^{\prime}})\cdot\boldsymbol{e^{i^{\prime}}}$ , where $\boldsymbol{e^{i^{\prime}}}$ denotes the unit vector with $i^{\prime}$ th-component being 1. Since $y^{*}_{i^{\prime}}>0$ , by complementarity constraints, we know $y^{*}_{j}=0$ for any $j\in\delta(i^{\prime})$ . Therefore, it is easy to verify that both $\boldsymbol{y^{0}}$ and $\boldsymbol{y^{1}}$ satisfy the complementarity constraints $y_{i}\cdot y_{j}=0\ \forall\{i,j\}\in E$ . Since $\boldsymbol{y^{*}}$ can be written as the convex combination of $\boldsymbol{y^{0}}$ and $\boldsymbol{y^{1}}$ , we know that the fractional point $\boldsymbol{y^{*}}$ cannot be an extreme point of set (30).

To prove the first equation, by Section 4, we only need to show that, for any binary $(\boldsymbol{y^{*}},\boldsymbol{q^{*}},\boldsymbol{\bar{q}^{*}},\boldsymbol{v^{*}},\boldsymbol{\bar{v}^{*}})\in\mathcal{S}_{\mathcal{T}}$ and any $(i^{\prime},j^{\prime})\in E$ , we have $y^{*}_{i^{\prime}}\cdot y^{*}_{j^{\prime}}=0$ . Since $\mathcal{T}$ is a feasible cover partition, there exists $T^{*}\in\mathcal{T}$ such that $i^{\prime}\in T^{*}$ or $j^{\prime}\in T^{*}$ . Without loss of generality assume $i^{\prime}\in T^{*}$ . We then obtain $j^{\prime}\in\delta(T^{*})$ . By equations (4), (7), (21) with respect to index $T^{*}$ , we have: $\bar{q}^{*}_{T^{*}}\cdot y^{*}_{i}=\bar{v}^{*}_{T^{*},i}=0\ \forall i\in T^{*}$ , $q^{*}_{T^{*}}\cdot y^{*}_{j}=v^{*}_{T^{*},j}=0\ \forall j\in\delta(T^{*})$ , $q^{*}_{T^{*}}+\bar{q}^{*}_{T^{*}}=1$ . Since $q^{*}_{T^{*}},\bar{q}^{*}_{T^{*}}\in\{0,1\}$ and $i^{\prime}\in T^{*},j^{\prime}\in\delta(T^{*})$ , at least one of $y^{*}_{i^{\prime}}$ and $y^{*}_{j^{\prime}}$ is 0. Thus we complete the proof. ∎

From Section 5, we directly obtain the next corollary.

Corollary 2.

Let $G$ be a graph and let $\mathcal{T}$ be a feasible cover partition of $G$ . If $\boldsymbol{\alpha}^{\mathsf{T}}\boldsymbol{y}\leq\beta$ is a valid inequality for the stable set polytope of $G$ , then for any $T\in\mathcal{T}$ , $\boldsymbol{\alpha}^{\mathsf{T}}\boldsymbol{v_{T}}\leq\beta q_{T}$ and $\boldsymbol{\alpha}^{\mathsf{T}}\boldsymbol{\bar{v}_{T}}\leq\beta\bar{q}_{T}$ are both valid inequalities for $\mathop{\rm conv}(\mathcal{S}_{\mathcal{T}})$ .

Proof.

Arbitrarily pick a point $(\boldsymbol{y^{*}},\boldsymbol{q^{*}},\boldsymbol{\bar{q}^{*}},\boldsymbol{v^{*}},\boldsymbol{\bar{v}^{*}})$ of $\mathcal{S}_{\mathcal{T}}$ . From Section 5, we know $\boldsymbol{\alpha}^{\mathsf{T}}\boldsymbol{y^{*}}\leq\beta$ . By multiplying both sides of such inequality with $q^{*}_{T}$ and $\bar{q}^{*}_{T}$ for any $T\in\mathcal{T}$ , from equation (21), we conclude the proof. ∎

4 Numerical experiments

In this section, we conduct numerical experiments to compare the optimality gaps of various relaxations for some particular LPCCs. We use Python 3.6.0 with CPLEX 12.9 as the LP and MIP solver.

For each LPCC instance we created, its optimal value $v^{*}$ is obtained from formulating it as a MIP. Specifically, for any complementarity constraint $y_{i}\cdot y_{j}=0$ , we add additional binary variables $z_{i},z_{j}$ and enforce $z_{i}+z_{j}\leq 1$ , $y_{i}\leq z_{i}$ , $y_{j}\leq z_{j}$ . Then the optimality gap of one particular relaxation procedure is $|(v_{R}-v^{*})/v^{*}|$ , where $v_{R}$ denotes the optimal value of such relaxation. Here we take the absolute value, because our generated instances are not necessarily all maximization problems, and $val^{*}$ can also be negative.

In this section, we use the following acronyms to denote the optimality gap for each individual relaxation method:

LP: Optimality gap of the LP relaxation of the LPCC, where we simply ignore all the complementarity constraints.
B&C: When formulating the LPCC as a MIP, it denotes the optimality gap of the internal branch-and-cut procedure of CPLEX, where we only allow the branching to occur at the root node and turn off a list of generic-purpose cuts: disjunctive cuts, Gomory cuts, multi-commodity flow cuts, zero-half cuts, MIR cuts, lift-and-project cuts, and flow cover cuts. All the other problem-specific cuts, e.g., clique cuts, cover cuts, GUB cuts are kept.
ER-ee: Optimality gap of the edge-by-edge-based extended relaxation $\mathcal{M}$ in (11).
ER-vc: Optimality gap of the vertex-cover-based extended relaxation $\mathcal{E}_{\mathcal{T}}(P)$ .
ER-vc-cuts: Optimality gap of the relaxation obtained by adding some of the cutting-planes we introduced before (see Section 4.1 for details) to the vertex-cover-based extended relaxation $\mathcal{E}_{\mathcal{T}}(P)$ .

In particular, by comparing columns ER-vc and ER-vc-cuts, one is able to see the strength of those added cuts. Here we should mention that, due to the lack of an efficient separation method for those cuts, to show how much they can further tighten the extended relaxation, when computing ER-vc-cuts we treated those cuts as additional linear constraints and added them altogether into the formulation of $\mathcal{E}_{\mathcal{T}}(P)$ . Next, we introduce the specific cutting-planes from Section 3 that were added into extended relaxations to obtain ER-vc-cuts.

4.1 Cutting-planes for experiments

4.1.1 Stable set cuts

The first type of cuts comes from the stable set polytope of $G$ . In specific, we consider the following well-known inequalities for the stable set polytope:

1.

Clique constraints: $\sum_{i\in C}y_{i}\leq 1$ where $C$ is a clique.
2.

Odd cycle constraints: $\sum_{i\in D}y_{i}\leq(|D|-1)/2$ where $D$ induces a chordless odd cycle.
3.

Odd anti-cycle constraints: $\sum_{i\in\bar{D}}y_{i}\leq 2$ where $\bar{D}$ induces the complement of a chordless odd cycle.

See [29] and [25] for a detailed introduction to these families of cuts. By Section 5, all these inequalities are valid for $\mathop{\rm conv}(\mathcal{S}_{\mathcal{T}})$ , hence can be used as cutting-planes to strenghten $\mathcal{E}_{\mathcal{T}}(P)$ . By Section 2, the corresponding inequalities involving $\boldsymbol{v}(\text{or }\boldsymbol{\bar{v}})$ and $\boldsymbol{q}(\text{or }\boldsymbol{\bar{q}})$ can also be added as cuts.

For a given graph $G$ , we used the Python package NetworkX to create the list of maximal cliques, odd cycles and odd anti-cycles.

4.1.2 Clique q-cuts

This type of cuts comes from Section 3: If clique $C$ is covered by a minimal subset $\{T_{1},\ldots,T_{k}\}$ of $\mathcal{T}$ , then adding $\sum_{i=1}^{k}q_{T_{i}}\leq 1$ into $\tilde{\mathcal{E}}_{\mathcal{T}}(P)$ remains to be an extended formulation of $P^{\perp}$ , so it can be added to tighten the linear system of $\mathcal{E}_{\mathcal{T}}(P)$ . Such inequality comes from a clique of the conflict graph and it only involves $q$ -variables, hence we name it clique q-cut. Similarly, inequality $\sum_{i=1}^{k}\boldsymbol{v_{T_{i}}}\leq\boldsymbol{y}$ can also be added into $\mathcal{E}_{\mathcal{T}}(P)$ to tighten the linear relaxation.

4.1.3 BQP cuts

The last type of cuts we added comes from $\mathcal{BQP}_{2|\mathcal{T}|,n}$ . As recently studied by Sripratak et al. [33], a few families of valid inequalities have been proposed. However, the odd-cycle inequalities are the only inequalities that can be facet-defining for $\mathcal{BQP}_{2|\mathcal{T}|,n}$ , while all the other inequalities therein, e.g., rounded clique inequalities, rounded cut inequalities are actually valid for the linear relaxation given by the McCormick constraints. Due to the lack of a complete understanding of the polyhedral structure of $\mathcal{BQP}_{2|\mathcal{T}|,n}$ , we only added odd-cycle inequalities with a particular size into our formulation. Specifically, we added the ones corresponding to a cycle $C$ with $|C|=4$ and the edge subset $M$ with $|M|=1$ in equation (24) in [28]. For any $T_{1}\neq T_{2}\in\mathcal{T}$ and $i\neq j\in[n]$ , we obtain odd-cycle inequalities:

	$\displaystyle-q_{T_{2}}-y_{j}+v_{T_{1},j}+v_{T_{2},i}+v_{T_{2},j}-v_{T_{1},i}\leq 0,$
	$\displaystyle-\bar{q}_{T_{2}}-y_{j}+\bar{v}_{T_{1},j}+\bar{v}_{T_{2},i}+\bar{v}_{T_{2},j}-\bar{v}_{T_{1},i}\leq 0,$
	$\displaystyle-q_{T_{2}}-y_{j}+\bar{v}_{T_{1},j}+v_{T_{2},i}+v_{T_{2},j}-\bar{v}_{T_{1},i}\leq 0,$
	$\displaystyle-\bar{q}_{T_{2}}-y_{j}+v_{T_{1},j}+\bar{v}_{T_{2},i}+\bar{v}_{T_{2},j}-v_{T_{1},i}\leq 0.$

Similarly, by picking a cycle $C$ with $|C|=4$ and edge subset $M$ with $|M|=3$ , for any $T_{1}\neq T_{2}\in\mathcal{T}$ and $i\neq j\in[n]$ , we obtain odd-cycle inequalities:

	$\displaystyle q_{T_{1}}+y_{j}+v_{T_{2},i}-v_{T_{1},i}-v_{T_{1},j}-v_{T_{2},j}\leq 1,$
	$\displaystyle\bar{q}_{T_{1}}+y_{j}+\bar{v}_{T_{2},i}-\bar{v}_{T_{1},i}-\bar{v}_{T_{1},j}-\bar{v}_{T_{2},j}\leq 1,$
	$\displaystyle q_{T_{1}}+y_{j}+\bar{v}_{T_{2},i}-v_{T_{1},i}-v_{T_{1},j}-\bar{v}_{T_{2},j}\leq 1,$
	$\displaystyle\bar{q}_{T_{1}}+y_{j}+v_{T_{2},i}-\bar{v}_{T_{1},i}-\bar{v}_{T_{1},j}-v_{T_{2},j}\leq 1.$

We mention that the number of inequalities of the above form is $\mathcal{O}(|\mathcal{T}|^{2}n^{2})$ which is also $\mathcal{O}(n^{4})$ . Without an efficient separation heuristic, adding these inequalities can be a great burden to the solver. Therefore, for this type of cuts, instead of adding all of them into the relaxation, we adopt the following iterative procedure: for each iteration and the optimal solution $p^{*}$ obtained at current step, we only add the BQP cuts that are able to separate $p^{*}$ , and then solve the new relaxation and obtain a new optimal solution for the next iteration. We terminate the iterations when the optimal value $v^{\prime}$ obtained in the current iteration is within a small distance $(<1\%\cdot v^{\prime})$ from the optimal value in the last iteration, or when the iteration number exceeds a certain threshold (we pick 5 as the iteration upper bound for our later experiments).

4.2 Instance sets and experimental results

In the following, we describe three applications from which we generated instances for our numerical experiments. For the first two types of instances in Section 4.2.1 and Section 4.2.2, the corresponding conflict graphs were generated randomly according to the Erdős-Rényi model with respect to some pre-determined density $\rho$ , where each edge is included in the conflict graph with probability $\rho$ , independently from every other edge. This can be realized using function erdos_renyi_graph of Python package NetworkX. For each of these conflict graphs, the function min_weighted_vertex_cover of NetworkX will also produce an approximate minimum vertex cover, from which we produced the feasible cover partition to construct our extended formulation $\mathcal{E}_{\mathcal{T}}(P)$ . For the third type of instances in Section 4.2.3, we specifically considered the LPCC with 1-regular conflict graph, which has been studied extensively in the literature.

4.2.1 Transportation problem with exclusionary side constraints

The first type of instances we considered are instances of the Transportation Problem with Exclusionary Side Constraints (TPESC), which was originally proposed by Cao [8] and later also studied by Sun [34], and by Syarif and Gen [35]. In this problem the goal is to transport goods from several sources $i\in S$ to destinations $j\in D$ at the lowest cost, while meeting all constraints on the supplies and demands. Due to some specific reasons, in this problem it is not allowed to carry certain goods to the same destination. For instance, hazardous materials may not be stored in the same warehouse. Denote the source-destination pairs $L:=S\times D$ , and the flow on arc $\ell\in L$ is denoted by $y_{\ell}$ . If $\ell=\{i,j\}$ then $y_{\ell}$ is also denoted as $y_{i,j}$ . Here we assume that $0\leq y_{\ell}\leq 1$ for any $\ell\in L$ . Then TPESC can be modeled as a classical transportation problem with additional complementarity constraints:

\displaystyle\begin{split}\text{minimize}\quad&\sum_{\ell\in L}c_{\ell}y_{\ell}\\ \text{subject to}\quad&\sum_{j\in D}y_{i,j}=\alpha_{i},\quad\forall i\in S\\ &\sum_{i\in S}y_{i,j}=\beta_{j},\quad\forall j\in D\\ &y_{i,j}\cdot y_{i^{\prime},j}=0,\quad\forall(i,i^{\prime})\in E,j\in D\\ &0\leq\boldsymbol{y}\leq\textbf{1}_{|L|}.\end{split}

(TPESC)

We remark that (TPESC) is a minimization problem instead of a maximization problem as (LPCC). Here $\boldsymbol{\alpha}\in{\mathbb{R}}_{+}^{|S|}$ denotes the supplies, $\boldsymbol{\beta}\in{\mathbb{R}}_{+}^{|D|}$ denotes the demands and $\boldsymbol{c}\in{\mathbb{R}}_{+}^{|L|}$ denotes the transportation costs. We further assume that $\sum_{i\in S}\alpha_{i}=\sum_{j\in D}\beta_{j}$ and $\alpha_{i}\leq|D|$ , $\beta_{j}\leq|S|$ for any $i\in S,j\in D$ , since otherwise (TPESC) is infeasible. Let $E\subseteq S\times S$ denote the set of conflicting pairs of $S$ which cannot transport goods to the same destination in $D$ . In other words, the conflict graph of (TPESC) is given by

\big{(}L,\{\big{(}\{i,j\},\{i^{\prime},j\}\big{)}\in L\times L\mid(i,i^{\prime})\in E,j\in D\}\big{)}.

For fixed source set $S$ and destination set $D$ , we randomly generated our instances in the following way: $c_{\ell}$ was chosen uniformly at random from $[3,8]$ for any $\ell\in L$ , $\alpha_{i}$ was chosen uniformly at random from $[1,\lfloor d/2\rfloor]$ for any $i\in S$ , and $\beta_{j}$ was chosen uniformly at random from $[1,\lfloor s/2\rfloor]$ for any $j\in D$ . In case supply exceeds demand, i.e., $\sum_{i\in S}\alpha_{i}>\sum_{j\in D}\beta_{j}$ , then $\alpha_{i}$ values were evenly reduced until the sums are balanced. We analogously treated the $\beta_{j}$ values in case demand exceeds supply, i.e., $\sum_{i\in S}\alpha_{i}<\sum_{j\in D}\beta_{j}$ .

Notice that for TPESC, the number of variables in the extended relaxation $\mathcal{E}_{\mathcal{T}}(P)$ is $\mathcal{O}(|S|^{2}|D|^{2})$ . For the ease of computation and illustration, we implemented our experiments using instances with relatively small sizes. In specific, we considered three problem sizes: $|S|=10,|D|=10$ ; $|S|=30,|D|=10$ and $|S|=50,|D|=5$ . For each problem size, we also considered various conflict graph densities, and 10 randomly generated instances were solved with respect to each fixed $|S|,|D|$ and conflict graph density $\rho$ . For each relaxations mentioned before, the averaged numerical results are recorded in Section 1.

Table 1: Optimality gap of different relaxations for (TPESC). (%)

$(\|S\|,\|D\|,\rho)$	LP	B&C	ER-ee	ER-vc	ER-vc-cuts
(10, 10, 0.2)	4.98	0.06	0.48	0.43	0.00
(10, 10, 0.4)	11.35	0.10	3.03	2.14	0.00
(10, 10, 0.6)	12.45	0.85	3.60	1.72	0.00
(30, 10, 0.04)	3.33	0.17	0.18	0.11	0.00
(30, 10, 0.1)	17.7	1.84	3.24	3.24	0.00
(30, 10, 0.2)	28.95	8.22	12.57	11.43	0.67
(50, 5, 0.04)	8.40	0.31	0.31	0.27	0.02
(50, 5, 0.08)	15.68	2.16	3.58	3.58	0.00
(50, 5, 0.12)	20.99	5.85	8.01	8.01	2.86

The first thing that one might notice is that the optimality gaps of almost all relaxations increase when the conflict graph becomes denser. Also, as shown by the smaller values in column ER-vc than those in ER-ee, we know that the vertex-cover-based formulation $\mathcal{E}_{\mathcal{T}}(P)$ is generally a tighter relaxation than the edge-by-edge formulation $\mathcal{M}$ . This observation justifies our statement at the end of Section 2.1. Moreover, even though in most of the testing results, the extended relaxation $\mathcal{E}_{\mathcal{T}}(P)$ itself alone does not seem to provide better optimality gap than the relaxation of B $\&$ C, but adding cutting-planes into the extended relaxation is able to provide a huge improvement for closing the optimality gap. This phenomenon will be further verified by the following experiments.

4.2.2 Continuous multi-dimensional knapsack problem with conflicts

The second type of instances that we considered comes from the Continuous Multi-dimensional Knapsack Problem with Conflicts (CMKPC):

\displaystyle\begin{split}\text{maximize}\quad&\boldsymbol{c}^{\mathsf{T}}\boldsymbol{y}\\ \text{subject to}\quad&M\boldsymbol{y}\leq\boldsymbol{b},\\ &y_{i}\cdot y_{j}=0,\quad\forall\{i,j\}\in E\\ &0\leq\boldsymbol{y}\leq\textbf{1}_{n}.\end{split}

(CMKPC)

Here $M\in{\mathbb{Z}}_{+}^{m\times n},\boldsymbol{b}\in{\mathbb{Z}}_{+}^{m}$ and $\boldsymbol{c}\in{\mathbb{Z}}_{+}^{n}$ .

The special case of CMKPC where there is only a single knapsack constraint and the conflict graph $([n],E)$ is given by the union of some disjoint cliques, was first investigated by Ibaraki et al. [22, 23]. Later, de Farias et al. [11] studied inequalities that define facets of the convex hull of its feasible set. Later, Hifi and Michrafy [18], Pferschy and Schauer [30], Luiz et al. [26] dealt with the knapsack problem with general conflict graph, but with binary variables.

Within the implementation of the experiments over CMKPC, we specifically considered three problem sizes: $n=20,m=5$ ; $n=60,m=4$ and $n=100,m=2$ . For each problem size we randomly generated conflict graph with respect to various graph densities. Then for each problem size and graph density, we conducted numerical experiments over 10 randomly generated instances, where we adopted the same setup as in [17]: the objective coefficients $c_{j}$ and row coefficients $M_{i,j}$ were generated uniformly at random in the interval $[10,25]$ , and the right hand side coefficients $b_{i}$ were determined by $b_{i}=0.3\cdot\textbf{1}_{n}^{\mathsf{T}}M_{i}$ , which comes from de Farias and Nemhauser [13]. We report the averaged numerical results of those 10 experiments in Section 2.

Table 2: Optimality gap of different relaxations for (CMKPC). (%)

$(n,m,\rho)$	LP	B&C	ER-ee	ER-vc	ER-vc-cuts
(20, 5, 0.05)	2.05	0.23	0.01	0.01	0.00
(20, 5, 0.1)	4.89	0.69	0.18	0.15	0.00
(20, 5, 0.35)	17.82	1.89	6.83	5.18	0.00
(20, 5, 0.6)	57.35	0.65	41.61	29.27	0.00
(60, 4, 0.05)	4.37	0.23	0.26	0.23	0.00
(60, 4, 0.1)	10.37	0.38	0.82	0.79	0.02
(60, 4, 0.15)	25.90	5.49	11.96	11.96	0.76
(60, 4, 0.2)	41.90	11.68	26.51	25.60	1.78
(60, 4, 0.35)	102.17	15.72	79.01	77.78	3.73
(60, 4, 0.6)	220.51	21.21	187.36	161.09	3.90
(100, 2, 0.05)	13.68	0.18	0.91	0.91	0.00
(100, 2, 0.1)	29.24	6.29	10.99	10.99	1.07
(100, 2, 0.15)	54.78	20.57	40.58	40.57	8.14
(100, 2, 0.2)	93.45	22.76	70.12	69.90	9.52

The numerical results in Section 2 further illustrate the great performance of our proposed extended relaxation when enhanced with cutting-planes. One can also see that, when the conflict graph is sparse, the extended relaxation from either the edge-by-edge formulation $\mathcal{M}$ or the vertex-cover-based formulation $\mathcal{E}_{\mathcal{T}}(P)$ can actually provide a decent approximation value for the corresponding LPCC. However, when the conflict graph becomes denser, those additional cutting-planes are able to dramatically further close the optimality gap.

4.2.3 LPCC with 1-regular conflict graph

For the last type of instances, we considered the special case of LPCC with 1-regular conflict graph, which is the problem studied in Sect. 4.2 of [27]:

\displaystyle\begin{split}\text{maximize}\quad&\boldsymbol{f_{x}}^{\mathsf{T}}\boldsymbol{x}+\boldsymbol{f_{y}}^{\mathsf{T}}\boldsymbol{y}+\boldsymbol{f_{z}}^{\mathsf{T}}\boldsymbol{z}\\ \text{subject to}\quad&A\boldsymbol{x}+B\boldsymbol{y}+C\boldsymbol{z}\leq\boldsymbol{d},\\ &y_{i}\cdot z_{i}=0,\quad\forall i\in[n]\\ &0\leq\boldsymbol{x}\leq\textbf{1}_{p},\ 0\leq\boldsymbol{y},\boldsymbol{z}\leq\textbf{1}_{n}.\end{split}

(1R)

Here $p,n\in{\mathbb{N}}$ , $\boldsymbol{f_{x}}\in{\mathbb{R}}^{p}$ , $\boldsymbol{f_{y}},\boldsymbol{f_{z}}\in{\mathbb{R}}^{n}$ , $A\in{\mathbb{R}}^{m\times p}$ , $B,C\in{\mathbb{R}}^{m\times n}$ , $\boldsymbol{d}\in{\mathbb{R}}^{m}$ .

We generated 25 instances of (1R) for each set of problem size using the same setup as in [27] (Sect. 4.2). In detail:

1.

The entries of vectors $\boldsymbol{f_{x}},\boldsymbol{f_{y}},\boldsymbol{f_{z}}$ are integers generated uniformly at random between -15 and 5;
2.

The entries of $A$ and $B$ are integers generated uniformly at random between -20 and 30;
3.

The entries of $C$ are obtained by generating integers $U_{i,j}$ uniformly at random between -10 and 10, and then by computing $C_{i,j}=-B_{i,j}+(\operatorname{sign}(B_{i,j})+0.5)^{-1}U_{i,j}$ ;
4.

The entries of $\boldsymbol{d}$ are obtained by generating reals $\theta_{j}$ uniformly at random between 0 and 1, and then by computing $d_{i}=\lfloor\theta(B_{i}+C_{i})\textbf{1}_{n}\rfloor$ .

Unlike in [27], where the authors only considered problem size $n=6,p=10,m=10$ , here we also considered another two sets of problem size: $n=20,p=10,m=5$ and $n=20,p=20,m=20$ .

For LPCC with 1-regular conflict graph, when constructing the vertex-cover-based extended relaxation, we chose $\{p+1,\ldots,p+n\}$ as the vertex cover, which are the set of indices correspond to the $\boldsymbol{y}$ -components. It is not hard to observe that, in this case, the edge-by-edge extended relaxation (11) coincides with such vertex-cover-based extended relaxation. Therefore, we do not report results of ER-ee. Furthermore, when the conflict graph is 1-regular, it will not contain any odd cycle, odd anti-cycle, or clique with size larger than 2, so for ER-vc-cuts, the cutting-planes we added into $\mathcal{E}_{\mathcal{T}}(P)$ only came from the BQP cuts in Section 4.1.3. We report the detailed results in Section 3.

Table 3: Optimality gap of different relaxations for (1R). (%)

$(n,p,m)$	LP	B&C	ER-vc	ER-vc-cuts
(6, 10, 10)	30.41	16.27	0.83	0.70
(20, 10, 5)	13.64	3.36	0.29	0.28
(20, 20, 20)	322.87	98.29	0.60	0.46

As we have argued in Section 2.2, for LPCC with 1-regular conflict graph, our proposed extended relaxation coincides with the ERLT relaxation in [27]. For this class of instances, the above Section 3 demonstrates the great performance of such extended relaxation, which confirms that ERLT relaxation can be significantly stronger than those available in literature, as remarked in [27]. Notice that when the conflict graph is 1-regular, the density of the edges is simply $n/\binom{2n}{2}=1/(2n-1)$ , which means that 1-regular conflict graphs are quite sparse. As we have also observed in Section 4.2.2, our extended relaxation can generally provide much better results when the conflict graph is sparse. Therefore, in some sense, this justifies the great performance of ERLT for this type of problems. Moreover, the last column of ER-vc-cuts shows that, despite the great performance of ERLT relaxation as shown in column ER-vc, additional BQP cuts can still further close the optimality gaps.

5 Conclusion

In this paper, we studied linear relaxations in an extended space for linear programs with general complementarity constraints, which generalizes the recent convexification technique called ERLT developed by Nguyen et al. [27]. We then proposed a few classes of cutting-planes to further strengthen the linear relaxation. We presented numerical experiments that showcase the significant improvement obtained from the addition of those cuts. To facilitate the future practical uses, one interesting future direction is the study of efficient separation algorithms for those cuts in the extended space. We believe that this paper provides a new perspective for developing branch-and-cut approaches for solving LPCCs with general conflict graph.

References

[1] Agostinho Agra, Mahdi Doostmohammadi, and Cid C. de Souza. Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph. Discrete Optim., 21:42–70, 2016.
[2] Alper Atamtürk, George L. Nemhauser, and Martin W. P. Savelsbergh. Conflict graphs in solving integer programming problems. European J. Oper. Res., 121(1):40–55, 2000.
[3] Alper Atamtürk, George L. Nemhauser, and Martin W. P. Savelsbergh. The mixed vertex packing problem. Math. Program., 89(1, Ser. A):35–53, 2000.
[4] Egon Balas. Intersection cuts—a new type of cutting planes for integer programming. Operations Res., 19:19–39, 1971.
[5] Egon Balas. Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J. Algebraic Discrete Methods, 6(3):466–486, 1985.
[6] Egon Balas. Disjunctive programming: properties of the convex hull of feasible points. Discrete Appl. Math., 89(1-3):3–44, 1998.
[7] Evelyn Martin Lansdowne Beale and John A Tomlin. Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. OR, 69(447-454):99, 1970.
[8] B. Cao. Transportation problem with nonlinear side constraints: a branch and bound approach. Z. Oper. Res., 36(2):185–197, 1992.
[9] M. Conforti, G. Cornuejols, and G. Zambelli. Integer Programming. Springer Publishing Company, Incorporated, 2014.
[10] IR de Farias, Ellis L Johnson, and George L Nemhauser. Branch-and-cut for combinatorial optimization problems without auxiliary binary variables. The Knowledge Engineering Review, 16(1):25–39, 2001.
[11] IR de Farias, Ellis L Johnson, and George L Nemhauser. Facets of the complementarity knapsack polytope. Mathematics of Operations Research, 27(1):210–226, 2002.
[12] IR de Farias, Ernee Kozyreff, and Ming Zhao. Branch-and-cut for complementarity-constrained optimization. Mathematical Programming Computation, 6(4):365–403, 2014.
[13] IR de Farias and George L Nemhauser. A polyhedral study of the cardinality constrained knapsack problem. Math. Program., 96(3, Ser. A):439–467, 2003.
[14] Alberto Del Pia, Jeff Linderoth, and Haoran Zhu. New classes of facets for complementarity knapsack problems. arXiv preprint arXiv:2203.02873, 2022.
[15] Michel Deza and Mathieu Dutour Sikirić. Enumeration of the facets of cut polytopes over some highly symmetric graphs. Int. Trans. Oper. Res., 23(5):853–860, 2016.
[16] Michael C Ferris and Jong-Shi Pang. Engineering and economic applications of complementarity problems. Siam Review, 39(4):669–713, 1997.
[17] Tobias Fischer and Marc E. Pfetsch. Branch-and-cut for linear programs with overlapping SOS1 constraints. Math. Program. Comput., 10(1):33–68, 2018.
[18] Mhand Hifi and Mustapha Michrafy. Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem. Computers & operations research, 34(9):2657–2673, 2007.
[19] Jing Hu, John E. Mitchell, Jong-Shi Pang, Kristin P. Bennett, and Gautam Kunapuli. On the global solution of linear programs with linear complementarity constraints. SIAM J. Optim., 19(1):445–471, 2008.
[20] Jing Hu, John E. Mitchell, Jong-Shi Pang, and Bin Yu. On linear programs with linear complementarity constraints. J. Global Optim., 53(1):29–51, 2012.
[21] Toshihide Ibaraki. The use of cuts in complementary programming. Operations Research, 21(1):353–359, 1973.
[22] Toshihide Ibaraki. Approximate algorithms for the multiple-choice continuous knapsack problems. J. Oper. Res. Soc. Japan, 23(1):28–63, 1980.
[23] Toshihide Ibaraki, Toshiharu Hasegawa, Katsumi Teranaka, and Jiro Iwase. The multiple-choice knapsack problem. Journal of the Operations Research Society of Japan, 21(1):59–95, 1978.
[24] Robert G Jeroslow. Cutting-planes for complementarity constraints. SIAM Journal on Control and Optimization, 16(1):56–62, 1978.
[25] László Lovász. Semidefinite programs and combinatorial optimization. In Recent advances in algorithms and combinatorics, pages 137–194. Springer, 2003.
[26] Thiago Alcântara Luiz, Haroldo Gambini Santos, and Eduardo Uchoa. Cover by disjoint cliques cuts for the knapsack problem with conflicting items. Oper. Res. Lett., 49(6):844–850, 2021.
[27] Trang T. Nguyen, Jean-Philippe P. Richard, and Mohit Tawarmalani. Convexification techniques for linear complementarity constraints. J. Global Optim., 80(2):249–286, 2021.
[28] Manfred Padberg. The Boolean quadric polytope: some characteristics, facets and relatives. Math. Programming, 45(1, (Ser. B)):139–172, 1989.
[29] Manfred W. Padberg. On the facial structure of set packing polyhedra. Math. Programming, 5:199–215, 1973.
[30] Ulrich Pferschy and Joachim Schauer. The knapsack problem with conflict graphs. J. Graph Algorithms Appl., 13(2):233–249, 2009.
[31] H. D. Sherali, R. S. Krishnamurthy, and F. A. Al-Khayyal. Enhanced intersection cutting-plane approach for linear complementarity problems. J. Optim. Theory Appl., 90(1):183–201, 1996.
[32] Hanif D. Sherali and Warren P. Adams. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math., 3(3):411–430, 1990.
[33] Piyashat Sripratak, Abraham P Punnen, and Tamon Stephen. The bipartite boolean quadric polytope. Discrete Optimization, page 100657, 2021.
[34] Minghe Sun. A tabu search heuristic procedure for solving the transportation problem with exclusionary side constraints. Journal of Heuristics, 3(4):305–326, 1998.
[35] Admi Syarif and Mitsuo Gen. Solving exclusionary side constrained transportation problem by using a hybrid spanning tree-based genetic algorithm. Journal of Intelligent Manufacturing, 14(3):389–399, 2003.