### Refine

#### Year of publication

#### Document Type

- ZIB-Report (8)
- In Proceedings (4)
- Article (1)

#### Keywords

- Mixed Integer Programming (4)
- IP (2)
- MIPLIB (2)
- ParaSCIP (2)
- Ubiquity Generator Framework (2)
- branch-and-cut (2)
- mixed integer programming (2)
- Constraint Integer Programming (1)
- Distributed Memory (1)
- MIP (1)

#### Institute

Mixed integer programming (MIP) has become one of the most important techniques in Operations Research and Discrete Optimization. SCIP (Solving Constraint Integer Programs) is currently one of the fastest non-commercial MIP solvers. It is based on the branch-and-bound procedure in which the problem is recursively split into smaller subproblems, thereby creating a so-called branching tree. We present ParaSCIP, an extension of SCIP, which realizes a parallelization on a distributed memory computing environment. ParaSCIP uses SCIP solvers as independently running processes to solve subproblems (nodes of the branching tree) locally. This makes the parallelization development independent of the SCIP development. Thus, ParaSCIP directly profits from any algorithmic progress in future versions of SCIP. Using a first implementation of ParaSCIP, we were able to solve two previously unsolved instances from MIPLIB2003, a standard test set library for MIP solvers. For these computations, we used up to 2048 cores of the HLRN~II supercomputer.

制約整数計画ソルバ SCIP の並列化
(2013)

制約整数計画(CIP: Constraint Integer Programming)は，制約プログラミング(CP: Constraint Programming)，
混合整数計画(MIP: Mixed Integer Programming), 充足可能性問題(SAT: Satisfiability Problems)の研究
分野におけるモデリング技術と解法を統合している．その結果，制約整数計画は，広いクラスの最適化問題を
扱うことができる．SCIP (Solving Constraint Integer Programs)は，CIPを解くソルバとして実装され,
Zuse Institute Berlin (ZIB)の研究者を中心として継続的に拡張が続けられている．本論文では，
著者らによって開発されたSCIP に対する2種類の並列化拡張を紹介する．
一つは，複数計算ノード間で大規模に並列動作するParaSCIP である．
もう一つは，複数コアと共有メモリを持つ１台の計算機上で(スレッド)並列で動作するFiberSCIP である．
ParaSCIP は，HLRN IIスーパーコンピュータ上で，
一つのインスタンスを解くために最大7,168 コアを利用した動作実績がある．また，
統計数理研究所のFujitsu PRIMERGY RX200S5上でも，最大512コアを利用した動作実績がある．
統計数理研究所のFujitsu PRIMERGY RX200S5上 では，これまでに最適解が得られていなかった
MIPLIB2010のインスタンスであるdg012142に最適解を与えた．

This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques for solving satisfiability problems. SCIP is available in source code and free for noncommercial use. We demonstrate the usefulness of CIP on three tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we demonstrate how to use CIP techniques to compute the number of optimal solutions of integer programs. Third, we employ the CIP framework to solve chip design verification problems, which involve some highly nonlinear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the nonlinear constraints by employing constraint programming techniques.

In the recent years there has been tremendous progress in the development of algorithms to find optimal solutions for integer programs. In many applications it is, however, desirable (or even necessary) to generate all feasible solutions. Examples arise in the areas of hardware and software verification and discrete geometry. In this paper, we investigate how to extend branch-and-cut integer programming frameworks to support the generation of all solutions. We propose a method to detect so-called unrestricted subtrees, which allows us to prune the integer program search tree and to collect several solutions simultaneously. We present computational results of this branch-and-count paradigm which show the potential of the unrestricted subtree detection.

Contemporary supercomputers can easily provide years of
CPU time per wall-clock hour. One challenge of today's software
development is how to harness this wast computing power in order to solve
really hard mixed integer programming instances. In 2010, two out of
six open MIPLIB2003 instances could be solved by ParaSCIP in more than
ten consecutive runs, restarting from checkpointing files.
The contribution of this paper is threefold:
For the first time, we present computational results of single runs for
those two instances. Secondly, we provide new improved upper and lower
bounds for all of the remaining four open MIPLIB2003 instances.
Finally, we explain which new developments led to these results and
discuss the current progress of ParaSCIP. Experiments were conducted on
HLRNII, on HLRN III, and on the Titan supercomputer, using up to 35,200 cores.

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.