Basic Polyhedral Theory

Basic Polyhedral theory

The set is called a polyhedron.

Lemma 1. Either the systemhas a solution or there is a vectorsuch that

Three cases, if solution in top row does not exist then there exists a such that the bottom is true. (in each column, x continuous).

If integer } = , x integer} and

}}, we say that the first formulation is Tighter (& better).

However we’re interested in integer solutions.

Integral polyhedra

Given a polyhedron P, its integer hull PI is the convex hull of all integral vectors in P.

For any rational polyhedron P, the PI is also a polyhedron.

The following method generates valid inequalities for PI (Chvatal’s theorem)

Let P=, where A and b integral, then

is valid for P, for any , and is valid for P, because ,

then

(1) is valid for PIbecause x is integral.

Let us call S1 the set of inequalities using (1), and set St+1 the set obtained by applying this operation to St. These sets generate a sequence

Example:

X(e1)+x(e4) +x(e6) =1

X(e1)+x(e5)+x(e7) =1

X(e3)+x(e4)+x(e8) =1

X(e3)+x(e5)+x(e9) =1

X(e2)+x(e7)+x(e9) =1

X(e2)+x(e6)+x(e8) =1

Consider taking ½*(first four inequalities) to get

(1/2+1/2)X(e1)+(1/2+1/2)x(e3)+(1/2+1/2)x(e4)+(1/2+1/2)x(e5) + 1/2 (x(e6)+x(e7)+x(e8)+x(e9))=2

X(e1)+x(e3)+x(e4)+x(e5) + (x(e6)+x(e7)+x(e8)+x(e9))=,

Where =0 so (x(e6)+x(e7)+x(e8)+x(e9))=0

X(e1)+x(e3)+x(e4)+x(e5)=2

Consider taking last three inequalities and first one with multiplier of ½

X(e2)+x(e6)+x(e9)=2

Total unimodularity:

If A is totally unimodular (TU) then

P(b)= is integral for which it is not empty

Example:

A matrix with (0,-1,1) elements, where no more than 2 non-zero elements in each column and if column j contains two non-zero elements, then A is TU.

Example:

A is TU if determinant of each submatrix of A is (0, -1 ,1), and A is (0,1,-1) matrix.

Duality

Primal problem:

Dual problem:

Weak duality

is primal feasible , u* is dual feasible , then

c

Strong Duality

If zLP or wLP is finite then both P and D have finite optimal value zLP= wLP

Weak dual of IP is any minimization problem

that satisfies and SD is dual integer problem.

If Dual problem is feasible then .

Strong dual of IP is a weak dual that also satisfies if bounded from above,

Duality gap: for weak duals of IP , the separation between primal and dual objective values.

Totally Dual Integrality

Given A and b with integral entries, we want to study cases when the LP

Max cx

Ax <= b

Has integer optimum primal and integer optimum dual solutions.

Examples:

a)network flow

max cx

Ax =b

x>=0

where each column of A has two non-zero entries. One with value 1 and other with value -1. network flow matrix

b)network flows with upper bounds 0<=x<=u

c)flow problems in cross-free families [Nemhauser & Wolsely textbook]

d)submodular flows ie. Directed cut covers, matroids

Perfect Matching problem:

The 2nd inequality is necessary in order to obtain integral solutions.

Without this inequality, fractional solutions are possible.

Consider the graph :

With only 1st constraint you’ll get a possible fractional solution which looks like:

But how do we automatically determine the form of inequality (2) to cut off the current fractional solution?

This is called the “Separation Problem”. For some problems like matching, we know how to solve this problem using Branch and cut. For other problems, we still do not know how to solve it, although some heuristics exist – but they are not guaranteed to obtain a cut.

For matching problem, we’re given a fractional vector , we want one set S such that

, for |S| odd.

So for a set S, we can use the min cut problem:

Given a graph G=(V,E) and edge weights, , we know how to solve the minimum cut problem:

This can be solved by network flow techniques.

If |S| is not odd, what do we do?

Supose we solve a minimum cut problem with weights . Let S be a solution. If |S| is odd, we are done.

If |S| is even we have to prove that there is an odd set in , included in S or in V\S that solves our problem. Using this property, we can decompose the problem.

Proof:

We know that the following is true.

long edge counts only in the right hand side of the inequality.

Suppose that S (|S| is even) gives a minimum cut and T gives a minimum cut with |T| odd.

Now is o+e<=e+o

If we have that , because |T| and are odd.

This set of inequalities imply

and

Proof. Therefore is also a solution for the minimum odd cut problem.

So take union or take complement of union V\(that is included in V\S).

Other possibility: is .

Then ,because we haveso therefore

Proof. In this case is also a solution to the minimum odd cut problem.

=

if S defines a minimum cut & |S| even, then solution exists in S or in V\S.

We decompose problem into two problems in the graphs

We generate a nested set of problems, that has at most 2n-1 elements. So in worst case we have to solve 2n-1 min cut problems.

Finding one minimum cut takes O(n^3), so this is an O(n^4) algorithm.

Non-Perfect Matching problem:

where E(S) are the edges with both ends in S.

This can also be solved similar to the perfect matching problem, using mincut algorithm.

Other problems, we know what some of the (facets) inequalities look like, but we can’t solve the separation problem:

Node or Vertex Packing Problems:

Given a graph G=(V,E) consider

for definition of the problem. However for obtaining integral solutions we need to add more inequalities (specifically facets, which intersect integer vertices of search space).

(if subgraph is complete)

(where C is an odd cycle)

However there are more facets which are difficult to obtain and for which we don’t know all of them.

There are lifting lemmas one can use to obtain more facets of this problem.

Knapsack problem:

we need facets of PI

, define facets

Let be an integer vector in P, we say that set is independent.

Let C be a minimal dependent set

C\{i} is independent

The inequality (1)

is valid for PI

Assume that are given. A minimal dependent set C, define

E(C) =

The inequality (2)

is also valid for PI and stronger than (1).

The inequality (2) defines a facet of PI under any of the following conditions:

a)C=N

b)E(C)=N & (i) C\{j1,j2} is independent

c)C=E(C) and (ii) C\{j1} is independent, p

d)C & (i) & (ii)

Where C={j1,j2, … , jk}

EXAMPLE:

C1={1,2,3}

C2={1,2,4,5}

C3={1,3,4,5}

C4={2,3,4,5} are minimal dependent sets

Now,

E(C1)=C1

E(C2)=C2

E(C3)=C3

E(C4)=C4

Lets see if any of the new inequalities of the form (2) are facets:

E(C1):

(1) is a facet if

(ii) C\{j1} = {2,3,4} is independent, p

Therefore it’s a facet *.

E(C2):

(2) is a facet if

(ii) C\{j1} = {2,4,5,3} is independent. It is not independent, therefore we do not know whether it is a facet or not.

E(C3):

(3) is a facet if

(ii) C\{j1} = {3,4,5,2} is independent.It is not independent, therefore we do not know whether it is a facet or not.

E(C4):

(4) is a facet if (case b))

(i)C\{j1,j2}=C\{2,3} = {4,5,1} is independent. Is is independent, therefore it is a facet *.

NOTE: any inequality which is a linear combination of facets, cannot be a facet.

(3) = (4) + () , therefore (3) is not a facet. (because it’s a +ve combination of 2 facets).

(2) = (4) + () , therefore (2) does not define a facet.