Sökning: id:"swepub:oai:DiVA.org:liu-201875" >
Exact Complexity Ce...
Exact Complexity Certification of Start Heuristics in Branch-and-Bound Methods for Mixed-Integer Linear Programming
-
- Shoja, Shamisa (författare)
- Linköpings universitet,Reglerteknik,Tekniska fakulteten
-
- Axehill, Daniel (författare)
- Linköpings universitet,Reglerteknik,Tekniska fakulteten
-
(creator_code:org_t)
- IEEE, 2023
- 2023
- Engelska.
-
Ingår i: 2023 62ND IEEE CONFERENCE ON DECISION AND CONTROL, CDC. - : IEEE. - 9798350301243 - 9798350301250 ; , s. 2292-2299
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Model predictive control (MPC) with linear performance measure for hybrid systems requires the solution of a mixed-integer linear program (MILP) at each time instance. A well-known method to solve MILP problems is branch-and-bound (B&B). To enhance the performance of B&B, start heuristic methods are often used, where they have shown to be useful supplementary tools to find good feasible solutions early in the B&B search tree, hence, reducing the overall effort in B&B to find optimal solutions. In this work, we extend the recently-presented complexity certification framework for B&B-based MILP solvers to also certify computational complexity of the start heuristics that are integrated into B&B. Therefore, the exact worst-case computational complexity of the three considered start heuristics and, consequently, the B&B method when applying each one can be determined offline, which is of significant importance for real-time applications of hybrid MPC. The proposed algorithms are validated by comparing against the corresponding online heuristic-based MILP solvers in numerical experiments.
Ämnesord
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Reglerteknik (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Control Engineering (hsv//eng)
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas