Optimization Online


Orbital Conflict: Cutting Planes for Symmetric Integer Programs

Jeff Linderoth(linderoth***at***wisc.edu)
Jose Nunez-Ares(jose.nunezares***at***kuleuven.be)
James Ostrowski(jostrows***at***utk.edu)
Fabrizio Rossi(fabrizio.rossi***at***univaq.it)
Stefano Smriglio(stefano.smriglio***at***univaq.it)

Abstract: Cutting planes have been an important factor in the impressive progress made by integer programming (IP) solvers in the past two decades. However, cutting planes have had little impact on improving performance for symmetric IPs. Rather, the main breakthroughs for solving symmetric IPs have been achieved by cleverly exploiting symmetry in the enumeration phase of branch and bound. In this work, we introduce a hierarchy of cutting planes that arise from a reinterpretation of symmetry-exploiting branching methods. There are too many inequalities in the hierarchy to be used efficiently in a direct manner. However, the lowest levels of this cutting-plane hierarchy can be implicitly exploited by enhancing the conflict graph of the integer programming instance and by generating inequalities such as clique cuts valid for the stable-set relaxation of the instance. We provide computational evidence that the resulting symmetry-powered clique cuts can improve state-of-the-art symmetry exploiting methods. The inequalities are then employed in a two-phase approach with high-throughput computations to solve heretofore unsolved symmetric integer programs arising from covering designs, establishing for the first time the covering radii of two binary-ternary codes.

Keywords: Integer programming -- symmetry -- conflict graph

Category 1: Integer Programming

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 03/15/2020
Entry Accepted: 03/16/2020
Entry Last Modified: 03/15/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society