In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined bymulti-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint- based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly.

Branching on Multi-aggregated Variables / Gamrath, Gerald; Melchiori, Anna; Berthold, Timo; Gleixner, Ambros M.; Salvagnin, Domenico. - 9075:(2015), pp. 141-156. (Intervento presentato al convegno 12th International Conference on Integration of Artificial Intelligence and Operations Research techniques in Constraint Programming, CPAIOR 2015 tenutosi a Barcelona; Spain) [10.1007/978-3-319-18008-3_10].

Branching on Multi-aggregated Variables

Melchiori, Anna
;
2015

Abstract

In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined bymulti-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint- based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly.
2015
12th International Conference on Integration of Artificial Intelligence and Operations Research techniques in Constraint Programming, CPAIOR 2015
Theoretical Computer Science; Computer Science (all); Linear Programming; Relaxation; Dual Bound; Constraint Integer; Operation Research Letter; Linear Programming Solution
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Branching on Multi-aggregated Variables / Gamrath, Gerald; Melchiori, Anna; Berthold, Timo; Gleixner, Ambros M.; Salvagnin, Domenico. - 9075:(2015), pp. 141-156. (Intervento presentato al convegno 12th International Conference on Integration of Artificial Intelligence and Operations Research techniques in Constraint Programming, CPAIOR 2015 tenutosi a Barcelona; Spain) [10.1007/978-3-319-18008-3_10].
File allegati a questo prodotto
File Dimensione Formato  
Gamrath_Branching_2015.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 245.11 kB
Formato Adobe PDF
245.11 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1185685
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact