A semidefinite programming based polyhedral cut and price approach for the maxcut problem

A semidefinite programming based polyhedral cut and price approach for the maxcut problem

0.00 Avg rating0 Votes
Article ID: iaor20062297
Country: Netherlands
Volume: 33
Issue: 1
Start Page Number: 51
End Page Number: 71
Publication Date: Jan 2006
Journal: Computational Optimization and Applications
Authors: ,
Keywords: programming: network
Abstract:

We investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP relaxation of maxcut is formulated as a semi-infinite linear programming problem, which is solved within an interior point cutting plane algorithm in a dual setting; this constitutes the pricing (column generation) phase of the algorithm. Cutting planes based on the polyhedral theory of the maxcut problem are then added to the primal problem in order to improve the SDP relaxation; this is the cutting phase of the algorithm. We provide computational results, and compare these results with a standard SDP cutting plane scheme.

Reviews

Required fields are marked *. Your email address will not be published.