Orbital shrinking: Theory and applications

被引：2

作者：

Fischetti, Matteo ^{[1
]}

Liberti, Leo ^{[2
]}

Salvagnin, Domenico ^{[1
]}

Walsh, Toby ^{[3
,4
]}

机构：

[1] Univ Padua, DEI, Padua, Italy

[2] Ecole Polytech, CNRS LIX, F-91128 Palaiseau, France

[3] NICTA, Sydney, NSW, Australia

[4] UNSW, Sydney, NSW, Australia

来源：

DISCRETE APPLIED MATHEMATICS | 2017年 / 222卷

关键词：

Mathematical programming; Constraint programming; Discrete optimization; Symmetry; Relaxation; MINLP; SYMMETRY; CONSTRAINT; BOUNDS;

D O I：

10.1016/j.dam.2017.01.015

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We present a method, based on formulation symmetry, for generating Mixed-Integer Linear Programming (MILP) relaxations with fewer variables than the original symmetric MILP. Our technique also extends to convex MINLP, and some nonconvex MINLP with a special structure. We showcase the effectiveness of our relaxation when embedded in a decomposition method applied to two important applications (multi-activity shift scheduling and multiple knapsack problem), showing that it can improve CPU times by several orders of magnitude compared to pure MIP or CP approaches. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：109 / 123

页数：15

共 47 条

[1] [Anonymous], GEC GEN CONSTR DEV E
[2] [Anonymous], 1981, PRACTICAL GRAPH ISOM
[3] [Anonymous], 1979, INTRO AUTOMATA THEOR
[4] Branching and bounds tightening techniques for non-convex MINLP
Belotti, Pietro
Lee, Jon
Liberti, Leo
Margot, Francois
Waechter, Andreas
[J]. OPTIMIZATION METHODS & SOFTWARE, 2009, 24 (4-5) : 597 - 634
[5] Algorithms for highly symmetric linear and integer programs
Boedi, Richard
Herr, Katrin
Joswig, Michael
[J]. MATHEMATICAL PROGRAMMING, 2013, 137 (1-2) : 65 - 90
[6] Cohen D, 2005, LECT NOTES COMPUT SC, V3709, P17, DOI 10.1007/11564751_5
[7] Formal languages for integer programming modeling of shift scheduling problems
Cote, Marie-Claude
Gendron, Bernard
Quimper, Claude-Guy
Rousseau, Louis-Martin
[J]. CONSTRAINTS, 2011, 16 (01) : 54 - 76
[8] Grammar-Based Integer Programming Models for Multiactivity Shift Scheduling
Cote, Marie-Claude
Gendron, Bernard
Rousseau, Louis-Martin
[J]. MANAGEMENT SCIENCE, 2011, 57 (01) : 151 - 163
[9] CPLEX, 2012, CPLEX 12 4 US MAN
[10] Fischetti Matteo, 2012, Combinatorial Optimization. Second International Symposium, ISCO 2012. Revised Selected Papers, P48, DOI 10.1007/978-3-642-32147-4_6

← 1 2 3 4 5 →