Modified orbital branching for structured symmetry with an application to unit commitment

• 成果类型: Article; Proceedings Paper
• 署名作者: Ostrowski, James; Anjos, Miguel F.; Vannelli, Anthony
• 署名单位: University of Tennessee System; University of Tennessee Knoxville; Universite de Montreal; Universite de Montreal; Polytechnique Montreal; University of Guelph
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0812-y
• 发表日期: 2015
• 页码: 99-129
• 关键词: thermal unit

摘要

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 mixed integer linear programming 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 0/1 matrices where the problem's symmetry group contains all permutations of the columns. We use the unit commitment problem, an important problem in power systems, to demonstrate the strength of modified orbital branching.