Achterberg, Tobias
Refine
Year of publication
Document Type
- ZIB-Report (23)
- In Proceedings (9)
- Article (8)
- Doctoral Thesis (2)
- Book chapter (1)
- Other (1)
Keywords
- mixed integer programming (8)
- Mixed Integer Programming (7)
- Constraint Programming (3)
- Ganzzahlige Programmierung (3)
- IP (3)
- MIP (3)
- SAT (3)
- branch-and-cut (3)
- chip verification (3)
- constraint programming (3)
- integer programming (3)
- Branch-and-Bound (2)
- Chip-Verifikation (2)
- Constraint Programmierung (2)
- Integer Programming (2)
- MIPLIB (2)
- Mathematical Programming (2)
- ParaSCIP (2)
- Ubiquity Generator Framework (2)
- branch-and-bound (2)
- optimization software (2)
- scip (2)
- Algebraic Modelling Languages (1)
- Branch-And-Cut (1)
- Branching Rules (1)
- CP (1)
- CPAIOR (1)
- Chip Verification (1)
- Chipverifikation (1)
- Constraint Integer Programming (1)
- Distributed Memory (1)
- Eigenschaftsprüfer (1)
- Gurobi (1)
- IST-20 (1)
- Instances (1)
- Late Breaking Abstracts (1)
- MIP-Solver (1)
- MIPLIB2003 (1)
- MOMENTUM (1)
- Mathematische Programmierung (1)
- Mixed Integer Programming, Parallel processing, Node merging, Racing, ParaSCIP, Ubiquity Generator Framework, MIPLIB (1)
- Mixed-integer-programming (1)
- Modelling (1)
- Node merging (1)
- Optimierungssoftware (1)
- Optimization (1)
- Parallel Computing (1)
- Parallel processing (1)
- Problem Instances (1)
- Pseudocost Branching (1)
- Pseudocost-Branching (1)
- Racing ParaSCIP (1)
- Reliability-Branching (1)
- Strong-Branching (1)
- Supercomputer (1)
- Teaching (1)
- UMTS (1)
- Variable selection (1)
- Zählen (1)
- branch and cut (1)
- configuration (1)
- conflict analysis (1)
- constraint integer programming (1)
- counting (1)
- cplex (1)
- cut-based inequalities (1)
- domain propagation (1)
- feasibility pump (1)
- formal chip verification (1)
- formale Chip Verifikation (1)
- ganzzahlige Programme (1)
- massive parallization (1)
- mathematical model (1)
- micro chip (1)
- network detection (1)
- network planning (1)
- perfect power control (1)
- presolving (1)
- primal heuristic (1)
- primal heuristics (1)
- property checking (1)
- radio interface (1)
Institute
Hybrid Branching
(2009)
制約整数計画ソルバ 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 である. もう一つは,複数コアと共有メモリを持つ1台の計算機上で(スレッド)並列で動作するFiberSCIP である. ParaSCIP は,HLRN IIスーパーコンピュータ上で, 一つのインスタンスを解くために最大7,168 コアを利用した動作実績がある.また,統計数理研究所のFujitsu PRIMERGY RX200S5上でも,最大512コアを利用した動作実績がある.統計数理研究所のFujitsu PRIMERGY RX200S5上 では,これまでに最適解が得られていなかったMIPLIB2010のインスタンスであるdg012142に最適解を与えた.
Primal heuristics are an important component of state-of-the-art codes for
mixed integer programming. In this paper, we focus on primal heuristics
that only employ computationally inexpensive procedures such as rounding
and logical deductions (propagation). We give an overview of eight
different approaches. To assess the impact of these primal heuristics on
the ability to find feasible solutions, in particular early during search,
we introduce a new performance measure, the primal integral. Computational
experiments evaluate this and other measures on MIPLIB~2010 benchmark
instances.
As part of the CPAIOR 2011 a call was made for late breaking abstracts for
presentation at the conference. These abstracts were meant to represent
work in process, recent work, or work appearing in other academic areas but
of interest to the CPAIOR community. A total of 19 submissions were
received of which 16 were selected by the program chairs for
presentation. This document is a compilation of the presented abstracts.
MIPLIB 2010
(2010)
This paper reports on the fifth version of the Mixed Integer Programming Library.
The MIPLIB 2010 is the first MIPLIB release that has been assembled by a large group from academia and from industry, all of whom work in integer programming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups.
This includes the main benchmark test set of 87 instances, which
are all solvable by today's codes, and also the challenge test set with 164 instances, many of which are currently unsolved.
For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to
test the accuracy of provided solutions using exact arithmetic.
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 a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity-flow formulations. We identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of SCIP and CPLEX. We make use of the complemented mixed integer rounding framework (cMIR) but provide a special purpose aggregation heuristic that exploits the network structure. Our separation scheme speeds-up the computation for a large set of MIPs coming from network design problems by a factor of two on average.
This thesis introduces the novel paradigm of "constraint integer programming" (CIP), which integrates constraint programming (CP) and mixed integer programming (MIP) modeling and solving techniques. It is supplemented by the software SCIP, which is a solver and framework for constraint integer programming that also features SAT solving techniques. SCIP is freely available in source code for academic and non-commercial purposes. Our constraint integer programming approach is a generalization of MIP that allows for the inclusion of arbitrary constraints, as long as they turn into linear constraints on the continuous variables after all integer variables have been fixed. The constraints, may they be linear or more complex, are treated by any combination of CP and MIP techniques: the propagation of the domains by constraint specific algorithms, the generation of a linear relaxation and its solving by LP methods, and the strengthening of the LP by cutting plane separation. The current version of SCIP comes with all of the necessary components to solve mixed integer programs. In the thesis, we cover most of these ingredients and present extensive computational results to compare different variants for the individual building blocks of a MIP solver. We focus on the algorithms and their impact on the overall performance of the solver. In addition to mixed integer programming, the thesis deals with chip design verification, which is an important topic of electronic design automation. Chip manufacturers have to make sure that the logic design of a circuit conforms to the specification of the chip. Otherwise, the chip would show an erroneous behavior that may cause failures in the device where it is employed. An important subproblem of chip design verification is the property checking problem, which is to verify whether a circuit satisfies a specified property. We show how this problem can be modeled as constraint integer program and provide a number of problem-specific algorithms that exploit the structure of the individual constraints and the circuit as a whole. Another set of extensive computational benchmarks compares our CIP approach to the current state-of-the-art SAT methodology and documents the success of our method.