Heuristic algorithms in global MINLP solvers
Published on 2. February 2015
Book
Hardback
380 pages
978-3-8439-1931-9 (ISBN)
Description
In the literature for mixed integer programming, heuristic algorithms (particularly primal heuristics) are often considered as stand-alone procedures; in that context, heuristics are treated as an alternative to solving a problem to proven optimality. This conceals the fact that heuristic algorithms are a fundamental component of state-of-the-art global solvers for mixed integer linear programming (MIP) and mixed integer nonlinear programming (MINLP).
We focus on this latter aspect: we study heuristic algorithms that are tightly integrated within global MINLP solvers and analyze their impact on the overall solution process. Our contributions comprise generalizations of primal heuristics for MIP towards MINLP as well as novel ideas for MINLP primal heuristics and for heuristic algorithms to take branching decisions and to collect global information in MIP. These are:
- Shift-and-Propagate, a propagation heuristic for MIP that does not require the solution to an LP relaxation,
- a generic way to generalize large neighborhood search (LNS) heuristics from MIP to MINLP,
- an Objective Feasibility Pump heuristic for nonconvex MINLP that uses second-order information and a dynamic selection of rounding procedures,
- RENS, an LNS start heuristic for MINLP that optimizes over the set of feasible roundings of an LP solution,
- Undercover, an LNS start heuristic for MINLP that solves a largest sub-MIP of a given MINLP,
- Rapid Learning, a heuristic algorithm to generate globally valid conflict constraints for MIPs,
- Cloud Branching, a heuristic algorithm that exploits dual degeneracy to reduce the number of candidates for branching variable selection.
Additionally, we propose a new performance measure, the primal integral, that captures the benefits of primal heuristics better than traditional methods. In our computational study, we compare the performance of the MIP and MINLP solver SCIP with and without primal heuristics. We observe that heuristics improve the solver performance regarding all measures that we used. We further see that the harder a problem is to solve to global optimality, the more important the deployment of primal heuristics becomes.
The algorithms presented in this thesis are available in source code as part of the solver SCIP, of which the author has been a main developer for the last years. Methods described in this thesis have been re-implemented within several commercial and noncommercial MIP and MINLP software packages.
We focus on this latter aspect: we study heuristic algorithms that are tightly integrated within global MINLP solvers and analyze their impact on the overall solution process. Our contributions comprise generalizations of primal heuristics for MIP towards MINLP as well as novel ideas for MINLP primal heuristics and for heuristic algorithms to take branching decisions and to collect global information in MIP. These are:
- Shift-and-Propagate, a propagation heuristic for MIP that does not require the solution to an LP relaxation,
- a generic way to generalize large neighborhood search (LNS) heuristics from MIP to MINLP,
- an Objective Feasibility Pump heuristic for nonconvex MINLP that uses second-order information and a dynamic selection of rounding procedures,
- RENS, an LNS start heuristic for MINLP that optimizes over the set of feasible roundings of an LP solution,
- Undercover, an LNS start heuristic for MINLP that solves a largest sub-MIP of a given MINLP,
- Rapid Learning, a heuristic algorithm to generate globally valid conflict constraints for MIPs,
- Cloud Branching, a heuristic algorithm that exploits dual degeneracy to reduce the number of candidates for branching variable selection.
Additionally, we propose a new performance measure, the primal integral, that captures the benefits of primal heuristics better than traditional methods. In our computational study, we compare the performance of the MIP and MINLP solver SCIP with and without primal heuristics. We observe that heuristics improve the solver performance regarding all measures that we used. We further see that the harder a problem is to solve to global optimality, the more important the deployment of primal heuristics becomes.
The algorithms presented in this thesis are available in source code as part of the solver SCIP, of which the author has been a main developer for the last years. Methods described in this thesis have been re-implemented within several commercial and noncommercial MIP and MINLP software packages.