MIPLIB 2010
(2011)
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.
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.
制約整数計画ソルバ SCIP の並列化
(2013)
制約整数計画(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 に最適解を与えた.
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.
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.
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.
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.