Handling polyhedral symmetries with a dedicated Branch&Cut: application to a knapsack variant

Alexandre Heintzmann (1, 2) , Pascale Bendotti (3, 4) , Cécile Rottner (2)

1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
2 EDF Labs
3 EDF R&D OSIRIS - Optimisation, Simulation, Risque et Statistiques pour les Marchés de l’Energie
4 RO - Recherche Opérationnelle

In this paper, we define a new variant of the knapsack problem, the Symmetric-weight Chain Precedence Knapsack problem (SCPKP). The (SCPKP) is the core structure of the Hydro Unit Commitment problem, the latter being a production scheduling problem relative to hydroelectric plants. The (SCPKP) is shown to be NP-hard. Polyhedral symmetries, featured by the (SCPKP), are introduced as a generalization of the classical symmetries applying only on the constraints without restricting the values of two symmetric solutions to be equal. A polyhedral study focuses on inequalities with 0-1 coefficients. Necessary facet defining conditions are described through a new structure, called pattern, encoding the polyhedral symmetries of the (SCPKP). A dedicated two-phase Branch & Cut scheme is defined to exploit the symmetries on the pattern inequalities. Experimental results demonstrate the efficiency of the proposed scheme in particular with respect to default CPLEX and a family of cover inequalities related to the Precedence Knapsack Problem.

Mots clés: Polyhedral study Precedence constraints Cover inequalities; Polyhedral study; Precedence constraints; Cover inequalities

Domaines: Recherche opérationnelle [math.OC]

Alexandre Heintzmann, Pascale Bendotti, Cécile Rottner. Handling polyhedral symmetries with a dedicated Branch&Cut: application to a knapsack variant. 2024. ⟨hal-04493165v1⟩