Group for Research in Decision Analysis

Cuts for mixed 0-1 conic programming

Mehmet Tolga Cezik

In this study we show that cut generation techniques, such as Gomory cuts, disjunctive cuts, cuts from Lovasz-Schrijver lifting, etc., developed in the context of mixed 0-1 linear programs extend in a straightforward manner to mixed 0-1 conic programs. In addition, one can generate valid convex quadratic inequalities as well. We show that the Gomory cuts have interesting implications for comparing semidefinite and linear relaxations of combinatorial optimization problems. We also include results from our preliminary computational experiments with these cuts.