Orbital shrinking: Theory and applications

Matteo Fischetti; Leo Liberti; Domenico Salvagnin; Toby Walsh

doi:10.1016/j.dam.2017.01.015

Orbital shrinking: Theory and applications

Matteo Fischetti
, Leo Liberti
, Domenico Salvagnin
, Toby Walsh

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	109-123
Number of pages	15
Journal	Discrete Applied Mathematics
Volume	222
DOIs	https://doi.org/10.1016/j.dam.2017.01.015
Publication status	Published - 11 May 2017

Keywords

Constraint programming
Discrete optimization
MINLP
Mathematical programming
Relaxation
Symmetry

Access to Document

10.1016/j.dam.2017.01.015

Cite this

@article{fb31581bdf7e46ca9f9dc72573e0403d,

title = "Orbital shrinking: Theory and applications",

abstract = "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.",

keywords = "Constraint programming, Discrete optimization, MINLP, Mathematical programming, Relaxation, Symmetry",

author = "Matteo Fischetti and Leo Liberti and Domenico Salvagnin and Toby Walsh",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier B.V.",

year = "2017",

month = may,

day = "11",

doi = "10.1016/j.dam.2017.01.015",

language = "English",

volume = "222",

pages = "109--123",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

}

TY - JOUR

T1 - Orbital shrinking

T2 - Theory and applications

AU - Fischetti, Matteo

AU - Liberti, Leo

AU - Salvagnin, Domenico

AU - Walsh, Toby

PY - 2017/5/11

Y1 - 2017/5/11

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

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

KW - Constraint programming

KW - Discrete optimization

KW - MINLP

KW - Mathematical programming

KW - Relaxation

KW - Symmetry

U2 - 10.1016/j.dam.2017.01.015

DO - 10.1016/j.dam.2017.01.015

M3 - Article

AN - SCOPUS:85013040942

SN - 0166-218X

VL - 222

SP - 109

EP - 123

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Orbital shrinking: Theory and applications

Abstract

Keywords

Access to Document

Fingerprint

Cite this