Handling Sub-symmetry in Integer Programming using Activation Handlers

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

Abstract

Symmetry in integer programs (IPs) can be exploited to reduce solving times. Usually only symmetries of the original IP are handled, but new symmetries may arise at some nodes of the branch-and-bound tree. While symmetry-handling inequalities (SHIs) can easily be used to handle original symmetries, handling sub-symmetries arising later on is more intricate. To handle sub-symmetries, it has been proposed to add SHIs that are activated by auxiliary variables. But this may increase the IP’s size substantially as all sub-symmetries need to be modeled explicitly. We propose an alternative framework for generically activating SHIs, so-called activation handlers. In this framework, we define a callback that checks for active sub-symmetries, eliminating the need for auxiliary variables. In particular, activation handlers can activate symmetry-handling techniques that are more powerful than SHIs. We show that our approach is flexible, with applications in the multiple-knapsack and unit commitment problems. Numerical results show a substantial performance improvement on the existing sub-symmetry-handling methods.

Original languageEnglish
Title of host publicationGraphs and Combinatorial Optimization: from Theory to Applications. CTW 2023
PublisherSpringer
Pages95-107
Number of pages13
DOIs
Publication statusPublished - 2024

Publication series

NameAIRO Springer Series
Volume13

Fingerprint

Dive into the research topics of 'Handling Sub-symmetry in Integer Programming using Activation Handlers'. Together they form a unique fingerprint.

Cite this