### Refine

#### Year of publication

#### Document Type

- ZIB-Report (19)
- In Proceedings (10)
- Article (6)
- Book chapter (1)

#### Keywords

#### 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.

Given the steady increase in cores per CPU, it is only a matter of time
until supercomputers will have a million or more cores. In this article, we
investigate the opportunities and challenges that will arise when trying to
utilize this vast computing power to solve a single integer linear optimization
problem. We also raise the question of whether best practices in sequential
solution of ILPs will be eﬀective in massively parallel environments.

この論文ではソフトウェア・パッケージSCIP Optimization Suite を紹介し，その３つの構成要素：モデリン
グ言語Zimpl, 線形計画（LP: linear programming) ソルバSoPlex, そして，制約整数計画(CIP: constraint
integer programming) に対するソフトウェア・フレームワークSCIP, について述べる．本論文では，この３つの
構成要素を利用して，どのようにして挑戦的な混合整数線形計画問題(MIP: mixed integer linear optimization
problems) や混合整数非線形計画問題(MINLP: mixed integer nonlinear optimization problems) をモデル化
し解くのかを説明する．SCIP は，現在，最も高速なMIP,MINLP ソルバの１つである．いくつかの例により，
Zimpl, SCIP, SoPlex の利用方法を示すとともに，利用可能なインタフェースの概要を示す．最後に，将来の開
発計画の概要について述べる．

This paper introduces the SCIP Optimization Suite and discusses the capabilities of its three components: the modeling language Zimpl, the linear programming solver SoPlex, and the constraint integer programming framework SCIP. We explain how these can be used in concert to model and solve challenging mixed integer linear and nonlinear optimization problems. SCIP is currently one of the fastest non-commercial MIP and MINLP solvers. We demonstrate the usage of Zimpl, SCIP, and SoPlex by selected examples, we give an overview of available interfaces, and outline plans for future development.

To attain the highest performance of energy supply systems, it is necessary to
rationally determine types, capacities, and numbers of equipment in consideration of
their operational strategies corresponding to seasonal and hourly variations in energy
demands. In the combinatorial optimization method based on the mixed-integer linear
programming (MILP), integer variables are used to express the selection, numbers, and
on/off status of operation of equipment, and the number of these variables increases
with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. In this paper, a MILP method utilizing the
hierarchical relationship between design and operation variables is proposed to solve the optimal design problem of energy supply systems efficiently: At the upper level, the
optimal values of design variables are searched by the branch and bound method; At
the lower level, the values of operation variables are optimized independently at each period by the branch and bound method under the values of design variables given
tentatively during the search at the upper level; Lower bounds for the optimal value of the objective function are evaluated, and are utilized for the bounding operations at both the levels. This method is implemented into open and commercial MILP solvers. Illustrative and practical case studies on the optimal design of cogeneration systems are conducted, and the validity and effectiveness of the proposed method are clarified.

The purpose of this work is to improve the throughput of step-and-scan lithography equipment to shorten the production time of a wafer. For this purpose, we propose a method for solving the MSOP (Movement Sequence Optimization Problem), which is the problem of computing the fastest schedule for visiting all shots on a wafer. It is well-known that the MSOP on step-and-repeat lithography equipment can be modeled as a traveling salesman problem. In contrast to step-and-repeat lithography equipment, a schedule for step-and-scan lithography equipment must also indicate the scanning direction of each shot, in addition to the sequence of the shots. For this reason, the traveling salesman problem formulation for step-and-repeat lithography equipment cannot be applied to solve the MSOP on step-and-scan lithography equipment directly. We overcame this difficulty by introducing auxiliary vertices to model the scanning directions in the traveling salesman problem formulation. By this method, we were able to compute exact optimal sequences considering the scanning directions of shots for several MSOP instances. Our numerical experiments demonstrated that our proposed method was capable of computing exact optimal solutions for real-world MSOP instances having up to 232 shots on a wafer. These optimal solutions gave a 0.25% to 4.66% improvement in productivity over solutions computed by previously known methods.