Automatic generation of symmetry-breaking constraints

Leo Liberti

doi:10.1007/978-3-540-85097-7_31

Automatic generation of symmetry-breaking constraints

Leo Liberti

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

21 Citations (Scopus)

Abstract

Solution symmetries in integer linear programs often yield long Branch-and-Bound based solution processes. We propose a method for finding elements of the permutation group of solution symmetries, and two different types of symmetry-breaking constraints to eliminate these symmetries at the modelling level. We discuss some preliminary computational results.

Original language	English
Title of host publication	Combinatorial Optimization and Applications - Second International Conference, COCOA 2008, Proceedings
Publisher	Springer Verlag
Pages	328-338
Number of pages	11
ISBN (Print)	3540850961, 9783540850960
DOIs	https://doi.org/10.1007/978-3-540-85097-7_31
Publication status	Published - 1 Jan 2008
Event	2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008 - St. John's, NL, Canada Duration: 21 Aug 2008 → 24 Aug 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5165 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008
Country/Territory	Canada
City	St. John's, NL
Period	21/08/08 → 24/08/08

Access to Document

10.1007/978-3-540-85097-7_31

Cite this

Liberti, L. (2008). Automatic generation of symmetry-breaking constraints. In Combinatorial Optimization and Applications - Second International Conference, COCOA 2008, Proceedings (pp. 328-338). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5165 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-85097-7_31

@inproceedings{048840f9a59e4d5d9067ee21ea78d9f8,

title = "Automatic generation of symmetry-breaking constraints",

abstract = "Solution symmetries in integer linear programs often yield long Branch-and-Bound based solution processes. We propose a method for finding elements of the permutation group of solution symmetries, and two different types of symmetry-breaking constraints to eliminate these symmetries at the modelling level. We discuss some preliminary computational results.",

author = "Leo Liberti",

year = "2008",

month = jan,

day = "1",

doi = "10.1007/978-3-540-85097-7\_31",

language = "English",

isbn = "3540850961",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "328--338",

booktitle = "Combinatorial Optimization and Applications - Second International Conference, COCOA 2008, Proceedings",

note = "2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008 ; Conference date: 21-08-2008 Through 24-08-2008",

}

Liberti, L 2008, Automatic generation of symmetry-breaking constraints. in Combinatorial Optimization and Applications - Second International Conference, COCOA 2008, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5165 LNCS, Springer Verlag, pp. 328-338, 2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008, St. John's, NL, Canada, 21/08/08. https://doi.org/10.1007/978-3-540-85097-7_31

Automatic generation of symmetry-breaking constraints. / Liberti, Leo.
Combinatorial Optimization and Applications - Second International Conference, COCOA 2008, Proceedings. Springer Verlag, 2008. p. 328-338 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5165 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Automatic generation of symmetry-breaking constraints

AU - Liberti, Leo

PY - 2008/1/1

Y1 - 2008/1/1

N2 - Solution symmetries in integer linear programs often yield long Branch-and-Bound based solution processes. We propose a method for finding elements of the permutation group of solution symmetries, and two different types of symmetry-breaking constraints to eliminate these symmetries at the modelling level. We discuss some preliminary computational results.

AB - Solution symmetries in integer linear programs often yield long Branch-and-Bound based solution processes. We propose a method for finding elements of the permutation group of solution symmetries, and two different types of symmetry-breaking constraints to eliminate these symmetries at the modelling level. We discuss some preliminary computational results.

U2 - 10.1007/978-3-540-85097-7_31

DO - 10.1007/978-3-540-85097-7_31

M3 - Conference contribution

AN - SCOPUS:51849085158

SN - 3540850961

SN - 9783540850960

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 328

EP - 338

BT - Combinatorial Optimization and Applications - Second International Conference, COCOA 2008, Proceedings

PB - Springer Verlag

T2 - 2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008

Y2 - 21 August 2008 through 24 August 2008

ER -

Liberti L. Automatic generation of symmetry-breaking constraints. In Combinatorial Optimization and Applications - Second International Conference, COCOA 2008, Proceedings. Springer Verlag. 2008. p. 328-338. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-85097-7_31

Automatic generation of symmetry-breaking constraints

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this