Basic Polyhedral Theory

GAMS for modeling mathematical programming problems.

Consider the following LP problem.

The Gams version is linked to web.

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).

Chvatal’s Theorem

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:

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 ,

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.