TY - GEN A1 - Berthold, Timo A1 - Witzig, Jakob T1 - Conflict Analysis for MINLP N2 - 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. T3 - ZIB-Report - 20-20 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78964 SN - 1438-0064 ER - TY - GEN A1 - Witzig, Jakob A1 - Berthold, Timo T1 - Conflict-Free Learning for Mixed Integer Programming N2 - Conflict learning plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. A major step for MIP conflict learning is to aggregate the LP relaxation of an infeasible subproblem to a single globally valid constraint, the dual proof, that proves infeasibility within the local bounds. Among others, one way of learning is to add these constraints to the problem formulation for the remainder of the search. We suggest to not restrict this procedure to infeasible subproblems, but to also use global proof constraints from subproblems that are not (yet) infeasible, but can be expected to be pruned soon. As a special case, we also consider learning from integer feasible LP solutions. First experiments of this conflict-free learning strategy show promising results on the MIPLIB2017 benchmark set. T3 - ZIB-Report - 19-59 KW - mixed integer programming KW - conflict analysis KW - dual proof analysis KW - no-good learning KW - solution learning Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-75338 SN - 1438-0064 ER - TY - CHAP A1 - Witzig, Jakob A1 - Berthold, Timo T1 - Conflict-Free Learning for Mixed Integer Programming T2 - Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2020 N2 - Conflict learning plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. A major step for MIP conflict learning is to aggregate the LP relaxation of an infeasible subproblem to a single globally valid constraint, the dual proof, that proves infeasibility within the local bounds. Among others, one way of learning is to add these constraints to the problem formulation for the remainder of the search. We suggest to not restrict this procedure to infeasible subproblems, but to also use global proof constraints from subproblems that are not (yet) infeasible, but can be expected to be pruned soon. As a special case, we also consider learning from integer feasible LP solutions. First experiments of this conflict-free learning strategy show promising results on the MIPLIB2017 benchmark set. Y1 - 2020 U6 - https://doi.org/10.1007/978-3-030-58942-4_34 IS - 12296 SP - 521 EP - 530 PB - Springer, Cham. ER - TY - GEN A1 - Gamrath, Gerald A1 - Anderson, Daniel A1 - Bestuzheva, Ksenia A1 - Chen, Wei-Kun A1 - Eifler, Leon A1 - Gasse, Maxime A1 - Gemander, Patrick A1 - Gleixner, Ambros A1 - Gottwald, Leona A1 - Halbig, Katrin A1 - Hendel, Gregor A1 - Hojny, Christopher A1 - Koch, Thorsten A1 - Le Bodic, Pierre A1 - Maher, Stephen J. A1 - Matter, Frederic A1 - Miltenberger, Matthias A1 - Mühmer, Erik A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Tawfik, Christine A1 - Vigerske, Stefan A1 - Wegscheider, Fabian A1 - Weninger, Dieter A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 7.0 N2 - The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming frame- work SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies mixed-integer linear op- timization problems and can be used stand-alone or integrated into SCIP via a presolver plugin. SCIP 7.0 provides additional support for decomposition algorithms. Besides im- provements in the Benders’ decomposition solver of SCIP, user-defined decomposition structures can be read, which are used by the automated Benders’ decomposition solver and two primal heuristics. Additionally, SCIP 7.0 comes with a tree size estimation that is used to predict the completion of the overall solving process and potentially trigger restarts. Moreover, substantial performance improvements of the MIP core were achieved by new developments in presolving, primal heuristics, branching rules, conflict analysis, and symmetry handling. Last, not least, the report presents updates to other components and extensions of the SCIP Optimization Suite, in particular, the LP solver SoPlex and the mixed-integer semidefinite programming solver SCIP-SDP. T3 - ZIB-Report - 20-10 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78023 SN - 1438-0064 ER - TY - GEN A1 - Hendel, Gregor A1 - Anderson, Daniel A1 - Le Bodic, Pierre A1 - Pfetsch, Marc T1 - Estimating the Size of Branch-And-Bound Trees N2 - This paper investigates the estimation of the size of Branch-and-Bound (B&B) trees for solving mixed-integer programs. We first prove that the size of the B&B tree cannot be approximated within a factor of~2 for general binary programs, unless P equals NP. Second, we review measures of the progress of the B&B search, such as the gap, and propose a new measure, which we call leaf frequency. We study two simple ways to transform these progress measures into B&B tree size estimates, either as a direct projection, or via double-exponential smoothing, a standard time-series forecasting technique. We then combine different progress measures and their trends into nontrivial estimates using Machine Learning techniques, which yields more precise estimates than any individual measure. The best method we have identified uses all individual measures as features of a random forest model. In a large computational study, we train and validate all methods on the publicly available MIPLIB and Coral general purpose benchmark sets. On average, the best method estimates B&B tree sizes within a factor of 3 on the set of unseen test instances even during the early stage of the search, and improves in accuracy as the search progresses. It also achieves a factor 2 over the entire search on each out of six additional sets of homogeneous instances we have tested. All techniques are available in version 7 of the branch-and-cut framework SCIP. T3 - ZIB-Report - 20-02 KW - mixed integer programming KW - machine learning KW - branch and bound KW - forecasting Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78144 SN - 1438-0064 ER - TY - JOUR A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Miltenberger, Matthias A1 - Kniasew, Dimitri A1 - Schlögel, Dominik A1 - Martin, Alexander A1 - Weninger, Dieter T1 - Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming JF - Journal of Computational Mathematics N2 - The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of robust and future-proof decision support systems. The complexity of industrial-scale supply chain optimization, however, often poses limits to the application of general mixed-integer programming solvers. In this paper we describe algorithmic innovations that help to ensure that MIP solver performance matches the complexity of the large supply chain problems and tight time limits encountered in practice. Our computational evaluation is based on a diverse set, modeling real-world scenarios supplied by our industry partner SAP. Y1 - 2019 U6 - https://doi.org/10.4208/jcm.1905-m2019-0055 VL - 37 SP - 866 EP - 888 ER - TY - GEN A1 - Berthold, Timo A1 - Gamrath, Gerald A1 - Salvagnin, Domenico T1 - Exploiting Dual Degeneracy in Branching N2 - Branch-and-bound methods for mixed-integer programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper, we study branching strategies for mixed-integer programs that exploit the knowledge of multiple alternative optimal solutions (a cloud ) of the current LP relaxation. These strategies naturally extend common methods like most infeasible branching, strong branching, pseudocost branching, and their hybrids, but we also propose a novel branching rule called cloud diameter branching. We show that dual degeneracy, a requirement for alternative LP optima, is present for many instances from common MIP test sets. Computational experiments show significant improvements in the quality of branching decisions as well as reduced branching effort when using our modifications of existing branching rules. We discuss different ways to generate a cloud of solutions and present extensive computational results showing that through a careful implementation, cloud modifications can speed up full strong branching by more than 10 % on standard test sets. Additionally, by exploiting degeneracy, we are also able to improve the state-of-the-art hybrid branching rule and reduce the solving time on affected instances by almost 20 % on average. T3 - ZIB-Report - 19-17 KW - mixed integer programming KW - branching rule KW - search strategy KW - dual degeneracy Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73028 SN - 1438-0064 ER - TY - GEN A1 - Witzig, Jakob A1 - Berthold, Timo A1 - Heinz, Stefan T1 - Computational Aspects of Infeasibility Analysis in Mixed Integer Programming N2 - The analysis of infeasible subproblems plays an important 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 this analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept is called conflict graph analysis and 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. Every ray of the dual LP provides a set of multipliers that can be used to generate a single new globally valid linear constraint. This method is called dual proof analysis. The main contribution of this paper is twofold. Firstly, we present three enhancements of dual proof analysis: presolving via variable cancellation, strengthening by applying mixed integer rounding functions, and a filtering mechanism. Further, we provide an intense computational study evaluating the impact of every presented component regarding dual proof analysis. Secondly, this paper presents the first integrated approach to use both conflict graph and dual proof analysis simultaneously within a single MIP solution process. All experiments are carried out on general MIP instances from the standard public test set MIPLIB 2017; the presented algorithms have been implemented within the non-commercial MIP solver SCIP and the commercial MIP solver FICO Xpress. T3 - ZIB-Report - 19-54 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74962 SN - 1438-0064 ER - TY - THES A1 - Scheizel, Jenia T1 - A fast Flow based Heuristic for MIP modelled SCM Problems Y1 - 2018 ER - TY - GEN A1 - Anderson, Daniel A1 - Hendel, Gregor A1 - Le Bodic, Pierre A1 - Viernickel, Jan Merlin T1 - Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation N2 - We propose a simple and general online method to measure the search progress within the Branch-and-Bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for Mixed-Integer Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant. Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances. It is implemented in the MIP solver SCIP and will be available in future releases. T3 - ZIB-Report - 19-11 KW - Mixed-Integer Programming solvers KW - Restart KW - Progress measures KW - tree-size estimates Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-72653 SN - 1438-0064 ER - TY - GEN A1 - Gleixner, Ambros A1 - Eifler, Leon A1 - Gally, Tristan A1 - Gamrath, Gerald A1 - Gemander, Patrick A1 - Gottwald, Robert Lion A1 - Hendel, Gregor A1 - Hojny, Christopher A1 - Koch, Thorsten A1 - Miltenberger, Matthias A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Puchert, Christian A1 - Rehfeldt, Daniel A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Viernickel, Jan Merlin A1 - Vigerske, Stefan A1 - Weninger, Dieter A1 - Witt, Jonas T. A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 5.0 N2 - This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 % faster than SCIP 4.0 and over twice as fast on instances that take at least 100 seconds to solve. For MINLP, SCIP 5.0 is about 17 % faster overall and 23 % faster on instances that take at least 100 seconds to solve. This boost is due to algorithmic advances in several parts of the solver such as cutting plane generation and management, a new adaptive coordination of large neighborhood search heuristics, symmetry handling, and strengthened McCormick relaxations for bilinear terms in MINLPs. Besides discussing the theoretical background and the implementational aspects of these developments, the report describes recent additions for the other software packages connected to SCIP, in particular for the LP solver SoPlex, the Steiner tree solver SCIP-Jack, the MISDP solver SCIP-SDP, and the parallelization framework UG. T3 - ZIB-Report - 17-61 KW - constraint integer programming KW - linear programming KW - mixed-integer linear programming KW - mixed-integer nonlinear programming KW - optimization solver KW - branch-and-cut KW - branch-and-price KW - column generation framework KW - parallelization KW - mixed-integer semidefinite programming KW - Steiner tree optimization Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66297 SN - 1438-0064 ER - TY - JOUR A1 - Hendel, Gregor T1 - Adaptive Large Neighborhood Search for Mixed Integer Programming JF - Mathematical Programming Computation N2 - Large Neighborhood Search (LNS) heuristics are among the most powerful but also most expensive heuristics for mixed integer programs (MIP). Ideally, a solver learns adaptively which LNS heuristics work best for the MIP problem at hand in order to concentrate its limited computational budget. To this end, this work introduces Adaptive Large Neighborhood Search (ALNS) for MIP, a primal heuristic that acts a framework for eight popular LNS heuristics such as Local Branching and Relaxation Induced Neighborhood Search (RINS). We distinguish the available LNS heuristics by their individual search domains, which we call neighborhoods. The decision which neighborhood should be executed is guided by selection strategies for the multi armed bandit problem, a related optimization problem during which suitable actions have to be chosen to maximize a reward function. In this paper, we propose an LNS-specific reward function to learn to distinguish between the available neighborhoods based on successful calls and failures. A second, algorithmic enhancement is a generic variable fixing priorization, which ALNS employs to adjust the subproblem complexity as needed. This is particularly useful for some neighborhoods which do not fix variables by themselves. The proposed primal heuristic has been implemented within the MIP solver SCIP. An extensive computational study is conducted to compare different LNS strategies within our ALNS framework on a large set of publicly available MIP instances from the MIPLIB and Coral benchmark sets. The results of this simulation are used to calibrate the parameters of the bandit selection strategies. A second computational experiment shows the computational benefits of the proposed ALNS framework within the MIP solver SCIP. Y1 - 2018 ER - TY - CHAP A1 - Witzig, Jakob A1 - Berthold, Timo A1 - Heinz, Stefan T1 - A Status Report on Conflict Analysis in Mixed Integer Nonlinear Programming T2 - Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2019 N2 - Mixed integer nonlinear programs (MINLPs) are arguably among the hardest optimization problems, with a wide range of applications. MINLP solvers that are based on linear relaxations and spatial branching work similar as mixed integer programming (MIP) solvers in the sense that they are based on a branch-and-cut algorithm, enhanced by various heuristics, domain propagation, and presolving techniques. However, the analysis of infeasible subproblems, which is an important component of most major MIP solvers, has been hardly studied in the context of MINLPs. There are two main approaches for infeasibility analysis in MIP solvers: conflict graph analysis, which originates from artificial intelligence and constraint programming, and dual ray analysis. The main contribution of this short paper is twofold. Firstly, we present the first computational study regarding the impact of dual ray analysis on convex and nonconvex MINLPs. In that context, we introduce a modified generation of infeasibility proofs that incorporates linearization cuts that are only locally valid. Secondly, we describe an extension of conflict analysis that works directly with the nonlinear relaxation of convex MINLPs instead of considering a linear relaxation. This is work-in-progress, and this short paper is meant to present first theoretical considerations without a computational study for that part. Y1 - 2019 U6 - https://doi.org/10.1007/978-3-030-19212-9_6 VL - 11494 SP - 84 EP - 94 PB - Springer ER - TY - CHAP A1 - Berthold, Timo A1 - Stuckey, Peter A1 - Witzig, Jakob T1 - Local Rapid Learning for Integer Programs T2 - Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2019 N2 - Conflict learning algorithms are an important component of modern MIP and CP solvers. But strong conflict information is typically gained by depth-first search. While this is the natural mode for CP solving, it is not for MIP solving. Rapid Learning is a hybrid CP/MIP approach where CP search is applied at the root to learn information to support the remaining MIP solve. This has been demonstrated to be beneficial for binary programs. In this paper, we extend the idea of Rapid Learning to integer programs, where not all variables are restricted to the domain {0, 1}, and rather than just running a rapid CP search at the root, we will apply it repeatedly at local search nodes within the MIP search tree. To do so efficiently, we present six heuristic criteria to predict the chance for local Rapid Learning to be successful. Our computational experiments indicate that our extended Rapid Learning algorithm significantly speeds up MIP search and is particularly beneficial on highly dual degenerate problems. Y1 - 2019 U6 - https://doi.org/10.1007/978-3-030-19212-9_5 VL - 11494 SP - 67 EP - 83 PB - Springer ER - TY - CHAP A1 - Anderson, Daniel A1 - Hendel, Gregor A1 - Le Bodic, Pierre A1 - Viernickel, Jan Merlin T1 - Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation T2 - AAAI-19: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence N2 - We propose a simple and general online method to measure the search progress within the branch-and-bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for Mixed-Integer Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant. Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances. It is implemented in the MIP solver SCIP and will be available in future releases. Y1 - 2018 ER - TY - JOUR A1 - Gamrath, Gerald A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Winkler, Michael T1 - Structure-driven fix-and-propagate heuristics for mixed integer programming JF - Mathematical Programming Computation N2 - Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early and help to reduce the time needed to prove optimality. In this paper, we present a scheme for start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved first as an LP, and then as an auxiliary MIP if the rounded LP solution does not provide a feasible solution already. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about 60 % of the instances and by this, help to improve several performance measures for MIP solvers, including the primal integral and the average solving time. Y1 - 2019 U6 - https://doi.org/10.1007/s12532-019-00159-1 VL - 11 IS - 4 SP - 675 EP - 702 PB - Springer CY - Berlin Heidelberg ER - TY - GEN A1 - Berthold, Timo A1 - Stuckey, Peter A1 - Witzig, Jakob T1 - Local Rapid Learning for Integer Programs N2 - Conflict learning algorithms are an important component of modern MIP and CP solvers. But strong conflict information is typically gained by depth-first search. While this is the natural mode for CP solving, it is not for MIP solving. Rapid Learning is a hybrid CP/MIP approach where CP search is applied at the root to learn information to support the remaining MIP solve. This has been demonstrated to be beneficial for binary programs. In this paper, we extend the idea of Rapid Learning to integer programs, where not all variables are restricted to the domain {0, 1}, and rather than just running a rapid CP search at the root, we will apply it repeatedly at local search nodes within the MIP search tree. To do so efficiently, we present six heuristic criteria to predict the chance for local Rapid Learning to be successful. Our computational experiments indicate that our extended Rapid Learning algorithm significantly speeds up MIP search and is particularly beneficial on highly dual degenerate problems. T3 - ZIB-Report - 18-56 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71190 SN - 1438-0064 ER - TY - GEN A1 - Hendel, Gregor T1 - Adaptive Large Neighborhood Search for Mixed Integer Programming N2 - Large Neighborhood Search (LNS) heuristics are among the most powerful but also most expensive heuristics for mixed integer programs (MIP). Ideally, a solver learns adaptively which LNS heuristics work best for the MIP problem at hand in order to concentrate its limited computational budget. To this end, this work introduces Adaptive Large Neighborhood Search (ALNS) for MIP, a primal heuristic that acts a framework for eight popular LNS heuristics such as Local Branching and Relaxation Induced Neighborhood Search (RINS). We distinguish the available LNS heuristics by their individual search domains, which we call neighborhoods. The decision which neighborhood should be executed is guided by selection strategies for the multi armed bandit problem, a related optimization problem during which suitable actions have to be chosen to maximize a reward function. In this paper, we propose an LNS-specific reward function to learn to distinguish between the available neighborhoods based on successful calls and failures. A second, algorithmic enhancement is a generic variable fixing priorization, which ALNS employs to adjust the subproblem complexity as needed. This is particularly useful for some neighborhoods which do not fix variables by themselves. The proposed primal heuristic has been implemented within the MIP solver SCIP. An extensive computational study is conducted to compare different LNS strategies within our ALNS framework on a large set of publicly available MIP instances from the MIPLIB and Coral benchmark sets. The results of this simulation are used to calibrate the parameters of the bandit selection strategies. A second computational experiment shows the computational benefits of the proposed ALNS framework within the MIP solver SCIP. T3 - ZIB-Report - 18-60 KW - mixed integer programming KW - primal heuristics KW - large neighborhood search KW - multi armed bandit problem Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71167 SN - 1438-0064 ER - TY - GEN A1 - Witzig, Jakob A1 - Berthold, Timo A1 - Heinz, Stefan T1 - A Status Report on Conflict Analysis in Mixed Integer Nonlinear Programming N2 - Mixed integer nonlinear programs (MINLPs) are arguably among the hardest optimization problems, with a wide range of applications. MINLP solvers that are based on linear relaxations and spatial branching work similar as mixed integer programming (MIP) solvers in the sense that they are based on a branch-and-cut algorithm, enhanced by various heuristics, domain propagation, and presolving techniques. However, the analysis of infeasible subproblems, which is an important component of most major MIP solvers, has been hardly studied in the context of MINLPs. There are two main approaches for infeasibility analysis in MIP solvers: conflict graph analysis, which originates from artificial intelligence and constraint programming, and dual ray analysis. The main contribution of this short paper is twofold. Firstly, we present the first computational study regarding the impact of dual ray analysis on convex and nonconvex MINLPs. In that context, we introduce a modified generation of infeasibility proofs that incorporates linearization cuts that are only locally valid. Secondly, we describe an extension of conflict analysis that works directly with the nonlinear relaxation of convex MINLPs instead of considering a linear relaxation. This is work-in-progress, and this short paper is meant to present first theoretical considerations without a computational study for that part. T3 - ZIB-Report - 18-57 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71170 SN - 1438-0064 ER - TY - JOUR A1 - Witzig, Jakob A1 - Gleixner, Ambros T1 - Conflict-Driven Heuristics for Mixed Integer Programming JF - INFORMS Journal on Computing N2 - 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. Y1 - 2020 U6 - https://doi.org/10.1287/ijoc.2020.0973 VL - 33 IS - 2 SP - 706 EP - 720 ER - TY - JOUR A1 - Gleixner, Ambros A1 - Hendel, Gregor A1 - Gamrath, Gerald A1 - Achterberg, Tobias A1 - Bastubbe, Michael A1 - Berthold, Timo A1 - Christophel, Philipp M. A1 - Jarck, Kati A1 - Koch, Thorsten A1 - Linderoth, Jeff A1 - Lübbecke, Marco A1 - Mittelmann, Hans A1 - Ozyurt, Derya A1 - Ralphs, Ted A1 - Salvagnin, Domenico A1 - Shinano, Yuji T1 - MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library JF - Mathematical Programming Computation N2 - 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. Y1 - 2021 U6 - https://doi.org/10.1007/s12532-020-00194-3 VL - 13 IS - 3 SP - 443 EP - 490 ER - TY - GEN A1 - Georges, Alexander A1 - Gleixner, Ambros A1 - Gojic, Gorana A1 - Gottwald, Robert Lion A1 - Haley, David A1 - Hendel, Gregor A1 - Matejczyk, Bartlomiej T1 - Feature-Based Algorithm Selection for Mixed Integer Programming N2 - Mixed integer programming is a versatile and valuable optimization tool. However, solving specific problem instances can be computationally demanding even for cutting-edge solvers. Such long running times are often significantly reduced by an appropriate change of the solver's parameters. In this paper we investigate "algorithm selection", the task of choosing among a set of algorithms the ones that are likely to perform best for a particular instance. In our case, we treat different parameter settings of the MIP solver SCIP as different algorithms to choose from. Two peculiarities of the MIP solving process have our special attention. We address the well-known problem of performance variability by using multiple random seeds. Besides solving time, primal dual integrals are recorded as a second performance measure in order to distinguish solvers that timed out. We collected feature and performance data for a large set of publicly available MIP instances. The algorithm selection problem is addressed by several popular, feature-based methods, which have been partly extended for our purpose. Finally, an analysis of the feature space and performance results of the selected algorithms are presented. T3 - ZIB-Report - 18-17 KW - algorithm selection KW - mixed integer programming Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-68362 SN - 1438-0064 ER - TY - CHAP A1 - Hendel, Gregor A1 - Miltenberger, Matthias A1 - Witzig, Jakob T1 - Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms T2 - OR 2018: International Conference on Operations Research N2 - 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. Y1 - 2018 ER - TY - THES A1 - Miltenberger, Matthias T1 - Linear Programming in MILP Solving - A Computational Perspective N2 - Mixed-integer linear programming (MILP) plays a crucial role in the field of mathematical optimization and is especially relevant for practical applications due to the broad range of problems that can be modeled in that fashion. The vast majority of MILP solvers employ the LP-based branch-and-cut approach. As the name suggests, the linear programming (LP) subproblems that need to be solved therein influence their behavior and performance significantly. This thesis explores the impact of various LP solvers as well as LP solving techniques on the constraint integer programming framework SCIP Optimization Suite. SCIP allows for comparisons between academic and open-source LP solvers like Clp and SoPlex, as well as commercially developed, high-end codes like CPLEX, Gurobi, and Xpress. We investigate how the overall performance and stability of an MILP solver can be improved by new algorithmic enhancements like LP solution polishing and persistent scaling that we have implemented in the LP solver SoPlex. The former decreases the fractionality of LP solutions by selecting another vertex on the optimal hyperplane of the LP relaxation, exploiting degeneracy. The latter provides better numerical properties for the LP solver throughout the MILP solving process by preserving and extending the initial scaling factors, effectively also improving the overall performance of SCIP. Both enhancement techniques are activated by default in the SCIP Optimization Suite. Additionally, we provide an analysis of numerical conditions in SCIP through the lens of the LP solver by comparing different measures and how these evolve during the different stages of the solving process. A side effect of our work on this topic was the development of TreeD: a new and convenient way of presenting the search tree interactively and animated in the three-dimensional space. This visualization technique facilitates a better understanding of the MILP solving process of SCIP. Furthermore, this thesis presents the various algorithmic techniques like the row representation and iterative refinement that are implemented in SoPlex and that distinguish the solver from other simplex-based codes. Although it is often not as performant as its competitors, SoPlex demonstrates the ongoing research efforts in the field of linear programming with the simplex method. Aside from that, we demonstrate the rapid prototyping of algorithmic ideas and modeling approaches via PySCIPOpt, the Python interface to the SCIP Optimization Suite. This tool allows for convenient access to SCIP's internal data structures from the user-friendly Python programming language to implement custom algorithms and extensions without any prior knowledge of SCIP's programming language C. TreeD is one such example, demonstrating the use of several Python libraries on top of SCIP. PySCIPOpt also provides an intuitive modeling layer to formulate problems directly in the code without having to utilize another modeling language or framework. All contributions presented in this thesis are readily accessible in source code in SCIP Optimization Suite or as separate projects on the public code-sharing platform GitHub. KW - linear programming KW - mixed-integer programming KW - optimization KW - simplex KW - SCIP Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-91873 UR - https://www.dr.hut-verlag.de/9783843953238.html SN - 9783843953238 PB - Verlag Dr. Hut GmbH ER - TY - GEN A1 - Witzig, Jakob A1 - Gleixner, Ambros T1 - Conflict-Driven Heuristics for Mixed Integer Programming N2 - 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. T3 - ZIB-Report - 19-08 KW - mixed integer programming; primal heuristics; conflict analysis; branch-and-bound Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-72204 SN - 1438-0064 ER - TY - GEN A1 - Hendel, Gregor A1 - Miltenberger, Matthias A1 - Witzig, Jakob T1 - Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms N2 - 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. T3 - ZIB-Report - 18-36 KW - mixed integer programming KW - primal heuristics KW - multi armed bandit Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69563 SN - 1438-0064 ER - TY - GEN A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Miltenberger, Matthias A1 - Weninger, Dieter T1 - Progress in Presolving for Mixed Integer Programming N2 - 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. T3 - ZIB-Report - 13-48 KW - mixed-integer programming KW - presolving KW - preprocessing Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42530 SN - 1438-0064 ER - TY - CHAP A1 - Gamrath, Gerald A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Winkler, Michael T1 - Structure-Based Primal Heuristics for Mixed Integer Programming T2 - Optimization in the Real World N2 - 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. Y1 - 2015 SN - 978-4-431-55419-6 U6 - https://doi.org/10.1007/978-4-431-55420-2_3 VL - 13 SP - 37 EP - 53 PB - Springer Japan ER - TY - GEN A1 - Witzig, Jakob A1 - Berthold, Timo A1 - Heinz, Stefan T1 - Experiments with Conflict Analysis in Mixed Integer Programming N2 - 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. T3 - ZIB-Report - 16-63 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61087 SN - 1438-0064 ER - TY - GEN A1 - Cheung, Kevin K. H. A1 - Gleixner, Ambros A1 - Steffy, Daniel T1 - Verifying Integer Programming Results N2 - 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. T3 - ZIB-Report - 16-58 KW - correctness, verification, proof, certificate, optimality, infeasibility, mixed-integer linear programming Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61044 SN - 1438-0064 ER - TY - GEN A1 - Fujisawa, Katsuki A1 - Shinano, Yuji A1 - Waki, Hayato T1 - Optimization in the Real World T2 - Mathematics for Industry (MFI) Y1 - 2015 SN - 978-4-431-55419-6 U6 - https://doi.org/10.1007/978-4-431-55420-2 VL - 13 PB - Springer Tokyo Heidelberg New York Dordrecht London ER - TY - GEN A1 - Gleixner, Ambros A1 - Bastubbe, Michael A1 - Eifler, Leon A1 - Gally, Tristan A1 - Gamrath, Gerald A1 - Gottwald, Robert Lion A1 - Hendel, Gregor A1 - Hojny, Christopher A1 - Koch, Thorsten A1 - Lübbecke, Marco A1 - Maher, Stephen J. A1 - Miltenberger, Matthias A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Puchert, Christian A1 - Rehfeldt, Daniel A1 - Schlösser, Franziska A1 - Schubert, Christoph A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Viernickel, Jan Merlin A1 - Walter, Matthias A1 - Wegscheider, Fabian A1 - Witt, Jonas T. A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 6.0 N2 - The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion for cutting planes, one focus of this release are decomposition algorithms. Both SCIP and the automatic decomposition solver GCG now include advanced functionality for performing Benders’ decomposition in a generic framework. GCG’s detection loop for structured matrices and the coordination of pricing routines for Dantzig-Wolfe decomposition has been significantly revised for greater flexibility. Two SCIP extensions have been added to solve the recursive circle packing problem by a problem-specific column generation scheme and to demonstrate the use of the new Benders’ framework for stochastic capacitated facility location. Last, not least, the report presents updates and additions to the other components and extensions of the SCIP Optimization Suite: the LP solver SoPlex, the modeling language Zimpl, the parallelization framework UG, the Steiner tree solver SCIP-Jack, and the mixed-integer semidefinite programming solver SCIP-SDP. T3 - ZIB-Report - 18-26 KW - constraint integer programming KW - linear programming KW - mixed-integer linear programming KW - mixed-integer nonlinear programming KW - optimization solver KW - branch-and-cut KW - branch-and-price KW - column generation framework KW - parallelization KW - mixed-integer semidefinite programming KW - Steiner tree optimization Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69361 SN - 1438-0064 ER - TY - JOUR A1 - Gemander, Patrick A1 - Chen, Wei-Kun A1 - Weninger, Dieter A1 - Gottwald, Leona A1 - Gleixner, Ambros T1 - Two-row and two-column mixed-integer presolve using hashing-based pairing methods JF - EURO Journal on Computational Optimization N2 - In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolve techniques successfully is their speed. Hence, most methods inspect constraints or variables individually in order to guarantee linear complexity. In this paper, we present new hashing-based pairing mechanisms that help to overcome known performance limitations of more powerful presolve techniques that consider pairs of rows or columns. Additionally, we develop an enhancement to one of these presolve techniques by exploiting the presence of set-packing structures on binary variables in order to strengthen the resulting reductions without increasing runtime. We analyze the impact of these methods on the MIPLIB 2017 benchmark set based on an implementation in the MIP solver SCIP. Y1 - 2020 U6 - https://doi.org/10.1007/s13675-020-00129-6 VL - 8 IS - 3-4 SP - 205 EP - 240 ER - TY - JOUR A1 - Gamrath, Gerald A1 - Berthold, Timo A1 - Salvagnin, Domenico T1 - An exploratory computational analysis of dual degeneracy in mixed-integer programming JF - EURO Journal on Computational Optimization N2 - Dual degeneracy, i.e., the presence of multiple optimal bases to a linear programming (LP) problem, heavily affects the solution process of mixed integer programming (MIP) solvers. Different optimal bases lead to different cuts being generated, different branching decisions being taken and different solutions being found by primal heuristics. Nevertheless, only a few methods have been published that either avoid or exploit dual degeneracy. The aim of the present paper is to conduct a thorough computational study on the presence of dual degeneracy for the instances of well-known public MIP instance collections. How many instances are affected by dual degeneracy? How degenerate are the affected models? How does branching affect degeneracy: Does it increase or decrease by fixing variables? Can we identify different types of degenerate MIPs? As a tool to answer these questions, we introduce a new measure for dual degeneracy: the variable–constraint ratio of the optimal face. It provides an estimate for the likelihood that a basic variable can be pivoted out of the basis. Furthermore, we study how the so-called cloud intervals—the projections of the optimal face of the LP relaxations onto the individual variables—evolve during tree search and the implications for reducing the set of branching candidates. Y1 - 2020 U6 - https://doi.org/10.1007/s13675-020-00130-z IS - 8 SP - 241 EP - 246 ER - TY - JOUR A1 - Gamrath, Gerald ED - Gomes, Carla ED - Sellmann, Meinolf T1 - Improving strong branching by propagation JF - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems N2 - Strong branching is an important component of most variable selection rules in branch-and-bound based mixed-integer linear programming solvers. It predicts the dual bounds of potential child nodes by solving auxiliary LPs and thereby helps to keep the branch-and-bound tree small. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Computational experiments on standard MIP instances indicate that this is beneficial in three aspects: It helps to reduce the average number of LP iterations per strong branching call, the number of branch-and-bound nodes, and the overall solving time. Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-38171-3_25 VL - 7874 SP - 347 EP - 354 PB - Springer Berlin Heidelberg ER - TY - JOUR A1 - Gamrath, Gerald A1 - Lübbecke, Marco ED - Festa, P. T1 - Experiments with a Generic Dantzig-Wolfe Decomposition for Integer Programs JF - Experimental Algorithms Y1 - 2010 U6 - https://doi.org/10.1007/978-3-642-13193-6_21 VL - 6049 SP - 239 EP - 252 PB - Springer-Verlag CY - Berlin ER - TY - JOUR A1 - Gamrath, Gerald T1 - Improving strong branching by domain propagation JF - EURO Journal on Computational Optimization N2 - One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs (LPs) and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique MIP solvers usually apply at every node of the branch-and-bound tree to tighten the local domains of variables. Computational experiments on standard MIP instances indicate that our improved strong branching method significantly improves the quality of the predictions and causes almost no additional effort. For a full strong branching rule, we are able to obtain substantial reductions of the branch-and-bound tree size as well as the solving time. Moreover, the state-of-the-art hybrid branching rule can be improved this way as well. This paper extends previous work by the author published in the proceedings of the CPAIOR 2013. Y1 - 2014 U6 - https://doi.org/10.1007/s13675-014-0021-8 VL - 2 IS - 3 SP - 99 EP - 122 PB - Springer CY - Berlin Heidelberg ER - TY - CHAP A1 - Hendel, Gregor A1 - Berthold, Timo A1 - Achterberg, Tobias T1 - Rounding and Propagation Heuristics for Mixed Integer Programming T2 - Operations Research Proceedings 2011 N2 - 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. Y1 - 2011 SP - 71 EP - 76 ER - TY - GEN A1 - Gamrath, Gerald T1 - Improving strong branching by domain propagation N2 - One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs (LPs) and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique usually used at every node of the branch-and-bound tree to tighten the local domains of variables. Computational experiments on standard MIP instances indicate that our improved strong branching method significantly improves the quality of the predictions and causes almost no additional effort. For a full strong branching rule, we are able to obtain substantial reductions of the branch-and-bound tree size as well as the solving time. Moreover, also the state-of-the-art hybrid branching rule can be improved this way. This paper extends previous work by the author published in the proceedings of the CPAIOR 2013. T3 - ZIB-Report - 13-47 KW - mixed-integer programming KW - branch-and-bound KW - branching rule KW - variable selection KW - strong branching KW - domain propagation Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42546 SN - 1438-0064 ER - TY - GEN A1 - Gamrath, Gerald A1 - Melchiori, Anna A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Salvagnin, Domenico T1 - Branching on multi-aggregated variables N2 - In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly. T3 - ZIB-Report - 15-10 KW - mixed-integer programming, branch-and-bound, branching rule, strong branching Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53829 SN - 1438-0064 ER - TY - GEN A1 - Witzig, Jakob A1 - Gamrath, Gerald A1 - Hiller, Benjamin T1 - Reoptimization Techniques in MIP Solvers N2 - Recently, there have been many successful applications of optimization algorithms that solve a sequence of quite similar mixed-integer programs (MIPs) as subproblems. Traditionally, each problem in the sequence is solved from scratch. In this paper we consider reoptimization techniques that try to benefit from information obtained by solving previous problems of the sequence. We focus on the case that subsequent MIPs differ only in the objective function or that the feasible region is reduced. We propose extensions of the very complex branch-and-bound algorithms employed by general MIP solvers based on the idea to ``warmstart'' using the final search frontier of the preceding solver run. We extend the academic MIP solver SCIP by these techniques to obtain a reoptimizing branch-and-bound solver and report computational results which show the effectiveness of the approach. T3 - ZIB-Report - 15-24 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54375 SN - 1438-0064 ER - TY - GEN A1 - Maher, Stephen J. A1 - Fischer, Tobias A1 - Gally, Tristan A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Gottwald, Robert Lion A1 - Hendel, Gregor A1 - Koch, Thorsten A1 - Lübbecke, Marco A1 - Miltenberger, Matthias A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Puchert, Christian A1 - Rehfeldt, Daniel A1 - Schenker, Sebastian A1 - Schwarz, Robert A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Weninger, Dieter A1 - Witt, Jonas T. A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 4.0 N2 - The SCIP Optimization Suite is a powerful collection of optimization software that consists of the branch-cut-and-price framework and mixed-integer programming solver SCIP, the linear programming solver SoPlex, the modeling language Zimpl, the parallelization framework UG, and the generic branch-cut-and-price solver GCG. Additionally, it features the extensions SCIP-Jack for solving Steiner tree problems, PolySCIP for solving multi-objective problems, and SCIP-SDP for solving mixed-integer semidefinite programs. The SCIP Optimization Suite has been continuously developed and has now reached version 4.0. The goal of this report is to present the recent changes to the collection. We not only describe the theoretical basis, but focus on implementation aspects and their computational consequences. T3 - ZIB-Report - 17-12 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-62170 SN - 1438-0064 ER - TY - GEN A1 - Gamrath, Gerald A1 - Fischer, Tobias A1 - Gally, Tristan A1 - Gleixner, Ambros A1 - Hendel, Gregor A1 - Koch, Thorsten A1 - Maher, Stephen J. A1 - Miltenberger, Matthias A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Puchert, Christian A1 - Rehfeldt, Daniel A1 - Schenker, Sebastian A1 - Schwarz, Robert A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Vigerske, Stefan A1 - Weninger, Dieter A1 - Winkler, Michael A1 - Witt, Jonas T. A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 3.2 N2 - The SCIP Optimization Suite is a software toolbox for generating and solving various classes of mathematical optimization problems. Its major components are the modeling language ZIMPL, the linear programming solver SoPlex, the constraint integer programming framework and mixed-integer linear and nonlinear programming solver SCIP, the UG framework for parallelization of branch-and-bound-based solvers, and the generic branch-cut-and-price solver GCG. It has been used in many applications from both academia and industry and is one of the leading non-commercial solvers. This paper highlights the new features of version 3.2 of the SCIP Optimization Suite. Version 3.2 was released in July 2015. This release comes with new presolving steps, primal heuristics, and branching rules within SCIP. In addition, version 3.2 includes a reoptimization feature and improved handling of quadratic constraints and special ordered sets. SoPlex can now solve LPs exactly over the rational number and performance improvements have been achieved by exploiting sparsity in more situations. UG has been tested successfully on 80,000 cores. A major new feature of UG is the functionality to parallelize a customized SCIP solver. GCG has been enhanced with a new separator, new primal heuristics, and improved column management. Finally, new and improved extensions of SCIP are presented, namely solvers for multi-criteria optimization, Steiner tree problems, and mixed-integer semidefinite programs. T3 - ZIB-Report - 15-60 KW - mixed-integer linear and nonlinear programming KW - MIP solver KW - MINLP solver KW - linear programming KW - LP solver KW - simplex method KW - modeling KW - parallel branch-and-bound KW - branch-cut-and-price framework KW - generic column generation KW - Steiner tree solver KW - multi-criteria optimization KW - mixed-integer semidefinite programming Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57675 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Hendel, Gregor T1 - Shift-And-Propagate N2 - For mixed integer programming, recent years have seen a growing interest in the design of general purpose primal heuristics for use inside complete solvers. Many of these heuristics rely on an optimal LP solution. Finding this may itself take a significant amount of time. The presented paper addresses this issue by the introduction of the Shift-And-Propagate heuristic. Shift-And-Propagate is a pre-root primal heuristic that does not require a previously found LP solution. It applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement of existing rounding and propagation heuristics. T3 - ZIB-Report - 13-03 KW - primal heuristic KW - mixed integer programming KW - domain propagation KW - rounding Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17596 SN - 1438-0064 ER - TY - GEN A1 - Gamrath, Gerald T1 - Improving strong branching by propagation N2 - Strong branching is an important component of most variable selection rules in branch-and-bound based mixed-integer linear programming solvers. It predicts the dual bounds of potential child nodes by solving auxiliary LPs and thereby helps to keep the branch-and-bound tree small. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Computational experiments on standard MIP instances indicate that this is beneficial in three aspects: It helps to reduce the average number of LP iterations per strong branching call, the number of branch-and-bound nodes, and the overall solving time. T3 - ZIB-Report - 12-46 KW - mixed-integer programming KW - branch-and-bound KW - branching rule KW - strong branching KW - domain propagation Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17701 SN - 1438-0064 ER - TY - CHAP A1 - Gottwald, Robert Lion A1 - Maher, Stephen J. A1 - Shinano, Yuji T1 - Distributed Domain Propagation T2 - 16th International Symposium on Experimental Algorithms (SEA 2017) N2 - Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite its simplicity, portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after the domain of a variable has been reduced. In this paper we introduce distributed domain propagation, a technique that shares bound tightenings across solvers to trigger further domain propagations. We investigate its impact in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions, they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers. Y1 - 2017 U6 - https://doi.org/10.4230/LIPIcs.SEA.2017.6 VL - 75 SP - 6:1 EP - 6:11 ER - TY - CHAP A1 - Gamrath, Gerald A1 - Schubert, Christoph T1 - Measuring the impact of branching rules for mixed-integer programming T2 - Operations Research Proceedings 2017 N2 - Branching rules are an integral component of the branch-and-bound algorithm typically used to solve mixed-integer programs and subject to intense research. Different approaches for branching are typically compared based on the solving time as well as the size of the branch-and-bound tree needed to prove optimality. The latter, however, has some flaws when it comes to sophisticated branching rules that do not only try to take a good branching decision, but have additional side-effects. We propose a new measure for the quality of a branching rule that distinguishes tree size reductions obtained by better branching decisions from those obtained by such side-effects. It is evaluated for common branching rules providing new insights in the importance of strong branching. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-319-89920-6_23 SP - 165 EP - 170 PB - Springer International Publishing ER - TY - GEN A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Miltenberger, Matthias A1 - Kniasew, Dimitri A1 - Schlögel, Dominik A1 - Martin, Alexander A1 - Weninger, Dieter T1 - Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming N2 - SAP's decision support systems for optimized supply network planning rely on mixed-integer programming as the core engine to compute optimal or near-optimal solutions. The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of a robust and future-proof decision support system for a large and diverse customer base. In this paper we describe our coordinated efforts to ensure that the performance of the underlying solution algorithms matches the complexity of the large supply chain problems and tight time limits encountered in practice. T3 - ZIB-Report - 16-45 KW - supply chain management, supply network optimization, mixed-integer linear programming, primal heuristics, numerical stability, large-scale optimization Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61107 SN - 1438-0064 ER - TY - GEN A1 - Gottwald, Robert Lion A1 - Maher, Stephen J. A1 - Shinano, Yuji T1 - Distributed domain propagation N2 - Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite it's simplicity portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after a variables domain has been reduced. This paper investigates the impact of distributed domain propagation in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers. T3 - ZIB-Report - 16-71 KW - mixed integer programming KW - parallelization KW - domain propagation KW - portfolio solvers Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61380 SN - 1438-0064 ER - TY - GEN A1 - Hendel, Gregor T1 - Enhancing MIP branching decisions by using the sample variance of pseudo-costs N2 - The selection of a good branching variable is crucial for small search trees in Mixed Integer Programming. Most modern solvers employ a strategy guided by history information, mainly the variable pseudo-costs, which are used to estimate the objective gain. At the beginning of the search, such information is usually collected via an expensive look-ahead strategy called strong-branching until variables are considered reliable. The reliability notion is thereby mostly based on fixed-number thresholds, which may lead to ineffective branching decisions on problems with highly varying objective gains. We suggest two new notions of reliability motivated by mathematical statistics that take into account the sample variance of the past observations on each variable individually. The first method prioritizes additional strong-branching look-aheads on variables whose pseudo-costs show a large variance by measuring the relative error of a pseudo-cost confidence interval. The second method performs a two-sample Student-t test for filtering branching candidates with a high probability to be better than the best history candidate. Both methods were implemented in the MIP-solver SCIP and computational results on standard MIP test sets are presented. T3 - ZIB-Report - 15-28 KW - mixed-integer programming KW - reliability branching Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54591 SN - 1438-0064 ER - TY - CHAP A1 - Hendel, Gregor T1 - Enhancing MIP Branching Decisions by Using the Sample Variance of Pseudo Costs T2 - Integration of AI and OR Techniques in Constraint Programming N2 - The selection of a good branching variable is crucial for small search trees in Mixed Integer Programming. Most modern solvers employ a strategy guided by history information, mainly the variable pseudo-costs, which are used to estimate the objective gain. At the beginning of the search, such information is usually collected via an expensive look-ahead strategy called strong branching until variables are considered reliable. The reliability notion is thereby mostly based on fixed-number thresholds, which may lead to ineffective branching decisions on problems with highly varying objective gains. We suggest two new notions of reliability motivated by mathematical statistics that take into account the sample variance of the past observations on each variable individually. The first method prioritizes additional strong branching look-aheads on variables whose pseudo-costs show a large variance by measuring the relative error of a pseudo-cost confidence interval. The second method performs a specialized version of a two-sample Student’s t -test for filtering branching candidates with a high probability to be better than the best history candidate. Both methods were implemented in the MIP-solver SCIP and computational results on standard MIP test sets are presented. Y1 - 2015 U6 - https://doi.org/10.1007/978-3-319-18008-3_14 VL - 9075 SP - 199 EP - 214 ER - TY - GEN A1 - Gamrath, Gerald A1 - Schubert, Christoph T1 - Measuring the impact of branching rules for mixed-integer programming N2 - Branching rules are an integral component of the branch-and-bound algorithm typically used to solve mixed-integer programs and subject to intense research. Different approaches for branching are typically compared based on the solving time as well as the size of the branch-and-bound tree needed to prove optimality. The latter, however, has some flaws when it comes to sophisticated branching rules that do not only try to take a good branching decision, but have additional side-effects. We propose a new measure for the quality of a branching rule that distinguishes tree size reductions obtained by better branching decisions from those obtained by such side-effects. It is evaluated for common branching rules providing new insights in the importance of strong branching. T3 - ZIB-Report - 17-34 KW - mixed-integer programming KW - branch-and-bound KW - branching rule KW - strong branching Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64722 SN - 1438-0064 ER - TY - GEN A1 - Miltenberger, Matthias A1 - Ralphs, Ted A1 - Steffy, Daniel T1 - Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization T2 - Operations Research Proceedings 2017 N2 - We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether such predictions can be used to make better algorithmic choices. In a first step towards this goal, we discuss here the numerical behavior of an existing solver in order to determine whether our intuitive understanding of this behavior is correct. T3 - ZIB-Report - 17-43 KW - Mixed Integer Programming KW - Linear Programming KW - Algorithm Analysis Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64645 SN - 1438-0064 ER - TY - CHAP A1 - Miltenberger, Matthias A1 - Ralphs, Ted A1 - Steffy, Daniel T1 - Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization T2 - Operations Research Proceedings 2017 N2 - We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether such predictions can be used to make better algorithmic choices. In a first step towards this goal, we discuss here the numerical behavior of an existing solver in order to determine whether our intuitive understanding of this behavior is correct. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-319-89920-6 SP - 151 EP - 157 PB - Springer International Publishing ER - TY - JOUR A1 - Gleixner, Ambros A1 - Steffy, Daniel A1 - Wolter, Kati T1 - Iterative Refinement for Linear Programming JF - INFORMS Journal on Computing N2 - 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 show that this algorithm is effective in practice for computing extended precision solutions and that it leads to a direct improvement of the best known methods for solving LPs exactly over the rational numbers. Our implementation is publically available as an extension of the academic LP solver SoPlex. Y1 - 2016 U6 - https://doi.org/10.1287/ijoc.2016.0692 VL - 28 IS - 3 SP - 449 EP - 464 ER - TY - CHAP A1 - Hendel, Gregor T1 - Exploiting Solving Phases for Mixed-Integer Programs T2 - Operations Research Proceedings 2015 N2 - Modern MIP solving software incorporates dozens of auxiliary algorithmic components for supporting the branch-and-bound search in finding and improving solutions and in strengthening the relaxation. Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process. We propose an adaptive solver behavior that dynamically reacts on transitions between the three typical phases of a MIP solving process: 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 demonstrate the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide heuristic alternatives to make use of the concept in practice. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-42902-1_1 SP - 3 EP - 9 ER - TY - GEN A1 - Witzig, Jakob T1 - Conflict Driven Diving for Mixed Integer Programming N2 - The analysis of infeasibility plays an important role in solving satisfiability problems (SAT) and mixed integer programs (MIPs). In mixed integer programming, this procedure is called conflict analysis. So far, modern MIP solvers use conflict analysis only for propagation and improving the dual bound, i.e., fathoming nodes that cannot contain feasible solutions. In this short paper, we present a new approach which uses conflict information to improve the primal bound during a MIP solve. To derive new improving primal solutions we use a conflict driven diving heuristic called conflict diving that uses the information obtained by conflict analysis. Conflict diving pursues a twofold strategy. By using conflict information the new diving approach is guided into parts of the search space that are usually not explored by other diving heuristics. At the same time, conflict diving has a fail-fast-strategy to reduce the time spent if it cannot find a new primal solution. As a byproduct, additional valid conflict constraints can be derived, from which a MIP solver can gain benefit to improve the dual bound as well. To show the added-value of conflict diving within a MIP solver, conflict diving has been implemented within the non-commercial MIP solver SCIP. Experiments are carried out on general MIP instances from standard public test sets, like MIPLIB2010 or Cor@l. T3 - ZIB-Report - 17-69 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66116 SN - 1438-0064 ER - TY - GEN A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Hendel, Gregor T1 - Rounding and Propagation Heuristics for Mixed Integer Programming N2 - 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. T3 - ZIB-Report - 11-29 KW - primal heuristic KW - mixed integer programming KW - domain propagation Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-13255 ER - TY - GEN A1 - Maher, Stephen J. A1 - Miltenberger, Matthias A1 - Pedroso, João Pedro A1 - Rehfeldt, Daniel A1 - Schwarz, Robert A1 - Serrano, Felipe T1 - PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite N2 - SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP. T3 - ZIB-Report - 16-64 KW - SCIP, Mathematical optimization, Python, Modeling Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61348 SN - 1438-0064 ER - TY - JOUR A1 - Berthold, Timo A1 - Hendel, Gregor A1 - Koch, Thorsten T1 - From feasibility to improvement to proof: three phases of solving mixed-integer programs JF - Optimization Methods and Software N2 - Modern mixed-integer programming (MIP) solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three distinct phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behaviour of the non-commercial MIP solver Scip at the predicted phase transition points. Y1 - 2017 U6 - https://doi.org/10.1080/10556788.2017.1392519 VL - 33 IS - 3 SP - 499 EP - 517 PB - Taylor & Francis ER - TY - CHAP A1 - Gamrath, Gerald A1 - Melchiori, Anna A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Salvagnin, Domenico T1 - Branching on Multi-aggregated Variables T2 - Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015 N2 - In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly. Y1 - 2015 U6 - https://doi.org/10.1007/978-3-319-18008-3_10 VL - 9075 SP - 141 EP - 156 ER - TY - JOUR A1 - Berthold, Timo A1 - Hendel, Gregor T1 - Shift-and-Propagate JF - Journal of Heuristics N2 - In recent years, there has been a growing interest in the design of general purpose primal heuristics for use inside complete mixed integer programming solvers. Many of these heuristics rely on an optimal LP solution, which may take a significant amount of time to find. In this paper, we address this issue by introducing a pre-root primal heuristic that does not require a previously found LP solution. This heuristic, named Shift-and-Propagate , applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement to existing rounding and propagation heuristics. Y1 - 2014 U6 - https://doi.org/10.1007/s10732-014-9271-0 VL - 21 IS - 1 SP - 73 EP - 106 ER - TY - GEN A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - SCIP-Jack - A massively parallel STP solver N2 - In this article we describe the impact from embedding a 15 year old model for solving the Steiner tree problem in graphs in a state-of-the-art MIP-Framework, making the result run in a massively parallel environment and extending the model to solve as many variants as possible. We end up with a high-perfomance solver that is capable of solving previously unsolved instances and, in contrast to its predecessor, is freely available for academic research. T3 - ZIB-Report - 14-35 KW - Steiner Tree Problem KW - Mixed-Integer Programming KW - Branch-and-Cut KW - DIMACS Challenge Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52293 SN - 1438-0064 ER - TY - CHAP A1 - Witzig, Jakob A1 - Berthold, Timo A1 - Heinz, Stefan T1 - Experiments with Conflict Analysis in Mixed Integer Programming T2 - Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2017 N2 - 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. Y1 - 2017 U6 - https://doi.org/10.1007/978-3-319-59776-8_17 VL - 10335 SP - 211 EP - 222 PB - Springer ER - TY - GEN A1 - Hendel, Gregor T1 - Exploiting Solving Phases for Mixed-Integer Programs N2 - Modern MIP solving software incorporates dozens of auxiliary algorithmic components for supporting the branch-and-bound search in finding and improving solutions and in strengthening the relaxation. Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process. We propose an adaptive solver behavior that dynamically reacts on transitions between the three typical phases of a MIP solving process: 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 demonstrate the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide heuristic alternatives to make use of the concept in practice. T3 - ZIB-Report - 15-64 KW - Branch-and-Bound, Mixed-Integer Programming Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57098 SN - 1438-0064 ER - TY - GEN A1 - Gleixner, Ambros A1 - Steffy, Daniel A1 - Wolter, Kati T1 - Iterative Refinement for Linear Programming N2 - 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 show that this algorithm is effective in practice for computing extended precision solutions and that it leads to a direct improvement of the best known methods for solving LPs exactly over the rational numbers. Our implementation is publically available as an extension of the academic LP solver SoPlex. T3 - ZIB-Report - 15-15 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-55118 SN - 1438-0064 ER - TY - GEN A1 - Gamrath, Gerald A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Winkler, Michael T1 - Structure-based primal heuristics for mixed integer programming N2 - 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. T3 - ZIB-Report - 15-26 KW - mixed-integer programming, large neighborhood search, primal heuristics, domain propagation Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-55518 SN - 1438-0064 ER - TY - CHAP A1 - Gamrath, Gerald A1 - Hiller, Benjamin A1 - Witzig, Jakob T1 - Reoptimization Techniques in MIP Solvers N2 - Recently, there have been many successful applications of optimization algorithms that solve a sequence of quite similar mixed-integer programs (MIPs) as subproblems. Traditionally, each problem in the sequence is solved from scratch. In this paper we consider reoptimization techniques that try to benefit from information obtained by solving previous problems of the sequence. We focus on the case that subsequent MIPs differ only in the objective function or that the feasible region is reduced. We propose extensions of the very complex branch-and-bound algorithms employed by general MIP solvers based on the idea to ``warmstart'' using the final search frontier of the preceding solver run. We extend the academic MIP solver SCIP by these techniques to obtain a reoptimizing branch-and-bound solver and report computational results which show the effectiveness of the approach. Y1 - 2015 SN - 978-3-319-20086-6 U6 - https://doi.org/10.1007/978-3-319-20086-6_14 VL - 9125 SP - 181 EP - 192 PB - Springer ET - Experimental Algorithms, Lecture Notes in Computer Science ER - TY - GEN A1 - Gamrath, Gerald A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Winkler, Michael T1 - Structure-driven fix-and-propagate heuristics for mixed integer programming N2 - Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early in the solving process and help to solve instances to optimality faster. In this paper, we present a scheme for primal start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved as an LP and the solution is rounded. If the rounded solution did not provide a feasible solution already, a sub-MIP is solved for the neighborhood defined by the variable fixings performed in the first phase. The global structures help to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about three out of five instances and therewith help to improve several performance measures for MIP solvers, including the primal integral and the average solving time. T3 - ZIB-Report - 17-56 KW - mixed-integer programming KW - primal heuristics KW - fix-and-propagate KW - large neighborhood search KW - domain propagation Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65387 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Hendel, Gregor A1 - Koch, Thorsten T1 - The Three Phases of MIP Solving N2 - Modern MIP solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three different phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behavior of the MIP solver SCIP at the predicted phase transition points. T3 - ZIB-Report - 16-78 KW - optimization software KW - mixed-integer programming KW - branch-and-bound KW - adaptive search behavior KW - optimality prediction Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61607 SN - 1438-0064 ER - TY - JOUR A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Miltenberger, Matthias A1 - Weninger, Dieter T1 - Progress in presolving for mixed integer programming JF - Mathematical Programming Computation N2 - This paper describes three presolving techniques for solving mixed integer programming problems (MIPs) that were implemented in the academic MIP solver SCIP. The task of presolving is to reduce the problem size and strengthen the formulation, mainly by eliminating redundant information and exploiting problem structures. The first method fixes continuous singleton columns and extends results known from duality fixing. The second analyzes and exploits pairwise dominance relations between variables, whereas the third detects isolated subproblems and solves them independently. The performance of the presented techniques is demonstrated on two MIP test sets. One contains all benchmark instances from the last three MIPLIB versions, while the other consists of real-world supply chain management problems. The computational results show that the combination of all three presolving techniques almost halves the solving time for the considered supply chain management problems. For the MIPLIB instances we obtain a speedup of 20 % on affected instances while not degrading the performance on the remaining problems. Y1 - 2015 U6 - https://doi.org/10.1007/s12532-015-0083-5 VL - 7 IS - 4 SP - 367 EP - 398 ER -