Restarting
after branching in the SDP approach to MAX-CUT
and similar combinatorial optimization problem
John E. Mitchell
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.
It is desirable that the solution to one node of the tree should
be exploited at the child node in order to speed up the solution of
the child.
We show how the solution to the parent relaxation can be
used as a warm start to construct an appropriate initial dual solution
to the child problem.
This restart method for SDP branch-and-cut can be regarded as
analogous to the use of the dual simplex method in the
branch-and-cut method for mixed integer linear programming problems.
Mathematical Sciences,
Rensselaer Polytechnic Institute,
Troy, NY 12180.
June 25, 1999
Contact: [email protected]
![[PS]](../gif/PS.gif)
![[IP PAGE]](../gif/HOME.gif)
![[SEARCH AGAIN]](../gif/SEARCH.gif)