Refine
Year of publication
Document Type
- In Proceedings (28)
- Article (21)
- In Collection (4)
- Book chapter (1)
- Doctoral Thesis (1)
- Master's Thesis (1)
Has Fulltext
- no (56) (remove)
Keywords
The Feasibility Pump (FP) is one of the best-known primal heuristics for mixed-integer programming (MIP): more than 15 papers suggested various modifications of all of its steps. So far, no variant considered information across multiple iterations, but all instead maintained the principle to optimize towards a single reference integer point. In this paper, we evaluate the usage of multiple reference vectors in all stages of the FP algorithm. In particular, we use LP-feasible vectors obtained during the main loop to tighten the variable domains before entering the computationally expensive enumeration stage. Moreover, we consider multiple integer reference vectors to explore further optimizing directions and introduce alternative objective scaling terms to balance the contributions of the distance functions and the original MIP objective. Our computational experiments demonstrate that the new method can improve performance on general MIP test sets. In detail, our modifications provide a 29.3% solution quality improvement and 4.0% running time improvement in an embedded setting, needing 16.0% fewer iterations over a large test set of MIP instances. In addition, the method’s success rate increases considerably within the first few iterations. In a standalone setting, we also observe a moderate performance improvement, which makes our version of FP suitable for the two main use-cases of the algorithm.
Conflict analysis has been successfully generalized from Boolean satisfiability (SAT) solving to mixed integer programming (MIP) solvers, but although MIP solvers operate with general linear inequalities, the conflict analysis in MIP has been limited to reasoning with the more restricted class of clausal constraint. This is in contrast to how conflict analysis is performed in so-called pseudo-Boolean solving, where solvers can reason directly with 0-1 integer linear inequalities rather than with clausal constraints extracted from such inequalities. In this work, we investigate how pseudo-Boolean conflict analysis can be integrated in MIP solving, focusing on 0-1 integer linear programs (0-1 ILPs). Phrased in MIP terminology, conflict analysis can be understood as a sequence of linear combinations and cuts. We leverage this perspective to design a new conflict analysis algorithm based on mixed integer rounding (MIR) cuts, which theoretically dominates the state-of-the-art division-based method in pseudo-Boolean solving. We also report results from a first proof-of-concept implementation of different pseudo-Boolean conflict analysis methods in the open-source MIP solver SCIP. When evaluated on a large and diverse set of 0-1 ILP instances from MIPLIB2017, our new MIR-based conflict analysis outperforms both previous pseudo-Boolean methods and the clause-based method used in MIP. Our conclusion is that pseudo-Boolean conflict analysis in MIP is a promising research direction that merits further study, and that it might also make sense to investigate the use of such conflict analysis to generate stronger no-goods in constraint programming.
Cutting planes and branching are two of the most important algorithms for solving mixed-integer linear programs. For both algorithms, disjunctions play an important role, being used both as branching candidates and as the foundation for some cutting planes. We relate branching decisions and cutting planes to each other through the underlying disjunctions that they are based on, with a focus on Gomory mixed-integer cuts and their corresponding split disjunctions. We show that selecting branching decisions based on quality measures of Gomory mixed-integer cuts leads to relatively small branch-and-bound trees, and that the result improves when using cuts that more accurately represent the branching decisions. Finally, we show how the history of previously computed Gomory mixed-integer cuts can be used to improve the performance of the state-of-the-art hybrid branching rule of SCIP. Our results show a $4\%$ decrease in solve time, and an $8\%$ decrease in number of nodes over affected instances of MIPLIB 2017.
The current cut selection algorithm used in mixed-integer programming solvers has remained largely unchanged since its creation. In this paper, we propose a set of new cut scoring measures, cut filtering techniques, and stopping criteria, extending the current state-of-the-art algorithm and obtaining a 5\% performance improvement for SCIP over the MIPLIB 2017 benchmark set.
Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.
This study investigates the progress made in lp and milp solver performance during the last two decades by comparing the solver software from the beginning of the millennium with the codes available today. On average, we found out that for solving lp/milp, computer hardware got about 20 times faster, and the algorithms improved by a factor of about nine for lp and around 50 for milp, which gives a total speed-up of about 180 and 1,000 times, respectively. However, these numbers have a very high variance and they considerably underestimate the progress made on the algorithmic side: many problem instances can nowadays be solved within seconds, which the old codes are not able to solve within any reasonable time.
We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of over 5,000 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, the compilation of these sets was done using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encoded requirements on diversity and balancedness with respect to instance features and performance data.
MILP. Try. Repeat.
(2021)
Conflict Analysis for MINLP
(2021)
The generalization of MIP techniques to deal with nonlinear, potentially non-convex, constraints have been a fruitful direction of research for computational MINLP in the last decade. In this paper, we follow that path in order to extend another essential subroutine of modern MIP solvers towards the case of nonlinear optimization: the analysis of infeasible subproblems for learning additional valid constraints. To this end, we derive two different strategies, geared towards two different solution approaches. These are using local dual proofs of infeasibility for LP-based branch-and-bound and the creation of nonlinear dual proofs for NLP-based branch-and-bound, respectively. We discuss implementation details of both approaches and present an extensive computational study, showing that both techniques can significantly enhance performance when solving MINLPs to global optimality.
It is a challenging task to fairly compare local solvers and heuristics against each other and against global solvers. How does one weigh a faster termination time against a better quality of the found solution? In this paper, we introduce the confined primal integral, a new performance measure that rewards a balance of speed and solution quality. It emphasizes the early part of the solution process by using an exponential decay. Thereby, it avoids that the order of solvers can be inverted by choosing an arbitrarily large time limit. We provide a closed analytic formula to compute the confined primal integral a posteriori and an incremental update formula to compute it during the run of an algorithm. For the latter, we show that we can drop one of the main assumptions of the primal integral, namely the knowledge of a fixed reference solution to compare against. Furthermore, we prove that the confined primal integral is a transitive measure when comparing local solves with different final solution values. Finally, we present a computational experiment where we compare a local MINLP solver that uses certain classes of cutting planes against a solver that does not. Both versions show very different tendencies w.r.t. average running time and solution quality, and we use the confined primal integral to argue which of the two is the preferred setting.