Optimization Online


Packing, Partitioning, and Covering Symresacks

Christopher Hojny (hojny***at***mathematik.tu-darmstadt.de)

Abstract: In this paper, we consider symmetric binary programs that contain set packing, partitioning, or covering inequalities. To handle symmetries as well as set packing, partitioning, or covering constraints simultaneously, we introduce constrained symresacks which are the convex hull of all binary points that are lexicographically not smaller than their image w.r.t. a coordinate permutation and which fulfill packing, partitioning, or covering constraints. We show that linear optimization problems over constrained symresacks can be solved in cubic time. Furthermore, we derive complete linear descriptions of constrained symresacks for particular classes of symmetries. These inequalities can then be used as strong symmetry handling cutting planes in a branch-and-bound procedure. Numerical experiments show that we can benefit from incorporating set packing, partitioning, or covering constraints into symmetry handling inequalities.

Keywords: symmetry, binary programming, complete linear description, extended formulation, total dual integral

Category 1: Integer Programming (0-1 Programming )

Citation: TU Darmstadt, Department of Mathematics, Research Group Optimization, Dolivostr. 15, 64293 Darmstadt, May 2018

Download: [PDF]

Entry Submitted: 05/03/2017
Entry Accepted: 05/03/2017
Entry Last Modified: 05/02/2018

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