Restarting after Branching in the SDP Approach to MAX-CUT and Similar Combinatorial Optimization Problems

John E. Mitchell ()
Additional contact information
John E. Mitchell: Rensselaer Polytechnic Institute

Journal of Combinatorial Optimization, 2001, vol. 5, issue 2, No 1, 166 pages

Abstract: 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. 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.

Keywords: semidefinite programming; MAX-CUT problems; branch-and-cut (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1011416130639 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:5:y:2001:i:2:d:10.1023_a:1011416130639

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1011416130639

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().