数理解析研究所講究録
1004 巻 1997 年 168-189

168

A Polyhedral Approach for Nonconvex Quadratic Programming
Problems with Box Constraints
東京工業大学 矢島安敏 (Yasutoshi Yajima)
東京工業大学 藤江哲也 (Tetsuya Fujie)

1Introduction

We consider the following nonconvex quadratic programming problem with box constraints:(1.1)$n+CX..$ ,$(P)|\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{n}\dot{\mathrm{u}}\mathrm{S}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{C}\mathrm{t}\mathrm{t}\mathrm{o}\mathrm{z}\mathrm{e}0\leq f(X)=XQ\tau_{1}XXi\leq,i=1,T2,.,$where $x^{T}=(x_{1}, x_{2}, \ldots, X_{n})$ is a variable vector of size $n,$
is a symmetric $n\cross n$matrix, and is a vector of size . If is a convex function, problem $(P)$ is an easy
convex minimization problem and a lot of standard convex nonlinear algorithms canbe applied for solving $(P)$ . Also, if is a concave function, i.e., matrix is negative
semidefinite, it is well known that problem $(P)$ has a globally optimal solution at anextreme point of box constraints. Problem $(P)$ is, therefore, equivalent to the folowing
quadratic zero-one programming:
$Q$

$c$

$f$

$n$

$Q$

$f$

(1.2)

$(IQ)|\mathrm{S}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{Z}\mathrm{e}\mathrm{t}0x_{i}\in\{0, 1xQ_{X}\tau Tx+C\},i=1,2,$$\ldots,$$n$.

Many methods have been proposed for solving $(IQ)$ . Among them are branch andcutting plane methods
bound algorithms $[12, 15]$ , linear relaxation methods
for solving equivalent linear zero-one integer programs or $\max$-cut problems [2, 14, 4],$[11]$ . In thiseigenvalue methods $[7, 16]$ , and semidefinite relaxationar.ticle,
.
$(P)$
is
indefinite.
It
that
the
is
one ofproblemwe consider the problem
when
seems
the simplest but the toughest global optimization problems.
Only a few methods have been proposed. Coleman and Hulbert [6] propose an
efficient algorithm for obtaining a local optimal solution of the problems. Hansen etpropose necessary conditions for optimality for $(P)$ . They also propose some kindof active set strategy and solve the problem optimally by branch and bound methods.
We will propose a polyhedral approach which is closely related to the linearization
technique proposed by Padberg [14] for solving $(IQ)$ . He linearizes the quadratic terms
by introducing new variables$\mathrm{a}\mathrm{n}\mathrm{d}/\mathrm{o}\mathrm{r}$$\mathrm{m}\mathrm{e}\mathrm{t}\mathrm{h}_{0}\mathrm{d}_{\mathrm{S}}.$$Q$$\mathrm{a}1.[9]$$x_{i}x_{j}$(1.3)$y_{j}\dot{.}=x_{i}x_{j}$, for all $1\leq i<i\leq n$ .

It is easy to verify that problem $(IQ)$ is equivalently reduced into the following Iinear
zero-one integer programming problem:

169

(1.4)

$| \mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{S}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}\mathrm{m}\mathrm{i}\mathrm{Z}\mathrm{e}y_{ij}\in\dot{.}\{0",1y_{ij}x_{i}i<\sum_{y_{*j}}j\in Q_{j}\leq Xiyij\leq x_{j},X_{i}.+Xj-1\{0yij1\},i=1,2,..

,n+cX\},\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{a}111\leq i’<\tau j\leq\leq n,\cdot$,

is a $(i,j)$ -element of matrix . We note thatwhere
: if $x_{i}\in\{0,1\}$ . Therefore,
without loss of generalities, we can replace the quadratic terms
tofor all $i=$
$1,2,$, and assume be a zero diagonal matrix.
He considers the convex hull of zero-one vectors satisfying the constraints of (1.4).
He calls it Boolean quadric polytope (BQP) and proposes three families of facets,
named, the clique-inequality, the cut-inequality and the generalized cut inequality.
Also, Simone [22] shows that the BQP is the image of the cut polytope
definedby [3], and that the polyhedral structure of CP can be easily reduced to those of BQP.
See also $[4, 5]$ for further details.
In this article, we will apply the same linearizing technique to the case whenare continuous between and 1. To linearize the problem, we will also introduce newvariables$Q$$Q_{ij}$$x_{i}^{2}=x$$x_{i}^{2}$$\ldots.’$x_{i}$$Q$n$$(\mathrm{C}\mathrm{P})$$x_{i}’ \mathrm{s}$

$0$

(1.5)

$y_{ij}=x_{i}x_{j}$,for all $1\leq i\leq j\leq n$ ,and consider set $QP$ and its convex hull $QP^{C}$ defined below:(1.6)$QP–$ { $(x,y)\in R^{n}\cross R^{\frac{\mathfrak{n}(n+1)}{2}}|0\leq x_{i}\leq 1,$(1.7)$QP^{C}=cmv\{QP\}$ .

$y_{ij}=x:x_{j}$for all$1\leq i\leq j\leq n$},

Here, the difference between $QP^{C}$ and BQP must be noted. Firstly, $QP$ has addi$(i=1,2, \ldots , n)$ which correspond totional variables. Since takes an arbitraryvalue between and 1,
can not be replaced by . Secondly, $QP^{C}$ is not a polyhedral
set any longer. Vertices of $QP^{C}$ consists of not only 0-1 vertices but also non integer
vertices. However, ignoring these additional variables , any 0-1 vertices of $QP^{C}$ are
identical to those of BQP. $QP^{C}$ can be viewed as a continuous generalization of BQP.
In a series of articles [18, 19, 21], Sherali et al. developed the same linearization
method for solving general nonconvex quadratic programming problem. Their idea
can be viewed as a technique for approximating $QP$. They take all possible pairwise
product of the original inequalities$x_{i}^{2}$$y_{ii}$$0$$x_{i}^{2}$$x_{i}$$y_{ii}$(1.8)$x_{i}\geq 0,$$i=1,2,$ $\ldots,n$$-x_{i}\geq-1,$$i=1,2,$$\ldots,$$n$,

and generate the following linear inequalities(1.9)(1.10)(1.11)(1.12)$x:+x_{j}-1$$\leq$$0$$\leq$$y:j$$y_{ij}$$\leq$$\leq$$y_{ij}$$y_{ij}$$x_{i}$$x_{j}$,,,,$x_{i}$

170by replacing quadratic term
$QP^{0}=$$x.\cdot x_{j}$with $y:j$ for all $1\leq i\leq j\leq n$ . Let us define{ $(x,y)|(x,y)$ satisfies $(1.8)\sim(1.12)$ },and consider the folowing linear programming problem:(1.13) Minimize. $+c^{T}x|(x, y)\in QP^{0}\}$ ,$\{2\sum_{i<j}Q:jy_{ij}+\dot{.}\sum_{=1}^{n}Q_{i}iy_{i*}$whereis a $(i,j)$ element of matrix . Since $QP^{0}\supseteq QP$ linear programming
problem (1.13) gives a lower und for $(P)$ .
Recently, some authors $[8, 17]$ propose senidefinite relaxations for general nonconvex
quadratic problems. Let us denote the positive semidefiniteness of a matrix
by. They approximate (1.5) by the positive semidefinite, orequivalently,$Q$$Q_{j}\dot{.}$$\mathrm{b}o$$A$$A\succeq \mathrm{O}$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}.\mathrm{Y}-xx\backslash \tau\succeq 0$$\succeq 0$ ,(1.14)

where is a symmetric matrix with element . Therefore, a lower bound for $(P)$ is
obtained by solving the semideffiuite programning problem:$\mathrm{Y}$$y_{ij}$(1.15) Minimize $\{2.\cdot\sum_{<j}Qijy_{i}j+\sum_{i=1}^{n}Qiiy_{i:}+c^{T}x|(x, y)\in QP^{SDP}\}$ ,where(1.16)$QP^{SDP}=QP^{0}\cap${ $(x,y)|(x,y)$ satisfies (1.14)}.

Many algorithms [1, 10, 13, etc.] have been proposed for solving (1.15).
propose seve al classes of valid linear inequalities of $QP$. It
In thi article, wewill be shown that a polytope defined by our inequalities is tighter than that defined by$(1.9)\sim(1.12)$ . We also propose cutting plane
employing these inequalities
as cutting planes. The article is orgmized as follows. In Section 2, we introduce
notation and some basic
ults. Sections 3 is devoted to propose several classes of$QP$. We ako show that the se inequalities are closely related to thevalid inequalities of
facets of BQP. In Section 4, we describe cutting plane algorithms for solving $(P)$ . We
also describe heuristic procedures for generating cutting planes. Results of preliminary
computational experiments how that our inequalities generate a polytope which is afairly nice approximation of $QP$.
$s$$\mathrm{w}\mathrm{i}\mathrm{l}$$r$$\mathrm{a}_{01}\cdot \mathrm{i}\mathrm{t}\mathrm{h}\mathrm{m}s$$r\mathrm{e}s$$s$2Basic Results and Notation

Let us consider the following indefinite quadratic programming problem:

171(2.17)$(P)|\mathrm{S}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{Z}\mathrm{e}0\leq X_{i}\leq 1,if(x)=X^{\tau T}Q_{X}+cx2=1,,$$\ldots,n$,and its associated convex programming problem with linear objective function:(2.18)

Minimize$f_{L}(x, y)=2 \sum_{:<j}Qiiyij+\sum_{i=1}^{n}Q_{i}iy_{ii}+c^{T}x$

Subject to$(x, y)\in QP^{C}$$(P_{L})$

Theorem 2.1 Problem
solution of $(P)$ .

.

has an optimal solution$(P_{L})$$(x^{*}, y^{*})$

such that$x^{*}is$an optimal

Proof It is obvious that any vertex of $QP^{C}$ satisfies (1.5), and that problem
has an optimal solution among the vertices of $QP^{C}$ . Then, finding an optimal vertex
ofamounts to solve the problem $(P)$ .
$(P_{L})$$(P_{L})$$\square$

In order to propose valid inequalities for $QP^{C}$ , we will use the following notation.
Let $N$ be a set of indices $N=\{1,2, \ldots, n\}$ . For any
we define polynomials$S\subseteq N$$Vs(X)=i \sum_{\in s}x_{i}$$V_{S}(_{X^{2}})=:,\in\sum x_{i}^{2}s$ ’

and$E_{S}(y)= \sum_{\in i,is,i<j}y_{ij}$.

such that
Moreove.r, for any$..(S, T)=$ { $(i,j)|i<j$ and either$S\cap T=\emptyset$$S,$ $T\subseteq N$

let us denote$i\in S,$ $j\in T$

T,$, or $i\in$j-\in
S$ }.

We define$E_{S,T}(y)= \sum_{)(i,j)\epsilon(s,T}y_{ij}$.

We note that if $(x,y)\in QP$ then $E_{S,T}(y)=V_{S}(x)V\tau(X)$ .
The following lemma plays an important role in this article.
Lemma 2.2 Let(2.19)
where
that

$S$

be a subset of $N$ and$t$

be a real number between$-(\alpha+\beta^{2})\leq \mathrm{n}\dot{\mathrm{u}}\mathrm{n}\{-Vs(x^{2})|V_{S}(X)=t, 0\leq x_{i}\leq 1, i\in S\}$$\alpha$and$\beta$

$0$

and

$|S|$

. Then,are arbitrary nonnegative integer and real number, respectively, such$\alpha+\beta=t$.

Moreover, equality in (2.19) is established when$\alpha=\lfloor t\rfloor$

.

172

optimalProof We note that (2.19) is a concave minimization problem and has, wheresolution among the vertices, whose objective values are equal$\mathrm{m}$$\mathrm{t}\mathrm{o}-(I+r^{2})$$I=\lfloor t\rfloor$, and $r=t-I$ .

Also, it is obvious to see$-(I+r^{2})\geq-(\alpha+\beta 2)$

for any nonnegative integer3$\alpha$and realsuch that $\alpha+\beta=t$ .

$\beta$$\square$Cutting Planes

Now, we are ready to propose several classes of valid inequalities for $QP$.

Theorem 3.3 (Clique Type Inequality) For any
the following inequality$S\subseteq N$

and any integer$\alpha,$$0\leq$$\alpha\leq|S|_{f}$(3.20)$\alpha V_{S}(x)-E_{S}(y)\leq\frac{\alpha(\alpha+1)}{2}$is valid for $QP$.

Proof For any $(x, y)\in QP$ , let $t=V_{S}(x)$ . Then we have$\{V_{S}(X)\}2$$=$$V_{S}(x^{2})+2E_{S}(y)$$=$$2E_{S}(y)$$=$$t^{2}$$t^{2}$,,$t^{2}-V_{S}(X2)$.

any nonnegative integer
By Lemma 2.
is bounded below by$2,f\mathrm{o}\mathrm{r}$(3.21)$2E_{S}(y)=t-V2s(x^{2})\geq t^{2}-(\alpha+\beta^{2})$or equivalently, for any integer

2 $E_{S}(y)$$\alpha$and real$\alpha$$\beta$such that $\alpha+\beta=t,$ $2E_{S}(y)$,such that $0\leq\alpha\leq|S|$ , we obtain,$\geq$$(\alpha+\beta)^{2}-(\alpha+\beta 2)$$=$$2\alpha(\alpha+\beta)-\alpha(\alpha+1)$$=$$2\alpha V_{S}(X)-\alpha(\alpha+1)$,,

which completes the proof.

$\square$with $|S|\leq 3$ and any integer
In [14], Padberg shows that for any$\alpha\leq|S|-2$ , inequalities (3.20) define facets of BQP. The idea of this proof can beapplied for BQP in the folowing way. Let$S\subseteq N$$\alpha,$$1\leq$173(3.22)$\overline{QP}=${$(x,\overline{y})\in R^{n}\cross R^{n(n-1)}/2|0\leq x_{i}\leq 1,$$y_{ij}=x_{i}x_{j}$for all $1\leq i<j\leq n$ }.

$(i=1, \ldots,n)$ and that
does not have elements such that
We note that
. It is straight forward to see that. the proof of Theorem 3.3
BQP is contained inholds true foras well as for $QP$. It should be emphasized that inequalities (3.20)
are not only valid for the convex
but also facets for BQP.
More generally, we have the following theorem:$\mathrm{v}\mathrm{e}\mathrm{C}\mathrm{t}_{0}\mathrm{r}\overline{y}$$y_{ii},$$\overline{QP}$$\overline{QP}$$\mathrm{h}\tau \mathrm{f}\mathrm{f}\mathrm{i}0\mathrm{f}\overline{QP}$

Theorem 3.4 (Cut Typeing inequality(3.23)) For any $S,T\subseteq N$ and integer , the follow$\alpha$$\mathrm{I}\mathrm{n}\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{t}\sim.\mathrm{y}$$E_{S}(y)+E_{T}(y)-Es, \tau(y)-\alpha V_{S}(X)+(\alpha+1)V_{T}(x)+\frac{\alpha(\alpha+1)}{2}\geq 0$

is valid for $QP$.

We note that inequality (3.23) includes (3.20) as a special case when$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{f}$. For any

$T=\emptyset$.

$(x, y)\in QP$, let$I_{S}=\lfloor V_{S}(x)\rfloor,$$r_{S}=V_{S}(x)-Is$$I_{T}=\lfloor V_{T}(x)\rfloor,$$r_{T}=V_{T}(x)-I\tau$and.

From (3.21), we have
$2E_{S}(y)=\{V_{S}(x)\}2-V_{S}2(X)\geq(I_{S}+r_{S})^{2}-(I_{S}+r_{S}^{2})$,and$2E_{T}(y\rangle=\{V_{T}(X)\}2-V_{\tau}2(X)\geq(I_{T}+r_{T})^{2}-(I_{T}+r_{T}^{2})$Then, we have the$\mathrm{f}\mathrm{o}\mathrm{l}\mathrm{o}\mathrm{W}\mathrm{i}\mathrm{n}\mathrm{g}$.

inequality.

$E_{S}(y)+E \tau(y)-E_{S},T(y)-\alpha Vs(x)+(\alpha+1)V\tau(_{X})+\frac{\alpha(\alpha+1)}{2}$$=E_{S}(y)+E \tau(y)-Vs(X)V_{T}(x)-\alpha Vs(X)+(\alpha+1)V\tau(X)+\frac{\alpha(\alpha+1)}{2}$$\geq$$\frac{1}{2}\{(IS-IT^{-}\alpha)(IS-I\tau-\alpha-1+2r_{S}-2r\tau)+2r_{T}(1-r_{S})\}$.

Let $I=I_{S}-I_{T}-\alpha$ and $\theta=-1+2r_{S}-2r\tau$ , we define$F(I)=I(I+\theta)+2rT(1-rs)$ .

Since $0\leq r_{T},r_{S}<1$ , we have $-3<\theta<1$ and $r_{T}(1-rs)\geq 0$ . Then, it is easy to seethat for any integer such that $I\leq 0$ , or $I\geq 3$
$I$

174

$F(I)\geq 0$.

When $I=1$ we have$F(1)=2r_{S}(1-r\tau)\geq 0$

and also when $I=2$$F(2)=2(1-r_{T}\rangle(1+r_{S})+2r_{S}\geq 0$.

$F(I)$ is, therefore, nonnegative for any integer $I$. We have,$E_{S}(y)+E_{T}(y)-Vs(X)V \tau(X)-\alpha V_{S}(X)+(\alpha+1)V_{T}(X)+\frac{\alpha(\alpha+1)}{2}\geq 0$

and the proof is complete.

$\square$In [14], Padberg shows that for any $S,T\subseteq N$ such that $S\cap T=\emptyset,$ $|S|\geq 1$ ,define facets of BQP when $\alpha=|T|-|S|$ . Also in
and$[4, 20]$ , inequalities (3.23) have been introduced by considering the product of two
linear functions below:$|T|\geq 2,\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{e}\mathrm{s}(3.23)$(3.24)$l(x)=(V_{S}(x)-V_{T}(X)-\alpha)(Vs(X)-V\tau(x)-\alpha-1)$ ,where a is an arbitrary integer. The nonnegativity of $l(x)$ is obvious if is integer.
toand to , we can obtain (3.23), which are
Expanding (3.24) and replacing
considered as valid inequalities for BQP. In our proof, however, the same inequalities
can be obtained without using 0-1 properties.
Finally, we will introduce some classes of inequalities which are obtained easily.
$x$$x_{i}^{2}$$x_{i}x_{j}$$y_{ij}$$x_{i}$

Theorem 3.5 For any $i\in N$ and real , the following inequality$r$(3.25)$y_{ii^{-2}}rx:+r^{2}\geq 0$

is valid for $QP$. Moreover, for any $i,j\in N$ such that $i<j$ , and any $r_{1},r_{2}\in R$ , the.
following inequality(3.26)$r_{1}^{2}y_{ii}+r_{2}^{2}y_{jj}-2r_{1}r_{2}y_{i}j\geq 0$

is valid for $QP$.

175

Proof For any$x_{i}$

and real $r\in R$ , the following inequality$(x_{i}-r)2\geq 0$

holds. Expanding the-side and replacing
to , we obtain (3.25), whichholds true for any $(x,y)\in QP$. It is easy to show inequality (3.26) in the same way.
$\mathrm{l}\mathrm{e}\mathrm{f}\mathrm{t}-\mathrm{h}\mathrm{a}\mathrm{n}\mathrm{d}$$x_{i}^{2}$$y_{*}.\dot{.}$$\square$

Let

Inequaliti.es (3.25) and$(3.26)\sim$

are closely related to positive semidefinite cone (1.14).

$X=$ ,and let us consider the determinant ofprincipal minors wluich consist of the first$X$
and therow of . We have the following convex sets
$2\cross 2$$i\mathrm{t}\mathrm{h}$(3.27)$\{(x, y)|y_{ii}-x_{i}^{2}\geq 0\}$

, $i=1,2,$$\ldots,n$,which include $QP^{SDP}$ . We see that for any $r\in R$ ,$yii^{-}2rx:+r=02$

defines a supporting hyperplane of (3.27) at $x_{i}=r,$ $y_{i:}=r^{2}$ , and that this hyperplane generates inequality (3.25). Also, the determinant ofprincipal minors not$X$containing the first row of defin the following convex sets
$2\cross 2$$e$(3.28)$\{(x, y)|y_{ii}y_{jj}-y_{ij}^{2}\geq 0\}$For any$r_{1},$$r_{2}\in R$, for all $i<j$ .

,$r_{1}^{2}y_{ii}+r_{2}^{2}y_{jj}-2r_{1}r2yij=0$, and generdefines a upporting hyperplane of (3.28) atates inequality (3.26).
be a given vector which does not satisp the positive semiMoreover, letbe an $n+1$ dimensional square matrix defined
definite condition (1.14), and let
below:$y_{ii}=r_{2}^{2},$$s$$y_{jj}=r_{1}^{2},$$y_{ij}=r_{1}r_{2}$$(\overline{x},\overline{y})$$\overline{X}$$\overline{X}=$ ,(3.29)
where$\overline{\mathrm{Y}}$is a symmetric matrix with element

Lemma 3.6 If$QP^{SDP}$$(\overline{x},\overline{y})\not\in QP^{SDP}$$\overline{y_{i}j}$. The following lemma has been shown.

, then the following inequality separates.

(3.30) $v^{T}v\geq 0$ ,
where

$v$

is an eigenvector$a\mathit{8}SoCiated$with a negative eigenvalue.

$of\overline{X}$$(\overline{x},\overline{y})$

from

176

Proof See [17].

$\square$

Algorithms

4

In this section, we describe our algorithms and the results of our numerical experiments.
. Section 4.1 is devoted toFirstly, we show the tails of.the cutting plane
procedures for generating the violated inequalities. We will also describe
strategies for electing, adding and dropping these violated inequalities.
$\mathrm{d}.e$$\mathrm{a}\mathrm{l}\mathrm{g}\mathrm{o}\mathrm{r}\prime \mathrm{i}\mathrm{t}\mathrm{h}\mathrm{m}$$\mathrm{d}\mathrm{e}\mathrm{s}\mathrm{c}\mathrm{r}\dot{\mathrm{i}}\mathrm{b}\mathrm{e}$

$s$

4.1

Generating Cutting Planes

For simplicity, in the rest of thi section, let us denote the clique and the cut type
inequality by$s$$l_{S}^{\mathrm{c}l}(x,y; \alpha)\equiv\alpha V_{s(}X)-E_{s}(y)-\frac{\alpha(\alpha+1)}{2}\leq 0$and$l_{s\tau 1}^{\mathrm{c}t}(X, y;\alpha)$$\equiv$$-E_{S}(y)-E_{\tau}(y)+E_{s,\tau(y)}+ \alpha Vs(X)-(\alpha+1)V_{\tau(}x)-\frac{\alpha(\alpha+1)}{2}\leq 0$,

respectively. Associated with these cuts, let us define the following quadratic functions:(4.31)$q_{S}^{\mathrm{c}l}(X, y)= \frac{1}{2}\{Vs(X)\}\{V_{s}(X)-1\}-Es(y)$and(4.32),$q_{s,T}^{\mathrm{C}}t(x, y)=q^{\mathrm{c}l}s(X, y)+q_{\tau^{l}}^{\mathrm{c}}(x, y)+E_{S,T}(y)-Vs(X)V_{\tau}(X)$which can be considered as the lower bounds for.
tively, in the$l_{S}^{\mathrm{c}l}(x, y;\alpha)$

and$l_{S}^{\mathrm{c}t},(\tau x, y;\alpha)$$\mathrm{f}\mathrm{o}1_{0}\mathrm{W}\mathrm{i}\mathrm{n}\mathrm{g}\dot{\mathrm{s}}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{e}$Lemma 4.7 For any(4.33)$Al\mathit{8}O$(4.34)$x,$ $y$and$q_{S}^{d}(x,y)\leq l_{S}^{d}(x,y;\alpha)$, for any

$x,$ $y$$S\subseteq N$, if$\alpha=\mathrm{L}^{V_{S}}(x)\rfloor$, then.

and $S,$ $T\subseteq NS\cap T=\emptyset$ , if$q_{S,T}^{ct}(X,y)\leq l_{S,\tau}^{\mathrm{c}t}(X,y;\alpha)$.

$\alpha=\lfloor V_{S}(X)-V\tau(X)\rfloor$, then, respec-

177

Proof It is obvious to see that$q_{s}^{d}(X, y)-l_{S}^{Cl}(X, y; \alpha)=\frac{1}{2}\{VS(_{X})-\alpha\}\{VS(_{X)}-\alpha-1\}\leq 0$

if$\alpha=\lfloor V_{s}(X)\rfloor$.

Also$q_{s,T}^{c\ell}(x, y)-l_{S}^{\mathrm{c}}i|T(X, y; \alpha)=\frac{1}{2}\{V_{S}(_{X)}-V_{\tau(x)\}\{V_{s}}-\alpha(x)-V\tau(X)-\alpha-1\}\leq 0$

if $\alpha=\lfloor V_{S}(X)-V\tau(x)\rfloor$ .
$\square$Lemma 4.7 gives ufficient conditions for generating the cutting planes. Therefore,, if we find $S\subseteq Ns$uch thatgiven a vector$s$$(\overline{x},\overline{y})$$q_{S}^{\mathrm{c}l}(\overline{x},\overline{y})>0$,

then we can generate the clique inequality$l_{S}^{cl}(X,y;\lfloor V_{S}(\overline{X})\rfloor)\leq 0$

which cuts off.
Moreover, suppose that we find $S,T\subseteq NS\cap T=\emptyset$ such that$(\overline{x},\overline{y})$$q_{s}^{cl}(\overline{X},\overline{y})+q^{\mathrm{c}\iota_{()>0}}T\overline{X},\overline{y}$.

Now, let us consider the clique inequality generat by the union ofthat
can be calculated in the following way:$e\mathrm{d}$

$S$

and

$T$

. We see$q_{s\cup T}^{\mathrm{c}l}(x, y)$$q_{s^{l}\cup}^{c}T(x, y)$$=$$\frac{1}{2}\{V_{S\cup\tau}(x)\}\{VS\cup\tau(X)-1\}-Es\cup\tau(y)$$=q_{S}^{\mathrm{c}l}(x, y)+q_{T}^{cl}(x, y)+Vs(x)V\tau_{\vee}(X.)-ES,T(y)$.

Then, we can obtain at least either the clique inequality$l_{s_{\cup}\tau}^{\mathrm{c}l}(x, y;\mathrm{L}^{V_{S\cup}}\tau(\overline{X})\rfloor)\leq 0$or the cut inequality$l_{S,T}^{\mathrm{c}t}(X, y;\lfloor V_{S}(\overline{x})-V\tau(\overline{x})\rfloor)\leq 0$,.
which cut off the vector
In our cutting plane algorithms, we solve (1.13) as the initial relaxation problem
and repeatedly solve LPs by adding violated linear inequalities until a termination
criterion holds or no cutting planes are found. We adopt the following relative error
criterion$(\overline{x},\overline{y})$(4.35)$f(x^{*})-\epsilon|f(x^{*})|\leq f_{L}\sim(\overline{x},\overline{y})$

,

178
,
is a feasible solution ofis an optimal solution of the current
where$0<\epsilon<1$$(P),$
andand. We note that since is a feasible solution of$(P)$, respectively.
give a lower and an upper bounds of
In our algorithm, we use the folowing procedures to generate violating inequalities
for a given point.
$\mathrm{L}\mathrm{P},$$(\overline{x},\overline{y})$$x^{*}$$\mathrm{Q}\mathrm{P}$$f(X^{*})$$f_{L}(\overline{x},\overline{y})$$\overline{x}$$(\overline{x},\overline{y})$Procedure TRIFirst enumerate all triples $i,j,$ $k\in N$, and generate violating clique type
inequalities
with $|S|=3$ and $\alpha=1$ , then enumerate allagain and generate violating cut type inequalities (3.23) with $|S|=1,$ $|T|=$
2 and $\alpha=1$ .
$tf\cdot iples$$(\mathit{3}.\mathit{2}\theta)$

We note that it requires $O(n^{3})$ computational time to perform this procedure andthat for each triple $i,j,$ , we can generate one clique type and thr cut type inequalities.
$k$$e\mathrm{e}$Procedure DIAG

1. For all $i\in N,$$r=\overline{x_{i}}$$if\overline{y_{*i}.}<\overline{x_{i^{2}}}$then generate inequalities (3.25) by setting.

2. For all pairs $i,j\in N,$
by setting$r_{1}^{2}=\overline{y_{jj}},$$if\overline{y_{ii}}\overline{y_{jj}}<\overline{y_{ij^{2}}}$$r_{2}^{2}=\overline{y_{ii}}$

then generate inequalities (3.26).

3. If some inequalities have been generated, then terminate.
4. Let be a matrix defined in Lemma 3.6. For all eigenvectors which, generate inequalities
are associated with negative eigenvalues of$\overline{X}$$v$$\overline{X}$$(\mathit{3}.\mathit{3}\theta)$.

We call the procedure DIAG since (3.25), (3.26) and (3.30) are the only inequalities
that contain “diagonal” variables .
$y_{ii}$

Procedure HYP

1. Enumerate all subsets of $N$ such that $|S|\leq 3$ andlet be a family of these subsets.
$S$$q_{S}^{cl}(\overline{X},\overline{y})>0$$S$

2. For all disjoint subset $S,T\in S$ , generate inequalities$l_{s_{\cup}\tau}^{\mathrm{c}l}(x,y;\mathrm{L}^{V_{S\cup T}}(\overline{X})\rfloor)\leq 0$$and/or$.

$l_{s,T}^{\mathrm{c}\ell}(X, y;\lfloor V_{S}(\overline{X})-V\tau(\overline{X})\rfloor)\leq 0$

Procedure HEU
The procedure consists of four subprocedures HE.Ul,..., HEU4.

, and

179

HEUI Execute the following

times.

$n$step 1 Generate a subset $S\subset N$ such that $|S|=3$ randomly.
step 2 For all
calculate. Let$i\in N\backslash S$$s^{*}:=.

$s_{i}:= \overline{x}:-\sum_{j\in s}\overline{y}_{ij}$and$i^{*}$\cdot\max_{\in N\backslash S}s.\cdot$

be the corresponding index.

step 3 If, quit the subprocedure. Otherwise let $S:=S\cup\{i^{*}\}$ .
step 4 Generate (3.20) with and. If $S\neq N$, go tostep 2.
$g^{*}\leq 0$$S$$\alpha=\lfloor Vs(\overline{x})\rfloor$

HEU2 The same as HEUI except that we letin step 2.

$s_{i}:= \overline{x}(\overline{x}-1)-2\sum j\in s(\overline{y}_{ij}-$$\overline{x}_{i}\overline{x}_{j})$HEU3 Execute the following

times.

$n$step 1 Generate $sub\mathit{8}eisS,T\subset N$ such that $|S|=1,$ $|T|=2$ and$S\cap T=\emptyset$

randomly.

step 2 For all $i\in N\backslash (S\cup T)$ calculate .
$s_{*}$

and$t_{i}:= \sum_{j\epsilon s}\overline{y}ij-\sum_{j\epsilon \mathrm{r}}\overline{y}_{ij}$

. Let

: and

$s^{*}>t^{*}$

be the$i_{S}^{*}$$s^{*}:=i \in N\backslash \max_{\mathrm{t}\cup T)}ss$

corresponding index. Similarly, letcorresponding index. If$:=- \overline{x}_{i}-\sum_{j\in s}\overline{y}.\cdot j+\sum_{j\in T}\overline{y}_{:j}$: and, go to step 3. Otherwise$t^{*}:=i \in N\backslash (ST)\max_{\cup}t$

be the$i_{T}^{*}$$g.\delta\backslash$to step

4.

step 3 If, quit the subprocedure. Otherwise let $S:=S\cup\{i_{S}^{*}\}$ .
step 4 If, quit the. Otherwise let $T:=T\cup\{i_{T}^{*}\}$ .
step 5 Generate (3.23) withand. If $S\cup T\neq$$N$ , go to step 2.
$s^{*}\leq 0$$t^{*}\leq 0$$\mathit{8}ubpfOCedu\Gamma e$$S,$ $T$$\mathrm{H}\dot{\mathrm{E}}$$\alpha=\lfloor V_{S}(\overline{X})-V\tau(\overline{x})\rfloor$

U4 The same as HEU3 except that we let$\overline{x}_{i}\overline{x}_{j})+2j\sum_{\in\tau}(\overline{y}ij-\overline{x}i\overline{x}_{j})$$\overline{x}:\overline{x}_{j})$and$t_{i}:= \overline{x}(\overline{x}-1)+2\sum_{j\epsilon S}(\overline{y}_{ij}.-\overline{X}_{ij}\overline{X})-2\sum_{j\epsilon T}(\overline{y}ij-$

in step 2.

In HEUI (resp. HEU2), we maximize
one. In HEU3 (resp. HEU4), we maximize$S\cup T$ one by one.

$l_{S}^{cl}(\overline{x},\overline{y};1)$

4.2

${ }$

$s::=. \overline{X}(\overline{X}-1)-2\sum_{Sj\epsilon}(\overline{y}_{j}.\cdot-$(resp.

) increasing one by(resp.
) increasing$S$$q_{s^{l}}^{c}(\overline{x},\overline{y})$$l_{S,T}^{\mathrm{c}l}(\overline{x},\overline{y}\cdot, -1)$$q_{s^{l}T}^{\mathrm{c}},(\overline{X},$$\overline{y})$Computational Experience

In this subsection, we show our computational experiences of the cutting plan methods
and the branch and bound methods.
Test problems are generated as follows. The coefficients $Q_{ij}(1\leq i\leq j\leq n)$ and$c.\cdot(1\leq i\leq n)$ of the objective function in (1.1) are integers assigned randomly between$-100$ and 100 with density . We generate ten problems for eachand . Table 4.1
$e$

$d$

$n$

$d$

180

Table 4.1: Sign of the eigenvalues of$Q$and zero eigenvalue of, negative
average number of positive
displaysgenerated matrices are full rank and have
. We can see that most of thealmost the ame number of positive and negative eigenvalues. All problems are solved
and we use CPLEX 2.0 calable library as an LP solver.
on a SUN
Throughout the rest of the article we set $\epsilon=0.01$ .
We consider the following four strategies (cuto, cutl, cut2, cut3) for the cutting plane generating phase, which is denoted by CUT phase for short.
$\mathrm{t}\mathrm{h}\mathrm{e}\sim$

$Q$

$s$

$(\mathrm{n}\mathrm{e}\mathrm{g}.)$$(\mathrm{p}\mathrm{o}\mathrm{s}.)$$Q$$\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{o}\grave{\mathrm{m}}\mathrm{l}\mathrm{y}$$s$$\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{S}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{i}_{0}\mathrm{n}1$.
generate no cutting planes, that is, just solve initialexecute TRIthen quit the hase,first execute TRI. If some cutting plan..escute DIAG.
otherwise
first execute TRI. If some cutting planes are found then quit the phase,otherwi se execute DIAG. If some cutting planes are found then quit
the phase, otherwise execute HEU.

::
cut2 :
cutO
cutl$\mathrm{L}\mathrm{P}(1.13)$$\mathrm{a},\mathrm{r}.\mathrm{e}.‘ \mathrm{f}_{\mathrm{o}\mathrm{u}\mathrm{n}}\mathrm{d}$$.\mathrm{p}$$\mathrm{e}\mathrm{x}e$

cut3

:

We detect a violating inequality as a cutting plane if the distance between
and the inequality is no less than . We first set $\delta=0.1$ and dynamically change fromone phase to the next. In our experiments, we minat the cutting plane algorithm
if no cutting plane is found with $\delta=10^{-5}$ or an optimal solution is found. The total
number of inequalities added to the initial LP is limited to 1500. We provide a routine
for deleting inequalities whose slacks are greater than 0.01.
Result of the cutting plane method are given in Tables $4.2\sim 4.4$ . In Tables 4.2
and 4.3, $m$ denotes the number of problems which are solved to optimality, and Ave.
. denote the average and the maximum cpu time in seconds, respectively. In
andTable 4.4, the average and the maximum number of the total nerated cutting planes.. ..
are shown.
$(\overline{x},\overline{y})$$\delta$$\delta$$\mathrm{t}\mathrm{e}r$$e$$\epsilon$$s$$\epsilon$${\rm Max}$$\mathrm{g}e$181

Table 4.2: The number of solved problems $(m)$ and cpu time in seconds (1)Table 4.3: The number of solved$\mathrm{p}r$oblems $(m)$ and cpu time in seconds (2)182

Table 4.4: The number of generated cutting planes

bom these tables, we can see that the performance of the cutting plane methods depend on the density of the matrix as well as . Note that algorithms given
by Hansen et
behave similarly, although their test problems are generated in asomewhat different way
ours. When matrix is sparse solving (1.13) is sufficientfor most of the problems to obtain an optimal solution. Whereas, it is necessary
to add the elaborate cutting planes when the density increases. In our computational
experiment , all test problems are solved to optimality by strategy cut2.
See Table 4.5. Here, diag shows the results of the cutting plane method whichuses procedure DIAG alone in CUT phase. cutl and cut2 are taken from Table 4.2.
Thi table indicates that combination of the triangle inequalities and the eigenvalue
is important to generate an optimal solution.
Next, we show results of a branch and bound method for $(P)$ combined with the
cutting plane method. The outline of the method is described as follows:
$Q$

$n$

$\mathrm{a}1.[9]$$Q$$\mathrm{h}\mathrm{o}\mathrm{m}$$\epsilon$$s$$\epsilon$$s$$\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{e}\dot{s}$$\epsilon$

step

$0$

Let $N:=\{(0,1)\}$ and $z^{*}:=+\infty$ .

, stop. Otherwise pick $(f,u)\in N$ : If $|N|\leq n$ , the way tostep 1 If
pick is followed by a breadth first fashion. Otherwise it is followed bya depth first hion. Let $N:=N\backslash \{(f,u)\}$ .
$N=\emptyset$$\mathrm{f}\mathrm{a}s$

step 2 Solve a (sub)problem$\leq u_{i},if(x)=x^{\tau}QX+c^{\tau}Xn=1,$$(P_{\ell,u})|\mathrm{s}_{\mathrm{u}}\mathrm{b}\mathrm{j}\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{Z}\mathrm{e}\mathrm{t}\mathrm{t}\mathrm{o}\ell_{i}\leq x_{*}$

.

$2,$

$\ldots,$.

For this purpose, use a linear transformation to yield an equivalent
problem183
Table 4.5: The effectiveness of the triangle inequaliti$es$$ndX’+$$(P_{\ell,u}’)|\mathrm{S}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{Z}\mathrm{e}0\leq X_{i}\leq \mathfrak{l}1,i=f(x)=x’\tau Q’X’+C’T1,2,\ldots,$,

where is a scalar. Solveby the cutting plane method. Let(
be its solution. Then use the transformation again to obtain asolution. If
corresponding to, go tostep 1. If
, let
and
.
$d$

$(P_{\ell,u}’)$$\overline{x’},y\neg’$$(P_{\ell,u})$$(\overline{x},\overline{y})$$f(\overline{x})<z^{*}$$x^{*}:=\overline{x}$$z^{*}-\epsilon|z^{*}|\leq f_{L}(\overline{x},\overline{y})$$z^{*}=f(\overline{x})$step 3 Select a branching variable by the following ul $e[21]$ . Calculat$r$$d_{1}= \dot{\mathrm{m}}\mathrm{n}\{\min_{1\leq k\leq n}^{1}\{\min_{\leq k<l\leq n\min}\{\min\{0_{k\ell}2q\{\mathrm{o},q’(\overline{y}kh-\overline{X}_{k}^{2})\}\}u(\overline{y}h\ell-\overline{x}k)\overline{X}_{\mathit{1}}\}\},$

$\}$

$e$

.

If $d_{1}=0$ , go to step 1. Otherwise let
be indices which give$k^{*}=f^{*}$$i^{*}=k^{*}$Ifthen. Otherwise calculate$k^{*},f^{*}$$d_{1}$.

$d_{2}(t)= \sum_{j=1}^{t-1}\min\{0,2qjt(\overline{y}_{j}t-\overline{X}j\overline{x}_{\ell})\}+\sum_{j=t+1}^{n}\min\{0,2q_{i}j(\overline{y}lj-\overline{X}_{t^{\overline{X}_{j}}})\}$$+ \min\{0, q_{t}t(\overline{y}u-\overline{x}_{t})2\}$

for $t=k^{*},f^{*}$ and let
ame vector as except thatexcept that
. Let
$s$

$f$

$\overline{u}_{i}\cdot=\overline{x}.\cdot\cdot$$\overline{f}_{i}\cdot=\overline{x}_{i}\cdot,$

and$\overline{u}$. Letbe thebe the same vector as. Go to step 1.

$i^{*}:=\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}\{d_{2(t)} :t=k^{*},f^{*}\}$$\overline{f}$$u$$N:=N\cup\{(\overline{\ell}, u), (f, \overline{u})\}$

Note that there is a choice how to solve subproblems by the cutting plane method.
Since, as seen in the previous section, all test problems are solved to optimality by$\epsilon$

184

cut2, cutl is used to solve subproblems to compare with the cutting plane methodwith cut2.
Tables 4.6 and 4.7 show the results, where BRANCH denotes the number of branchdenotes the number upda.tes of an incumbent olution
ing nodes and.
of $(P)$ .
We also implemented a locai search heuristics for $(P)$ . The’ branch and boundas folow :method is$0.\mathrm{f}$$s$$\mathrm{m}\mathrm{o}\mathrm{d}.\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{e}\mathrm{d}$$\bullet$In step .
Solve $(P)$ by a multiple start local search. Thus, let $z^{*}:=f..(x^{*})$ instead of$z^{*}:=\infty$ ,is a solution the heuristics.
where
$0$

$\mathrm{o}\mathrm{f}^{\mathrm{c}}$$x^{*}$$\bullet$$x^{*}$$s$$\mathrm{U}.\mathrm{P}\mathrm{D}\mathrm{A}\dot{\mathrm{T}}\mathrm{E}$In step 2.
Apply alocal search starting
last statement in step becomes$\mathrm{b}\mathrm{o}\mathrm{m}\overline{x}$$\dot{2}$(to obtain a better feasible point . Then the”.
then letand$‘ \mathrm{I}\mathrm{f}f(\tilde{x})<z^{*}$$\overline{x}$$x^{*}:=\tilde{x}$$z^{*}=f(\tilde{x})$Tables 4.8 and 4.9 show that the local search procedures reduce a considerable
amount of cpu time.
To conclude, we show ults of the branch and bound method with adopting heuristics and cut2 in Tables 4.10\sim 4.13. Compared with [9], our method needs more cpu
must solve many linear programming problems. Our method,
time. Thi is becau
however, can be applied for more general quadratic programs which have linear
quadratic constraints. Sherali et al. [18, 19, 21] proposed the linear ogramming relaxation for these problems, and then our proposed valid inequalities can be applied as
cutting planes since the valid inequalities for $QP$ are also valid for general quadratic
programs. On the other hand, since $QP$ strictly contains the new linearized set ofgeneral quadratic programs in general, our proposed valid inequalities might not contribute as the cutting plane. Therefore new valid inequalities including the structure
quadratic constraints should be proposed.
of linear$r\mathrm{e}s$$s\mathrm{e}\dot{\mathrm{w}}\mathrm{e}$$s$$\mathrm{a}\mathrm{n}\mathrm{d}/\mathrm{o}\mathrm{r}$$\mathrm{p}r$$\mathrm{a}\mathrm{n}\mathrm{d}/\mathrm{o}r$

References[1] Alizadeh, W. F. (1995), Interior point methods in semidefinite programming withapplication to combinatorial optimization, SIAM Joumal on Optimization, 5, 13-51.
[2] Barahona, F., J\"onger, M. and Reinelt, G. (1989), “Experiments in Quadratic 0-1
Programming,” Mathematical Programming, 44, 127-137.
[3] Barahona, F. and Mahjoub, A. R. (1986), “On the Cut Polytope,” Mathematical
Programming, 36, 157-173.
t

185

Table 4.6: Result of the branch and bound method (1)Table 4.7: Result of the br anch and bound method (2)186

Table 4.8: Resffi of the branch and bound method with heuristics (1)Table 4.9: Result of the branch and bound method with heuristics (2)

187

Table

$4.1\tilde{0}$: Final result of the branch and bound method with heuristics (1)Table 4.11: Final result of the branch and bound method with heuristics (2)188Table 4.12: Final result of the branch and bound method with heuristics (3)Table 4.13: Final result of the branch and bound method with heuristics (4)$\ovalbox{\tt\small REJECT}_{\mathrm{a}\mathrm{V}}d\mathrm{a}\mathrm{v}\mathrm{e}\max \mathrm{e}\max \mathrm{a}\mathrm{V}\mathrm{e}\mathrm{D}\mathrm{B}\mathrm{R}\mathrm{A}\mathrm{N}\mathrm{C}\mathrm{H}\mathrm{c}\mathrm{U}\mathrm{T}\mathrm{U}\mathrm{P}n=50,\mathrm{C}\mathrm{u}\mathrm{t}2\mathrm{A}\mathrm{T}\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{E}\mathrm{T}\mathrm{m}\mathrm{E}\mathrm{a}\mathrm{V}\mathrm{e}\max$-Cut Problem and Quadratic 0-1[4] Boros, E. and Hammer, P. L. (1991), “TheOptinization; Polyhedral Aspect, Relaxations and Bounds,” Annals of Operations
Research, 33, 151-180.
${\rm Max}$[5] Boros, E. and Hammer, P. L. (1993), “Cut Polytopes, Boolean Quadric PolyFunctions,” Mathematics of Operations
topes md Nomegative
Research, 18, 245-253.
$\mathrm{P}s\mathrm{e}\mathrm{u}\mathrm{d}\mathrm{o}-\mathrm{b}\mathrm{o}\mathrm{o}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{n}$Direct Active Set Algorithm for[6] Coleman, T. F. and Hulbert, L. A. (1989),
Large Sparse Quadratic Programs with Simple Bounds,” Mathematical Programming, 45, 373-406.
($‘ \mathrm{A}$Eigenvalues and the Maximun Cut[7] Delorme, C. and Poljak, S. (1993),
Problem,” Mathematical $p_{rog_{\Gamma am}}ming,$ $62$ , 557-574.
$‘(\mathrm{L}\mathrm{a}\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{C}\mathrm{i}\mathrm{a}\mathrm{n}$[8] Fbjie, T., and Kojima, M. (1995), “Semidefinite Programning Relaxation for Nonconvex Quadratic Programs,” Research Report #298, Dept. of Mathematical andComputing Sciences, Tokyo Institute of Technology.
[9] Hansen, P., Jaumard, B., Ruiz, M. and Xiong, J. (1993), “Global Minimizationof Indefinite Quadratic Fhnctions Subject to Box Constraints,” Naval Research
Logistics, 40, 373-392.

189[10] Helmberg, C., Rendl, F., Vanderbei, R. J. and Wolkowicz, H. (1996), An interiorpointforumal on Optimization, 6,
programmin..
$\mathrm{v}\mathrm{s}\mathrm{e}\mathrm{m}\mathrm{i}\mathrm{d}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}$.

$\mathrm{g},$$SI.AMJ\sim..\cdot\prime \mathit{0}$$\mathrm{m}\mathrm{e}\mathrm{t}\mathrm{h}..\mathrm{o}\mathrm{d}$342-361.

[11] Helmberg, C. and Rendl, F. (1995), “Solving Quadratic $(0,1)$ -Problems by
Semidefinite Programs and Cutting Planes,” ZIB Preprint.
$\mathrm{s}\mathrm{c}_{-}95-35$[12] Kalantari, B. and Bagchi, A. (1990), “An Algorithm for Quadratic Zero-One
Programs,” Naval Research Logistics, 37, 527-538.
[13] Kojima, M., Shindoh, S. and Hara, S. (1995), Interior-point methods for the monotone semidefinite linear complementarity problems, Research Report #282, Dept.
of Mathematical and Computing Sciences, Tokyo Institute of Technology.

[14] Padberg, M. (1989), “The Boolean Quadratic Polytope: Some Charact ristics,
Facets and Relatives,” Mathematical Programming, 45, 139-172.
$e$[15] Pardalos, P. M. and Rodgers, G. P. (1990), “Computational Aspects of a Branch
and Bound Algorithm for Quadratic Zero-One Programming,” Computing, 45,

131-144.
[16] Poljak, S. and Rendl, F. (1995), “Solving the”Discrete Applied Mathematics, 62, 249-278.

-Cut Problem using Eigenvalues,${\rm Max}$[17] Ramana, M. (1993), An algorithmicof multiquadratic and semidefinite.
thesis, Johns Hopkins University, Baltimore,programming problems,$analy_{\mathit{8}is}$$\mathrm{P}\mathrm{h}\mathrm{D}$$\mathrm{M}\mathrm{D}$[18] Sherali, H. and Alameddine, A. (1990), “An Explicit Charatcterization of theConvex Envelope of a Bivariate Bilinear Knction Over Special Polytopes,” Annals$25$ , 197-214.
of Operations$Re\mathit{8}earch,$[19] Sherali, H. and Alameddine, A. (1992), “A New Reformulation-Linearization for
Solving Bihinear Programming Problems,” Joumal of Global Optimization, 2, 397-

410.
[20] Sherali, H., Lee, Y. and Adams, W. P. (1995), “A Simultaneous Lifting Strategy
for Identifying New Class of Facets for Boolean Quadric Polytope,”
Research Letters, 17, 19-26.
$Opefation\mathit{8}$[21] Sherali, H. and Tuncbilek, C. H. (1995), “A Reformulation-Convexification Appr oach for Solving Nonconvex Quadratic Programming Problems,” J. of Global
Optimization, 7, 1-31.

[22] Simone, C. D. (1989), “The Cut Polytope and The Boolean Quadric Polytope,”
Discrete Mathematics, 79, 71-75.