.png){kind=icon}
.png){kind=icon}
Return
Achieving MILP feasibility quickly using general disjunctions
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2013.03.001.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Branch and bound algorithms for Mixed-Integer Linear Programming (MILP) almost universally branch on a single variable to create disjunctions. General linear expressions involving multiple variables are another option for branching disjunctions, but are not used for two main reasons: (i) descendent LPs tend to solve more slowly because of the added constraints, so the overall solution time is increased, and (ii) it is difficult to quickly find an effective general disjunction. We study the use of general disjunctions to reach the first MILP-feasible solution quickly, showing for the first time that general disjunctions can provide speed improvements for hard MILP models. The speed-up is due to new and efficient ways to (i) trigger the inclusion of a general disjunction only when it is likely to be beneficial, and (ii) construct effective general disjunctions very quickly. Our empirical results show performance improvements versus a state of the art commercial MILP solver. (C) 2013 Elsevier Ltd. All rights reserved.
Keywords:
Mixed integer linear programming
General disjunctions
Branching
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W