Problems refer to Integer Programming, Wolsey and the handout
"A Branch and Cut Algorithm for Steiner Problem in Graphs" Lucena
and Beasely (LB)
1. Show that for the travelling salesman problem, the cut set constraints
are equivalent to the subtour elimination constraints (see p.8 of Wolsey).
Show that these two sets of constraints are not equivalent for
the Steiner
Problem in Graphs.
2. The purpose of this problem is to investigate the vertices of polyhedra
connected to Minimum Spanning Tree and Steiner Problems. Equation
numbers refer to the handout. You will need to use lrs to compute vertices.
Homepage: http://cgm.cs.mcgill.ca/~avis/C/lrs.html
(lrs programs are available on lab110-*.cs.mcgill.ca machines in /usr/local/pkgs/lrslib-041
)
Consider the complete graph K_6, and the vertex set K={1,2,3,4}
(Go to http://cgm.cs.mcgill.ca/~avis/courses/567/uls/
to see sample files for the ULS problem.)
(a) Construct the MST polytope for G using (LB) equation(2) , inequalities
(3)
and 0 <= x_ij <= 1
for all edges ij.
Use lrs to find the vertices.
Prove that the vertices of this polytope are
0/1 vectors representing the spanning
trees of G, for any connected graph G.
(b) Compute the vertices of the SPG represented by the polytope in (a)
and inequalities
(4) and 8. For some fractional
vertex, construct a cost vector so that the LP relaxation
gives this fractional vertex.
What are the 0/1 vertices?
(c) Restrict the polytope in (b) by adding (6) and compute
the vertices.
Try to find a cost vector
so that for this polytope it optimizes to a 0/1 solution,
but for the polytope
in (b) it gives a fractional vertex.
Notes:
1. The lrs computations in (b) and (c) take time (have a coffee or
even dinner).
lrs1 and glrs are faster than lrs.
2. Do not hand in all the output! Just give a small sample, and the
totals lines at the end
of the run.