TY - JOUR A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Vigerske, Stefan A1 - Winkler, Michael T1 - 制約整数計画ソルバ SCIP の並列化 JF - 統計数理 N2 - 制約整数計画(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 に最適解を与えた. N2 - The paradigm of constraint integer programming (CIP) combines modeling and solving techniques from the fields of constraint programming (CP), mixed-integer programming (MIP) and satisfability problem (SAT). This paradigm allows us to address a wide range of optimization problems. SCIP is an implementation of the idea of CIP and is now being continuously extended by a group of researchers centered at Zuse Institute Berlin (ZIB). This paper introduces two parallel extensions of SCIP. One is ParaSCIP, which is intended to run on a large scale distributed memory computing environment, and the other is FiberSCIP, intended to run on a shared memory computing environment. ParaSCIP has been run successfully on the HLRN II supercomputer utilizing up to 7,168 cores to solve a single difficult MIP. It has also been tested on an ISM supercomputer (Fujitsu PRIMERGY RX200S5 using up to 512 cores). The previously unsolved instance dg012142 from MIPLIB2010 was solved by using the ISM supercomputer. Y1 - 2013 UR - https://www.ism.ac.jp/editsec/toukei/pdf/61-1-047.pdf VL - 61 IS - 1 SP - 47 EP - 78 ER - TY - JOUR A1 - Berthold, Timo A1 - Mexi, Gioni A1 - Salvagnin, Domenico T1 - Using Multiple Reference Vectors and Objective Scaling in the Feasibility Pump JF - EURO Journal on Computational Optimization N2 - 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. Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-87392 VL - 11 ER - TY - JOUR A1 - Berthold, Timo A1 - Gleixner, Ambros T1 - Undercover: a primal MINLP heuristic exploring a largest sub-MIP JF - Mathematical Programming N2 - We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib. It turns out that the majority of these instances allow for small covers. Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers. Y1 - 2014 U6 - https://doi.org/10.1007/s10107-013-0635-2 VL - 144 IS - 1-2 SP - 315 EP - 346 ER - TY - JOUR A1 - Gleixner, Ambros A1 - Berthold, Timo A1 - Müller, Benjamin A1 - Weltge, Stefan T1 - Three Enhancements for Optimization-Based Bound Tightening JF - Journal of Global Optimization N2 - Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efficient implementation of OBBT. Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs. We conduct extensive computational experiments on MINLPLib2. Our results indicate that OBBT is most beneficial on hard instances, for which we observe a speedup of 17% to 19% on average. Most importantly, more instances can be solved when using OBBT. Y1 - 2017 U6 - https://doi.org/10.1007/s10898-016-0450-4 VL - 67 IS - 4 SP - 731 EP - 757 ER - TY - JOUR A1 - Csizmadia, Zsolt A1 - Berthold, Timo T1 - The confined primal integral: a measure to benchmark heuristic MINLP solvers against global MINLP solvers JF - Mathematical Programming N2 - It is a challenging task to fairly compare local solvers and heuristics against each other and against global solvers. How does one weigh a faster termination time against a better quality of the found solution? In this paper, we introduce the confined primal integral, a new performance measure that rewards a balance of speed and solution quality. It emphasizes the early part of the solution process by using an exponential decay. Thereby, it avoids that the order of solvers can be inverted by choosing an arbitrarily large time limit. We provide a closed analytic formula to compute the confined primal integral a posteriori and an incremental update formula to compute it during the run of an algorithm. For the latter, we show that we can drop one of the main assumptions of the primal integral, namely the knowledge of a fixed reference solution to compare against. Furthermore, we prove that the confined primal integral is a transitive measure when comparing local solves with different final solution values. Finally, we present a computational experiment where we compare a local MINLP solver that uses certain classes of cutting planes against a solver that does not. Both versions show very different tendencies w.r.t. average running time and solution quality, and we use the confined primal integral to argue which of the two is the preferred setting. Y1 - 2020 U6 - https://doi.org/10.1007/s10107-020-01547-5 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 - 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 - JOUR A1 - Koch, Thorsten A1 - Berthold, Timo A1 - Pedersen, Jaap A1 - Vanaret, Charlie T1 - Progress in mathematical programming solvers from 2001 to 2020 JF - EURO Journal on Computational Optimization N2 - 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. Y1 - 2022 U6 - https://doi.org/10.1016/j.ejco.2022.100031 VL - 10 SP - 100031 ER - TY - JOUR A1 - Shinano, Yuji A1 - Berthold, Timo A1 - Heinz, Stefan T1 - ParaXpress: An Experimental Extension of the FICO Xpress-Optimizer to Solve Hard MIPs on Supercomputers JF - Optimization Methods & Software N2 - The Ubiquity Generator (UG) is a general framework for the external parallelization of mixed integer programming (MIP) solvers. In this paper, we present ParaXpress, a distributed memory parallelization of the powerful commercial MIP solver FICO Xpress. Besides sheer performance, an important feature of Xpress is that it provides an internal parallelization for shared memory systems. When aiming for a best possible performance of ParaXpress on a supercomputer, the question arises how to balance the internal Xpress parallelization and the external parallelization by UG against each other. We provide computational experiments to address this question and we show computational results for running ParaXpress on a Top500 supercomputer, using up to 43,344 cores in parallel. Y1 - 2018 U6 - https://doi.org/10.1080/10556788.2018.1428602 VL - 33 IS - 3 SP - 530 EP - 539 ER - TY - JOUR A1 - Berthold, Timo A1 - Farmer, James A1 - Heinz, Stefan A1 - Perregaard, Michael T1 - Parallelization of the FICO Xpress Optimizer JF - Optimization Methods and Software N2 - Computing hardware has mostly thrashed out the physical limits for speeding up individual computing cores. Consequently, the main line of progress for new hardware is growing the number of computing cores within a single CPU. This makes the study of efficient parallelization schemes for computation-intensive algorithms more and more important. A natural precondition to achieving reasonable speedups from parallelization is maintaining a high workload of the available computational resources. At the same time, reproducibility and reliability are key requirements for software that is used in industrial applications. In this paper, we present the new parallelization concept for the state-of-the-art MIP solver FICO Xpress-Optimizer. MIP solvers like Xpress are expected to be deterministic. This inevitably results in synchronization latencies which render the goal of a satisfying workload a challenge in itself. We address this challenge by following a partial information approach and separating the concepts of simultaneous tasks and independent threads from each other. Our computational results indicate that this leads to a much higher CPU workload and thereby to an improved, almost linear, scaling on modern high-performance CPUs. As an added value, the solution path that Xpress takes is not only deterministic in a fixed environment, but also, to a certain extent, thread-independent. This paper is an extended version of Berthold et al. [Parallelization of the FICO Xpress-Optimizer, in Mathematical Software – ICMS 2016: 5th International Conference, G.-M. Greuel, T. Koch, P. Paule, and A. Sommere, eds., Springer International Publishing, Berlin, 2016, pp. 251–258] containing more detailed technical descriptions, illustrative examples and updated computational results. Y1 - 2018 U6 - https://doi.org/10.1080/10556788.2017.1333612 VL - 33 IS - 3 SP - 518 EP - 529 ER -