Restarting after branching in the SDP approach to MAX-CUT
and similar combinatorial optimization problems
Journal of
Combinatorial Optimization, 5(2), 2001, pages 151-166.
Download the paper,
postscript or pdf.
Author:
John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj@rpi.edu
June 25, 1999.
Abstract:
Many combinatorial optimization problems have relaxations that
are semidefinite programming problems.
In principle, the combinatorial optimization problem can then
be solved by using a branch-and-cut procedure, where the problems
to be solved at the nodes of the tree are semidefinite programs.
When branching, it is desirable to use the solution to
the parent relaxation as a warm start for the child relaxation.
We show that a new dual strictly feasible solution can be found
in a straightforward manner.
The branch-and-cut approach to mixed integer linear programming
problems can be restarted at each node of the tree using the
dual simplex method;
our method for SDP branch-and-cut algorithms gives an analogous
method for efficiently solving the child problems.
Download the paper,
postscript or pdf.
Return to my list of papers.