Orbitopal fixing for the full orbitope and application to the Unit Commitment Problem
Abstract: It is common knowledge that symmetries arising in integer programs could impair the solution process, in particular when symmetric solutions lead to an excessively large branch and bound (B&B) search tree. Techniques like isomorphic pruning , orbital branching  and orbitopal fixing  have been shown to be essential to solve very symmetric instances from the literature. This paper focuses on formulations involving a set of 2-index variables, also referred to as matrix, such that the corresponding symmetry group is the set of all column permutations. Such formulations arise for example from scheduling problems with a discrete time horizon. Orbitopal fixing as introduced in  is restricted to the special case of partitioning (resp. packing) formulations involving a solution matrix with exactly (resp. at most) one 1-entry in each row. It relies on the linear description of the partitioning (resp. packing) orbitope , i.e., the convex hull of binary matrices with lexicographically non-increasing columns and exactly (resp. at most) one 1-entry per row. The main result of this paper is to extend orbitopal fixing to the full orbitope, namely with no restriction on the number of ones in each row. We propose a linear time orbitopal fixing algorithm for the full orbitope, referred to as the static version, as it is defined for the natural lexicographical order. We also introduce a dynamic version of this algorithm where the lexicographical order follows the branching decisions occurring along the B&B process. Experimental results for the Unit Commitment Problem are presented. A comparison with state of the art techniques like modified orbital branching  is also considered to show the effectiveness of the proposed algorithms.
Keywords: Full Orbitope; Symmetry-breaking; Variable Fixing; Unit Commitment
Category 1: Integer Programming (0-1 Programming )
Category 2: Combinatorial Optimization (Branch and Cut Algorithms )
Category 3: Combinatorial Optimization (Polyhedra )
Citation: EDF R&D, 7 Boulevard Gaspard Monge, 91120 Palaiseau, France; Sorbonne UniversitÚs, UniversitÚ Pierre et Marie Curie, LIP6 CNRS UMR 7606, 4 Place Jussieu, 75005 Paris. October, 2017.
Entry Submitted: 10/27/2017
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|