@inproceedings{BleyGleixnerKochetal.2012, author = {Bley, Andreas and Gleixner, Ambros and Koch, Thorsten and Vigerske, Stefan}, title = {Comparing MIQCP Solvers to a Specialised Algorithm for Mine Production Scheduling}, booktitle = {Modeling, Simulation and Optimization of Complex Processes. Proceedings of the Fourth International Conference on High Performance Scientific Computing, March 2-6, 2009, Hanoi, Vietnam}, doi = {10.1007/978-3-642-25707-0_3}, pages = {25 -- 39}, year = {2012}, abstract = {In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm.}, language = {en} } @misc{MuellerKuhlmannVigerske2017, author = {M{\"u}ller, Benjamin and Kuhlmann, Renke and Vigerske, Stefan}, title = {On the performance of NLP solvers within global MINLP solvers}, issn = {1438-0064}, doi = {10.1007/978-3-319-89920-6_84}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64504}, year = {2017}, abstract = {Solving mixed-integer nonlinear programs (MINLPs) to global optimality efficiently requires fast solvers for continuous sub-problems. These appear in, e.g., primal heuristics, convex relaxations, and bound tightening methods. Two of the best performing algorithms for these sub-problems are Sequential Quadratic Programming (SQP) and Interior Point Methods. In this paper we study the impact of different SQP and Interior Point implementations on important MINLP solver components that solve a sequence of similar NLPs. We use the constraint integer programming framework SCIP for our computational studies.}, language = {en} } @inproceedings{HendelMiltenbergerWitzig2018, author = {Hendel, Gregor and Miltenberger, Matthias and Witzig, Jakob}, title = {Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms}, booktitle = {OR 2018: International Conference on Operations Research}, year = {2018}, abstract = {State-of-the-art solvers for mixed integer programs (MIP) govern a variety of algorithmic components. Ideally, the solver adaptively learns to concentrate its computational budget on those components that perform well on a particular problem, especially if they are time consuming. We focus on three such algorithms, namely the classes of large neighborhood search and diving heuristics as well as Simplex pricing strategies. For each class we propose a selection strategy that is updated based on the observed runtime behavior, aiming to ultimately select only the best algorithms for a given instance. We review several common strategies for such a selection scenario under uncertainty, also known as Multi Armed Bandit Problem. In order to apply those bandit strategies, we carefully design reward functions to rank and compare each individual heuristic or pricing algorithm within its respective class. Finally, we discuss the computational benefits of using the proposed adaptive selection within the SCIP Optimization Suite on publicly available MIP instances.}, language = {en} } @misc{BertholdGleixner2009, author = {Berthold, Timo and Gleixner, Ambros}, title = {Undercover - a primal heuristic for MINLP based on sub-MIPs generated by set covering}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11632}, number = {09-40}, year = {2009}, abstract = {We present Undercover, a primal heuristic for mixed-integer nonlinear programming (MINLP). The heuristic constructs a mixed-integer linear subproblem (sub-MIP) of a given MINLP by fixing a subset of the variables. We solve a set covering problem to identify a minimal set of variables which need to be fixed in order to linearise each constraint. Subsequently, these variables are fixed to approximate values, e.g. obtained from a linear outer approximation. The resulting sub-MIP is solved by a mixed-integer linear programming solver. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. Although general in nature, the heuristic seems most promising for mixed-integer quadratically constrained programmes (MIQCPs). We present computational results on a general test set of MIQCPs selected from the MINLPLib.}, language = {en} } @misc{GleixnerWeltge2013, author = {Gleixner, Ambros and Weltge, Stefan}, title = {Learning and Propagating Lagrangian Variable Bounds for Mixed-Integer Nonlinear Programming}, issn = {1438-0064}, doi = {10.1007/978-3-642-38171-3_26}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17631}, year = {2013}, abstract = {Optimization-based bound tightening (OBBT) is a domain reduction technique commonly used in nonconvex mixed-integer nonlinear programming that solves a sequence of auxiliary linear programs. Each variable is minimized and maximized to obtain the tightest bounds valid for a global linear relaxation. This paper shows how the dual solutions of the auxiliary linear programs can be used to learn what we call Lagrangian variable bound constraints. These are linear inequalities that explain OBBT's domain reductions in terms of the bounds on other variables and the objective value of the incumbent solution. Within a spatial branch-and-bound algorithm, they can be learnt a priori (during OBBT at the root node) and propagated within the search tree at very low computational cost. Experiments with an implementation inside the MINLP solver SCIP show that this reduces the number of branch-and-bound nodes and speeds up solution times.}, language = {en} } @misc{BertholdGleixnerHeinzetal.2013, author = {Berthold, Timo and Gleixner, Ambros and Heinz, Stefan and Vigerske, Stefan}, title = {Analyzing the computational impact of MIQCP solver components}, issn = {1438-0064}, doi = {10.3934/naco.2012.2.739}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17754}, year = {2013}, abstract = {We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on a linear relaxation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.}, language = {en} } @inproceedings{MuellerKuhlmannVigerske2018, author = {M{\"u}ller, Benjamin and Kuhlmann, Renke and Vigerske, Stefan}, title = {On the performance of NLP solvers within global MINLP solvers}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-89920-6_84}, pages = {633 -- 639}, year = {2018}, abstract = {Solving mixed-integer nonlinear programs (MINLPs) to global optimality efficiently requires fast solvers for continuous sub-problems. These appear in, e.g., primal heuristics, convex relaxations, and bound tightening methods. Two of the best performing algorithms for these sub-problems are Sequential Quadratic Programming (SQP) and Interior Point Methods. In this paper we study the impact of different SQP and Interior Point implementations on important MINLP solver components that solve a sequence of similar NLPs. We use the constraint integer programming framework SCIP for our computational studies.}, language = {en} } @misc{GleixnerSteffyWolter2012, author = {Gleixner, Ambros and Steffy, Daniel and Wolter, Kati}, title = {Improving the Accuracy of Linear Programming Solvers with Iterative Refinement}, issn = {1438-0064}, doi = {10.1145/2442829.2442858}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15451}, year = {2012}, abstract = {We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description. We demonstrate that this algorithm is effective in practice for computing extended precision solutions and that this leads to direct improvement of the best known methods for solving LPs exactly over the rational numbers.}, language = {en} } @misc{BleyGleixnerKochetal.2009, author = {Bley, Andreas and Gleixner, Ambros and Koch, Thorsten and Vigerske, Stefan}, title = {Comparing MIQCP solvers to a specialised algorithm for mine production scheduling}, organization = {ZIB}, issn = {1438-0064}, doi = {10.1007/978-3-642-25707-0}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11507}, number = {09-32}, year = {2009}, abstract = {In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm.}, language = {en} } @misc{BertholdGleixner2013, author = {Berthold, Timo and Gleixner, Ambros}, title = {Undercover Branching}, issn = {1438-0064}, doi = {10.1007/978-3-642-38527-8_20}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18030}, year = {2013}, abstract = {In this paper, we present a new branching strategy for nonconvex MINLP that aims at driving the created subproblems towards linearity. It exploits the structure of a minimum cover of an MINLP, a smallest set of variables that, when fixed, render the remaining system linear: whenever possible, branching candidates in the cover are preferred. Unlike most branching strategies for MINLP, Undercover branching is not an extension of an existing MIP branching rule. It explicitly regards the nonlinearity of the problem while branching on integer variables with a fractional relaxation solution. Undercover branching can be naturally combined with any variable-based branching rule. We present computational results on a test set of general MINLPs from MINLPLib, using the new strategy in combination with reliability branching and pseudocost branching. The computational cost of Undercover branching itself proves negligible. While it turns out that it can influence the variable selection only on a smaller set of instances, for those that are affected, significant improvements in performance are achieved.}, language = {en} } @misc{Gleixner2012, author = {Gleixner, Ambros}, title = {Factorization and update of a reduced basis matrix for the revised simplex method}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-16349}, year = {2012}, abstract = {In this paper, we describe a method to enhance the FTRAN and BTRAN operations in the revised simplex algorithm by using a reduced basis matrix defined by basic columns and nonbasic rows. This submatrix of the standard basis matrix is potentially much smaller, but may change its dimension dynamically from iteration to iteration. For the classical product form update ("eta update"), the idea has been noted already by Zoutendijk, but only preliminarily tested by Powell in the early 1970s. We extend these ideas to Forrest-Tomlin type update formulas for an LU factorization of the reduced basis matrix, which are suited for efficient implementation within a state-of-the-art simplex solver. The computational advantages of the proposed method apply to pure LP solving as well as to LP-based branch-and-cut algorithms. It can easily be integrated into existing simplex codes.}, language = {en} } @misc{BertholdGleixnerHeinzetal.2011, author = {Berthold, Timo and Gleixner, Ambros and Heinz, Stefan and Vigerske, Stefan}, title = {On the computational impact of MIQCP solver components}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11998}, number = {11-01}, year = {2011}, abstract = {We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on linear outer approximation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.}, language = {en} } @inproceedings{MuellerMuñozGasseetal.2020, author = {M{\"u}ller, Benjamin and Muñoz, Gonzalo and Gasse, Maxime and Gleixner, Ambros and Lodi, Andrea and Serrano, Felipe}, title = {On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming}, booktitle = {Integer Programming and Combinatorial Optimization: 21th International Conference, IPCO 2020}, doi = {10.1007/978-3-030-45771-6_25}, pages = {322 -- 337}, year = {2020}, abstract = {The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solver can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm's ability to generate strong dual bounds through extensive computational experiments.}, language = {en} } @misc{WitzigGleixner2019, author = {Witzig, Jakob and Gleixner, Ambros}, title = {Conflict-Driven Heuristics for Mixed Integer Programming}, issn = {1438-0064}, doi = {10.1287/ijoc.2020.0973}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-72204}, year = {2019}, abstract = {Two essential ingredients of modern mixed-integer programming (MIP) solvers are diving heuristics that simulate a partial depth-first search in a branch-and-bound search tree and conflict analysis of infeasible subproblems to learn valid constraints. So far, these techniques have mostly been studied independently: primal heuristics under the aspect of finding high-quality feasible solutions early during the solving process and conflict analysis for fathoming nodes of the search tree and improving the dual bound. Here, we combine both concepts in two different ways. First, we develop a diving heuristic that targets the generation of valid conflict constraints from the Farkas dual. We show that in the primal this is equivalent to the optimistic strategy of diving towards the best bound with respect to the objective function. Secondly, we use information derived from conflict analysis to enhance the search of a diving heuristic akin to classical coefficient diving. The computational performance of both methods is evaluated using an implementation in the source-open MIP solver SCIP. Experiments are carried out on publicly available test sets including Miplib 2010 and Cor@l.}, language = {en} } @misc{HendelMiltenbergerWitzig2018, author = {Hendel, Gregor and Miltenberger, Matthias and Witzig, Jakob}, title = {Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69563}, year = {2018}, abstract = {State-of-the-art solvers for mixed integer programs (MIP) govern a variety of algorithmic components. Ideally, the solver adaptively learns to concentrate its computational budget on those components that perform well on a particular problem, especially if they are time consuming. We focus on three such algorithms, namely the classes of large neighborhood search and diving heuristics as well as Simplex pricing strategies. For each class we propose a selection strategy that is updated based on the observed runtime behavior, aiming to ultimately select only the best algorithms for a given instance. We review several common strategies for such a selection scenario under uncertainty, also known as Multi Armed Bandit Problem. In order to apply those bandit strategies, we carefully design reward functions to rank and compare each individual heuristic or pricing algorithm within its respective class. Finally, we discuss the computational benefits of using the proposed adaptive selection within the \scip Optimization Suite on publicly available MIP instances.}, language = {en} } @misc{GamrathKochMartinetal.2013, author = {Gamrath, Gerald and Koch, Thorsten and Martin, Alexander and Miltenberger, Matthias and Weninger, Dieter}, title = {Progress in Presolving for Mixed Integer Programming}, issn = {1438-0064}, doi = {10.1007/s12532-015-0083-5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42530}, year = {2013}, abstract = {Presolving attempts to eliminate redundant information from the problem formulation and simultaneously tries to strengthen the formulation. It can be very effective and is often essential for solving instances. Especially for mixed integer programming problems, fast and effective presolving algorithms are very important. In this paper, we report on three new presolving techniques. The first method searches for singleton continuous columns and tries to fix the corresponding variables. Then we present a presolving technique which exploits a partial order of the variables to induce fixings. Finally, we show an approach based on connected components in graphs. Our computational results confirm the profitable use of the algorithms in practice.}, language = {en} } @incollection{GamrathBertholdHeinzetal.2015, author = {Gamrath, Gerald and Berthold, Timo and Heinz, Stefan and Winkler, Michael}, title = {Structure-Based Primal Heuristics for Mixed Integer Programming}, volume = {13}, booktitle = {Optimization in the Real World}, publisher = {Springer Japan}, isbn = {978-4-431-55419-6}, doi = {10.1007/978-4-431-55420-2_3}, pages = {37 -- 53}, year = {2015}, abstract = {Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They help to reach optimality faster and provide good feasible solutions early in the solving process. In this paper, we present two new primal heuristics which take into account global structures available within MIP solvers to construct feasible solutions at the beginning of the solving process. These heuristics follow a large neighborhood search (LNS) approach and use global structures to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. The definition of the neighborhood is done by iteratively fixing variables and propagating these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. The neighborhood is solved as a sub-MIP and solutions are transferred back to the original problem. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about every third instance and therewith help to improve the average solving time.}, language = {en} } @misc{WitzigBertholdHeinz2016, author = {Witzig, Jakob and Berthold, Timo and Heinz, Stefan}, title = {Experiments with Conflict Analysis in Mixed Integer Programming}, issn = {1438-0064}, doi = {10.1007/978-3-319-59776-8_17}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61087}, year = {2016}, abstract = {The analysis of infeasible subproblems plays an import role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications obtained by domain propagation that led to infeasibility. The result of the analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept has its origin in solving satisfiability problems and is similarly used in constraint programming. The second concept is to analyze infeasible linear programming (LP) relaxations. The dual LP solution provides a set of multipliers that can be used to generate a single new globally valid linear constraint. The main contribution of this short paper is an empirical evaluation of two ways to combine both approaches. Experiments are carried out on general MIP instances from standard public test sets such as Miplib2010; the presented algorithms have been implemented within the non-commercial MIP solver SCIP. Moreover, we present a pool-based approach to manage conflicts which addresses the way a MIP solver traverses the search tree better than aging strategies known from SAT solving.}, language = {en} } @misc{GleixnerMaherMuelleretal.2017, author = {Gleixner, Ambros and Maher, Stephen J. and M{\"u}ller, Benjamin and Pedroso, Jo{\~a}o Pedro}, title = {Exact Methods for Recursive Circle Packing}, doi = {10.1007/s10479-018-3115-5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62039}, year = {2017}, abstract = {Packing rings into a minimum number of rectangles is an optimization problem which appears naturally in the logistics operations of the tube industry. It encompasses two major difficulties, namely the positioning of rings in rectangles and the recursive packing of rings into other rings. This problem is known as the Recursive Circle Packing Problem (RCPP). We present the first dedicated method for solving RCPP that provides strong dual bounds based on an exact Dantzig-Wolfe reformulation of a nonconvex mixed-integer nonlinear programming formulation. The key idea of this reformulation is to break symmetry on each recursion level by enumerating one-level packings, i.e., packings of circles into other circles, and by dynamically generating packings of circles into rectangles. We use column generation techniques to design a "price-and-verify" algorithm that solves this reformulation to global optimality. Extensive computational experiments on a large test set show that our method not only computes tight dual bounds, but often produces primal solutions better than those computed by heuristics from the literature.}, language = {en} } @misc{CheungGleixnerSteffy2016, author = {Cheung, Kevin K. H. and Gleixner, Ambros and Steffy, Daniel}, title = {Verifying Integer Programming Results}, issn = {1438-0064}, doi = {10.1007/978-3-319-59250-3_13}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61044}, year = {2016}, abstract = {Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MILP solution algorithms, the ideal form of such a certificate is not entirely clear. This paper proposes such a certificate format, illustrating its capabilities and structure through examples. The certificate format is designed with simplicity in mind and is composed of a list of statements that can be sequentially verified using a limited number of simple yet powerful inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of mixed-integer linear programming instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates.}, language = {en} } @misc{FujisawaShinanoWaki2015, author = {Fujisawa, Katsuki and Shinano, Yuji and Waki, Hayato}, title = {Optimization in the Real World}, volume = {13}, journal = {Mathematics for Industry (MFI)}, publisher = {Springer Tokyo Heidelberg New York Dordrecht London}, isbn = {978-4-431-55419-6}, doi = {10.1007/978-4-431-55420-2}, year = {2015}, language = {en} }