90C59 Approximation methods and heuristics
Refine
Year of publication
Document Type
- ZIB-Report (17)
- Doctoral Thesis (3)
- Master's Thesis (2)
Language
- English (22)
Is part of the Bibliography
- no (22)
Keywords
Institute
Primal heuristics are an important component of state-of-the-art codes for
mixed integer programming. In this paper, we focus on primal heuristics
that only employ computationally inexpensive procedures such as rounding
and logical deductions (propagation). We give an overview of eight
different approaches. To assess the impact of these primal heuristics on
the ability to find feasible solutions, in particular early during search,
we introduce a new performance measure, the primal integral. Computational
experiments evaluate this and other measures on MIPLIB~2010 benchmark
instances.
In this paper we give an overview of the heuristics which are integrated into the open source branch-cut-and-price-framework SCIP. We briefly describe the fundamental ideas of different categories of heuristics and present some computational results which demonstrate the impact of heuristics on the overall solving process of SCIP.
A lot of problems arising in Combinatorial Optimization and Operations Research can be formulated as Mixed Integer Programs (MIP). Although MIP-solving is an NP-hard optimization problem, many practically relevant instances can be solved in reasonable time. In modern MIP-solvers like the branch-cut-and-price-framework SCIP, primal heuristics play a major role in finding and improving feasible solutions at the early steps of the solution process. This helps to reduce the overall computational effort, guides the remaining search process, and proves the feasibility of the MIP model. Furthermore, a heuristic solution with a small gap to optimality often is sufficient in practice. We investigate 16 different heuristics, all of which are available in SCIP. Four of them arise from the literature of the last decade, nine are specific implementations of general heuristic ideas, three have been newly developed. We present an improved version of the feasibility pump heuristic by Fischetti et al., which in experiments produced solutions with only a third of the optimality gap compared to the original version. Furthermore, we introduce two new Large Neighborhood Search (LNS) heuristics. Crossover is an LNS improvement heuristic making use of similarities of diverse MIP solutions to generate new incumbent solutions. RENS is an LNS rounding heuristic which evaluates the space of all possible roundings of a fractional LP-solution. This heuristic makes it possible to determine whether a point can be rounded to an integer solution and which is the best possible rounding. We conclude with a computational comparison of all described heuristics. It points out that a single heuristic on its own has only a slight impact on the overall performance of SCIP, but the combination of all of them reduces the running time by a factor of two compared to a version without any heuristics.
In the recent years, a couple of quite successful large neighborhood search heuristics for mixed integer programs has been published. Up to our knowledge, all of them are improvement heuristics. We present a new start heuristic for general MIPs working in the spirit of large neighborhood search. It constructs a sub-MIP which represents the space of all feasible roundings of some fractional point - normally the optimum of the LP-relaxation of the original MIP. Thereby, one is able to determine whether a point can be rounded to a feasible solution and which is the best possible rounding. Furthermore, a slightly modified version of RENS proves to be a well-performing heuristic inside the branch-cut-and-price-framework SCIP.
In modern MIP solvers, primal heuristics play a major role in finding and improving feasible solutions early in the solution process. However, classical performance measures such as time to optimality or number of branch-and-bound nodes reflect the impact of primal heuristics on the overall solving process badly. This article discusses the question of how to evaluate the effect of primal heuristics.
Therefore, we introduce a new performance measure, the "primal integral" which depends on the quality of solutions found during the solving process as well as on the points in time when they are found. Our computational results reveal that heuristics improve the performance of MIP solvers in terms of the primal bound by around 80%. Further, we compare five state-of-the-art MIP solvers w.r.t. the newly proposed measure.
Primal heuristics are an important component of state-of-the-art codes for mixed integer nonlinear programming (MINLP). In this article we give a compact overview of primal heuristics for MINLP that have been suggested in the literature of recent years. We sketch the fundamental concepts of different classes of heuristics and discuss specific implementations. A brief computational experiment shows that primal heuristics play a key role in achieving feasibility and finding good primal bounds within a global MINLP solver.
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).
In the present thesis, 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 novel 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 on six test sets with altogether 983 instances from academic and industrial sources, including our project partners ForNe, SAP, and Siemens. We observe that heuristics improve the solver performance regarding all measures that we used - by different orders of magnitude. 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 also been re-implemented within several commercial and noncommercial MIP and MINLP software packages, including Bonmin, CBC, Cplex, Gams, Sulum, and Xpress.
RENS – the optimal rounding
(2012)
This article introduces RENS, the relaxation enforced neighborhood search, a large neighborhood search algorithm for mixed integer nonlinear programming (MINLP) that uses a sub-MINLP to explore the set of feasible roundings of an optimal solution x' of a linear or nonlinear relaxation. The sub-MINLP is constructed by fixing integer variables x_j with x'_j in Z and bounding the remaining integer variables to x_j in {floor(x'_j), ceil(x'_j)}. We describe two different applications of RENS: as a standalone algorithm to compute an optimal rounding of the given starting solution and as a primal heuristic inside a complete MINLP solver.
We use the former to compare different kinds of relaxations and the impact of cutting planes on the roundability of the corresponding optimal solutions. We further utilize RENS to analyze the performance of three rounding heuristics implemented in the branch-cut-and-price framework SCIP. Finally, we study the impact of RENS when it is applied as a primal heuristic inside SCIP.
All experiments were performed on three publically available test sets of mixed integer linear programs (MIPs), mixed integer quadratically constrained programs (MIQCPs), and MINLPs, using solely software which is available in source code.
It turns out that for these problem classes 60% to 70% of the instances have roundable relaxation optima and that the success rate of RENS does not depend on the percentage of fractional variables. Last but not least, RENS applied as primal heuristic complements nicely with existing root node heuristics in SCIP and improves the overall performance.
Learning during search allows solvers for discrete optimization problems to remember parts of the search that they have already performed and avoid revisiting redundant parts. Learning approaches pioneered by the SAT and CP communities have been successfully incorporated into the SCIP constraint integer programming platform. In this paper we show that performing a heuristic constraint programming search during root node processing of a binary program can rapidly learn useful nogoods, bound changes, primal solutions, and branching statistics that improve the remaining IP search.
We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem.
We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib. It turns out that the majority of these instances allow for small covers. Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers.