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 [11], orbital branching [16] and orbitopal fixing [8] 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 [8] 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 [9], 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 [14] is also considered to show the effectiveness of the proposed algorithms.
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.