Sökning: WFRF:(Karlsson Emil 1990 ) >
Strengthening of fe...
Strengthening of feasibility cuts in logic-based Benders decomposition
-
- Karlsson, Emil, 1990- (författare)
- Linköpings universitet,Tekniska fakulteten,Tillämpad matematik,Saab AB, Linköping, Sweden
-
- Rönnberg, Elina, 1981- (författare)
- Linköpings universitet,Tillämpad matematik,Tekniska fakulteten
-
(creator_code:org_t)
- 2021-06-17
- 2021
- Engelska.
-
Ingår i: INTEGRATION OF CONSTRAINT PROGRAMMING, ARTIFICIAL INTELLIGENCE, AND OPERATIONS RESEARCH. - Cham : Springer. - 9783030782290 - 9783030782306 ; , s. 45-61
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- As for any decomposition method, the computational performance of a logic-based Benders decomposition (LBBD) scheme relies on the quality of the feedback information. Therefore, an important acceleration technique in LBBD is to strengthen feasibility cuts by reducing their sizes. This is typically done by solving additional subproblems to evaluate potential cuts. In this paper, we study three cut-strengthening algorithms that differ in the computational efforts made to find stronger cuts and in the guarantees with respect to the strengths of the cuts. We give a unified description of these algorithms and present a computational evaluation of their impact on the efficiency of a LBBD scheme. This evaluation is made for three different problem formulations, using over 2000 instances from five different applications. Our results show that it is usually beneficial to invest the time needed to obtain irreducible cuts. In particular, the use of the depth-first binary search cut-strengthening algorithm gives a good performance. Another observation is that when the subproblem can be separated into small independent problems, the impact of cut strengthening is dominated by that of the separation, which has an automatic strengthening effect.
Ämnesord
- NATURVETENSKAP -- Matematik -- Beräkningsmatematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Computational Mathematics (hsv//eng)
Nyckelord
- Logic-based Benders decomposition; Cut strengthening; Feasibility cuts; Irreducible infeasible subset of constraints
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas