Optimization Online


Orbitopal fixing for the full (sub-)orbitope and application to the Unit Commitment Problem

Pascale Bendotti (pascale.bendotti***at***edf.fr)
Pierre Fouilhoux (pierre.fouilhoux***at***lip6.fr)
CÚcile Rottner (cecile.rottner***at***edf.fr)

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 [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.

Keywords: Full Orbitope; Sub-symmetries; 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.

Download: [PDF]

Entry Submitted: 10/27/2017
Entry Accepted: 10/27/2017
Entry Last Modified: 03/21/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society