Cardinality Cuts: New Cutting Planes for 0-1 Programming

Osman Oguz (ooguzbilkent.edu.tr)

Abstract: We present new valid inequalities that work in similar ways to well known cover inequalities.The differences exist in three aspects. First difference is in the generation of the inequalities. The method used in generation of the new cuts is more practical in contrast to classical cover inequalities. Second difference is the more general applicability, i.e., being useful for problems like TSP. The third aspect is superior efficiency as indicated by our preliminary experiments.

Keywords: 0-1 integer programming, cutting planes

Category 1: Integer Programming

Category 2: Integer Programming (0-1 Programming )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: Dept. of Industrial Engineering, Bilkent University, Ankara, Turkey.(November 2006)

Download: [PDF]

Entry Submitted: 11/13/2006
Entry Accepted: 11/13/2006
Entry Last Modified: 11/26/2006

Modify/Update this entry