# Certificates of Optimality for Mixed Integer Linear Programming Using Generalized Subadditive Generator Functions

Authors: Kevin K. H. Cheung; Babak Moazzez
Journal: Advances in Operations Research
 (2016)

---

## Abstract

We introduce generalized subadditive generator functions for mixed integer linear programs. Our results extend Klabjan’s work from pure integer programs with nonnegative entries to general MILPs. These functions suffice to achieve strong subadditive duality. Several properties of the functions are shown. We then use this class of functions to generate certificates of optimality for MILPs. We have performed a computational test study on knapsack problems to investigate the efficiency of the certificates.


---

## Body

## 1. Introduction

Most optimization problems in industry and science today are solved using commercial software packages. Such software packages are to some extent reliable and fast but they generally lack one important feature: verifiability of computations and/or optimality. Verification of reported benchmark results is very crucial in computational research [1]. Commercial solvers rarely, if at all, release to the user the exact procedure that has been followed to solve a specific problem. Without this, on what basis does one trust a solution generated using these solvers? Even if one uses his/her own code for optimization, there are possibilities of bugs, mistakes, and so forth.This issue becomes more apparent when we encounter MILP instances for which different solvers return different solutions as optimal. See [2] for such examples and related discussions.The answer to this problem is to obtain a certificate of optimality: some information that proves the optimality of the solution at hand but is easier to check compared to the original optimization problem.Suppose that a MILP has been solved using a solver. Verifying the optimality of the solution could be an arduous task. Let us assume that we have used cutting planes to solve a MILP instance. In order to verify the optimality, we need to verify that each cutting plane that has been generated is indeed valid for MILP. Both numerical round-off errors and/or coding errors can cause generation of invalid inequalities. Verifying validity of a cut is equivalent to solving another MILP as hard as the original problem. If we use a branch and bound method, then verification of optimality is equivalent to a tree traversal and, in each node of the tree, the correctness of LP relaxation bound must be verified. This can get very complicated if a branch and cut method is used.For example, see [3] where the authors provide a certificate of optimality for an optimal TSP tour through 85,900 cities. This certificate consists of traversing the branch and bound tree and checking optimality at each node and also checking the validity of each cutting plane that has been added. The time needed to check the optimality using this certificate might reach up to 568.9 hours (24 days). The actual time for solving the problem is 286.2 days.On the other hand, a dual function with the same value as the objective value of the (doubtfully) optimal solution verifies the optimality immediately. In the case of linear programming, this is trivial since the dual vector provides such a tool for certification of optimality. However, in the case of MILP, subadditive dual must be used to avoid duality gaps. This calls for a family of functions which are feasible to the subadditive dual and are also easy to evaluate.Subadditive generator functions defined by Klabjan [4] can serve as certificates of optimality for specific families of integer programs. However, they are restricted to pure integer programs with nonnegative entries. In this paper, we first generalize these functions to general mixed integer linear programming and then we show that these functions are feasible in the subadditive dual and that they are enough to get strong duality; that is, if we consider this family only, strong duality still holds. Then, we will make use of these functions for generating certificates of optimality.Sensitivity analysis is another important topic in MILP studies. It has been studied in the work of Wolsey [5] using Chvátal functions and value functions of integer programs and also by Hooker [6] using branch and bound tree and inference duality (see also [7] for a survey). However, in both cases, for a large-size problem, it is not easy to perform sensitivity analysis. In this paper, we will see that if we have an optimal dual feasible function, we can generalize the tools for sensitivity analysis in linear programming to mixed integer programming.Section2 states some preliminaries about subadditive duality. Generalized subadditive generator functions are introduced in Section 3. In Section 4, we show some more properties of these functions. Certificates of optimality and sensitivity analysis using subadditive generator functions are discussed in Section 5, and, in the last section, we present some of our computational experiments and numerical results.


## 2. Preliminaries

Letm and n be positive integers. Let A
∈
Q
m
×
n
,
b
∈
Q
m
,
c
∈
Q
n
,
N
=
1
,
…
,
n
,
I
⊆
N, and C
=
N
∖
I. Let M
A
=
v
∈
R
m
:
v
=
A
x
,
x
i
∈
Z
+
∀
i
∈
I
,
x
i
∈
R
+
∀
i
∈
C. Consider the following mixed integer linear program: M
I
L
P
m
i
n
c
x
s
.
t
.
A
x
=
b
x
≥
0
x
i
∈
Z
∀
i
∈
I
.The subadditive dual of M
I
L
P [7] is given by S
D
m
a
x
F
b
s
.
t
.
F
a
j
≤
c
j
∀
j
∈
I
F
¯
a
j
≤
c
j
∀
j
∈
C
F
∈
Γ
m
, where a
j denotes the jth column of A and Γ
m is the set of subadditive functions F
:
M
A
→
R
∪
-
∞ with F
0
=
0 and F
¯
d
=
lim
⁡
⁡
s
u
p
δ
→
0
+
F
δ
d
/
δ. Recall a function F
:
Δ
→
R
∪
-
∞, where Δ
⊂
R
m is closed under addition (i.e., a monoid) and is said to be subadditive if F
x
+
y
≤
F
x
+
F
y
for all
x
,
y
∈
Δ with the convention that -
∞
-
∞
=
-
∞.Lemma 1.
IfF
∈
Γ
m, then, for any d
∈
M
A with F
¯
d
<
∞ and λ
≥
0, F
λ
d
≤
λ
F
¯
d.Proof.
See [7].Theorem 2 (see [7] (weak duality)).
Supposex is a feasible solution to M
I
L
P and F is a feasible solution to the subadditive dual S
D. Then, F
b
≤
c
x.Proof.
(1)
F
b
=
F
A
x
=
F
∑
i
=
1
n
a
i
x
i
=
F
∑
i
∈
I
a
i
x
i
+
∑
i
∈
C
a
i
x
i
≤
F
∑
i
∈
I
a
i
x
i
+
F
∑
i
∈
C
a
i
x
i
≤
∑
i
∈
I
F
a
i
x
i
+
∑
i
∈
C
F
¯
a
i
x
i
≤
c
x
. The inequalities follow from subadditivity of F and Lemma 1.Theorem 3 (see [8]).
If the primal problemM
I
L
P has a finite optimum, then so does the dual problem S
D and in this case they are equal.Unlike linear programming, finding a dual optimal subadditive function does not seem to be straightforward. Two well-known families are known [9], but they appear to be difficult to work with. However, in the case when all the entries of A and b are nonnegative and all variables are required to be integers, Klabjan [4] defined a family of subadditive functions sufficient for strong duality that are computationally attractive.In the case of linear programming, it is easy to see that the functionF
L
P
d
=
max
v
∈
R
m
⁡
v
d
:
v
A
≤
c is a feasible subadditive function and, using this function, the subadditive dual will reduce to the LP dual.The subadditive dual plays an important role in the study of mixed integer programming. Any feasible solution to the dual gives a lower bound to theM
I
L
P. A dual feasible function F with F
b
=
z
I
P is a certificate of optimality for the M
I
L
P. It will be equivalent to the dual vector in LP and the reduced cost of column i can be defined as c
i
-
F
a
i. Many other properties of LP, such as complementary slackness, for example, can also be extended to MILP. Similar to LP, all optimal solutions can only have nonzero values for variables indexed by i with c
i
=
F
a
i for an optimal F (see [4] for more details).


## 3. Generalized Subadditive Generator Functions

Klabjan [4] defined subadditive generator functions for pure integer programming problems with nonnegative entries as follows.For a pure integer program(2)
min
⁡
c
x
s.t.
A
x
=
b
x
≥
0
,
integer,with nonnegative A and b, asubadditive generator function is defined for a given α
∈
R
m as(3)
F
α
l
=
α
l
-
max
⁡
∑
i
∈
E
α
α
a
i
-
c
i
x
i
:
∑
i
∈
E
α
a
i
x
i
≤
l
,
x
≥
0
,
integer
,where E
α
=
i
∈
N
:
α
a
i
>
c
i.Also, asubadditive ray generator function is defined for a given β
∈
R
m as(4)
G
β
l
=
β
l
-
max
⁡
∑
i
∈
E
β
β
a
i
x
i
:
∑
E
β
a
i
x
i
≤
l
,
x
≥
0
,
integer
,where E
β
=
i
∈
N
:
β
a
i
>
0.In [4], it is shown that these functions are feasible to the subadditive dual, and they are sufficient to achieve strong duality for an IP with nonnegative rational data. In this paper, we extend Klabjan’s work to M
I
L
P with no restriction on input data. Let α
∈
R
m and define E
α
=
i
∈
N
:
α
a
i
>
c
i. Let E
⊆
N be such that E
α
⊆
E. Also, let K
⊆
R
m be such that(5)
∑
i
∉
E
x
i
a
i
:
x
≥
0
,
x
i
∈
Z
∀
i
∈
I
∖
E
⊆
K
.Definition 4.
Forα
∈
R
m
,
E, and K as specified above, define the subadditive generator function F
α
,
E
,
K
:
M
A
→
R
∪
-
∞ by (6)
F
α
,
E
,
K
l
=
α
l
-
max
⁡
∑
i
∈
E
α
a
i
-
c
i
x
i
:
l
-
∑
i
∈
E
a
i
x
i
∈
K
,
x
≥
0
,
x
i
∈
Z
∀
i
∈
E
∩
I
. Also, for E
β
=
i
∈
N
:
β
a
i
>
0, a subadditive ray generator function G
β
,
E
,
K
:
M
A
→
R
∪
-
∞ is defined as(7)
G
β
,
E
,
K
l
=
β
l
-
m
a
x
∑
i
∈
E
β
a
i
x
i
:
l
-
∑
i
∈
E
a
i
x
i
∈
K
,
x
≥
0
,
x
i
∈
Z
∀
i
∈
E
∩
I
.Note that ifK
=
R
n and E
=
∅, then F
α
,
E
,
K
l
=
α
l. We will show in Section 5 that empty E means that the LP relaxation of M
I
L
P solves the M
I
L
P as well, so α
l is an optimal LP dual vector. Also, if K
=
R
n and E
=
E
α
≠
∅, then F
α
,
E
,
K is identically -
∞. In general, one can choose E and K in many different ways. However, later in Section 5, we will show that, with specific choices of E and K (E
=
E
α
∪
i
∈
N
:
a
i
≱
0 and K
=
R
+
n), we can generate good certificates for M
I
L
P. Also, note that 0
∈
K.For a polyhedronP
⊆
R
n, the recession cone of P is defined as r
e
c
P
=
y
∈
R
n
:
x
+
t
y
∈
P
f
o
r
a
l
l
x
∈
P
,
t
≥
0. We will need the following result of Meyer [10].Theorem 5 (Meyer [10]).
Given rational matricesA and G and a rational vector b, let P
:
=
x
,
y
:
A
x
+
G
y
≤
b and let S
≔
x
,
y
∈
P
:
x
i
n
t
e
g
r
a
l. (1)
There exist rational matricesA
′ and G
′ and a rational vector b
′ such that(8)
conv
⁡
S
=
x
,
y
:
A
′
x
+
G
′
y
≤
b
′
.
(2)
IfS is nonempty, the recession cones of conv
⁡
S and P coincide.Theorem 6.
F
α
,
E
,
K
a
i
≤
c
i
f
o
r
a
l
l
i
∈
I and F
¯
α
,
E
,
K
a
i
≤
c
i
f
o
r
a
l
l
i
∈
C.Proof.
First, we will show thatF
α
,
E
,
K
a
i
≤
c
i
f
o
r
a
l
l
i
∈
I. We have (9)
F
α
,
E
,
K
a
i
=
α
a
i
-
max
⁡
∑
i
∈
E
α
a
i
-
c
i
x
i
:
a
i
-
∑
i
∈
E
a
i
x
i
∈
K
,
x
≥
0
,
x
i
∈
Z
∀
i
∈
E
∩
I
. There are two cases: for i
∈
I, i is either in E or not. If i
∈
E, then x
=
δ
i is a feasible solution to the maximization problem where δ
i is the unit vector with 1 as the ith component and zero elsewhere. This gives us F
α
,
E
,
K
a
i
≤
c
i. If i
∉
E, then i
∉
E
α, so α
a
i
≤
c
i which implies that x
=
0 is a feasible solution to the maximization problem and gives us F
α
,
E
,
K
a
i
=
α
a
i
≤
c
i.
To show thatF
¯
α
,
E
,
K
a
i
≤
c
i
f
o
r
a
l
l
i
∈
C, first note that Gomory and Johnson [11] shows that if F
¯
α
,
E
,
K
l is finite, then the limsup and the ordinary limit coincide. Now, we have (10)
F
¯
α
,
E
,
K
a
i
=
lim
h
→
0
+
⁡
F
α
,
E
,
K
h
a
i
h
=
α
a
i
-
lim
h
→
0
+
⁡
1
h
max
⁡
∑
i
∈
E
α
a
i
-
c
i
x
i
:
h
a
i
-
∑
i
∈
E
a
i
x
i
∈
K
,
x
≥
0
,
x
i
∈
Z
∀
i
∈
E
∩
I
. If i is in E, then x
=
h
δ
i is a feasible solution to the maximization problem where δ
i is the unit vector. Then, the maximum will be greater than or equal to h
α
a
i
-
c
i, so the limit will be greater than or equal to α
a
i
-
c
i since h
>
0. This gives us F
¯
α
,
E
,
K
a
i
≤
c
i. If i
∉
E, then x
=
0 is a feasible solution to the maximization problem and a similar argument gives us F
¯
α
,
E
,
K
a
i
≤
α
a
i
≤
c
i.Theorem 7.
LetK be a finitely generated convex cone satisfying (5). Then, F
α
,
E
,
K
l is subadditive for any choice of α and E.Proof.
Letl
1
,
l
2
∈
M
A. To prove subadditivity, that is, F
α
,
E
,
K
l
1
+
l
2
≤
F
α
,
E
,
K
l
1
+
l
2
≤
F
α
,
E
,
K
l
1
+
F
α
,
E
,
K
l
2, it suffices to show (11)
max
⁡
∑
i
∈
E
α
a
i
-
c
i
x
i
:
l
1
-
∑
i
∈
E
a
i
x
i
∈
K
,
x
≥
0
,
x
i
∈
Z
∀
i
∈
E
∩
I
+
max
⁡
∑
i
∈
E
α
a
i
-
c
i
x
i
:
l
2
-
∑
i
∈
E
a
i
x
i
∈
K
,
x
≥
0
,
x
i
∈
Z
∀
i
∈
E
∩
I
≤
max
⁡
∑
i
∈
E
α
a
i
-
c
i
x
i
:
l
1
+
l
2
-
∑
i
∈
E
a
i
x
i
∈
K
,
x
≥
0
,
x
i
∈
Z
∀
i
∈
E
∩
I
. If x
1
∗ and x
2
∗ are optimal solutions for two maximization problems on the left, then x
1
∗
+
x
2
∗ is a feasible solution to the problem on the right and the result follows.The following lemma shows thatF
α
,
E
,
K
0
=
0 for any α
∈
R
m.Lemma 8.
IfF
α
,
E
,
K is not identically -
∞, then F
α
,
E
,
K
0
=
0.Proof.
First, note that(12)
F
α
,
E
,
K
0
=
-
max
⁡
∑
i
∈
E
α
a
i
-
c
i
x
i
:
-
∑
i
∈
E
a
i
x
i
∈
K
,
x
≥
0
.Since x
=
0 satisfies -
∑
i
∈
E
‍
a
i
x
i
∈
K, we get F
α
,
E
,
K
0
≤
0.
Suppose thatF
α
,
E
,
K
0
<
0. If F
α
,
E
,
K
0
=
-
∞, then, by subadditivity,(13)
F
α
,
E
,
K
l
≤
F
α
,
E
,
K
l
+
F
α
,
E
,
K
0
=
-
∞
∀
l
∈
M
A
. Hence, F
α
,
E
,
K
0 is identically -
∞, contradicting the assumption. If F
α
,
E
,
K
0
>
-
∞, then, by subadditivity,(14)
F
α
,
E
,
K
0
≤
F
α
,
E
,
K
0
+
F
α
,
E
,
K
0
, implying that F
α
,
E
,
K
0
≥
0. The result now follows.Theorem 9 (strong duality).
IfM
I
L
P is feasible, then there exist α
∈
R
m, a set E, and a finitely generated convex cone K with F
α
,
E
,
K
b
=
z
M
I
L
P
∗ and F
α
,
E
,
K
0
=
0. If M
I
L
P is infeasible, then there exist β
∈
R
m
,
E, and a finitely generated convex cone K with G
α
,
E
,
K
b
>
0
.Proof.
Without loss of generality, we can assume thatb
≥
0, since otherwise one can multiply rows of A
x
=
b with negative right hand side by -
1 to make b nonnegative and then consider the new problem.
LetK
=
x
:
x
≥
0. Let M
I
L
P be feasible, and let π
j
x
≤
π
0
j
f
o
r
j
∈
J be valid inequalities for the set(15)
V
=
x
:
A
x
≤
b
,
x
≥
0
,
x
i
∈
Z
∀
i
∈
I such that (16)
z
MILP
∗
=
m
i
n
c
x
s
.
t
.
A
x
=
b
π
j
x
≤
π
0
j
j
∈
J
x
≥
0
. Finding such valid inequalities is possible by Theorem 5 where it is shown that if A and b in M
I
L
P are rational, then the convex hull of the feasible points is a polyhedron (finitely generated). Let α
,
γ be an optimal dual vector where γ corresponds to constraints π
j
x
≤
π
0
j
,
j
∈
J. Let E
=
E
α
∪
i
∈
N
:
a
i
≱
0. Then, we have(17)
K
=
x
:
x
≥
0
⊇
∑
i
∉
E
a
i
x
i
:
x
≥
0
,
x
i
∈
Z
∀
i
∈
I
∖
E
. We show that, for these E and K, F
α
,
E
,
K
b
≥
z
MILP
∗.
The dual program of the above LP is(18)
m
a
x
b
α
-
∑
j
∈
J
π
0
j
γ
j
s
.
t
.
α
a
i
-
∑
j
∈
J
π
i
j
γ
j
≤
c
i
,
i
∈
N
α
unrestricted,
γ
≥
0
.The optimal value of this problem is z
MILP
∗. Let x be a nonnegative vector with x
i integer for i
∈
I and ∑
i
∈
E
‍
a
i
x
i
≤
b. We have (19)
∑
i
∈
E
α
a
i
-
c
i
x
i
≤
∑
i
∈
E
∑
j
∈
J
x
i
π
i
j
γ
j
=
∑
j
∈
J
γ
j
∑
i
∈
E
x
i
π
i
j
≤
∑
j
∈
J
γ
j
π
0
j
=
b
α
-
z
M
I
L
P
∗
. The last inequality holds because γ
≥
0 and ∑
i
∈
E
x
i
π
i
j
≤
π
0
j is a valid inequality for the set x
:
∑
i
∈
E
a
i
x
i
≤
b
,
x
≥
0
,
x
i
∈
Z
∀
i
∈
I (which follows from the fact that π
j
x
≤
π
0
j is valid for V and b
≥
0 and that E contains all columns which are not entirely nonnegative). Recall here that K
=
x
:
x
≥
0 and b
-
A
x belong to K (this implies that A
x
≤
b). So we get(20)
max
⁡
∑
i
∈
E
α
a
i
-
c
i
x
i
:
∑
i
∈
E
a
i
x
i
≤
b
,
x
≥
0
,
x
i
∈
Z
∀
i
∈
E
∩
I
≤
b
α
-
z
M
I
L
P
∗
.
This impliesF
α
,
E
,
K
b
≥
z
M
I
L
P
∗. Also, we know that F
α
,
E
,
K
b
≤
z
MILP
∗ since F
α
,
E
,
K is feasible to subadditive dual problem for M
I
L
P. So F
α
,
E
,
K
b
=
z
MILP
∗. Moreover, by Lemma 8, F
α
,
E
,
K
0
=
0.
IfM
I
L
P is infeasible, with the same E and K as above, the problem (21)
m
i
n
1
u
s
.
t
.
A
x
+
u
=
b
x
,
u
≥
0
x
j
integer for
j
∈
Ihas optimal value z
∗
>
0. So there exists some β such that(22)
z
∗
=
b
β
-
max
⁡
∑
i
∈
E
β
a
i
x
i
+
∑
i
∈
E
~
β
i
-
1
u
i
:
∑
i
∈
E
a
i
x
i
+
u
≤
b
,
x
,
u
≥
0
,
x
i
∈
Z
∀
i
∈
I
∩
E
,where E
~
=
i
∈
1
,
…
,
m
:
β
i
>
1 and E
=
i
∈
N
:
β
a
i
>
0
∪
i
∈
N
:
a
i
≱
0. Since u
=
0 is feasible to the maximization problem in (22), we have (23)
0
<
z
∗
≤
b
β
-
max
⁡
∑
i
∈
E
β
a
i
x
i
:
∑
i
∈
E
a
i
x
i
≤
b
,
x
≥
0
,
x
i
∈
Z
∀
i
∈
E
∩
I
,and the proof is complete.


## 4. Properties of Generalized Subadditive Generator Functions

IfF is any subadditive function with F
(
0
)
=
0 and is dual feasible, then (24)
∑
j
∈
I
F
a
j
x
j
+
∑
j
∈
C
F
¯
a
j
x
j
≥
F
b is a valid inequality for M
I
L
P [8].In this section, we will show that, for any MILP, there is a finite set of generalized subadditive generator functions such that their corresponding valid inequalities give a finite description of the convex hull of the MILP. For this reason, it is enough to restrict our attention to a subset of subadditive generator functions called basic subadditive generator functions.In this section,A
E denotes a submatrix of A with column indices in E, and c
E is a subvector of c with indices in E.Theorem 10.
The optimum value ofM
I
L
P is equal to m
a
x
{
η
:
η
,
α
∈
Q
b
E
}, where(25)
Q
b
E
=
η
,
α
∈
R
×
R
m
:
α
a
i
≤
c
i
for
i
∈
N
∖
E
,
η
+
α
A
E
x
-
b
≤
c
E
x
,
b
-
A
E
x
∈
K
,
x
∈
Z
+
E
∩
I
×
R
+
E
∩
C for some E and K.Proof.
By Theorem9, there exists α
∈
R
m with F
α
,
E
,
K
b
=
z
MILP
∗. Choose E
=
E
α
∪
i
∈
N
:
a
i
≱
0, let K
=
x
:
x
≥
0, and consider Q
b
E. Then, (26)
η
∗
=
max
⁡
η
:
η
,
α
∈
Q
b
E
=
max
⁡
η
:
η
≤
c
E
x
-
α
A
E
x
-
b
:
b
-
A
E
x
∈
K
,
x
≥
0
,
x
i
∈
Z
∀
i
∈
I
∩
E
=
α
b
+
max
⁡
c
E
-
α
A
E
x
:
b
-
A
E
x
∈
K
,
x
≥
0
,
x
i
∈
Z
∀
i
∈
I
∩
E
=
F
α
,
E
,
K
b
=
z
MILP
∗
.Theorem 11.
IfK is a finitely generated convex cone, then Q
b
E is a polyhedron.Proof.
K has a finite number of extreme rays. Let M denote the set of extreme rays of K. Since M is finite, we have (27)
Q
b
E
=
η
,
α
∈
R
×
R
m
:
α
a
i
≤
c
i
for
i
∈
N
∖
E
,
η
+
α
A
E
x
-
b
≤
c
E
x
∀
x
∈
M
, which is obviously a polyhedron (finitely generated).Definition 12.
A subadditive generator functionF
α
,
E
,
K is called basic if (
F
α
,
E
,
K
b
,
α
) is an extreme point of (25).It is obvious that one only needs basic subadditive generator functions. But since there are finite choices forE and Q
b
E has a finite number of extreme points, there are only a finite number of basic subadditive generator functions. So the following theorem holds.Theorem 13.
GivenA
,
b, and c, there exists a finite set S
b of subadditive generator functions such that the linear program(28)
m
i
n
c
x
A
x
=
b
∑
j
∈
I
F
α
,
E
,
K
a
j
x
j
+
∑
j
∈
C
F
¯
α
,
E
,
K
a
j
x
j
≥
F
α
,
E
,
K
b
F
α
,
E
,
K
∈
S
b
x
j
≥
0
∀
j
∈
Nhas the following properties: (1)
LP (28) is infeasible if and only if M
I
L
P is infeasible.
(2)
LP (28) has unbounded optimum value if and only if M
I
L
P has unbounded optimum value.
(3)
If neither of the cases above holds, then LP (28) has an optimal extreme point solution which is also optimal for M
I
L
P.IfP
⊆
R
n is a convex polyhedron, then a face of P is defined as F
=
P
∩
x
∈
R
n
:
c
x
=
d, where c
x
≤
d is a valid inequality for P. A facet is a face with dimension d
i
m
(
P
)
-
1. Since we know that the convex hull of feasible solutions to M
I
L
P is polyhedral, that is, it can be described by a finite set of facet defining valid inequalities, we have the following corollary.Corollary 14.
ForA and b rational, there exists a finite set of subadditive generator functions F
α
i
,
E
,
K
i
=
1
R such that (29)
A
x
=
b
,
∑
j
∈
I
F
α
i
,
E
,
K
a
j
x
j
+
∑
j
∈
C
F
¯
α
i
,
E
,
K
a
j
x
j
≥
F
α
i
,
E
,
K
b
i
=
1
,
…
,
R
,
x
j
≥
0
∀
j
∈
Nis the convex hull of solutions to M
I
L
P with right hand side b.


## 5. Certificates of Optimality and Sensitivity Analysis

In this section, we show that subadditive generator functions can be used as certificates of optimality for MILPs.Definition 15.
A certificate of optimality for a MILP is the information that can be used to check optimality without having to solve the MILP itself.Ideally, we are interested in types of certificates that allow us to perform the checking in (much) shorter time. By Theorem9, any subadditive generator function with F
α
,
E
,
K
b
=
z
M
I
L
P
∗ for which E is smaller than N can be used as a certificate of optimality.Definition 16.
ForM
I
L
P with optimal solution x
∗, α is a certificate of optimality if F
α
,
E
,
K
b
=
c
x
∗. One calls α
∈
R
m a “good” certificate if E
≪
n. α
∗ is called minimal if one has(30)
α
∗
=
argmin
α
∈
R
m
⁡
E
:
F
α
,
E
,
K
b
=
z
M
I
L
P
∗
.Theorem 17.
Assume thatE
=
E
α
∪
i
∈
N
:
a
i
≱
0. Let E
=
∅. Then, α is a minimal certificate of optimality for M
I
L
P if and only if the optimal solution of the linear programming relaxation of M
I
L
P solves M
I
L
P.Proof.
Without loss of generality, assume thatb
≥
0. If α is such that E
=
∅, then F
α
,
E
,
K
b
=
α
b with α
A
≤
c. This means that α is the optimal solution to the linear programming dual of the LP relaxation of M
I
L
P. Conversely, suppose that α is the optimal solution to the linear programming dual of the LP relaxation. Then, we have F
α
,
E
,
K
b
=
α
b with α
A
≤
c and obviously E
=
∅.The following example shows that there might not be a unique optimalα.Example 18.
Consider the following IP:(31)
m
i
n
6
x
1
+
6
x
2
+
9
x
3
+
10
x
4
+
7
x
5
s
.
t
.
x
4
+
x
5
=
1
x
1
+
x
2
+
x
3
+
x
4
=
1
x
1
+
x
5
=
1
x
∈
0,1
5
.Any α
1
,
α
2
,
α
3 with α
1
=
7
,
α
2
=
6 and α
3
∈
[
3,7
] gives F
α
,
E
,
K
b
=
z
M
I
L
P
∗ with E
=
E
α
=
1,4
,
5. Any α with E
≤
2 will give F
α
,
E
,
K
b
<
z
M
I
L
P
∗.Note that if the size ofE is much smaller than N, then the certificate that we have is much easier to check since the number of variables is remarkably reduced. However, there still might be instances where E
=
N or size of E is comparable to N. In this case, obviously, we do not have a good certificate. Fortunately, in our computational experiments, such cases are not observed for the families of problems considered. For example, consider the following pure ILP: (32)
m
i
n
x
1
+
2
x
2
+
⋯
+
n
x
n
s
.
t
.
2
x
1
+
2
x
2
+
⋯
+
2
x
n
-
1
+
x
n
=
3
x
∈
Z
+
n
.Clearly, there is a unique optimal solution (x
1
=
x
n
=
1 and x
2
=
⋯
=
x
n
-
1
=
0). In this example, α
∗
=
n with E
=
1
,
…
,
n
-
1.Note that, in such cases whereE has large cardinality, we still have a certificate; that is, we have a (subadditive) dual feasible function F with F
b
=
z
MILP
∗. Verifying the optimality using this certificate is still less expensive than using the branch and bound tree as a certificate and verifying the validity of all cutting planes (as mentioned before, verification of validity of a cutting plane is equivalent to solving a mixed integer of the same size as the original MILP).Remark 19 (see [12]).
ForM
I
L
P with optimal solution x
∗, α with F
α
,
E
,
K
b
=
c
x
∗ can be used for sensitivity analysis.We refer the reader to [5, 13] where the authors state the conditions under which primal feasibility, dual feasibility, and optimality still hold for x
∗ and F
∗ (optimal primal vector and subadditive dual function) after changes made to the input of M
I
L
P.In Definition4, K can be any convex cone satisfying (5). However, choosing K to be the nonnegative orthant makes us able to generate better certificates. For the rest of the paper, we focus on subadditive generator functions with E
=
E
α
∪
i
∈
N
:
a
i
≱
0 and K
=
x
:
x
≥
0 as stated previously in the proof of Theorem 9.


### 5.1. Obtainingα
∗

Theorem9 tells us that if we add a family of cutting planes π
j
x
≤
π
0
j
,
j
∈
J, to the LP relaxation of M
I
L
P, such that we have(33)
z
M
I
L
P
∗
=
m
i
n
c
x
s
.
t
.
A
x
=
b
π
j
x
≤
π
0
j
,
j
∈
J
x
≥
0
,then if α
,
γ is an optimal dual vector where γ corresponds to constraints π
j
x
≤
π
0
j
,
j
∈
J, F
α
b
≥
z
MILP
∗. In other words, the existence of such α is guaranteed by Theorem 9.Note that if we add the cutc
x
≥
z
M
I
L
P
∗ to M
I
L
P, then obviously we can use α calculated using Theorem 9 since for that α we have F
α
b
=
c
x
∗
=
z
MILP
∗. However, based on our empirical observations through computational experiments, the size of E
α in this case is usually equal to or comparable to n. We have observed that the more cuts we add to the LP relaxation of M
I
L
P, the better α we can get using Theorem 9. We have also observed that if we add enough cuts so that the optimal solution of the LP relaxation is x
∗, then the size of E is much less than N, so we can consider it as a good certificate.We should note that the cutting planesπ
j
x
≤
π
0
j
,
j
∈
J, must be valid inequalities for the set V
=
x
∈
Z
+
I
×
R
+
C
:
A
x
≤
b by Theorem 9. This leads us to the lifting problem: each cutting plane that we add to the LP relaxation of M
I
L
P must be lifted first to become valid for the set V.Next, we show that the setx
,
y
∈
Z
+
n
×
R
+
n
:
A
x
+
B
y
=
b
≠
∅ is a face of x
,
y
∈
Z
+
n
×
R
+
n
:
A
x
+
B
y
≤
b. So the problem of lifting is well defined. In other words, the following theorem shows that the feasible region of M
I
L
P is a face of the polyhedral set V.Theorem 20.
The polyhedral set(34)
conv
⁡
x
,
y
∈
Z
+
n
×
R
+
n
:
A
x
+
B
y
=
b
≠
∅ is a face of the polyhedral set(35)
conv
⁡
x
,
y
∈
Z
+
n
×
R
+
n
:
A
x
+
B
y
≤
b
, where A and b have rational entries.In order to prove this theorem, we first need few lemmas.Lemma 21.
LetP
=
x
:
A
x
≤
b be a polyhedron and let T
=
x
:
α
x
≤
α
0 be a supporting hyperplane of P. Then, P
∩
x
:
α
x
=
α
0 is a face of P.Proof.
See [14].LetP
1
=
x
,
y
∈
Z
+
n
×
R
+
n
:
A
x
+
B
y
=
b
≠
∅ and P
2
=
x
,
y
∈
Z
+
n
×
R
+
n
:
A
x
+
B
y
≤
b. Also, let P
1
′
=
conv
⁡
P
1 and P
2
′
=
conv
⁡
P
2. Let π
1
=
1
A and π
2
=
1
B and π
0
=
1
b, where 1 is the vector of ones. Obviously, π
1
x
+
π
2
y
≤
π
0 is a supporting hyperplane of P
2
′. To see this, let x
∗
,
y
∗ be a feasible point of P
1. This point is on the hyperplane π
1
x
+
π
2
y
=
π
0 and is also in P
2 and so in P
2
′. Also, any point in P
2
′ will satisfy A
x
+
B
y
≤
b and hence π
1
x
+
π
2
y
≤
π
0 (note that P
1
⊆
P
1
′
⊆
{
x
,
y
∈
R
+
n
+
p
:
A
x
+
B
y
=
b
} and P
2
⊆
P
2
′
⊆
x
,
y
∈
R
+
n
+
p
:
A
x
+
B
y
≤
b).Lemma 22.
e
x
t
P
1
′
⊆
P
2
′
∩
x
,
y
:
π
1
x
+
π
2
y
=
π
0, where e
x
t is the set of extreme points.Proof.
Suppose thatx
,
y
∈
e
x
t
P
1
′. This means that x
,
y
∈
P
1
′ and x is integral. So, we have A
x
+
B
y
=
b. Now, we conclude that π
1
x
+
π
2
y
=
π
0 and A
x
+
B
y
≤
b. Since x is integral, x
,
y
∈
P
2, which implies x
,
y
∈
P
2
′, and this completes the proof.Lemma 23.
e
x
t
P
2
′
∩
x
,
y
:
π
1
x
+
π
2
y
=
π
0
⊆
P
1
′.Proof.
Letx
,
y be an extreme point of P
2
′ with π
1
x
+
π
2
y
=
π
0. Since x
,
y
∈
P
2
′, we have A
x
+
B
y
≤
b and also x is integral. Since π
1
x
+
π
2
y
=
π
0 and A
x
+
B
y
≤
b, we conclude that A
x
+
B
y
=
b (we can take proper combinations of the rows of the two systems). Since x is integral, x
,
y
∈
P
1 and so x
,
y
∈
P
1
′.Proof of the Theorem.
From Theorem5, we know that(36)
rec
⁡
P
1
=
rec
⁡
P
1
′
,
rec
⁡
P
2
=
rec
⁡
P
2
′
. Also, it is obvious that since P
1
⊆
P
2, rec
⁡
P
1
⊆
rec
⁡
(
P
2
), so(37)
rec
⁡
P
1
′
⊆
rec
⁡
P
2
′
.Moreover, we know(38)
rec
⁡
P
1
=
x
,
y
∈
Z
+
n
×
R
+
n
:
A
x
+
B
y
=
0
,
rec
⁡
P
2
=
x
,
y
∈
Z
+
n
×
R
+
n
:
A
x
+
B
y
≤
0
. Now, let x
,
y
∈
P
1
′. Then, by a theorem of Minkowski and Weyl (see [14, page 88]), we can write(39)
x
,
y
=
∑
λ
i
x
i
,
y
i
+
∑
μ
i
z
i
,
w
i
, where ∑
‍
λ
i
=
1 and x
i
,
y
i are extreme points and z
i
,
w
i are extreme rays of P
1
′. By Lemma 22, x
i
,
y
i
∈
P
2
′
∩
x
,
y
:
π
1
x
+
π
2
y
=
π
0. Also, we have(40)
π
1
x
+
π
2
y
=
∑
λ
i
π
1
x
i
+
π
2
y
i
+
∑
μ
i
π
1
z
i
+
π
2
w
i
. But π
1
z
i
+
π
2
w
i
=
0 since (
z
i
,
w
i
) are extreme rays of P
1
′ and π
1
=
1
A, π
2
=
1
B, and ∑
‍
λ
i
π
1
x
i
+
π
2
y
i
=
∑
‍
λ
i
π
0
=
π
0. This shows that π
1
x
+
π
2
y
=
π
0. Now, using (37) and the fact that P
2
′ and x
,
y
:
π
1
x
+
π
2
y
=
π
0 are both convex sets, we can conclude x
,
y
∈
P
2
′
∩
x
,
y
:
π
1
x
+
π
2
y
=
π
0.
Conversely, letx
,
y
∈
P
2
′
∩
x
,
y
:
π
1
x
+
π
2
y
=
π
0. We can write(41)
x
,
y
=
∑
λ
i
x
i
,
y
i
+
∑
μ
i
z
i
,
w
i
,where ∑
‍
λ
i
=
1 and x
i
,
y
i are extreme points and z
i
,
w
i are extreme rays of P
2
′. By Lemma 21
x
i
,
y
i
∈
{
x
,
y
:
π
1
x
+
π
2
y
=
π
0
} and by Lemma 23
x
i
,
y
i
∈
P
1
′.
Now, we claim thatz
i
,
w
i
∈
rec
⁡
(
P
1
′
) for every i. We know z
i
,
w
i
∈
rec
⁡
P
2
′
⁡; thus, we have A
z
i
+
B
w
i
≤
0. Moreover,(42)
π
1
x
+
π
2
y
=
∑
λ
i
π
1
x
i
+
π
2
y
i
+
∑
μ
i
π
1
z
i
+
π
2
w
i
=
π
0
. But since ∑
‍
λ
i
π
1
x
i
+
π
2
y
i
=
π
0, it follows ∑
‍
μ
i
π
1
z
i
+
π
2
w
i
=
0. Since μ
i
≥
0 and π
1
z
i
+
π
2
w
i
≤
0, we conclude that π
1
z
i
+
π
2
w
i
=
0
f
o
r
a
l
l
i and therefore z
i
,
w
i
∈
rec
⁡
P
1
′ for every i, and the claim follows.
Now, by the above claim and the fact thatP
1
′ is a convex set, we get the desired result.Assume thatM
I
L
P has been solved to optimality using a cutting plane method and that we have access to all the cutting planes that have been added to the LP relaxation of M
I
L
P.Now, we can use a standard method mentioned in [15] by Espinoza et al. to lift all the cuts that we need and then, by Theorem 9, the optimal dual vector of the LP relaxation will give us the desired α. The steps of this algorithm can be stated as follows.Algorithm 24 (algorithm to obtain certificate of optimality for MILP).
11
Data. Mixed integer linear program min
⁡
c
x
:
A
x
=
b
,
x
≥
0
,
x
i
∈
0,1
for
i
∈
I with a finite set π
j
x
≤
π
0
j
,
j
∈
J of cutting planes was used to solve the problem.
Result (Certificate of Optimality
α
∗)(1)
For allj
∈
J, lift cutting plane π
j
x
≤
π
0
j using algorithm in [15] to become valid for the set V in Theorem 9. This is possible by Theorem 20.
(2)
Add these cuts to the LP relaxation of theM
I
L
P and solve this LP which will give (43)
z
M
I
L
P
∗
=
min
⁡
c
x
s.t.
A
x
=
b
π
j
x
≤
π
0
j
,
j
∈
J
x
≥
0
.
(3)
Find the optimal dual vector of the LPα
,
γ. α is the portion of the dual vector corresponding to the original constraints in M
I
L
P. α is a certificate of optimality and F
α
(
b
)
=
z
M
I
L
P
∗.In [16], it is shown that if we have a branch and bound tree instead of a set of cutting planes, we can still get the cutting planes that we need from the tree. This is done by using two different families of cuts, namely, infeasibility cuts (extracted from an infeasible node of the tree) and disjunctive cuts (extracted from a disjunction of the tree or a branch). It is also shown that these cuts could be lifted inexpensively to become valid for the original MILP. However, in this article, we assume that the cutting planes are already available to the user. This can be achieved by using a solver such as Cplex or Coin-OR Cgl (Cut Generating Library). We have used Cgl in some of our computational experiments.


## 5.1. Obtainingα
∗

Theorem9 tells us that if we add a family of cutting planes π
j
x
≤
π
0
j
,
j
∈
J, to the LP relaxation of M
I
L
P, such that we have(33)
z
M
I
L
P
∗
=
m
i
n
c
x
s
.
t
.
A
x
=
b
π
j
x
≤
π
0
j
,
j
∈
J
x
≥
0
,then if α
,
γ is an optimal dual vector where γ corresponds to constraints π
j
x
≤
π
0
j
,
j
∈
J, F
α
b
≥
z
MILP
∗. In other words, the existence of such α is guaranteed by Theorem 9.Note that if we add the cutc
x
≥
z
M
I
L
P
∗ to M
I
L
P, then obviously we can use α calculated using Theorem 9 since for that α we have F
α
b
=
c
x
∗
=
z
MILP
∗. However, based on our empirical observations through computational experiments, the size of E
α in this case is usually equal to or comparable to n. We have observed that the more cuts we add to the LP relaxation of M
I
L
P, the better α we can get using Theorem 9. We have also observed that if we add enough cuts so that the optimal solution of the LP relaxation is x
∗, then the size of E is much less than N, so we can consider it as a good certificate.We should note that the cutting planesπ
j
x
≤
π
0
j
,
j
∈
J, must be valid inequalities for the set V
=
x
∈
Z
+
I
×
R
+
C
:
A
x
≤
b by Theorem 9. This leads us to the lifting problem: each cutting plane that we add to the LP relaxation of M
I
L
P must be lifted first to become valid for the set V.Next, we show that the setx
,
y
∈
Z
+
n
×
R
+
n
:
A
x
+
B
y
=
b
≠
∅ is a face of x
,
y
∈
Z
+
n
×
R
+
n
:
A
x
+
B
y
≤
b. So the problem of lifting is well defined. In other words, the following theorem shows that the feasible region of M
I
L
P is a face of the polyhedral set V.Theorem 20.
The polyhedral set(34)
conv
⁡
x
,
y
∈
Z
+
n
×
R
+
n
:
A
x
+
B
y
=
b
≠
∅ is a face of the polyhedral set(35)
conv
⁡
x
,
y
∈
Z
+
n
×
R
+
n
:
A
x
+
B
y
≤
b
, where A and b have rational entries.In order to prove this theorem, we first need few lemmas.Lemma 21.
LetP
=
x
:
A
x
≤
b be a polyhedron and let T
=
x
:
α
x
≤
α
0 be a supporting hyperplane of P. Then, P
∩
x
:
α
x
=
α
0 is a face of P.Proof.
See [14].LetP
1
=
x
,
y
∈
Z
+
n
×
R
+
n
:
A
x
+
B
y
=
b
≠
∅ and P
2
=
x
,
y
∈
Z
+
n
×
R
+
n
:
A
x
+
B
y
≤
b. Also, let P
1
′
=
conv
⁡
P
1 and P
2
′
=
conv
⁡
P
2. Let π
1
=
1
A and π
2
=
1
B and π
0
=
1
b, where 1 is the vector of ones. Obviously, π
1
x
+
π
2
y
≤
π
0 is a supporting hyperplane of P
2
′. To see this, let x
∗
,
y
∗ be a feasible point of P
1. This point is on the hyperplane π
1
x
+
π
2
y
=
π
0 and is also in P
2 and so in P
2
′. Also, any point in P
2
′ will satisfy A
x
+
B
y
≤
b and hence π
1
x
+
π
2
y
≤
π
0 (note that P
1
⊆
P
1
′
⊆
{
x
,
y
∈
R
+
n
+
p
:
A
x
+
B
y
=
b
} and P
2
⊆
P
2
′
⊆
x
,
y
∈
R
+
n
+
p
:
A
x
+
B
y
≤
b).Lemma 22.
e
x
t
P
1
′
⊆
P
2
′
∩
x
,
y
:
π
1
x
+
π
2
y
=
π
0, where e
x
t is the set of extreme points.Proof.
Suppose thatx
,
y
∈
e
x
t
P
1
′. This means that x
,
y
∈
P
1
′ and x is integral. So, we have A
x
+
B
y
=
b. Now, we conclude that π
1
x
+
π
2
y
=
π
0 and A
x
+
B
y
≤
b. Since x is integral, x
,
y
∈
P
2, which implies x
,
y
∈
P
2
′, and this completes the proof.Lemma 23.
e
x
t
P
2
′
∩
x
,
y
:
π
1
x
+
π
2
y
=
π
0
⊆
P
1
′.Proof.
Letx
,
y be an extreme point of P
2
′ with π
1
x
+
π
2
y
=
π
0. Since x
,
y
∈
P
2
′, we have A
x
+
B
y
≤
b and also x is integral. Since π
1
x
+
π
2
y
=
π
0 and A
x
+
B
y
≤
b, we conclude that A
x
+
B
y
=
b (we can take proper combinations of the rows of the two systems). Since x is integral, x
,
y
∈
P
1 and so x
,
y
∈
P
1
′.Proof of the Theorem.
From Theorem5, we know that(36)
rec
⁡
P
1
=
rec
⁡
P
1
′
,
rec
⁡
P
2
=
rec
⁡
P
2
′
. Also, it is obvious that since P
1
⊆
P
2, rec
⁡
P
1
⊆
rec
⁡
(
P
2
), so(37)
rec
⁡
P
1
′
⊆
rec
⁡
P
2
′
.Moreover, we know(38)
rec
⁡
P
1
=
x
,
y
∈
Z
+
n
×
R
+
n
:
A
x
+
B
y
=
0
,
rec
⁡
P
2
=
x
,
y
∈
Z
+
n
×
R
+
n
:
A
x
+
B
y
≤
0
. Now, let x
,
y
∈
P
1
′. Then, by a theorem of Minkowski and Weyl (see [14, page 88]), we can write(39)
x
,
y
=
∑
λ
i
x
i
,
y
i
+
∑
μ
i
z
i
,
w
i
, where ∑
‍
λ
i
=
1 and x
i
,
y
i are extreme points and z
i
,
w
i are extreme rays of P
1
′. By Lemma 22, x
i
,
y
i
∈
P
2
′
∩
x
,
y
:
π
1
x
+
π
2
y
=
π
0. Also, we have(40)
π
1
x
+
π
2
y
=
∑
λ
i
π
1
x
i
+
π
2
y
i
+
∑
μ
i
π
1
z
i
+
π
2
w
i
. But π
1
z
i
+
π
2
w
i
=
0 since (
z
i
,
w
i
) are extreme rays of P
1
′ and π
1
=
1
A, π
2
=
1
B, and ∑
‍
λ
i
π
1
x
i
+
π
2
y
i
=
∑
‍
λ
i
π
0
=
π
0. This shows that π
1
x
+
π
2
y
=
π
0. Now, using (37) and the fact that P
2
′ and x
,
y
:
π
1
x
+
π
2
y
=
π
0 are both convex sets, we can conclude x
,
y
∈
P
2
′
∩
x
,
y
:
π
1
x
+
π
2
y
=
π
0.
Conversely, letx
,
y
∈
P
2
′
∩
x
,
y
:
π
1
x
+
π
2
y
=
π
0. We can write(41)
x
,
y
=
∑
λ
i
x
i
,
y
i
+
∑
μ
i
z
i
,
w
i
,where ∑
‍
λ
i
=
1 and x
i
,
y
i are extreme points and z
i
,
w
i are extreme rays of P
2
′. By Lemma 21
x
i
,
y
i
∈
{
x
,
y
:
π
1
x
+
π
2
y
=
π
0
} and by Lemma 23
x
i
,
y
i
∈
P
1
′.
Now, we claim thatz
i
,
w
i
∈
rec
⁡
(
P
1
′
) for every i. We know z
i
,
w
i
∈
rec
⁡
P
2
′
⁡; thus, we have A
z
i
+
B
w
i
≤
0. Moreover,(42)
π
1
x
+
π
2
y
=
∑
λ
i
π
1
x
i
+
π
2
y
i
+
∑
μ
i
π
1
z
i
+
π
2
w
i
=
π
0
. But since ∑
‍
λ
i
π
1
x
i
+
π
2
y
i
=
π
0, it follows ∑
‍
μ
i
π
1
z
i
+
π
2
w
i
=
0. Since μ
i
≥
0 and π
1
z
i
+
π
2
w
i
≤
0, we conclude that π
1
z
i
+
π
2
w
i
=
0
f
o
r
a
l
l
i and therefore z
i
,
w
i
∈
rec
⁡
P
1
′ for every i, and the claim follows.
Now, by the above claim and the fact thatP
1
′ is a convex set, we get the desired result.Assume thatM
I
L
P has been solved to optimality using a cutting plane method and that we have access to all the cutting planes that have been added to the LP relaxation of M
I
L
P.Now, we can use a standard method mentioned in [15] by Espinoza et al. to lift all the cuts that we need and then, by Theorem 9, the optimal dual vector of the LP relaxation will give us the desired α. The steps of this algorithm can be stated as follows.Algorithm 24 (algorithm to obtain certificate of optimality for MILP).
11
Data. Mixed integer linear program min
⁡
c
x
:
A
x
=
b
,
x
≥
0
,
x
i
∈
0,1
for
i
∈
I with a finite set π
j
x
≤
π
0
j
,
j
∈
J of cutting planes was used to solve the problem.
Result (Certificate of Optimality
α
∗)(1)
For allj
∈
J, lift cutting plane π
j
x
≤
π
0
j using algorithm in [15] to become valid for the set V in Theorem 9. This is possible by Theorem 20.
(2)
Add these cuts to the LP relaxation of theM
I
L
P and solve this LP which will give (43)
z
M
I
L
P
∗
=
min
⁡
c
x
s.t.
A
x
=
b
π
j
x
≤
π
0
j
,
j
∈
J
x
≥
0
.
(3)
Find the optimal dual vector of the LPα
,
γ. α is the portion of the dual vector corresponding to the original constraints in M
I
L
P. α is a certificate of optimality and F
α
(
b
)
=
z
M
I
L
P
∗.In [16], it is shown that if we have a branch and bound tree instead of a set of cutting planes, we can still get the cutting planes that we need from the tree. This is done by using two different families of cuts, namely, infeasibility cuts (extracted from an infeasible node of the tree) and disjunctive cuts (extracted from a disjunction of the tree or a branch). It is also shown that these cuts could be lifted inexpensively to become valid for the original MILP. However, in this article, we assume that the cutting planes are already available to the user. This can be achieved by using a solver such as Cplex or Coin-OR Cgl (Cut Generating Library). We have used Cgl in some of our computational experiments.


## 6. Computational Studies and Numerical Results

When we allow entries of the original matrixA to be any number, we have to include in E all columns with at least one negative element (note that, in case of knapsack problems, a column has only one element). This will increase the size of E compared to the case when all entries of A are nonnegative. Hence, in the case when there are negative entries, we only report the ratio of the number of nonnegative columns in E, that is, E
+, over the number of variables with nonnegative entries N
+.A 0-1 knapsack problem is an optimization problem of the form(44)
m
a
x
∑
i
=
1
n
c
i
x
i
s
.
t
.
∑
i
=
1
n
a
i
x
i
≤
b
x
∈
0,1
n
.If we have continuous variables in the problem, then it is called a mixed integer 0-1 knapsack problem.0-1 knapsack problems are probably the simplest problems that one could find a certificate for sinceα has length one. Our computational experiments show that, in most 0-1 mixed integer knapsack problems, the size of E
+ is significantly smaller than N
+. In lower dimensions, the size of E
+ is usually about 10% of the size of N
+, but when N
+ is large this ratio will decrease to 1% on average and even less depending on the problem type. In the best case, we had E
+
/
N
+
=
0.01.Also, the results are even better when we are working with nonnegative entries, that is, whenA and b in M
I
L
P are nonnegative. This is obvious because all columns with at least one negative element should be put in E. However, if we have a problem with lots of negative entries, we can multiply rows of A by −1 to get a better structure of the problem.All the instances that we work with are generated randomly; that is, the coefficients, objective values, and the right hand side are chosen randomly from specific intervals. These instances include problems with coefficients in{
0,1
} and also instances where coefficients vary as the size of the problem increases.In this section, we represent our numerical experiments for each family of problems. Coin-OR Cbc [17] has been used as MILP solver. Solving times have been only reported for the problems for which it takes Cbc more than 0.1 seconds to solve. All computations have been performed on a 64-bit Intel Core i3 M380 quad core 2.53 GHz CPU with 4 GB of RAM.Tables1 and 2 show the results for pure and mixed integer knapsack problems with nonnegative coefficients, respectively. In Tables 3 and 4, we show the results for pure and mixed integer knapsack problems, respectively, without any restriction in input data.Table 1
Pure integer knapsack problems with nonnegative coefficients.
Problem
Number of variables
|
E
|
Ratio|
E
|
/
|
N
|
MILP time (s)
Certificate time (s)
ipkn1.mps
100
11
0.11
ipkn3.mps
500
62
0.124
ipkn4.mps
1000
104
0.104
ipkn5.mps
1000
24
0.024
ipkn6.mps
5000
109
0.0218
0.4
0.08
ipkn7.mps
10000
212
0.0212
3.42
0.04
ipkn8.mps
50000
2131
0.04262
14.23
0.29
ipkn9.mps
100000
2227
0.02227
72.83
0.16Table 2
Mixed integer knapsack problems with nonnegative coefficients.
Problem
|
I
|, |
C
|
|
E
|
Ratio|
E
|
/
|
N
|
MILP time (s)
Certificate time (s)
mipkn1.mps
100, 100
8
0.04
mipkn2.mps
500, 500
28
0.028
mipkn3.mps
1000, 1000
91
0.0455
mipkn4.mps
5000, 5000
155
0.0155
29.97
0.01
mipkn5.mps
10000, 10000
998
0.0499
1944.64
0.01
mipkn6.mps
50000, 50000
5022
0.05022
2449.36
0.05Table 3
Pure integer knapsack problems.
Problem
Number of variables
|
E
+
|
Ratio|
E
+
|
/
|
N
+
|
MILP time (s)
Certificate time (s)
nipkn1.mps
200
15
0.13
nipkn2.mps
1000
40
0.077
nipkn3.mps
2000
45
0.044
nipkn4.mps
10000
1006
0.19
0.23
0.19
nipkn5.mps
20000
1974
0.193
0.95
0.56
nipkn6.mps
50000
1136
0.04
3.19
0.79Table 4
Mixed integer knapsack problems.
Problem
|
I
|, |
C
|
|
E
+
|
Ratio|
E
+
|
/
|
N
+
|
MILP time (s)
Certificate time (s)
nmipkn1.mps
100, 100
10
0.07
nmipkn3.mps
500, 500
198
0.3
nmipkn4.mps
1000, 1000
270
0.19
0.86
0.03
nmipkn5.mps
5000, 5000
687
0.1
4.13
0.06
nmipkn6.mps
10000, 10000
1278
0.09
68.44
0.76All the instances used for computational experiments are available in MPS or LP file format fromhttp://web.cs.ucdavis.edu/~bmoazzez/P1.html along with the generated optimal certificates.For pure integer knapsack problems with nonnegative coefficients, we get the best results. We have several examples with 100,000 variables withE
/
N about 0.02.We have also done experiments on set covering problems of the form(45)
m
i
n
c
x
s
.
t
.
A
x
≥
1
x
∈
0,1
n
, where 1 is a vector of ones and elements of A are in 0,1. The results for set covering problems are very satisfying. On average, we are able to generate good certificates. See Table 5 for set covering certificates.Table 5
Set covering problems.
Problem name
Number of variables
|
E
|
Ratio|
E
|
/
|
N
|
MILP time (ms)
Certificate time (ms)
scp1.mps
10
3
0.3
scp2.mps
20
5
0.25
scp3.mps
30
20
0.66
scp4.mps
40
8
0.2
scp5.mps
50
25
0.5
scp6.mps
60
7
0.11
scp7.mps
70
17
0.24
scp8.mps
80
45
0.56
scp9.mps
90
51
0.56
scp10.mps
100
60
0.6
scp11.mps
110
84
0.7
scp12.mps
150
43
0.28
scp13.mps
200
94
0.47
scp14.mps
250
17
0.06
70
10
scp15.mps
300
7
0.02
80
20
scp16.mps
500
12
0.02
120
30
scp17.mps
750
339
0.45
240
70Our results show that our method successfully generates certificates of optimality for any MILP. In the case of knapsack and set covering problems, our certificates are very good certificates in the sense that they take very short time to verify the optimality compared to the time they take to solve the original problem. Also, we have observed that as the number of variables increases we can generate better certificates. The size of the best certificate that we have generated is roughly 1% of the size of the original MILP, and it takes about 10 milliseconds to verify the optimality while it takes 29970 milliseconds to solve the original problem which means that it is about 3000 times faster to verify the optimality.


## 7. Summary and Conclusion

We have generalized the definition of subadditive generator functions and subadditive ray generator functions to mixed integer programming problems without any restriction in the input data. We have shown that this family of functions is very strong in the sense that one can achieve strong duality considering this class solely in the subadditive dual. Also, it is shown that the convex hull of a MILP could be represented using a finite number of these functions. Our main result states that these functions can be used as a certificate of optimality for specific classes of MILP problems. Checking certificates generated using this method is computationally less expensive. Our computational experiments show that for the knapsack problem (pure or mixed) the ratio ofE over N in the best case is 1 percent.



---

*Source: 5017369-2016-08-31.xml*