Optimization Online


Modified Orbital Branching with Applications to Orbitopes and to Unit Commitment

James Ostrowski (jostrows***at***utk.edu)
Miguel F. Anjos (anjos***at***stanfordalumni.org)
Anthony Vannelli (vannelli***at***uoguelph.ca)

Abstract: The past decade has seen advances in general methods for symmetry breaking in mixed-integer linear programming. These methods are advantageous for general problems with general symmetry groups. Some important classes of MILP problems, such as bin packing and graph coloring, contain highly structured symmetry groups. This observation has motivated the development of problem-specific techniques. In this paper we show how to strengthen orbital branching in order to exploit special structures in a problem's symmetry group. The proposed technique, to which we refer as modified orbital branching, is able to solve problems with structured symmetry groups more efficiently. One class of problems for which this technique is effective is when the solution variables can be expressed as orbitopes, as this technique extends the classes of orbitopes where symmetry can be efficiently removed. We use the unit commitment problem, an important problem in power systems, to demonstrate the strength of modified orbital branching.

Keywords: symmetry; integer programming; orbital branching; orbitopes; unit commitment

Category 1: Integer Programming

Category 2: Applications -- Science and Engineering

Citation: Cahier du GERAD G-2012-61, October 2012.

Download: [PDF]

Entry Submitted: 10/27/2012
Entry Accepted: 10/27/2012
Entry Last Modified: 10/27/2012

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