  


Orbitopal fixing for the full (sub)orbitope and application to the Unit Commitment Problem
Pascale Bendotti (pascale.bendottiedf.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 2index 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 1entry 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 nonincreasing columns and exactly (resp. at most) one 1entry 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; Subsymmetries; Symmetrybreaking; Variable Fixing; Unit Commitment Category 1: Integer Programming (01 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  