Packing, partitioning, and covering symresacks

Christopher Hojny (Corresponding author)

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Samenvatting

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 hulls 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.
Originele taal-2Engels
Pagina's (van-tot)689-717
Aantal pagina's29
TijdschriftDiscrete Applied Mathematics
Volume283
DOI's
StatusGepubliceerd - 15 sep 2020

Vingerafdruk Duik in de onderzoeksthema's van 'Packing, partitioning, and covering symresacks'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit