@article{GleixnerHendelGamrathetal.2021, author = {Gleixner, Ambros and Hendel, Gregor and Gamrath, Gerald and Achterberg, Tobias and Bastubbe, Michael and Berthold, Timo and Christophel, Philipp M. and Jarck, Kati and Koch, Thorsten and Linderoth, Jeff and L{\"u}bbecke, Marco and Mittelmann, Hans and Ozyurt, Derya and Ralphs, Ted and Salvagnin, Domenico and Shinano, Yuji}, title = {MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library}, volume = {13}, journal = {Mathematical Programming Computation}, number = {3}, doi = {10.1007/s12532-020-00194-3}, pages = {443 -- 490}, year = {2021}, abstract = {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.}, language = {en} } @article{ShinanoAchterbergBertholdetal.2013, author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Vigerske, Stefan and Winkler, Michael}, title = {制約整数計画ソルバ SCIP の並列化}, volume = {61}, journal = {統計数理}, number = {1}, pages = {47 -- 78}, year = {2013}, abstract = {制約整数計画(CIP: Constraint Integer Programs)は,制約プログラミング(CP: Constraint Programming),混合整数計画(MIP: Mixed Integer Programming),充足可能性問題(SAT: Satisfability Problem)の研究分野におけるモデリング技術と解法を統合している.その結果,制約整数計画は,広いクラスの最適化問題を扱うことができる.SCIP(Solving Constraint Integer Programs)は,CIP を解くソルバとして実装され,Zuse Institute Berlin(ZIB)の研究者を中心として継続的に拡張が続けられている.本論文では,著者らによって開発された SCIP に対する2 種類の並列化拡張を紹介する.一つは,複数計算ノード間で大規模に並列動作する ParaSCIPである.もう一つは,複数コアと共有メモリを持つ 1 台の計算機上で(スレッド)並列で動作する FiberSCIP である.ParaSCIP は,HLRN II スーパーコンピュータ上で,一つのインスタンスを解くために最大 7,168 コアを利用した動作実績がある.また,統計数理研究所の Fujitsu PRIMERGY RX200S5 上でも,最大 512 コアを利用した動作実績がある.統計数理研究所のFujitsu PRIMERGY RX200S5 上では,これまでに最適解が得られていなかった MIPLIB2010のインスタンスである dg012142 に最適解を与えた.}, language = {ja} } @inproceedings{BertholdGleixner2010, author = {Berthold, Timo and Gleixner, Ambros}, title = {Undercover - a primal heuristic for MINLP based on sub-MIPs generated by set covering}, booktitle = {Proceedings of the European Workshop on Mixed Integer Nonlinear Programming, April 12-16, 2010, Marseilles, France}, editor = {Bonami, Pierre and Liberti, Leo and Miller, Andrew J. and Sartenaer, Annick}, pages = {103 -- 112}, year = {2010}, abstract = {We present Undercover, a primal heuristic for mixed-integer nonlinear programming (MINLP). The heuristic constructs a mixed-integer linear subproblem (sub-MIP) of a given MINLP by fixing a subset of the variables. We solve a set covering problem to identify a minimal set of variables which need to be fixed in order to linearise each constraint. Subsequently, these variables are fixed to approximate values, e.g. obtained from a linear outer approximation. The resulting sub-MIP is solved by a mixed-integer linear programming solver. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. Although general in nature, the heuristic seems most promising for mixed-integer quadratically constrained programmes (MIQCPs). We present computational results on a general test set of MIQCPs selected from the MINLPLib.}, language = {en} } @inproceedings{TurnerBertholdBesanconetal.2023, author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu and Koch, Thorsten}, title = {Cutting Plane Selection with Analytic Centers and Multiregression}, volume = {13884}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2023.}, publisher = {Springer}, doi = {10.1007/978-3-031-33271-5_4}, pages = {52 -- 68}, year = {2023}, abstract = {Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.}, language = {en} } @misc{TurnerBertholdBesanconetal.2022, author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu and Koch, Thorsten}, title = {Cutting Plane Selection with Analytic Centers and Multiregression}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89065}, year = {2022}, abstract = {Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.}, language = {en} } @misc{BertholdGleixner2009, author = {Berthold, Timo and Gleixner, Ambros}, title = {Undercover - a primal heuristic for MINLP based on sub-MIPs generated by set covering}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11632}, number = {09-40}, year = {2009}, abstract = {We present Undercover, a primal heuristic for mixed-integer nonlinear programming (MINLP). The heuristic constructs a mixed-integer linear subproblem (sub-MIP) of a given MINLP by fixing a subset of the variables. We solve a set covering problem to identify a minimal set of variables which need to be fixed in order to linearise each constraint. Subsequently, these variables are fixed to approximate values, e.g. obtained from a linear outer approximation. The resulting sub-MIP is solved by a mixed-integer linear programming solver. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. Although general in nature, the heuristic seems most promising for mixed-integer quadratically constrained programmes (MIQCPs). We present computational results on a general test set of MIQCPs selected from the MINLPLib.}, language = {en} } @misc{BertholdMexiSalvagnin2022, author = {Berthold, Timo and Mexi, Gioni and Salvagnin, Domenico}, title = {Using Multiple Reference Vectors and Objective Scaling in the Feasibility Pump}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-88513}, year = {2022}, abstract = {The Feasibility Pump (FP) is one of the best-known primal heuristics for mixed-integer programming (MIP): more than 15 papers suggested various modifications of all of its steps. So far, no variant considered information across multiple iterations, but all instead maintained the principle to optimize towards a single reference integer point. In this paper, we evaluate the usage of multiple reference vectors in all stages of the FP algorithm. In particular, we use LP-feasible vectors obtained during the main loop to tighten the variable domains before entering the computationally expensive enumeration stage. Moreover, we consider multiple integer reference vectors to explore further optimizing directions and introduce alternative objective scaling terms to balance the contributions of the distance functions and the original MIP objective. Our computational experiments demonstrate that the new method can improve performance on general MIP test sets. In detail, our modifications provide a 29.3\% solution quality improvement and 4.0\% running time improvement in an embedded setting, needing 16.0\% fewer iterations over a large test set of MIP instances. In addition, the method's success rate increases considerably within the first few iterations. In a standalone setting, we also observe a moderate performance improvement, which makes our version of FP suitable for the two main use-cases of the algorithm.}, language = {en} } @misc{BertholdGleixnerHeinzetal.2013, author = {Berthold, Timo and Gleixner, Ambros and Heinz, Stefan and Vigerske, Stefan}, title = {Analyzing the computational impact of MIQCP solver components}, issn = {1438-0064}, doi = {10.3934/naco.2012.2.739}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17754}, year = {2013}, abstract = {We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on a linear relaxation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.}, language = {en} } @article{KochBertholdPedersenetal.2022, author = {Koch, Thorsten and Berthold, Timo and Pedersen, Jaap and Vanaret, Charlie}, title = {Progress in mathematical programming solvers from 2001 to 2020}, volume = {10}, journal = {EURO Journal on Computational Optimization}, doi = {10.1016/j.ejco.2022.100031}, pages = {100031}, year = {2022}, abstract = {This study investigates the progress made in lp and milp solver performance during the last two decades by comparing the solver software from the beginning of the millennium with the codes available today. On average, we found out that for solving lp/milp, computer hardware got about 20 times faster, and the algorithms improved by a factor of about nine for lp and around 50 for milp, which gives a total speed-up of about 180 and 1,000 times, respectively. However, these numbers have a very high variance and they considerably underestimate the progress made on the algorithmic side: many problem instances can nowadays be solved within seconds, which the old codes are not able to solve within any reasonable time.}, language = {en} } @misc{BertholdGleixner2013, author = {Berthold, Timo and Gleixner, Ambros}, title = {Undercover Branching}, issn = {1438-0064}, doi = {10.1007/978-3-642-38527-8_20}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18030}, year = {2013}, abstract = {In this paper, we present a new branching strategy for nonconvex MINLP that aims at driving the created subproblems towards linearity. It exploits the structure of a minimum cover of an MINLP, a smallest set of variables that, when fixed, render the remaining system linear: whenever possible, branching candidates in the cover are preferred. Unlike most branching strategies for MINLP, Undercover branching is not an extension of an existing MIP branching rule. It explicitly regards the nonlinearity of the problem while branching on integer variables with a fractional relaxation solution. Undercover branching can be naturally combined with any variable-based branching rule. We present computational results on a test set of general MINLPs from MINLPLib, using the new strategy in combination with reliability branching and pseudocost branching. The computational cost of Undercover branching itself proves negligible. While it turns out that it can influence the variable selection only on a smaller set of instances, for those that are affected, significant improvements in performance are achieved.}, language = {en} } @misc{BertholdGleixnerHeinzetal.2011, author = {Berthold, Timo and Gleixner, Ambros and Heinz, Stefan and Vigerske, Stefan}, title = {On the computational impact of MIQCP solver components}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11998}, number = {11-01}, year = {2011}, abstract = {We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on linear outer approximation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.}, language = {en} } @inproceedings{TurnerBertholdBesancon2025, author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu}, title = {A Context-Aware Cutting Plane Selection Algorithm for Mixed-Integer Programming}, booktitle = {Operations Research Proceedings 2023. OR 2023.}, doi = {10.1007/978-3-031-58405-3_28}, pages = {217 -- 244}, year = {2025}, abstract = {The current cut selection algorithm used in mixed-integer programming solvers has remained largely unchanged since its creation. In this paper, we propose a set of new cut scoring measures, cut filtering techniques, and stopping criteria, extending the current state-of-the-art algorithm and obtaining a 5\\% performance improvement for SCIP over the MIPLIB 2017 benchmark set.}, language = {en} } @misc{TurnerBertholdBesanconetal.2023, author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu and Koch, Thorsten}, title = {Branching via Cutting Plane Selection: Improving Hybrid Branching}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91120}, year = {2023}, abstract = {Cutting planes and branching are two of the most important algorithms for solving mixed-integer linear programs. For both algorithms, disjunctions play an important role, being used both as branching candidates and as the foundation for some cutting planes. We relate branching decisions and cutting planes to each other through the underlying disjunctions that they are based on, with a focus on Gomory mixed-integer cuts and their corresponding split disjunctions. We show that selecting branching decisions based on quality measures of Gomory mixed-integer cuts leads to relatively small branch-and-bound trees, and that the result improves when using cuts that more accurately represent the branching decisions. Finally, we show how the history of previously computed Gomory mixed-integer cuts can be used to improve the performance of the state-of-the-art hybrid branching rule of SCIP. Our results show a 4\% decrease in solve time, and an 8\% decrease in number of nodes over affected instances of MIPLIB 2017.}, language = {en} } @misc{TurnerBertholdBesancon2023, author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu}, title = {A Context-Aware Cutting Plane Selection Algorithm for Mixed-Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91691}, year = {2023}, abstract = {The current cut selection algorithm used in mixed-integer programming solvers has remained largely unchanged since its creation. In this paper, we propose a set of new cut scoring measures, cut filtering techniques, and stopping criteria, extending the current state-of-the-art algorithm and obtaining a 5\\% performance improvement for SCIP over the MIPLIB 2017 benchmark set.}, language = {en} } @misc{ShinanoAchterbergBertholdetal.2020, author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Winkler, Michael}, title = {Solving Previously Unsolved MIP Instances with ParaSCIP on Supercomputers by using up to 80,000 Cores}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-78393}, year = {2020}, abstract = {Mixed-integer programming (MIP) problem is arguably among the hardest classes of optimization problems. This paper describes how we solved 21 previously unsolved MIP instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper, we describe the basic parallelization mechanism of ParaSCIP, improvements of the dynamic load balancing and novel techniques to exploit the power of parallelization for MIP solving. We give a detailed overview of computing times and statistics for solving open MIPLIB instances.}, language = {en} } @incollection{GamrathBertholdHeinzetal.2015, author = {Gamrath, Gerald and Berthold, Timo and Heinz, Stefan and Winkler, Michael}, title = {Structure-Based Primal Heuristics for Mixed Integer Programming}, volume = {13}, booktitle = {Optimization in the Real World}, publisher = {Springer Japan}, isbn = {978-4-431-55419-6}, doi = {10.1007/978-4-431-55420-2_3}, pages = {37 -- 53}, year = {2015}, abstract = {Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They help to reach optimality faster and provide good feasible solutions early in the solving process. In this paper, we present two new primal heuristics which take into account global structures available within MIP solvers to construct feasible solutions at the beginning of the solving process. These heuristics follow a large neighborhood search (LNS) approach and use global structures to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. The definition of the neighborhood is done by iteratively fixing variables and propagating these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. The neighborhood is solved as a sub-MIP and solutions are transferred back to the original problem. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about every third instance and therewith help to improve the average solving time.}, language = {en} } @misc{WitzigBertholdHeinz2016, author = {Witzig, Jakob and Berthold, Timo and Heinz, Stefan}, title = {Experiments with Conflict Analysis in Mixed Integer Programming}, issn = {1438-0064}, doi = {10.1007/978-3-319-59776-8_17}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61087}, year = {2016}, abstract = {The analysis of infeasible subproblems plays an import role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications obtained by domain propagation that led to infeasibility. The result of the analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept has its origin in solving satisfiability problems and is similarly used in constraint programming. The second concept is to analyze infeasible linear programming (LP) relaxations. The dual LP solution provides a set of multipliers that can be used to generate a single new globally valid linear constraint. The main contribution of this short paper is an empirical evaluation of two ways to combine both approaches. Experiments are carried out on general MIP instances from standard public test sets such as Miplib2010; the presented algorithms have been implemented within the non-commercial MIP solver SCIP. Moreover, we present a pool-based approach to manage conflicts which addresses the way a MIP solver traverses the search tree better than aging strategies known from SAT solving.}, language = {en} } @article{BertholdMexiSalvagnin2023, author = {Berthold, Timo and Mexi, Gioni and Salvagnin, Domenico}, title = {Using Multiple Reference Vectors and Objective Scaling in the Feasibility Pump}, volume = {11}, journal = {EURO Journal on Computational Optimization}, doi = {10.1016/j.ejco.2023.100066}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-87392}, year = {2023}, abstract = {The Feasibility Pump (FP) is one of the best-known primal heuristics for mixed-integer programming (MIP): more than 15 papers suggested various modifications of all of its steps. So far, no variant considered information across multiple iterations, but all instead maintained the principle to optimize towards a single reference integer point. In this paper, we evaluate the usage of multiple reference vectors in all stages of the FP algorithm. In particular, we use LP-feasible vectors obtained during the main loop to tighten the variable domains before entering the computationally expensive enumeration stage. Moreover, we consider multiple integer reference vectors to explore further optimizing directions and introduce alternative objective scaling terms to balance the contributions of the distance functions and the original MIP objective. Our computational experiments demonstrate that the new method can improve performance on general MIP test sets. In detail, our modifications provide a 29.3\% solution quality improvement and 4.0\% running time improvement in an embedded setting, needing 16.0\% fewer iterations over a large test set of MIP instances. In addition, the method's success rate increases considerably within the first few iterations. In a standalone setting, we also observe a moderate performance improvement, which makes our version of FP suitable for the two main use-cases of the algorithm.}, language = {en} } @misc{RalphsShinanoBertholdetal.2018, author = {Ralphs, Ted and Shinano, Yuji and Berthold, Timo and Koch, Thorsten}, title = {Parallel Solvers for Mixed Integer Linear Optimization}, journal = {Handbook of Parallel Constraint Reasoning}, editor = {Hamadi, Youssef}, publisher = {Springer Nature}, doi = {10.1007/978-3-319-63516-3_8}, pages = {283 -- 336}, year = {2018}, language = {en} } @misc{AchterbergBerthold2005, author = {Achterberg, Tobias and Berthold, Timo}, title = {Improving the Feasibility Pump}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8754}, number = {05-42}, year = {2005}, abstract = {The Feasibility Pump of Fischetti, Glover, Lodi, and Bertacco has proved to be a very successful heuristic for finding feasible solutions of mixed integer programs. The quality of the solutions in terms of the objective value, however, tends to be poor. This paper proposes a slight modification of the algorithm in order to find better solutions. Extensive computational results show the success of this variant: in 89 out of 121 MIP instances the modified version produces improved solutions in comparison to the original Feasibility Pump.}, language = {en} } @article{BolusaniBesanconGleixneretal.2024, author = {Bolusani, Suresh and Besan{\c{c}}on, Mathieu and Gleixner, Ambros and Berthold, Timo and D'Ambrosio, Claudia and Mu{\~n}oz, Gonzalo and Paat, Joseph and Thomopulos, Dimitri}, title = {The MIP workshop 2023 computational competition on reoptimization}, volume = {16}, journal = {Mathematical Programming Computation}, doi = {10.1007/s12532-024-00256-w}, pages = {255 -- 266}, year = {2024}, abstract = {This paper describes the computational challenge developed for a computational competition held in 2023 for the 20th anniversary of the Mixed Integer Programming Workshop. The topic of this competition was reoptimization, also known as warm starting, of mixed integer linear optimization problems after slight changes to the input data for a common formulation. The challenge was to accelerate the proof of optimality of the modified instances by leveraging the information from the solving processes of previously solved instances, all while creating high-quality primal solutions. Specifically, we discuss the competition's format, the creation of public and hidden datasets, and the evaluation criteria. Our goal is to establish a methodology for the generation of benchmark instances and an evaluation framework, along with benchmark datasets, to foster future research on reoptimization of mixed integer linear optimization problems.}, language = {en} }