Week 1 : Formulations, polyhedra and convex hull

Question 1

Definition of a Polyhedron

Answer 1

Basically, a polyhedron is a finite set of inequalities.

A set P⊆ R^n is called a polyhedron, if there exists some m × n matrix A and some
b ∈ Rm such that
P := {x ∈ R^n : Ax ≤ b}

Question 2

Definition of a formulation

Answer 2

A polyhedron P ⊆ R^(n+p) is called a formulation for a set X ⊆ Z^n × R^p if and
only if X = P ∩ (Z^n × R^p)

Question 3

Remark 1 :

Answer 3

An integer programming problem can have different formulations.

Question 4

Remark 2 :

Answer 4

A linear programming relaxation of an integer program is to replace in relation the constraints x ∈ Z^n by x ∈ R^n. Hence, this is given by max{c⊤x : x ∈ P }.

Question 5

Lemma (3) : About nonempty polyhedron

Answer 5

Any nonempty polyhedron P ⊆ R^n can be written in the form
{x ∈ R^p : Ax ≤ b, x ≥ 0}

Question 6

Definition (4) : Extreme point or vertex

Answer 6

Let P be a polyhedron. The point x is called an extreme point or vertex of P if x ∈ P and there are no two distinct points x1, x2 ∈ P such that x = αx1 + (1 − α)x2 for some 0 < α < 1.

Question 7

Lemma (5) : About the set of vertices of. polyhedron.

Answer 7

If the set of vertices of a polyhedron P is nonempty, then this set is always finite.

Question 8

Definition (6) : A convex set

Answer 8

The set C ⊆ R^n is called convex if for every x1, x2 ∈ C and 0 < α < 1 it holds that
αx1 + (1 − α)x2 ∈ C.

Question 9

Definition (7) : Convex hull

Answer 9

Observe the convex hull of X is given by the set of all finite convex combinations of the set X.

If X ⊆ Rn is an arbitrary nonempty set, then the convex hull conv(X) of X is
given by {Sum(1,k) αlphaixi : αlphi ≥ 0, Sum(1,k) αi = 1, xi ∈ X, k ∈ Z+}

Question 10

Lemma (8) : Convex hull

Answer 10

The convex hull conv(X) of a set X is the smallest convex set containing X.

Question 11

Lemma (9) : Convex hull and polyhedron

Answer 11

If X is the feasible region of a (mixed) integer linear program given by
X = {x ∈ R^n : Ax ≤ b, x ∈ N^n} or X = {(x, y) : Ax+Cy ≤ b, x ≥ 0, y ∈ N^p},
then conv(X) is a polyhedron.

Question 12

Lemma (10) : Convex hull and vertices

Answer 12

If the set conv(X) is a nonempty polyhedron containing vertices, then the set of
all vertices of conv(X) is finite and every vertex belongs to X.

Question 13

Theorem (11) : optimal vertex

Answer 13

Let x∗ be an optimal vertex of the problem max{c⊤x : x ∈ conv(X)} with
X = {x ∈ Nn : Ax ≤ b}. Then x∗ is an optimal solution of the integer program
max{c⊤x : Ax ≤ b, x ∈ Nn}.

This also holds for mixed integer sets.

Question 14

Definition (12) : Good formulation

Answer 14

If we have two different formulations P1 and P2 of an integer linear programming
problem given by
max{c⊤x : x ∈ Pi ∩ Zn}, i = 1, 2,
we say formulation P1 is stronger than formulation P2 if P1 ⊂ P2.