# Two New Reformulation Convexification Based Hierarchies for 0-1 MIPs

Authors: Hacene Ouzia
Journal: Advances in Operations Research
 (2015)

---

## Abstract

First, we introduce two new reformulation convexification based hierarchies calledRTC and RSC for which the rank d continuous relaxations are denoted by P
^
R
T
C
d and P
^
R
S
C
d, respectively. These two hierarchies are obtained using two different convexification schemes: term convexification in the case of the RTC hierarchy and standard convexification in the case of the RSC hierarchy. Secondly, we compare the strength of these two hierarchies. We will prove that (i) the hierarchy RTC is equivalent to the RLT hierarchy of Sherali-Adams, (ii) the hierarchy RTC dominates the hierarchy RSC, and (iii) the hierarchy RSC is dominated by the Lift-and-Project hierarchy. Thirdly, for every rank d, we will prove that conv
T
d
∩
E
t
d
⊆
P
^
R
T
C
d
⊆
T
d and conv
S
d
∩
E
s
d
⊆
P
^
R
S
C
d
⊆
S
d where the sets T
d and S
d are convex, while E
t
d and E
s
d are two nonconvex sets with empty interior (all these sets depend on the convexification step). The first inclusions allow, in some cases, an explicit characterization (in the space of the original variables) of the RLT relaxations. Finally, we will discuss weak version of both RTC and RSC hierarchies and we will emphasize some connections between them.


---

## Body

## 1. Introduction

Letn and m be two integers. Let E and N be the two sets 1
,
…
,
n and 1
,
…
,
n
+
m, respectively. Let X be a subset of R
+
n
+
m representing the set of feasible solutions of a mixed integer linear program. The integer n indicates the number of binary variables. We will assume that the set X isbounded and has the following nonlinear description:(1)
∑
j
∈
N
a
j
x
j
≤
b
,
(2)
x
j
≤
1
,
j
∈
N
,
(3)
-
x
j
≤
0
,
j
∈
N
,
(4)
x
j
∈
0,1
,
j
∈
E
.In descriptions (1)–(4) above the set E contains the indices of the n binary variables describing X; for each index j belonging to N the vectors a
j and b belong to R
ρ, where ρ is a positive integer indicating the number of constraints in (1). The ith component of the two vectors a
j and b will be denoted by a
i
j and b
i, respectively. Finally, X
¯ defined by the constraints (1), (2), and (3) will denote thecontinuous (or linear) relaxation of the mixed integer set X.In the sequel, two linear descriptions are said to beequivalent if they define the same polyhedron. A linear description D
1
dominates another linear description D
2 if the polyhedron defined by D
1 is included in the polyhedron defined by D
2.Optimizing even a linear function over the mixed integer setX is an NP-hard problem in general (see [1–4]). A way of building strengthened linear relaxations is to use an approach combining reformulation, linearization, and projection such as those proposed in [5–10]. In such approach, one first reformulates the constraints defining the set of feasible solutions by introducing nonlinearities. Then, the resulting nonlinear system is linearized and projected back onto the original space.Two important properties characterize thereformulation-linearization approach (also known asLift-and-Project methods (do not confuse this with theLift-and-Project hierarchy introduced by Balas et al., see [5])). First, the approach leads to a wholehierarchy (see [10, 11]) of relaxations which lie between the continuous relaxation X
¯ and the convex hull of the mixed integer set X. And for a given hierarchy, a relaxation of higher rank (see [10, 11]) is always stronger than a relaxation of lower rank. Secondly, optimizing a linear function over any relaxation of the hierarchy can be done in a polynomial time.Many hierarchies were introduced. To mention a few,L
&
P hierarchy (Balas et al., see [5]),  L
S hierarchy (Lovász and Schrijver, see [7]), R
L
T hierarchy (Sherali and Admas, see [9, 10]),  L
A
S hierarchy (Lasserre, see [6]),  B
Z hierarchy (Bienstock and Zuckerberg, see [12]), and D
R
L
∗ hierarchy (Minoux and Ouzia, see [8, 13]). For more details, a set-theoretical interpretation of the reformulation-linearization approaches has been proposed in [14] and a theoretical comparative study between the R
L
T,  L
S,  and  L
A
S  relaxations can be found in [15].Theconvexification technique is also widely used to solve nonlinear and nonconvex optimization problems (see [16] and the references therein). Roughly speaking, this technique consists in approximating a nonconvex optimization problem by a convex problem (or a family of convex problems). This can be done by approximating the nonconvex objective function by a convex function and/or by approximating the nonconvex set of feasible solutions by a convex one (see [17–24] and the references therein). In this paper, new hierarchies of continuous relaxations using a reformulation, convexification, and linearization approach will be defined. Theses hierarchies are obtained using two different convexification schemes.The paper is organized as follows. In the second section, first, we will recall the definition of areformulation-linearization hierarchies and then give the definition of the Sherali-Adams hierarchy. In the third section, we will define tworeformulation-convexification hierarchies: R
T
C and R
S
C hierarchies. We will study the main properties of these new hierarchies. In the fourth section, we will study the connections between R
T
C, R
S
C, and  L
&
P hierarchies. In the fifth section, we will introduce a weak version of the hierarchies R
T
C and R
S
C and emphasize some connections between them. In the last section we make some concluding remarks.


## 2. The Reformulation-Linearization Hierarchies

First, we will introduce the general concept of reformulation-linearization hierarchies. Then, we recall the definition of the well-known Sherali-Adams hierarchy (for more details see [9, 10, 25]).Letp be a positive integer. For a finite nonempty set S let S
p be the set of all subsets of S with cardinality p, whereas S
p is the set of all subset of S with cardinality at most p. Sometimes we will need to indicate the cardinality of the sets under consideration, so we will use the notation H
p to indicate (do not confuse this with the Cartesian product of sets) that the set H has cardinality p.LetJ
d be a set of d elements belonging to the set of binary indices E and let J be a subset from J
d. We call d-factor associated with the sets J and J
d, denoted by F
d
J
,
J
d
∖
J, the degree d polynomial defined as follows:(5)
F
d
J
,
J
d
∖
J
=
∏
j
∈
J
x
j
∏
j
∈
J
d
∖
J
1
-
x
j
, with the convention that ∏
j
∈
∅
y
j
=
1.Example 1.
In the case whereE
=
1,2
,
3 and d
=
2 we have the following 12 nontrivial 2-factors: x
1
x
2, x
1
x
3, x
2
x
3, 1
-
x
1
x
2, 1
-
x
1
x
3, 1
-
x
2
x
1, 1
-
x
2
x
3, 1
-
x
3
x
1, 1
-
x
3
x
2, 1
-
x
1
1
-
x
2, 1
-
x
1
1
-
x
3, and 1
-
x
2
1
-
x
3.A rankd reformulation-linearization relaxation (of the mixed integer set X described by (1)–(4)) is defined in three steps. First, the problem isreformulated as a 0-1 polynomial (semialgebraic (a n-dimensionalsemialgebraic set is a solution set of a finite system of polynomial equalities and inequalities; for more details see [26, 27])) mixed integer system by multiplying constraints (1)–(3) with all possible d-factors (that is multiplying by F
d
J
,
J
d
∖
J for all subsets J
d of E and all J
⊆
J
d). Then, the nonlinear terms arelinearized by replacing them with new variables giving rise to a higher dimensional linear system. The third step consists inprojecting back the resulting polyhedron onto the original x-space. As observed in [8] the linearization step can be performed in various ways, leading to various hierarchies of relaxations.The solution set inR
n
+
m associated with the nonlinear (semialgebraic) description resulting from the reformulation step will be denoted by R
d and it is defined as follows:(6)
R
d
=
⋂
J
d
∈
E
d
R
d
J
d
,where, for each subset J
d of E, R
d
J
d is the solution set defined by the following nonlinear system:(7)
∑
j
∈
N
a
j
x
j
F
d
J
,
J
d
∖
J
≤
b
F
d
J
,
J
d
∖
J
,
J
⊆
J
d
,
x
j
F
d
J
,
J
d
∖
J
≤
F
d
J
,
J
d
∖
J
,
j
∈
N
,
J
⊆
J
d
,
-
x
j
F
d
J
,
J
d
∖
J
≤
0
,
j
∈
N
,
J
⊆
J
d
,
-
F
d
J
,
J
d
∖
J
≤
0
,
J
⊆
J
d
.Starting from this semialgebraic reformulation, various linear relaxations can be constructed depending on the type of linearization considered (for more details see [8, 13]).


### 2.1. The Sherali-Adams Hierarchy

The description of the rankd Sherali-Adams relaxation for the mixed integer set X defined by (1)–(4), denoted by P
^
R
L
T
d, is a reformulation-linearization relaxation of rank d where the nonlinear terms appearing in (7) are linearized by introducing a new set of variables w
J and w
J
k defined by(8)
w
J
=
∏
j
∈
J
x
j
∀
J
⊆
E
with
J
≤
min
⁡
d
+
1
,
n
,
w
J
k
=
x
k
∏
j
∈
J
x
j
∀
k
∈
N
∖
E
,
J
⊆
E
with
J
≤
min
⁡
d
,
n
,where it is assumed that w
∅
=
1 and w
∅
k
=
x
k for every index k (belonging to N
∖
E) of a continuous variable.Example 2.
In the case whereE
=
1,2
,
3 and N
=
E
∪
4 we have the following linearization: (9)
w
1,2
=
x
1
x
2
,
w
1,3
=
x
1
x
3
,
w
2,3
=
x
2
x
3
,
w
1
4
=
x
1
x
4
,
w
2
4
=
x
2
x
4
,
w
3
4
=
x
3
x
4
.The resulting higher dimensional linear description will be denoted byP
R
L
T
d and it is defined as follows:(10)
P
R
L
T
d
=
⋂
J
d
∈
E
d
P
R
L
T
d
J
d
,where, for each cardinality d subset J
d of E, the linear description of the polyhedron P
R
L
T
d
J
d is(11)
∑
j
∈
N
a
j
W
j
J
,
J
d
-
b
W
0
J
,
J
d
≤
0
,
J
⊆
J
d
,
W
j
J
,
J
d
-
W
0
J
,
J
d
≤
0
,
j
∈
N
,
J
⊆
J
d
,
W
j
J
,
J
d
≥
0
,
j
∈
N
,
J
⊆
J
d
,
W
0
J
,
J
d
≥
0
,
J
⊆
J
d
,and where, for every index j belonging to N
∖
E, W
j
J
,
J
d and W
0
J
,
J
d denote the linearized forms of the polynomials x
j
F
d
J
,
J
d
∖
J and F
d
J
,
J
d
∖
J, respectively; these are related to the w
J and w
J
k variables as follows:(12)
W
j
J
,
J
d
=
∑
J
⊆
H
⊆
J
d
-
1
H
∖
J
w
H
∪
j
,
J
d
,
J
⊆
J
d
,
j
∈
E
,
W
j
J
,
J
d
=
∑
J
⊆
H
⊆
J
d
-
1
H
∖
J
w
H
j
,
J
d
,
J
⊆
J
d
,
j
∈
N
∖
E
,
W
0
J
,
J
d
=
∑
J
⊆
H
⊆
J
d
-
1
H
∖
J
w
H
,
J
d
,
J
⊆
J
d
.The above relations (12) are easily obtained by expanding the products involved in the definition of the d-factors.After linearizing the nonlinear terms in (7) using the w variables defined in (8) above, the P
R
L
T
d description turns out to involve a number of variables and constraints exponential in d. The number of variables needed to linearize the nonlinear system (7) is ∑
k
=
1
m
i
n
d
+
1
,
n
‍
n
k
+
m
∑
k
=
0
d
‍
n
k (notice that the variable w
∅ is not counted here since w
∅
=
1). Also, it is seen that the number of constraints is O
(
n
d
2
d
n
+
m
).The rankd Sherali-Adams relaxation P
^
R
L
T
d is obtained by projecting the polyhedron P
R
L
T
d onto the subspace R
n
+
m of the x variables.


## 2.1. The Sherali-Adams Hierarchy

The description of the rankd Sherali-Adams relaxation for the mixed integer set X defined by (1)–(4), denoted by P
^
R
L
T
d, is a reformulation-linearization relaxation of rank d where the nonlinear terms appearing in (7) are linearized by introducing a new set of variables w
J and w
J
k defined by(8)
w
J
=
∏
j
∈
J
x
j
∀
J
⊆
E
with
J
≤
min
⁡
d
+
1
,
n
,
w
J
k
=
x
k
∏
j
∈
J
x
j
∀
k
∈
N
∖
E
,
J
⊆
E
with
J
≤
min
⁡
d
,
n
,where it is assumed that w
∅
=
1 and w
∅
k
=
x
k for every index k (belonging to N
∖
E) of a continuous variable.Example 2.
In the case whereE
=
1,2
,
3 and N
=
E
∪
4 we have the following linearization: (9)
w
1,2
=
x
1
x
2
,
w
1,3
=
x
1
x
3
,
w
2,3
=
x
2
x
3
,
w
1
4
=
x
1
x
4
,
w
2
4
=
x
2
x
4
,
w
3
4
=
x
3
x
4
.The resulting higher dimensional linear description will be denoted byP
R
L
T
d and it is defined as follows:(10)
P
R
L
T
d
=
⋂
J
d
∈
E
d
P
R
L
T
d
J
d
,where, for each cardinality d subset J
d of E, the linear description of the polyhedron P
R
L
T
d
J
d is(11)
∑
j
∈
N
a
j
W
j
J
,
J
d
-
b
W
0
J
,
J
d
≤
0
,
J
⊆
J
d
,
W
j
J
,
J
d
-
W
0
J
,
J
d
≤
0
,
j
∈
N
,
J
⊆
J
d
,
W
j
J
,
J
d
≥
0
,
j
∈
N
,
J
⊆
J
d
,
W
0
J
,
J
d
≥
0
,
J
⊆
J
d
,and where, for every index j belonging to N
∖
E, W
j
J
,
J
d and W
0
J
,
J
d denote the linearized forms of the polynomials x
j
F
d
J
,
J
d
∖
J and F
d
J
,
J
d
∖
J, respectively; these are related to the w
J and w
J
k variables as follows:(12)
W
j
J
,
J
d
=
∑
J
⊆
H
⊆
J
d
-
1
H
∖
J
w
H
∪
j
,
J
d
,
J
⊆
J
d
,
j
∈
E
,
W
j
J
,
J
d
=
∑
J
⊆
H
⊆
J
d
-
1
H
∖
J
w
H
j
,
J
d
,
J
⊆
J
d
,
j
∈
N
∖
E
,
W
0
J
,
J
d
=
∑
J
⊆
H
⊆
J
d
-
1
H
∖
J
w
H
,
J
d
,
J
⊆
J
d
.The above relations (12) are easily obtained by expanding the products involved in the definition of the d-factors.After linearizing the nonlinear terms in (7) using the w variables defined in (8) above, the P
R
L
T
d description turns out to involve a number of variables and constraints exponential in d. The number of variables needed to linearize the nonlinear system (7) is ∑
k
=
1
m
i
n
d
+
1
,
n
‍
n
k
+
m
∑
k
=
0
d
‍
n
k (notice that the variable w
∅ is not counted here since w
∅
=
1). Also, it is seen that the number of constraints is O
(
n
d
2
d
n
+
m
).The rankd Sherali-Adams relaxation P
^
R
L
T
d is obtained by projecting the polyhedron P
R
L
T
d onto the subspace R
n
+
m of the x variables.


## 3. Two New Reformulation-Convexification Hierarchies

We will consider two newreformulation-convexification hierarchies. The first one is calledreformulation-term-convexification (R
T
C) hierarchy. It is obtained by convexifying themonomials (also calledterms) resulting from the reformulation step. The second hierarchy is calledreformulation-standard-convexification (R
S
C). It is obtained by convexifying the nonlinearfactors (a linear combination of monomial products) resulting from the reformulation step.


### 3.1. Reformulation-Term-Convexification Hierarchy

A rankd relaxation of the R
T
C hierarchy is obtained by applyinglocal convexification to each constraint of the nonlinear system defining R
d as follows. For every subset J from E and every subset H from N
∖
E with at most one element, let l be the following operator:(13)
l
α
∏
k
∈
H
x
k
∏
j
∈
J
x
j
=
α
∑
j
∈
J
∪
H
x
j
-
J
∪
H
+
1
+
i
f
α
>
0
,
α
min
⁡
x
j
:
j
∈
J
∪
H
i
f
α
≤
0
,with the convention that ∏
k
∈
∅
‍
x
k
=
1 and, for any real r, r
+ is equal to m
a
x
0
,
r.The convexification scheme (13) assumes that the constraint to which it is applied is of the form ≤.LetT
d be the following convex set:(14)
T
d
=
⋂
J
d
∈
E
d
T
d
J
d
,where, for each cardinality d subset J
d from E, the convex set T
d
J
d corresponds to the solution set R
d
J
d defined by the nonlinear system deduced from (7) by convexification using scheme (13). Theconvex nonlinear description of the set T
d
J
d, for a given d, reads(15)
∑
j
∈
N
L
j
J
,
J
d
a
i
j
+
L
0
J
,
J
d
-
b
i
≤
0
,
J
⊆
J
d
,
i
=
1
,
…
,
ρ
,
L
j
J
,
J
d
1
+
L
0
J
,
J
d
-
1
≤
0
,
j
∈
N
,
J
⊆
J
d
,
L
j
J
,
J
d
1
≥
0
,
j
∈
N
,
J
⊆
J
d
,
L
0
J
,
J
d
1
≥
0
,
J
⊆
J
d
,where, for every index j belonging to N and any scalar σ, L
j
J
,
J
d
σ and L
0
J
,
J
d
σ denote theconvexified forms of the polynomials σ
x
j
F
d
J
,
J
d
∖
J and σ
F
d
J
,
J
d
∖
J, respectively; these are defined using the l operator as follows: (16)
L
j
J
,
J
d
σ
=
∑
J
⊆
H
⊆
J
d
l
σ
×
-
1
H
∖
J
∏
k
∈
H
∪
j
x
k
,
J
d
,
J
⊆
J
d
,
j
∈
E
,
L
j
J
,
J
d
σ
=
∑
J
⊆
H
⊆
J
d
l
σ
×
-
1
H
∖
J
x
j
∏
k
∈
H
x
k
,
J
d
,
J
⊆
J
d
,
j
∈
N
∖
E
,
L
0
J
,
J
d
σ
=
∑
J
⊆
H
⊆
J
d
l
σ
×
-
1
H
∖
J
∏
k
∈
H
x
k
,
J
d
,
J
⊆
J
d
.Since the setT
d is the intersection of convex sets (by construction), then we have the following result.Theorem 3.
For every integerd belonging to {
1
,
…
,
n
}, the set T
d as defined by (15) is a nonlinear convex relaxation of the mixed integer set X.For every integerd, let E
t
d be the set (the lower-script t is used to recall that our set is related to theterm convexification scheme):(17)
E
t
d
=
⋂
H
∈
E
d
,
K
∈
N
∖
H
1
E
t
H
∪
K
,where, for subsets H
∈
E
d and K
∈
N
∖
H
1, (18)
E
t
H
∪
K
=
x
∈
0,1
n
+
m
:
∑
j
∈
H
∪
K
x
j
-
H
∪
K
+
1
+
=
min
⁡
x
j
:
j
∈
H
∪
K
.Since every binary vector from0,1
n
+
m belongs to E
t
d then we deduce that c
o
n
v
E
t
d coincides with the hypercube 0,1
n
+
m.LetP
R
T
C
d be the extended linear description obtained from the set T
d
∩
E
t
d using the following steps. Let t and v be two sets of additional variables such that for every d-element set J
d, for every subset J from J
d and for every subset H from N
∖
J
d with at most one element. First, in (15), the variable t
J
H will replace the nonlinear term:(19)
min
⁡
x
j
:
j
∈
J
∪
H
,and the variable v
J
H will replace(20)
∑
j
∈
J
∪
H
x
j
-
J
∪
H
+
1
+
.Then, we impose the equality constraint:(21)
t
J
H
=
v
J
H
.We will use the notation t
J or t
J
k instead of t
J
H when H is empty or when H coincides with the singleton k, respectively.Thus, we have(22)
P
R
T
C
d
=
⋂
J
d
∈
E
d
P
R
T
C
d
J
d
,where, for each subset J
d of E, the polyhedron P
R
T
C
d
J
d reads(23)
∑
j
∈
N
a
j
T
j
J
,
J
d
-
b
T
0
J
,
J
d
≤
0
,
J
⊆
J
d
,
(24)
T
j
J
,
J
d
-
T
0
J
,
J
d
≤
0
,
j
∈
N
,
J
⊆
J
d
,
(25)
-
T
j
J
,
J
d
≤
0
,
j
∈
N
,
J
⊆
J
d
,
(26)
-
T
0
J
,
J
d
≤
0
,
J
⊆
J
d
,
(27)
min
⁡
x
j
:
j
∈
J
≥
t
J
,
J
⊆
J
d
,
(28)
∑
j
∈
J
x
j
-
J
+
1
≤
t
J
,
J
⊆
J
d
,
(29)
min
⁡
x
j
:
j
∈
J
∪
k
≥
t
J
k
,
J
⊆
J
d
,
k
∈
N
∖
E
,
(30)
x
k
+
∑
j
∈
J
x
j
-
J
≤
t
J
k
,
J
⊆
J
d
,
k
∈
N
∖
E
,
(31)
t
J
,
t
J
k
≥
0
,
J
⊆
J
d
,
k
∈
N
∖
E
,and where, for every index j belonging to N, T
j
J
,
J
d and T
0
J
,
J
d denote the linearized forms of the convexified form of the polynomials x
j
F
d
J
,
J
d
∖
J and F
d
J
,
J
d
∖
J, respectively; these are related to the t
J and t
J
k variables as follows:(32)
T
j
J
,
J
d
=
∑
J
⊆
H
⊆
J
d
-
1
H
∖
J
t
H
∪
j
,
J
d
,
J
⊆
J
d
,
j
∈
E
,
T
j
J
,
J
d
=
∑
J
⊆
H
⊆
J
d
-
1
H
∖
J
t
H
j
,
J
d
,
J
⊆
J
d
,
j
∈
N
∖
E
,
T
0
J
,
J
d
=
∑
J
⊆
H
⊆
J
d
-
1
H
∖
J
t
H
,
J
d
,
J
⊆
J
d
.The linear description (23)–(31) and (32) are stated using only the variables t
J
H. This is possible according to (21). As discussed in Section 5, discarding constraints (21) in the definition of the R
T
C hierarchy will lead to a weaker hierarchy.For every integerd belonging to 1
,
…
,
n, let P
^
R
T
C
d be the projection onto the x-space of the extended linear description P
R
T
C
d. The polyhedron P
^
R
T
C
d will be calledrank-d
reformulation-term-convexification relaxation of X.In the next theorem we will prove that the hierarchyR
T
C is equivalent to the hierarchy R
L
T.Theorem 4.
For every integerd belonging to 1
,
…
,
n, the two linear relaxations P
^
R
L
T
d and P
^
R
T
C
d are equivalent.Proof.
We will proceed by showing that the two extended linear descriptionsP
R
L
T
d and P
R
T
C
d are the same up to variable renaming. Let d be an integer belonging to 1
,
…
,
n. As shown in [8], for every set J
d belonging to E
[
d
], the constraints(33)
min
⁡
x
j
:
j
∈
J
≥
w
J
,
J
⊆
J
d
,
(34)
∑
j
∈
J
x
j
-
J
+
1
≤
w
J
,
J
⊆
J
d
,are implicit in the linear description of P
R
L
T
d. We claim that the constraints(35)
min
⁡
x
j
:
j
∈
J
∪
k
≥
w
J
k
,
J
⊆
J
d
,
k
∈
N
∖
E
,
(36)
x
k
+
∑
j
∈
J
x
j
-
J
≤
w
J
k
,
J
⊆
J
d
,
k
∈
N
∖
E
,are also implicit in the linear description of P
R
L
T
d. The argument is obvious for constraints (35). For constraints (36), let k be an index belonging to N
∖
E and let J be a subset from J
d, and the following constraint(37)
x
k
+
∏
j
∈
J
x
j
1
-
x
k
≤
1 is valid for P
^
R
L
T
d. Using R
L
T linearization, we get the constraint(38)
x
k
+
w
J
-
w
J
k
≤
1
. Combining this last constraint with constraint (34) we deduce that(39)
x
k
+
∑
j
∈
J
x
j
-
J
≤
w
J
k
,
J
⊆
J
d
,
k
∈
N
∖
E
. Now consider the following identifications: (40)
w
J
=
t
J
∀
J
⊆
E
,
J
≤
min
⁡
d
+
1
,
n
,
w
J
k
=
t
J
k
for  every
k
∈
N
∖
E
,
J
⊆
E
,
J
≤
min
⁡
d
,
n
.These identifications imply identifications between the W and T variables through (12) and (32). Thus, the two extended linear descriptions P
R
L
T
d and P
R
T
C
d are equivalent. This completes the proof.Consequently, the rank-n
R
T
C relaxation coincides with the convex hull of the mixed integer set X. The R
T
C hierarchy is motivated by the next theorem where it is shown that the projection onto the x-space of any R
T
C relaxation can be sandwiched between two convex sets. The following proposition will be useful.Proposition 5.
LetJ and H be two disjoint subsets from N, such that x
j belongs to 0,1 for all j belonging to J
∪
H; then (41)
∑
j
∈
J
x
j
+
∑
j
∈
H
1
-
x
j
-
J
∪
H
+
1
+
≤
min
⁡
m
i
n
h
∈
J
x
h
,
m
i
n
h
∈
H
1
-
x
h
.Theorem 6.
For every integerd belonging to 1
,
…
,
n, one has(42)
c
o
n
v
T
d
∩
E
t
d
⊆
P
^
R
T
C
d
⊆
T
d
.Proof.
First, to prove the left inclusion in (42) it is sufficient to prove that the set T
d
∩
E
t
d is included in P
^
R
T
C
d. Let x
^ be a point belonging to the set T
d
∩
E
t
d. Let x
^
,
t
^
,
v
^ be a vector such that(43)
t
^
J
=
min
⁡
x
^
j
:
j
∈
J
,
J
⊂
E
,
J
≤
m
i
n
d
+
1
,
n
,
t
^
J
k
=
min
⁡
x
^
j
:
j
∈
J
∪
k
,
k
∈
N
∖
E
,
J
⊂
J
d
,
J
d
∈
E
d
,
v
^
J
=
∑
j
∈
J
x
^
j
-
J
+
1
+
,
J
⊂
E
,
J
≤
min
⁡
d
+
1
,
n
,
v
^
J
k
=
x
^
k
+
∑
j
∈
J
x
^
j
-
J
+
2
+
,
k
∈
N
∖
E
,
J
⊂
J
d
,
J
d
∈
E
d
.Thus, by definition constraints (31) are fulfilled by the vector x
^
,
t
^
,
v
^. Since x
^ belongs to T
d, then x
^
,
t
^
,
v
^ satisfies constraints (23)–(26). By Proposition 5 the point x
^
,
t
^
,
v
^ satisfies constraints (27)–(30). Since the vector x
^ also belongs to the set E
t
d, then the vector x
^
,
t
^
,
v
^ also satisfies constraints (21). Consequently, the vector x
^
,
t
^
,
v
^ belongs to P
R
T
C
d. Thus, x
^ belongs to P
^
R
T
C
d.
Now, let us prove the right inclusion in (42). Let x
^ be a point belonging to P
^
R
T
C
d. There is a vector t
^ such that x
^
,
t
^ belongs to P
R
T
C
d. Without loss of generality, any constraint defining P
R
T
C
d can be written as follows:(44)
∑
J
∈
S
1
+
a
J
+
t
J
+
∑
J
∈
S
2
+
,
k
∈
N
∖
E
b
J
+
t
J
k
+
∑
J
∈
S
1
-
a
J
-
t
J
+
∑
J
∈
S
2
-
,
k
∈
N
∖
E
b
J
-
t
J
k
≤
0
,where S
1
+
,
S
2
+
,
S
1
-, and S
2
- are subsets of the power set of N (the superscript of a coefficient indicates its sign). Since the point x
^
,
t
^ satisfies the following inequalities: (45)
∑
j
∈
J
x
^
j
-
J
+
1
+
≤
t
^
J
≤
min
⁡
x
^
j
:
j
∈
J
,
J
⊆
J
d
,
x
^
k
+
∑
j
∈
J
x
^
j
-
J
+
≤
t
^
J
k
≤
min
⁡
x
^
j
:
j
∈
J
∪
k
,
J
⊆
J
d
,
k
∈
N
∖
E
,then we deduce(46)
∑
J
∈
S
1
+
a
J
+
∑
j
∈
J
x
^
j
-
J
+
1
+
+
∑
J
∈
S
2
+
,
k
∈
N
∖
E
b
J
+
x
^
k
+
∑
j
∈
J
x
^
j
-
J
+
+
∑
J
∈
S
1
-
a
J
-
m
i
n
j
∈
J
x
^
j
+
∑
J
∈
S
2
-
,
k
∈
N
∖
E
b
J
-
m
i
n
j
∈
J
∪
k
x
^
j
≤
0
.Consequently, the point x
^ satisfies all constraints defining T
d: that is, P
^
R
T
C
d
⊆
T
d. This completes the proof.Characterization (42) will allow us, in some cases (see Corollary 8), to give an explicit characterization of any R
L
T relaxation (characterization in the x-space). Before answering this question we will recall, in the next proposition, the simple result stating that any fractional point belonging to the set E
t will belong to either a facet or an edge of the hypercube. This implies that the set E
t has empty interior.Proposition 7.
For avery subsetJ from N, such that 0
<
x
j
≤
1 for all j belonging to the set J, if(47)
∑
j
∈
J
x
j
-
J
+
1
+
=
min
⁡
x
j
:
j
∈
J
,then at least J
-
1 variables are equal to 1.As a consequence of Theorem6 and Proposition 7 we have the following corollary.Corollary 8.
For every integerd belonging to 1
,
…
,
n, if the set T
d has integer vertices then it coincides with the projection of P
R
L
T
d onto the x-space.Proof.
Letd be an integer belonging to 1
,
…
,
n. On the one hand, the sets T
d and E
t
d are both subsets from the hypercube. On the other hand, if the set T
d has integer vertices then both sets T
d
∩
E
t
d and T
d have the same vertices (vertices of T
d). Thus, the convex envelope of the set T
d
∩
E
t
d coincides with the set T
d, because T
d is convex. Consequently, using Theorems 4 and 6 we conclude that (48)
P
^
R
L
T
d
=
T
d
.This completes the proof.The following example shows that restricting the setT
d to have integer vertices in Corollary 8 is not a sufficient condition to characterize P
^
R
L
T
d. Let us consider the following set:(49)
X
=
x
,
y
∈
0,1
2
:
-
9
x
+
6
y
≤
1
,
-
12
x
+
15
y
≤
6
.Its continuous relaxation X
¯ is the shaded region drawn in Figure 1. The set T
1 associated with the set X is the shaded region drawn in Figure 2. A careful analysis of the set T
1 shows that it features the following linear description: (50)
T
1
=
x
,
y
∈
0,1
2
:
-
5
x
+
6
y
≤
1
,
-
4
x
+
3
y
≤
0
.Figure 1
The setX
¯.Figure 2
The setT
1.The rank-1R
L
T relaxation has the same linear description as T
1. But, as shown in Figure 2, the set T
1 has a fractional vertex. Notice that set (49) coincides with the the rank-1  L
&
P relaxation. As discussed in Section 5, this equality is not true in general. Finally, the set T
2 (the shaded region in Figure 3) has integer vertices and it coincides with the rank-2
R
L
T relaxation.Figure 3
The setT
2.


### 3.2. Reformulation-Standard-Convexification Hierarchy

Contrary to theR
T
C hierarchy, in thereformulation-standard-convexification hierarchy (R
S
C) we convexify each factor obtained after reformulation and not the monomials appearing in each such factors. The termstandard extension was introduced by Crama (see [24]) in studying concave envelopes of pseudo-boolean functions.LetS
d be the nonlinear convex set:(51)
S
d
=
⋂
J
d
∈
E
d
S
d
J
d
,where, for each cardinality d subset J
d of E, the convex set S
d
J
d corresponds to the solution set of R
d
J
d defined by the nonlinear system deduced from (7) using the following convexification scheme: (52)
L
α
∏
k
∈
H
x
k
∏
j
∈
K
1
-
x
j
=
α
∑
j
∈
H
x
j
+
∑
j
∈
K
1
-
x
j
-
K
∪
H
+
1
+
i
f
α
>
0
,
α
min
⁡
m
i
n
j
∈
H
x
j
,
m
i
n
k
∈
K
1
-
x
k
i
f
α
≤
0
,where H and K are two subsets such that K
⊂
E, H
⊂
N, and H
∩
N
∖
E
≤
1.As for thel operator, depending on the type of the constraint (≥ or ≤), we use the m
i
n expression or the m
a
x expression in such a way that the resulting solution set will be convex.The nonlinear description of the setS
d
J
d, for a given d and a set J
d, is thus defined as follows:(53)
∑
j
∈
N
L
j
J
,
J
d
a
i
j
+
L
0
J
,
J
d
-
b
i
≤
0
,
J
⊆
J
d
,
i
=
1
,
…
,
ρ
,
L
j
J
,
J
d
1
+
L
0
J
,
J
d
-
1
≤
0
,
j
∈
E
,
J
⊆
J
d
,
L
j
J
,
J
d
-
1
≤
0
,
j
∈
N
,
J
⊆
J
d
,
L
0
J
,
J
d
-
1
≤
0
,
J
⊆
J
d
,where, for every index j belonging to N and any scalar σ, L
j
J
,
J
d
σ and L
0
J
,
J
d
σ denote the convexified forms of the polynomials σ
x
j
F
d
J
,
J
d
∖
J and σ
F
d
J
,
J
d
∖
J using the operator L, respectively.Since the setS
d as defined in (51) is the intersection of convex sets then we have the following results.Theorem 9.
For every integerd belonging to {
1
,
…
,
n
}, the set S
d as defined by (51) is a nonlinear convex relaxation of the mixed integer set X.For every integerd, let E
s
d be the set (the lower-script s is used to recall that our set is related to thestandard convexification scheme)(54)
E
s
d
=
⋂
J
d
∈
E
d
,
K
∈
N
∖
J
d
1
E
s
J
d
,
K
, where for subsets J
d
∈
E
d and K
∈
N
∖
J
d
1 the set E
s
J
d
,
K is the subset from 0,1
n
+
m defined by the following constraints: (55)
∑
j
∈
J
∪
K
x
j
+
∑
j
∈
J
d
∖
J
1
-
x
j
-
d
+
1
+
=
min
⁡
min
⁡
x
j
:
j
∈
J
∪
K
,
min
⁡
1
-
x
j
:
j
∈
J
d
∖
J
,
J
⊆
J
d
.Since every binary vector from0,1
n
+
m belongs to E
s
d then the set c
o
n
v
E
s
d coincides with the hypercube 0,1
n
+
m. Notice that the set E
s
d is a subset from E
t
d. As shown below, it is possible to represent S
d
∩
E
s
d as a polyhedron in some appropriate extended space.LetP
R
S
C
d denote the extended linear description of the set S
d
∩
E
s
d obtained by using the following steps. First, let G and D be two sets of variables such that, for every d-element set J
d, for every subset J from J
d, and for every subset K from N
∖
J
d with at most one element, G
K
J
,
J
d replaces in (53) the nonlinear term:(56)
min
⁡
m
i
n
h
∈
J
∪
K
x
h
,
m
i
n
k
∈
J
d
∖
J
1
-
x
k
,and the variable D
K
J
,
J
d replaces(57)
∑
h
∈
J
∪
K
x
h
+
∑
k
∈
J
d
∖
J
1
-
x
k
-
d
+
1
+
.Then we impose the following equality:(58)
G
K
J
,
J
d
=
D
K
J
,
J
d
.In the sequel, instead ofG
K
J
,
J
d or D
K
J
,
J
d we will use G
j
J
,
J
d or D
j
J
,
J
d when the set K coincides with the singleton j and G
0
J
,
J
d or D
0
J
,
J
d otherwise (recall that the set K has at most one element).Thus, we obtain the extended linear description:(59)
P
R
S
C
d
=
⋂
J
d
∈
E
d
P
R
S
C
d
J
d
,where, for each subset J
d of E, the polyhedron P
R
S
C
d
J
d reads(60)
∑
j
∈
N
a
j
G
j
J
,
J
d
-
b
G
0
J
,
J
d
≤
0
,
J
⊆
J
d
,
(61)
G
j
J
,
J
d
-
G
0
J
,
J
d
≤
0
,
j
∈
E
,
J
⊆
J
d
,
(62)
-
G
j
J
,
J
d
≤
0
,
j
∈
N
,
J
⊆
J
d
,
(63)
-
G
0
J
,
J
d
≤
0
,
J
⊆
J
d
,
(64)
min
⁡
x
k
:
k
∈
J
∪
j
≥
G
j
J
,
J
d
,
j
∈
N
∖
J
d
,
J
⊆
J
d
,
(65)
min
⁡
1
-
x
k
:
k
∈
J
d
∖
J
≥
G
j
J
,
J
d
,
j
∈
N
∖
J
d
,
J
⊆
J
d
,
(66)
min
⁡
x
k
:
k
∈
J
≥
G
0
J
,
J
d
,
J
⊆
J
d
,
(67)
min
⁡
1
-
x
k
:
k
∈
J
d
∖
J
≥
G
0
J
,
J
d
,
J
⊆
J
d
,
(68)
∑
h
∈
J
∪
j
x
h
+
∑
k
∈
J
d
∖
J
1
-
x
k
-
d
+
1
≤
G
j
J
,
J
d
,
j
∈
N
∖
J
d
,
J
⊆
J
d
,
(69)
∑
h
∈
J
x
h
+
∑
k
∈
J
d
∖
J
1
-
x
k
-
d
+
1
≤
G
0
J
,
J
d
,
J
⊆
J
d
.Notice that linear description (60)–(69) are stated using only the variables G. This is possible according to (58). As discussed in the last section, discarding constraints (58) in the definition of the R
S
C hierarchy will lead to a weaker hierarchy.For every integerd belonging to 1
,
…
,
n, let P
^
R
S
C
d be the projection onto the x-space of the extended linear description P
R
S
C
d. The continuous relaxation P
^
R
S
C
d will be calledrank-d
reformulation-standard-convexification relaxation of the mixed integer set X.As for theR
T
C hierarchy, in the following theorem we will prove that any relaxation of the R
S
C hierarchy can also be sandwiched between two convex sets.Theorem 10.
For every integerd belonging to 1
,
…
,
n, we have(70)
c
o
n
v
S
d
∩
E
s
d
⊆
P
^
R
S
C
d
⊆
S
d
.Proof.
Letd be an integer belonging to 1
,
…
,
n. First, to prove the left inclusion in (70) it is sufficient to prove that the set S
d
∩
E
s
d is a subset of P
^
R
S
C
d. Let x
^ be a point belonging to the set S
d
∩
E
s
d. Let x
^
,
G
^
,
D
^ be a vector where the two vectors G
^ and D
^ are defined as follows: for every d-element set J
d, for every subset J from J
d, and for every subset K from N
∖
J
d with at most one element:(71)
G
^
K
J
,
J
d
=
min
⁡
min
h
∈
J
∪
K
⁡
x
^
h
⁡
,
m
i
n
k
∈
J
d
∖
J
1
-
x
^
k
,
D
^
K
J
,
J
d
=
∑
h
∈
J
∪
K
x
^
h
+
∑
k
∈
J
d
∖
J
1
-
x
^
k
-
d
+
1
+
.By definition, x
^ belongs to S
d; then x
^
,
G
^
,
D
^ satisfies constraints (60)–(63). By Proposition 5 the point x
^
,
G
^
,
D
^ also satisfies constraints (64)–(69). Since the vector x
^ also belongs to the set E
s
d, then the vector x
^
,
G
^
,
D
^ also satisfies constraints (58). Thus, the vector x
^
,
G
^
,
D
^ belongs to P
R
S
C
d. Consequently, x
^ belongs to P
^
R
S
C
d. This completes the first part of the proof.
Now, let us show the right inclusion in (70). Let x
^ be a point belonging to P
^
R
S
C
d. There is a vector G
^ such that x
^
,
G
^ belongs to P
R
S
C
d. Without loss of generality, each constraint in (60) and (61) can be rewritten as follows:(72)
∑
j
∈
N
:
α
i
j
>
0
α
i
j
G
j
J
,
J
d
+
∑
j
∈
N
:
α
i
j
<
0
α
i
j
G
j
J
,
J
d
-
β
i
G
0
J
,
J
d
≤
0
,
J
⊆
J
d
.Without loss of generality, we can assume that β
i is nonnegative (the argument we will use holds also in the case where β
i is nonpositive). The point x
^
,
G
^ satisfies also the constraints: (73)
min
⁡
x
^
k
:
k
∈
J
≥
G
^
0
J
,
J
d
,
J
⊆
J
d
,
min
⁡
1
-
x
^
k
:
k
∈
J
d
∖
J
≥
G
^
0
J
,
J
d
,
J
⊆
J
d
,
∑
h
∈
J
x
^
h
+
∑
k
∈
J
d
∖
J
1
-
x
^
k
-
d
+
1
+
≤
G
^
0
J
,
J
d
,
J
⊆
J
d
,
min
⁡
x
^
k
:
k
∈
J
∪
j
≥
G
^
j
J
,
J
d
,
j
∈
N
∖
J
d
,
J
⊆
J
d
,
min
⁡
1
-
x
^
k
:
k
∈
J
d
∖
J
≥
G
^
j
J
,
J
d
,
j
∈
N
∖
J
d
,
J
⊆
J
d
,
∑
h
∈
J
∪
j
x
^
h
+
∑
k
∈
J
d
∖
J
1
-
x
^
k
-
d
+
1
+
≤
G
^
j
J
,
J
d
,
j
∈
N
∖
J
d
,
J
⊆
J
d
.Thus, we have (74)
∑
j
∈
N
:
α
i
j
>
0
α
i
j
∑
h
∈
J
x
^
h
+
∑
k
∈
J
d
∖
J
1
-
x
^
k
-
d
+
1
+
+
∑
j
∈
N
:
α
i
j
<
0
α
i
j
min
⁡
m
i
n
k
∈
J
∪
j
x
^
k
,
m
i
n
k
∈
J
d
∖
J
1
-
x
^
k
-
β
i
min
⁡
m
i
n
k
∈
J
x
^
k
,
m
i
n
k
∈
J
d
∖
J
1
-
x
^
k
G
0
J
,
J
d
≤
∑
j
∈
N
:
α
i
j
>
0
α
i
j
G
j
J
,
J
d
+
∑
j
∈
N
:
α
i
j
<
0
α
i
j
G
j
J
,
J
d
-
β
i
G
0
J
,
J
d
,
J
⊆
J
d
. This means that the point x
^ satisfies constraints (53). Thus, x
^ belongs to S
d. This completes the proof.


## 3.1. Reformulation-Term-Convexification Hierarchy

A rankd relaxation of the R
T
C hierarchy is obtained by applyinglocal convexification to each constraint of the nonlinear system defining R
d as follows. For every subset J from E and every subset H from N
∖
E with at most one element, let l be the following operator:(13)
l
α
∏
k
∈
H
x
k
∏
j
∈
J
x
j
=
α
∑
j
∈
J
∪
H
x
j
-
J
∪
H
+
1
+
i
f
α
>
0
,
α
min
⁡
x
j
:
j
∈
J
∪
H
i
f
α
≤
0
,with the convention that ∏
k
∈
∅
‍
x
k
=
1 and, for any real r, r
+ is equal to m
a
x
0
,
r.The convexification scheme (13) assumes that the constraint to which it is applied is of the form ≤.LetT
d be the following convex set:(14)
T
d
=
⋂
J
d
∈
E
d
T
d
J
d
,where, for each cardinality d subset J
d from E, the convex set T
d
J
d corresponds to the solution set R
d
J
d defined by the nonlinear system deduced from (7) by convexification using scheme (13). Theconvex nonlinear description of the set T
d
J
d, for a given d, reads(15)
∑
j
∈
N
L
j
J
,
J
d
a
i
j
+
L
0
J
,
J
d
-
b
i
≤
0
,
J
⊆
J
d
,
i
=
1
,
…
,
ρ
,
L
j
J
,
J
d
1
+
L
0
J
,
J
d
-
1
≤
0
,
j
∈
N
,
J
⊆
J
d
,
L
j
J
,
J
d
1
≥
0
,
j
∈
N
,
J
⊆
J
d
,
L
0
J
,
J
d
1
≥
0
,
J
⊆
J
d
,where, for every index j belonging to N and any scalar σ, L
j
J
,
J
d
σ and L
0
J
,
J
d
σ denote theconvexified forms of the polynomials σ
x
j
F
d
J
,
J
d
∖
J and σ
F
d
J
,
J
d
∖
J, respectively; these are defined using the l operator as follows: (16)
L
j
J
,
J
d
σ
=
∑
J
⊆
H
⊆
J
d
l
σ
×
-
1
H
∖
J
∏
k
∈
H
∪
j
x
k
,
J
d
,
J
⊆
J
d
,
j
∈
E
,
L
j
J
,
J
d
σ
=
∑
J
⊆
H
⊆
J
d
l
σ
×
-
1
H
∖
J
x
j
∏
k
∈
H
x
k
,
J
d
,
J
⊆
J
d
,
j
∈
N
∖
E
,
L
0
J
,
J
d
σ
=
∑
J
⊆
H
⊆
J
d
l
σ
×
-
1
H
∖
J
∏
k
∈
H
x
k
,
J
d
,
J
⊆
J
d
.Since the setT
d is the intersection of convex sets (by construction), then we have the following result.Theorem 3.
For every integerd belonging to {
1
,
…
,
n
}, the set T
d as defined by (15) is a nonlinear convex relaxation of the mixed integer set X.For every integerd, let E
t
d be the set (the lower-script t is used to recall that our set is related to theterm convexification scheme):(17)
E
t
d
=
⋂
H
∈
E
d
,
K
∈
N
∖
H
1
E
t
H
∪
K
,where, for subsets H
∈
E
d and K
∈
N
∖
H
1, (18)
E
t
H
∪
K
=
x
∈
0,1
n
+
m
:
∑
j
∈
H
∪
K
x
j
-
H
∪
K
+
1
+
=
min
⁡
x
j
:
j
∈
H
∪
K
.Since every binary vector from0,1
n
+
m belongs to E
t
d then we deduce that c
o
n
v
E
t
d coincides with the hypercube 0,1
n
+
m.LetP
R
T
C
d be the extended linear description obtained from the set T
d
∩
E
t
d using the following steps. Let t and v be two sets of additional variables such that for every d-element set J
d, for every subset J from J
d and for every subset H from N
∖
J
d with at most one element. First, in (15), the variable t
J
H will replace the nonlinear term:(19)
min
⁡
x
j
:
j
∈
J
∪
H
,and the variable v
J
H will replace(20)
∑
j
∈
J
∪
H
x
j
-
J
∪
H
+
1
+
.Then, we impose the equality constraint:(21)
t
J
H
=
v
J
H
.We will use the notation t
J or t
J
k instead of t
J
H when H is empty or when H coincides with the singleton k, respectively.Thus, we have(22)
P
R
T
C
d
=
⋂
J
d
∈
E
d
P
R
T
C
d
J
d
,where, for each subset J
d of E, the polyhedron P
R
T
C
d
J
d reads(23)
∑
j
∈
N
a
j
T
j
J
,
J
d
-
b
T
0
J
,
J
d
≤
0
,
J
⊆
J
d
,
(24)
T
j
J
,
J
d
-
T
0
J
,
J
d
≤
0
,
j
∈
N
,
J
⊆
J
d
,
(25)
-
T
j
J
,
J
d
≤
0
,
j
∈
N
,
J
⊆
J
d
,
(26)
-
T
0
J
,
J
d
≤
0
,
J
⊆
J
d
,
(27)
min
⁡
x
j
:
j
∈
J
≥
t
J
,
J
⊆
J
d
,
(28)
∑
j
∈
J
x
j
-
J
+
1
≤
t
J
,
J
⊆
J
d
,
(29)
min
⁡
x
j
:
j
∈
J
∪
k
≥
t
J
k
,
J
⊆
J
d
,
k
∈
N
∖
E
,
(30)
x
k
+
∑
j
∈
J
x
j
-
J
≤
t
J
k
,
J
⊆
J
d
,
k
∈
N
∖
E
,
(31)
t
J
,
t
J
k
≥
0
,
J
⊆
J
d
,
k
∈
N
∖
E
,and where, for every index j belonging to N, T
j
J
,
J
d and T
0
J
,
J
d denote the linearized forms of the convexified form of the polynomials x
j
F
d
J
,
J
d
∖
J and F
d
J
,
J
d
∖
J, respectively; these are related to the t
J and t
J
k variables as follows:(32)
T
j
J
,
J
d
=
∑
J
⊆
H
⊆
J
d
-
1
H
∖
J
t
H
∪
j
,
J
d
,
J
⊆
J
d
,
j
∈
E
,
T
j
J
,
J
d
=
∑
J
⊆
H
⊆
J
d
-
1
H
∖
J
t
H
j
,
J
d
,
J
⊆
J
d
,
j
∈
N
∖
E
,
T
0
J
,
J
d
=
∑
J
⊆
H
⊆
J
d
-
1
H
∖
J
t
H
,
J
d
,
J
⊆
J
d
.The linear description (23)–(31) and (32) are stated using only the variables t
J
H. This is possible according to (21). As discussed in Section 5, discarding constraints (21) in the definition of the R
T
C hierarchy will lead to a weaker hierarchy.For every integerd belonging to 1
,
…
,
n, let P
^
R
T
C
d be the projection onto the x-space of the extended linear description P
R
T
C
d. The polyhedron P
^
R
T
C
d will be calledrank-d
reformulation-term-convexification relaxation of X.In the next theorem we will prove that the hierarchyR
T
C is equivalent to the hierarchy R
L
T.Theorem 4.
For every integerd belonging to 1
,
…
,
n, the two linear relaxations P
^
R
L
T
d and P
^
R
T
C
d are equivalent.Proof.
We will proceed by showing that the two extended linear descriptionsP
R
L
T
d and P
R
T
C
d are the same up to variable renaming. Let d be an integer belonging to 1
,
…
,
n. As shown in [8], for every set J
d belonging to E
[
d
], the constraints(33)
min
⁡
x
j
:
j
∈
J
≥
w
J
,
J
⊆
J
d
,
(34)
∑
j
∈
J
x
j
-
J
+
1
≤
w
J
,
J
⊆
J
d
,are implicit in the linear description of P
R
L
T
d. We claim that the constraints(35)
min
⁡
x
j
:
j
∈
J
∪
k
≥
w
J
k
,
J
⊆
J
d
,
k
∈
N
∖
E
,
(36)
x
k
+
∑
j
∈
J
x
j
-
J
≤
w
J
k
,
J
⊆
J
d
,
k
∈
N
∖
E
,are also implicit in the linear description of P
R
L
T
d. The argument is obvious for constraints (35). For constraints (36), let k be an index belonging to N
∖
E and let J be a subset from J
d, and the following constraint(37)
x
k
+
∏
j
∈
J
x
j
1
-
x
k
≤
1 is valid for P
^
R
L
T
d. Using R
L
T linearization, we get the constraint(38)
x
k
+
w
J
-
w
J
k
≤
1
. Combining this last constraint with constraint (34) we deduce that(39)
x
k
+
∑
j
∈
J
x
j
-
J
≤
w
J
k
,
J
⊆
J
d
,
k
∈
N
∖
E
. Now consider the following identifications: (40)
w
J
=
t
J
∀
J
⊆
E
,
J
≤
min
⁡
d
+
1
,
n
,
w
J
k
=
t
J
k
for  every
k
∈
N
∖
E
,
J
⊆
E
,
J
≤
min
⁡
d
,
n
.These identifications imply identifications between the W and T variables through (12) and (32). Thus, the two extended linear descriptions P
R
L
T
d and P
R
T
C
d are equivalent. This completes the proof.Consequently, the rank-n
R
T
C relaxation coincides with the convex hull of the mixed integer set X. The R
T
C hierarchy is motivated by the next theorem where it is shown that the projection onto the x-space of any R
T
C relaxation can be sandwiched between two convex sets. The following proposition will be useful.Proposition 5.
LetJ and H be two disjoint subsets from N, such that x
j belongs to 0,1 for all j belonging to J
∪
H; then (41)
∑
j
∈
J
x
j
+
∑
j
∈
H
1
-
x
j
-
J
∪
H
+
1
+
≤
min
⁡
m
i
n
h
∈
J
x
h
,
m
i
n
h
∈
H
1
-
x
h
.Theorem 6.
For every integerd belonging to 1
,
…
,
n, one has(42)
c
o
n
v
T
d
∩
E
t
d
⊆
P
^
R
T
C
d
⊆
T
d
.Proof.
First, to prove the left inclusion in (42) it is sufficient to prove that the set T
d
∩
E
t
d is included in P
^
R
T
C
d. Let x
^ be a point belonging to the set T
d
∩
E
t
d. Let x
^
,
t
^
,
v
^ be a vector such that(43)
t
^
J
=
min
⁡
x
^
j
:
j
∈
J
,
J
⊂
E
,
J
≤
m
i
n
d
+
1
,
n
,
t
^
J
k
=
min
⁡
x
^
j
:
j
∈
J
∪
k
,
k
∈
N
∖
E
,
J
⊂
J
d
,
J
d
∈
E
d
,
v
^
J
=
∑
j
∈
J
x
^
j
-
J
+
1
+
,
J
⊂
E
,
J
≤
min
⁡
d
+
1
,
n
,
v
^
J
k
=
x
^
k
+
∑
j
∈
J
x
^
j
-
J
+
2
+
,
k
∈
N
∖
E
,
J
⊂
J
d
,
J
d
∈
E
d
.Thus, by definition constraints (31) are fulfilled by the vector x
^
,
t
^
,
v
^. Since x
^ belongs to T
d, then x
^
,
t
^
,
v
^ satisfies constraints (23)–(26). By Proposition 5 the point x
^
,
t
^
,
v
^ satisfies constraints (27)–(30). Since the vector x
^ also belongs to the set E
t
d, then the vector x
^
,
t
^
,
v
^ also satisfies constraints (21). Consequently, the vector x
^
,
t
^
,
v
^ belongs to P
R
T
C
d. Thus, x
^ belongs to P
^
R
T
C
d.
Now, let us prove the right inclusion in (42). Let x
^ be a point belonging to P
^
R
T
C
d. There is a vector t
^ such that x
^
,
t
^ belongs to P
R
T
C
d. Without loss of generality, any constraint defining P
R
T
C
d can be written as follows:(44)
∑
J
∈
S
1
+
a
J
+
t
J
+
∑
J
∈
S
2
+
,
k
∈
N
∖
E
b
J
+
t
J
k
+
∑
J
∈
S
1
-
a
J
-
t
J
+
∑
J
∈
S
2
-
,
k
∈
N
∖
E
b
J
-
t
J
k
≤
0
,where S
1
+
,
S
2
+
,
S
1
-, and S
2
- are subsets of the power set of N (the superscript of a coefficient indicates its sign). Since the point x
^
,
t
^ satisfies the following inequalities: (45)
∑
j
∈
J
x
^
j
-
J
+
1
+
≤
t
^
J
≤
min
⁡
x
^
j
:
j
∈
J
,
J
⊆
J
d
,
x
^
k
+
∑
j
∈
J
x
^
j
-
J
+
≤
t
^
J
k
≤
min
⁡
x
^
j
:
j
∈
J
∪
k
,
J
⊆
J
d
,
k
∈
N
∖
E
,then we deduce(46)
∑
J
∈
S
1
+
a
J
+
∑
j
∈
J
x
^
j
-
J
+
1
+
+
∑
J
∈
S
2
+
,
k
∈
N
∖
E
b
J
+
x
^
k
+
∑
j
∈
J
x
^
j
-
J
+
+
∑
J
∈
S
1
-
a
J
-
m
i
n
j
∈
J
x
^
j
+
∑
J
∈
S
2
-
,
k
∈
N
∖
E
b
J
-
m
i
n
j
∈
J
∪
k
x
^
j
≤
0
.Consequently, the point x
^ satisfies all constraints defining T
d: that is, P
^
R
T
C
d
⊆
T
d. This completes the proof.Characterization (42) will allow us, in some cases (see Corollary 8), to give an explicit characterization of any R
L
T relaxation (characterization in the x-space). Before answering this question we will recall, in the next proposition, the simple result stating that any fractional point belonging to the set E
t will belong to either a facet or an edge of the hypercube. This implies that the set E
t has empty interior.Proposition 7.
For avery subsetJ from N, such that 0
<
x
j
≤
1 for all j belonging to the set J, if(47)
∑
j
∈
J
x
j
-
J
+
1
+
=
min
⁡
x
j
:
j
∈
J
,then at least J
-
1 variables are equal to 1.As a consequence of Theorem6 and Proposition 7 we have the following corollary.Corollary 8.
For every integerd belonging to 1
,
…
,
n, if the set T
d has integer vertices then it coincides with the projection of P
R
L
T
d onto the x-space.Proof.
Letd be an integer belonging to 1
,
…
,
n. On the one hand, the sets T
d and E
t
d are both subsets from the hypercube. On the other hand, if the set T
d has integer vertices then both sets T
d
∩
E
t
d and T
d have the same vertices (vertices of T
d). Thus, the convex envelope of the set T
d
∩
E
t
d coincides with the set T
d, because T
d is convex. Consequently, using Theorems 4 and 6 we conclude that (48)
P
^
R
L
T
d
=
T
d
.This completes the proof.The following example shows that restricting the setT
d to have integer vertices in Corollary 8 is not a sufficient condition to characterize P
^
R
L
T
d. Let us consider the following set:(49)
X
=
x
,
y
∈
0,1
2
:
-
9
x
+
6
y
≤
1
,
-
12
x
+
15
y
≤
6
.Its continuous relaxation X
¯ is the shaded region drawn in Figure 1. The set T
1 associated with the set X is the shaded region drawn in Figure 2. A careful analysis of the set T
1 shows that it features the following linear description: (50)
T
1
=
x
,
y
∈
0,1
2
:
-
5
x
+
6
y
≤
1
,
-
4
x
+
3
y
≤
0
.Figure 1
The setX
¯.Figure 2
The setT
1.The rank-1R
L
T relaxation has the same linear description as T
1. But, as shown in Figure 2, the set T
1 has a fractional vertex. Notice that set (49) coincides with the the rank-1  L
&
P relaxation. As discussed in Section 5, this equality is not true in general. Finally, the set T
2 (the shaded region in Figure 3) has integer vertices and it coincides with the rank-2
R
L
T relaxation.Figure 3
The setT
2.


## 3.2. Reformulation-Standard-Convexification Hierarchy

Contrary to theR
T
C hierarchy, in thereformulation-standard-convexification hierarchy (R
S
C) we convexify each factor obtained after reformulation and not the monomials appearing in each such factors. The termstandard extension was introduced by Crama (see [24]) in studying concave envelopes of pseudo-boolean functions.LetS
d be the nonlinear convex set:(51)
S
d
=
⋂
J
d
∈
E
d
S
d
J
d
,where, for each cardinality d subset J
d of E, the convex set S
d
J
d corresponds to the solution set of R
d
J
d defined by the nonlinear system deduced from (7) using the following convexification scheme: (52)
L
α
∏
k
∈
H
x
k
∏
j
∈
K
1
-
x
j
=
α
∑
j
∈
H
x
j
+
∑
j
∈
K
1
-
x
j
-
K
∪
H
+
1
+
i
f
α
>
0
,
α
min
⁡
m
i
n
j
∈
H
x
j
,
m
i
n
k
∈
K
1
-
x
k
i
f
α
≤
0
,where H and K are two subsets such that K
⊂
E, H
⊂
N, and H
∩
N
∖
E
≤
1.As for thel operator, depending on the type of the constraint (≥ or ≤), we use the m
i
n expression or the m
a
x expression in such a way that the resulting solution set will be convex.The nonlinear description of the setS
d
J
d, for a given d and a set J
d, is thus defined as follows:(53)
∑
j
∈
N
L
j
J
,
J
d
a
i
j
+
L
0
J
,
J
d
-
b
i
≤
0
,
J
⊆
J
d
,
i
=
1
,
…
,
ρ
,
L
j
J
,
J
d
1
+
L
0
J
,
J
d
-
1
≤
0
,
j
∈
E
,
J
⊆
J
d
,
L
j
J
,
J
d
-
1
≤
0
,
j
∈
N
,
J
⊆
J
d
,
L
0
J
,
J
d
-
1
≤
0
,
J
⊆
J
d
,where, for every index j belonging to N and any scalar σ, L
j
J
,
J
d
σ and L
0
J
,
J
d
σ denote the convexified forms of the polynomials σ
x
j
F
d
J
,
J
d
∖
J and σ
F
d
J
,
J
d
∖
J using the operator L, respectively.Since the setS
d as defined in (51) is the intersection of convex sets then we have the following results.Theorem 9.
For every integerd belonging to {
1
,
…
,
n
}, the set S
d as defined by (51) is a nonlinear convex relaxation of the mixed integer set X.For every integerd, let E
s
d be the set (the lower-script s is used to recall that our set is related to thestandard convexification scheme)(54)
E
s
d
=
⋂
J
d
∈
E
d
,
K
∈
N
∖
J
d
1
E
s
J
d
,
K
, where for subsets J
d
∈
E
d and K
∈
N
∖
J
d
1 the set E
s
J
d
,
K is the subset from 0,1
n
+
m defined by the following constraints: (55)
∑
j
∈
J
∪
K
x
j
+
∑
j
∈
J
d
∖
J
1
-
x
j
-
d
+
1
+
=
min
⁡
min
⁡
x
j
:
j
∈
J
∪
K
,
min
⁡
1
-
x
j
:
j
∈
J
d
∖
J
,
J
⊆
J
d
.Since every binary vector from0,1
n
+
m belongs to E
s
d then the set c
o
n
v
E
s
d coincides with the hypercube 0,1
n
+
m. Notice that the set E
s
d is a subset from E
t
d. As shown below, it is possible to represent S
d
∩
E
s
d as a polyhedron in some appropriate extended space.LetP
R
S
C
d denote the extended linear description of the set S
d
∩
E
s
d obtained by using the following steps. First, let G and D be two sets of variables such that, for every d-element set J
d, for every subset J from J
d, and for every subset K from N
∖
J
d with at most one element, G
K
J
,
J
d replaces in (53) the nonlinear term:(56)
min
⁡
m
i
n
h
∈
J
∪
K
x
h
,
m
i
n
k
∈
J
d
∖
J
1
-
x
k
,and the variable D
K
J
,
J
d replaces(57)
∑
h
∈
J
∪
K
x
h
+
∑
k
∈
J
d
∖
J
1
-
x
k
-
d
+
1
+
.Then we impose the following equality:(58)
G
K
J
,
J
d
=
D
K
J
,
J
d
.In the sequel, instead ofG
K
J
,
J
d or D
K
J
,
J
d we will use G
j
J
,
J
d or D
j
J
,
J
d when the set K coincides with the singleton j and G
0
J
,
J
d or D
0
J
,
J
d otherwise (recall that the set K has at most one element).Thus, we obtain the extended linear description:(59)
P
R
S
C
d
=
⋂
J
d
∈
E
d
P
R
S
C
d
J
d
,where, for each subset J
d of E, the polyhedron P
R
S
C
d
J
d reads(60)
∑
j
∈
N
a
j
G
j
J
,
J
d
-
b
G
0
J
,
J
d
≤
0
,
J
⊆
J
d
,
(61)
G
j
J
,
J
d
-
G
0
J
,
J
d
≤
0
,
j
∈
E
,
J
⊆
J
d
,
(62)
-
G
j
J
,
J
d
≤
0
,
j
∈
N
,
J
⊆
J
d
,
(63)
-
G
0
J
,
J
d
≤
0
,
J
⊆
J
d
,
(64)
min
⁡
x
k
:
k
∈
J
∪
j
≥
G
j
J
,
J
d
,
j
∈
N
∖
J
d
,
J
⊆
J
d
,
(65)
min
⁡
1
-
x
k
:
k
∈
J
d
∖
J
≥
G
j
J
,
J
d
,
j
∈
N
∖
J
d
,
J
⊆
J
d
,
(66)
min
⁡
x
k
:
k
∈
J
≥
G
0
J
,
J
d
,
J
⊆
J
d
,
(67)
min
⁡
1
-
x
k
:
k
∈
J
d
∖
J
≥
G
0
J
,
J
d
,
J
⊆
J
d
,
(68)
∑
h
∈
J
∪
j
x
h
+
∑
k
∈
J
d
∖
J
1
-
x
k
-
d
+
1
≤
G
j
J
,
J
d
,
j
∈
N
∖
J
d
,
J
⊆
J
d
,
(69)
∑
h
∈
J
x
h
+
∑
k
∈
J
d
∖
J
1
-
x
k
-
d
+
1
≤
G
0
J
,
J
d
,
J
⊆
J
d
.Notice that linear description (60)–(69) are stated using only the variables G. This is possible according to (58). As discussed in the last section, discarding constraints (58) in the definition of the R
S
C hierarchy will lead to a weaker hierarchy.For every integerd belonging to 1
,
…
,
n, let P
^
R
S
C
d be the projection onto the x-space of the extended linear description P
R
S
C
d. The continuous relaxation P
^
R
S
C
d will be calledrank-d
reformulation-standard-convexification relaxation of the mixed integer set X.As for theR
T
C hierarchy, in the following theorem we will prove that any relaxation of the R
S
C hierarchy can also be sandwiched between two convex sets.Theorem 10.
For every integerd belonging to 1
,
…
,
n, we have(70)
c
o
n
v
S
d
∩
E
s
d
⊆
P
^
R
S
C
d
⊆
S
d
.Proof.
Letd be an integer belonging to 1
,
…
,
n. First, to prove the left inclusion in (70) it is sufficient to prove that the set S
d
∩
E
s
d is a subset of P
^
R
S
C
d. Let x
^ be a point belonging to the set S
d
∩
E
s
d. Let x
^
,
G
^
,
D
^ be a vector where the two vectors G
^ and D
^ are defined as follows: for every d-element set J
d, for every subset J from J
d, and for every subset K from N
∖
J
d with at most one element:(71)
G
^
K
J
,
J
d
=
min
⁡
min
h
∈
J
∪
K
⁡
x
^
h
⁡
,
m
i
n
k
∈
J
d
∖
J
1
-
x
^
k
,
D
^
K
J
,
J
d
=
∑
h
∈
J
∪
K
x
^
h
+
∑
k
∈
J
d
∖
J
1
-
x
^
k
-
d
+
1
+
.By definition, x
^ belongs to S
d; then x
^
,
G
^
,
D
^ satisfies constraints (60)–(63). By Proposition 5 the point x
^
,
G
^
,
D
^ also satisfies constraints (64)–(69). Since the vector x
^ also belongs to the set E
s
d, then the vector x
^
,
G
^
,
D
^ also satisfies constraints (58). Thus, the vector x
^
,
G
^
,
D
^ belongs to P
R
S
C
d. Consequently, x
^ belongs to P
^
R
S
C
d. This completes the first part of the proof.
Now, let us show the right inclusion in (70). Let x
^ be a point belonging to P
^
R
S
C
d. There is a vector G
^ such that x
^
,
G
^ belongs to P
R
S
C
d. Without loss of generality, each constraint in (60) and (61) can be rewritten as follows:(72)
∑
j
∈
N
:
α
i
j
>
0
α
i
j
G
j
J
,
J
d
+
∑
j
∈
N
:
α
i
j
<
0
α
i
j
G
j
J
,
J
d
-
β
i
G
0
J
,
J
d
≤
0
,
J
⊆
J
d
.Without loss of generality, we can assume that β
i is nonnegative (the argument we will use holds also in the case where β
i is nonpositive). The point x
^
,
G
^ satisfies also the constraints: (73)
min
⁡
x
^
k
:
k
∈
J
≥
G
^
0
J
,
J
d
,
J
⊆
J
d
,
min
⁡
1
-
x
^
k
:
k
∈
J
d
∖
J
≥
G
^
0
J
,
J
d
,
J
⊆
J
d
,
∑
h
∈
J
x
^
h
+
∑
k
∈
J
d
∖
J
1
-
x
^
k
-
d
+
1
+
≤
G
^
0
J
,
J
d
,
J
⊆
J
d
,
min
⁡
x
^
k
:
k
∈
J
∪
j
≥
G
^
j
J
,
J
d
,
j
∈
N
∖
J
d
,
J
⊆
J
d
,
min
⁡
1
-
x
^
k
:
k
∈
J
d
∖
J
≥
G
^
j
J
,
J
d
,
j
∈
N
∖
J
d
,
J
⊆
J
d
,
∑
h
∈
J
∪
j
x
^
h
+
∑
k
∈
J
d
∖
J
1
-
x
^
k
-
d
+
1
+
≤
G
^
j
J
,
J
d
,
j
∈
N
∖
J
d
,
J
⊆
J
d
.Thus, we have (74)
∑
j
∈
N
:
α
i
j
>
0
α
i
j
∑
h
∈
J
x
^
h
+
∑
k
∈
J
d
∖
J
1
-
x
^
k
-
d
+
1
+
+
∑
j
∈
N
:
α
i
j
<
0
α
i
j
min
⁡
m
i
n
k
∈
J
∪
j
x
^
k
,
m
i
n
k
∈
J
d
∖
J
1
-
x
^
k
-
β
i
min
⁡
m
i
n
k
∈
J
x
^
k
,
m
i
n
k
∈
J
d
∖
J
1
-
x
^
k
G
0
J
,
J
d
≤
∑
j
∈
N
:
α
i
j
>
0
α
i
j
G
j
J
,
J
d
+
∑
j
∈
N
:
α
i
j
<
0
α
i
j
G
j
J
,
J
d
-
β
i
G
0
J
,
J
d
,
J
⊆
J
d
. This means that the point x
^ satisfies constraints (53). Thus, x
^ belongs to S
d. This completes the proof.


## 4. Links betweenR
T
C, R
S
C, and L
&
P Extended Linear Descriptions

We will focus, in this section, on the connections between the extended linear descriptions of theR
T
C, R
S
C, and  L
&
P relaxations. First, we will compare the strength of the R
T
C and R
S
C hierarchies. We will prove that for every rank d the relaxation P
^
R
T
C
d dominates the relaxation P
^
R
S
C
d.LetI
=
i
1
,
…
,
i
p be a set of indices and let j be an integer less than or equal to I. Let I
j be the subset from I defined as follows:(75)
I
j
=
∅
,
i
f
j
=
0
,
i
k
∈
I
:
k
≤
j
,
o
t
h
e
r
w
i
s
e
.The following lemmas will be useful to prove the next theorem.Lemma 11.
LetI be i
1
,
…
,
i
p a subset of indices from E. Let K be the set i
0
∪
I, where i
0 does not belong to I. Let us consider the variables y satisfying(76)
y
∅
,
K
=
∑
H
⊆
K
-
1
H
x
H
,
(77)
y
i
k
,
K
∖
I
k
-
1
=
-
∑
i
k
⊆
H
⊆
K
∖
I
k
-
1
-
1
H
x
H
,
k
∈
1
,
…
,
p
.Then, we have the following equality:(78)
y
∅
,
i
0
∪
I
=
1
-
x
i
0
-
∑
k
=
1
p
y
i
k
,
K
∖
I
k
-
1
.Proof.
LetI be the set i
1
,
…
,
i
p and let K be the set i
0
∪
I, where i
0 does not belong to I. Let us consider the variables y satisfying (76)-(77). First, notice that the set(79)
H
⊆
K
:
H
⊆
i
0
∪
⋃
k
=
1
p
H
⊆
K
:
i
k
⊆
H
⊆
K
∖
I
k
-
1 is a partition of the power set of K. Thus,(80)
y
∅
,
K
=
∑
H
⊆
K
-
1
H
x
H
,
=
∑
H
⊆
i
0
-
1
H
x
H
+
∑
k
=
1
p
∑
i
k
⊆
H
⊆
K
∖
I
k
-
1
-
1
H
x
H
. Using (77) we obtain (81)
y
∅
,
K
=
∑
H
⊆
i
0
-
1
H
x
H
-
∑
k
=
1
p
y
i
k
,
K
∖
I
k
-
1
=
1
-
x
i
0
-
∑
k
=
1
p
y
i
k
,
K
∖
I
k
-
1
.Lemma 12.
Letd be an integer belonging to 1
,
…
,
n. Let J
d be a d-element subset from E. Let us consider the nonnegative variables y
J
,
J
d, where J is a subset from J
d, satisfying(82)
y
J
,
J
d
=
∑
J
⊆
H
⊆
J
d
-
1
H
∖
J
x
H
,
J
⊆
J
d
.If the variables x satisfy the following inequalities:(83)
x
H
≤
min
⁡
x
j
:
j
∈
H
,
H
⊆
J
d
,
(84)
x
H
≥
∑
k
∈
H
x
k
-
H
+
1
+
,then the variables y satisfy(85)
y
J
,
J
d
≤
min
⁡
x
j
:
j
∈
J
,
J
⊆
J
d
,
(86)
y
J
,
J
d
≤
min
⁡
1
-
x
j
:
j
∈
J
d
∖
J
,
J
⊆
J
d
,
(87)
y
J
,
J
d
≥
∑
k
∈
J
x
k
-
∑
k
∈
J
d
∖
J
x
k
-
J
+
1
+
.Proof.
Letd be an integer belonging to 1
,
…
,
n. Let E be a finite set and let J
d be a d-element subset from E. It is a well-known fact that the linear transformation (82) is a bijection (see [10]) and its inverse is given by(88)
x
J
=
∑
J
⊆
H
⊆
J
d
y
H
,
J
d
,
J
⊆
J
d
.First, the variables y
J
,
J
d satisfy inequalities (85) because of (88) and (83) and the fact that the variables y
J
,
J
d are all nonnegative. Then, using Lemma 11, which is legitimate because the variables y
J
,
J
d are assumed nonnegative, we deduce the inequalities (86). Finally, notice that for every subset J from J
d we have(89)
x
J
≤
y
J
,
J
d
+
∑
k
∈
J
d
∖
J
x
J
∪
k
. Using inequalities (84) we deduce that(90)
y
J
,
J
d
+
∑
k
∈
J
d
∖
J
x
J
∪
k
≥
∑
k
∈
J
x
k
-
J
+
1
, which is equivalent to(91)
y
J
,
J
d
≥
∑
j
∈
J
x
j
-
∑
k
∈
J
d
∖
J
x
J
∪
k
-
J
+
1
.Thus, for sets J and J
d the variable y
J
,
J
d satisfies inequalities (87) and this completes the proof.Theorem 13.
For every integerd belonging to 1
,
…
,
n we have(92)
P
^
R
T
C
d
⊆
P
^
R
S
C
d
.Proof.
Letd be an integer belonging to 1
,
…
,
n. We will prove that the extended linear description P
R
T
C
d is contained in P
R
S
C
d. Let x
^
,
t
^ be a point belonging to P
R
T
C
d. Let us define the point x
^
,
G
^ as follows:(93)
G
^
j
J
,
J
d
=
∑
J
⊆
H
⊆
J
d
-
1
H
∖
J
t
^
H
∪
j
,
J
d
,
J
⊆
J
d
,
j
∈
E
,
G
^
j
J
,
J
d
=
∑
J
⊆
H
⊆
J
d
-
1
H
∖
J
t
^
H
j
,
J
d
,
J
⊆
J
d
,
j
∈
N
∖
E
,
G
^
0
J
,
J
d
=
∑
J
⊆
H
⊆
J
d
-
1
H
∖
J
t
^
H
,
J
d
,
J
⊆
J
d
.Since the point x
^
,
t
^ satisfies constraints (23)–(25) and (32), then it also satisfies constraints (60)–(63). Particularly, the variables G
^ are nonnegative. Using Lemma 12, where the variables y are replaced by the variables G
^ and the variables x are replaced by the variables t
^, we deduce that the point x
^
,
G
^ satisfies constraints (66), (67), and (69). That is,(94)
min
⁡
x
^
k
:
k
∈
J
≥
G
^
0
J
,
J
d
,
J
⊆
J
d
,
min
⁡
1
-
x
^
k
:
k
∈
J
d
∖
J
≥
G
^
0
J
,
J
d
,
J
⊆
J
d
,
∑
h
∈
J
x
^
h
+
∑
k
∈
J
d
∖
J
1
-
x
^
k
-
d
+
1
≤
G
^
0
J
,
J
d
,
J
⊆
J
d
.We use the same arguments to prove that the point x
^
,
G
^ satisfies constraints (64), (65), and (68): that is,(95)
min
⁡
x
^
k
:
k
∈
J
∪
j
≥
G
^
j
J
,
J
d
,
j
∈
N
∖
J
d
,
J
⊆
J
d
,
min
⁡
1
-
x
^
k
:
k
∈
J
d
∖
J
≥
G
^
j
J
,
J
d
,
j
∈
N
∖
J
d
,
J
⊆
J
d
,
∑
h
∈
J
∪
j
x
^
h
+
∑
k
∈
J
d
∖
J
1
-
x
^
k
-
d
+
1
≤
G
^
j
J
,
J
d
,
j
∈
N
∖
J
d
,
J
⊆
J
d
.Thus, by identifying G
^
j
J
,
J
d with T
j
J
,
J
d and G
^
0
J
,
J
d with T
0
J
,
J
d we conclude that the point x
^
,
G
^ satisfies all constraints (60)–(63). This completes the proof.Now, we will compare the strength of the two hierarchiesR
S
C and L
&
P. As shown in [8], the  L
&
P hierarchy can be obtained from the semialgebraic set (6) using a suitable linearization (for more details, see [8]). Precisely, any rank-d
L
&
P relaxation is a rank-d reformulation-linearization relaxation where the linearization is performed using the following substitutions: for every subset J
d from E, let(96)
Z
j
J
,
J
d
=
x
j
F
d
J
,
J
d
∖
J
∀
j
∈
N
,
J
⊆
J
d
,
Z
0
J
,
J
d
=
F
d
J
,
J
d
∖
J
∀
J
⊆
J
d
.The linearized system we obtain reads(97)
∑
j
=
1
κ
a
j
Z
j
J
,
J
d
-
b
Z
0
J
,
J
d
≤
0
∀
J
⊆
J
d
,
J
d
∈
E
d
,
Z
j
J
,
J
d
-
Z
0
J
,
J
d
≤
0
∀
j
∈
E
,
J
⊆
J
d
,
J
d
∈
E
d
,
Z
j
J
,
J
d
,
Z
0
J
,
J
d
≥
0
∀
j
∈
N
,
J
⊆
J
d
,
J
d
∈
E
d
.Let  P
L
&
P
d be the extended linear description (97). As before, let  P
^
L
&
P
d be its projection onto the x-space.In the next theorem we will prove that the hierarchyL
&
P dominates the hierarchy R
S
C.Theorem 14.
For every integerd belonging to the set 1
,
…
,
n we have(98)
P
^
L
&
P
d
⊆
P
^
R
S
C
d
.Proof.
Letd be an integer belonging to the set 1
,
…
,
n. Let x
^ be a point belonging to  P
^
L
&
P
d. There exists a variable Z
^ such that x
^
,
Z
^ belongs to  P
L
&
P
d. Notice that, for every d-element subset J
d in E, every subset J from J
d, and for every index j from N we have (99)
∑
k
∈
J
∪
j
x
k
-
∑
k
∈
J
d
∖
J
x
k
-
J
+
1
+
≤
Z
j
J
,
J
d
≤
min
⁡
m
i
n
h
∈
J
∪
j
x
h
,
m
i
n
k
∈
J
d
∖
J
1
-
x
k
,
(100)
∑
k
∈
J
x
k
-
∑
k
∈
J
d
∖
J
x
k
-
J
+
1
+
≤
Z
0
J
,
J
d
≤
min
⁡
m
i
n
h
∈
J
x
h
,
m
i
n
k
∈
J
d
∖
J
1
-
x
k
.Constraints (97) and both relations (99) and (100) imply that the point x
^
,
Z
^ satisfies constraints (60)–(69). Thus, the point x
^
,
Z
^ belongs to P
R
S
C
d. Consequently, the point x
^ belongs to P
^
R
S
C
d. This completes the proof.As a byproduct of Theorem14 we obtain an indirect proof of Theorem 13. Indeed, for any rank d, we know from Theorem 4 that P
^
R
T
C
d is equivalent to P
^
R
L
T
d. It is a well-known fact that P
^
R
L
T
d is included in  P
^
L
&
P
d (see [8]). Thus, it follows using Theorem 14 that P
^
R
T
C
d is included in P
^
R
S
C
d.


## 5. WeakR
T
C and Weak R
S
C Hierarchies

In this section, we will introduce aweak version of the R
T
C and R
S
C hierarchies. For both weak hierarchies the rank d extended linear description is obtained by reformulation, convexification using min and max and then linearizing using two distinct sets of variables.More precisely, the rankd extended linear description of theweak-R
T
C hierarchy, denoted by  P
W
R
T
C
d, is defined as P
R
T
C
d except that we discard equality constraints (21) (see Section 3.1). Thus, both sets of variables t
J
H and v
J
H will appear in the description of  P
W
R
T
C
d. Similarly, the rank d extended linear description of theweak-R
S
C hierarchy, denoted by  P
W
R
S
C
d, is defined as  P
R
S
C
d except that we discard equality constraints (58) between the two sets of variables G
K
J
,
J
d and D
K
J
,
J
d (see Section 3.2).To emphasize some connections (small instances are sufficient to reveal these connections. We wish to emphasize that this is not a computational investigation) between the weak hierarchies we will use the computational results shown in Table1. The values computed are the minimum value of rank 1 R
T
C,  L
&
P, R
S
C, W
R
T
C, and  W
R
S
C relaxations for five instances of the multiple constraints knapsack problem. Each instance has 5 constraints and 3 variables. The instances have been generated using the Chu and Beasley procedure given in [28]. The constraint matrix coefficients are integers and randomly chosen in 0
,
…
,
1000. The right-hand-side coefficient of the ith constraint is set to 0.95
∑
j
=
1
3
‍
a
i
j. The jth objective function coefficient is set to 1
/
5
∑
i
=
1
5
a
i
j
+
500
ζ
j, where ζ
j is a real number randomly chosen from the interval 0,1.Table 1
Optimal values of the different relaxations.
Instance
Optimum values
P
^
R
T
C
1
P
^
L
&
P
1
P
^
R
S
C
1
P
^
W
R
T
C
1
P
^
W
R
S
C
1
i
nst-1
-
2676.783
-
2676.8066
-
2677.0347
-
3390.3195
-
2677.0347
inst-2
-
3390.3195
-
3390.7008
-
3391.2893
-
3390.3195
-
3391.2893
inst-3
-
3010.0385
-
3010.0385
-
3010.4338
-
3010.0385
-
3010.4338
inst-4
-
3229.0645
-
3229.1293
-
3229.1293
-
3229.0645
-
3229.1293
inst-5
-
3337.7582
-
3337.7582
-
3337.8134
-
3337.7582
-
3337.8134AlthoughR
T
C is stronger than R
S
C the W
R
T
C and W
R
S
C hierarchies are not comparable in strength as shown by the instances inst-1 and inst-2. The W
R
T
C hierarchy may be stronger than  L
&
P hierarchy as shown by the instances inst-2 and inst-4. Also, the computational results shown in the Table 1 are coherent with the theoretical results proved before: (i) the hierarchy R
T
C is stronger than both  L
&
P and R
S
C hierarchies; (ii) the hierarchy  L
&
P is stronger than hierarchy R
S
C; (iii) the hierarchies R
T
C and R
S
C are stronger than W
R
T
C and W
R
S
C, respectively.


## 6. Conclusion

In this paper, we introduced two new hierarchies calledR
T
C and R
S
C for which the rank d continuous relaxations were denoted by P
^
R
T
C
d and P
^
R
S
C
d, respectively. These two hierarchies are obtained using areformulation-convexification-linearization procedure. The hierarchy R
T
C is obtained using a term convexification scheme and the R
S
C hierarchy is obtained using a standard convexification scheme. Then we compared the strength of these two hierarchies. We proved that (i) the hierarchy R
T
C is equivalent to the R
L
T hierarchy of Sherali-Adams, (ii) the hierarchy R
T
C dominates the hierarchy R
S
C, and (iii) the hierarchy R
S
C is dominated by the Lift-and-Project hierarchy. Next, for every rank d, we proved that c
o
n
v
T
d
∩
E
t
d
⊆
P
^
R
T
C
d
⊆
T
d and c
o
n
v
S
d
∩
E
s
d
⊆
P
^
R
S
C
d
⊆
S
d, where the sets T
d and S
d are convex, while E
t
d and E
s
d are two nonconvex sets with empty interior. The first inclusions allow, in some cases, an explicit characterization of R
L
T relaxations. That is a convex nonlinear description of any R
L
T relaxation in the x-space. Finally, we discussed weak version of both R
T
C and R
S
C hierarchies and emphasized some connections between them using small numerical examples.We conclude with some open questions. First, one may ask whether the hierarchyR
S
C is equivalent to the hierarchy W
R
S
C or not. Also, does the rank n
R
S
C relaxation coincide with the convex envelope of the set X? Finally, is it possible to obtain stronger hierarchies using the exposed reformulation-convexification-linearization approach? Extending this work to more general nonlinear optimization problems will be the subject of a future work.



---

*Source: 784817-2015-11-29.xml*