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

Kartik Krishnan (kartikrice.edu)
John Mitchell (mitchjrpi.edu)

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.

Keywords: Semidefinite programming, column generation, cutting plane methods, combinatorial optimization

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: AdvOL-Report No. 2004/3, Department of Computing & Software, McMaster University, Hamilton, Canada. May 2004, revised March 2005. Also appears as Technical Report, Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, New York http://www.rpi.edu/~mitchj/papers/cutsdpmaxcut.html

Download: [Postscript][PDF]

Entry Submitted: 05/17/2004
Entry Accepted: 05/18/2004
Entry Last Modified: 03/09/2005

Modify/Update this entry