Publication Date:
2022-03-14
Description:
Modern solving software for mixed-integer programming (MIP)
incorporates numerous algorithmic components whose behavior is
controlled by user parameter choices,
and whose usefulness dramatically varies depending on the progress of the solving process.
In this thesis, our aim is to
construct a phase-based solver that dynamically reacts
on phase transitions with an appropriate change of its component behavior.
Therefore, we decompose the branch-and-bound solving process into three distinct phases:
The first phase objective is to find a feasible solution. During the second phase,
a sequence of incumbent solutions gets constructed
until the incumbent is eventually optimal. Proving
optimality is the central objective of the remaining third phase.
Based on the MIP-solver SCIP we construct a phase-based solver to make use of the phase concept in two steps:
First, we identify promising components for every solving phase individually and show that their
combination is beneficial on a test bed of practical MIP instances.
We then present and evaluate three heuristic criteria to make use of the phase-based solver
in practice, where it is infeasible to distinguish between the last two phases
before the termination of the solving process.
Language:
English
Type:
masterthesis
,
doc-type:masterThesis
Format:
application/pdf
Permalink
