Week 1 : Formulations, polyhedra and convex hull Flashcards
Definition of a Polyhedron
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}
Definition of a formulation
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)
Remark 1 :
An integer programming problem can have different formulations.
Remark 2 :
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 }.
Lemma (3) : About nonempty polyhedron
Any nonempty polyhedron P ⊆ R^n can be written in the form
{x ∈ R^p : Ax ≤ b, x ≥ 0}
Definition (4) : Extreme point or vertex
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.
Lemma (5) : About the set of vertices of. polyhedron.
If the set of vertices of a polyhedron P is nonempty, then this set is always finite.
Definition (6) : A convex set
The set C ⊆ R^n is called convex if for every x1, x2 ∈ C and 0 < α < 1 it holds that
αx1 + (1 − α)x2 ∈ C.
Definition (7) : Convex hull
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+}
Lemma (8) : Convex hull
The convex hull conv(X) of a set X is the smallest convex set containing X.
Lemma (9) : Convex hull and polyhedron
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.
Lemma (10) : Convex hull and vertices
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.
Theorem (11) : optimal vertex
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.
Definition (12) : Good formulation
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.