@incollection{GamrathBertholdHeinzetal., author = {Gamrath, Gerald and Berthold, Timo and Heinz, Stefan and Winkler, Michael}, title = {Structure-Based Primal Heuristics for Mixed Integer Programming}, series = {Optimization in the Real World}, 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}, 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} } @article{GamrathBertholdHeinzetal., author = {Gamrath, Gerald and Berthold, Timo and Heinz, Stefan and Winkler, Michael}, title = {Structure-driven fix-and-propagate heuristics for mixed integer programming}, series = {Mathematical Programming Computation}, volume = {11}, journal = {Mathematical Programming Computation}, number = {4}, publisher = {Springer}, address = {Berlin Heidelberg}, doi = {10.1007/s12532-019-00159-1}, pages = {675 -- 702}, abstract = {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.}, language = {en} } @article{HeinzSchlechteStephanetal., author = {Heinz, Stefan and Schlechte, Thomas and Stephan, R{\"u}diger and Winkler, Michael}, title = {Solving steel mill slab design problems}, series = {Constraints}, volume = {17}, journal = {Constraints}, number = {1}, doi = {10.1007/s10601-011-9113-8}, pages = {39 -- 50}, abstract = {The steel mill slab design problem from the CSPLIB is a combinatorial optimization problem motivated by an application of the steel industry. It has been widely studied in the constraint programming community. Several methods were proposed to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called the multiple knapsack problem with color constraints, originated from the same industrial problem, was discussed in the integer programming community. In particular, a simple integer program for this problem has been given by Forrest et al. (INFORMS J Comput 18:129-134, 2006). The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. (INFORMS J Comput 18:129-134, 2006) for the steel mill slab design problem. Using this model and a state-of-the-art integer program solver all instances of the steel mill slab library can be solved efficiently to optimality. We improved, thereby, the solution values of 76 instances compared to previous results (Schaus et al., Constraints 16:125-147, 2010). Finally, we consider a recently introduced variant of the steel mill slab design problem, where within all solutions which minimize the leftover one is interested in a solution which requires a minimum number of slabs. For that variant we introduce two approaches and solve all instances of the steel mill slab library with this slightly changed objective function to optimality.}, language = {en} } @article{ShinanoAchterbergBertholdetal., author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Vigerske, Stefan and Winkler, Michael}, title = {制約整数計画ソルバ SCIP の並列化}, series = {統計数理}, volume = {61}, journal = {統計数理}, number = {1}, pages = {47 -- 78}, 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{ShinanoAchterbergBertholdetal., author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Winkler, Michael}, title = {Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores}, series = {Proc. of 30th IEEE International Parallel \& Distributed Processing Symposium}, booktitle = {Proc. of 30th IEEE International Parallel \& Distributed Processing Symposium}, doi = {10.1109/IPDPS.2016.56}, abstract = {This paper describes how we solved 12 previously unsolved mixed-integer program- ming (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} } @inproceedings{ShinanoAchterbergBertholdetal., author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Winkler, Michael}, title = {Solving Hard MIPLIP2003 Problems with ParaSCIP on Supercomputers: An Update}, series = {IPDPSW'14 Proceedings of the 2014 IEEE, International Parallel \& Distributed Processing Symposium Workshops}, booktitle = {IPDPSW'14 Proceedings of the 2014 IEEE, International Parallel \& Distributed Processing Symposium Workshops}, editor = {IEEE,}, publisher = {IEEE Computer Society}, address = {Washington, DC, USA}, isbn = {978-1-4799-4117-9}, doi = {10.1109/IPDPSW.2014.174}, pages = {1552 -- 1561}, language = {en} } @article{ShinanoHeinzVigerskeetal., author = {Shinano, Yuji and Heinz, Stefan and Vigerske, Stefan and Winkler, Michael}, title = {FiberSCIP - A shared memory parallelization of SCIP}, series = {INFORMS Journal on Computing}, volume = {30}, journal = {INFORMS Journal on Computing}, number = {1}, doi = {10.1287/ijoc.2017.0762}, pages = {11 -- 30}, abstract = {Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a mixed-integer linear programming solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, we present the basic concept of having two parallel extensions, and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator), including an implementation of deterministic parallelization. Second, we discuss the difficulties in achieving a good performance that utilizes all resources on an actual computing environment, and the difficulties of performance evaluation of the parallel solvers. Third, we present a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions. Finally, we demonstrate the current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer nonlinear programs (MINLPs) in parallel.}, language = {en} } @inproceedings{TurnerChmielaKochetal., author = {Turner, Mark and Chmiela, Antonia and Koch, Thorsten and Winkler, Michael}, title = {PySCIPOpt-ML: Embedding Trained Machine Learning Models into Mixed-Integer Programs}, abstract = {A standard tool for modelling real-world optimisation problems is mixed-integer programming (MIP). However, for many of these problems there is either incomplete information describing variable relations, or the relations between variables are highly complex. To overcome both these hurdles, machine learning (ML) models are often used and embedded in the MIP as surrogate models to represent these relations. Due to the large amount of available ML frameworks, formulating ML models into MIPs is highly non-trivial. In this paper we propose a tool for the automatic MIP formulation of trained ML models, allowing easy integration of ML constraints into MIPs. In addition, we introduce a library of MIP instances with embedded ML constraints. The project is available at https://github.com/Opt-Mucca/PySCIPOpt-ML.}, language = {en} } @article{TurnerKochSerranoetal., author = {Turner, Mark and Koch, Thorsten and Serrano, Felipe and Winkler, Michael}, title = {Adaptive Cut Selection in Mixed-Integer Linear Programming}, series = {Open Journal of Mathematical Optimization}, volume = {4}, journal = {Open Journal of Mathematical Optimization}, doi = {10.5802/ojmo.25}, pages = {5}, abstract = {Cutting plane selection is a subroutine used in all modern mixed-integer linear programming solvers with the goal of selecting a subset of generated cuts that induce optimal solver performance. These solvers have millions of parameter combinations, and so are excellent candidates for parameter tuning. Cut selection scoring rules are usually weighted sums of different measurements, where the weights are parameters. We present a parametric family of mixed-integer linear programs together with infinitely many family-wide valid cuts. Some of these cuts can induce integer optimal solutions directly after being applied, while others fail to do so even if an infinite amount are applied. We show for a specific cut selection rule, that any finite grid search of the parameter space will always miss all parameter values, which select integer optimal inducing cuts in an infinite amount of our problems. We propose a variation on the design of existing graph convolutional neural networks, adapting them to learn cut selection rule parameters. We present a reinforcement learning framework for selecting cuts, and train our design using said framework over MIPLIB 2017 and a neural network verification data set. Our framework and design show that adaptive cut selection does substantially improve performance over a diverse set of instances, but that finding a single function describing such a rule is difficult. Code for reproducing all experiments is available at https://github.com/Opt-Mucca/Adaptive-Cutsel-MILP.}, language = {en} }