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
The reformulation-linearization technique (RLT) is a prominent approach to constructing tight linear relaxations of non-convex continuous and mixed-integer optimization problems. The goal of this paper is to extend the applicability and improve the performance of RLT for bilinear product relations. First, a method for detecting bilinear product relations implicitly contained in mixed-integer linear programs is developed based on analyzing linear constraints with binary variables, thus enabling the application of bilinear RLT to a new class of problems. Our second contribution addresses the high computational cost of RLT cut separation, which presents one of the major difficulties in applying RLT efficiently in practice. We propose a new RLT cutting plane separation algorithm which identifies combinations of linear constraints and bound factors that are expected to yield an inequality that is violated by the current relaxation solution. A detailed computational study based on implementations in two solvers evaluates the performance impact of the proposed methods.
Mixed-integer programming (MIP) problem is arguably among the hardest classes of optimization problems. This paper describes how we solved 21 previously unsolved 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.
We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of over 5,000 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, the compilation of these sets was done using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encoded requirements on diversity and balancedness with respect to instance features and performance data.
Mixed integer programming has become a very powerful tool for modeling and
solving real-world planning and scheduling problems, with the breadth of
applications appearing to be almost unlimited. A critical component in
the solution of these mixed-integer programs is a set of routines commonly
referred to as presolve. Presolve can be viewed as a collection of
preprocessing techniques that reduce the size of and, more importantly,
improve the ``strength'' of the given model formulation, that is, the degree
to which the constraints of the formulation accurately describe the
underlying polyhedron of integer-feasible solutions. As our computational
results will show, presolve is a key factor in the speed with which we can
solve mixed-integer programs, and is often the difference between a model
being intractable and solvable, in some cases easily solvable. In this
paper we describe the presolve functionality in the Gurobi commercial
mixed-integer programming code.
This includes an overview, or taxonomy of the different methods that are
employed, as well as more-detailed descriptions of several of the techniques,
with some of them appearing, to our knowledge, for the first time in the
literature.
Mixed integer programming has become a very powerful tool for modeling and
solving real-world planning and scheduling problems, with the breadth of
applications appearing to be almost unlimited. A critical component in
the solution of these mixed-integer programs is a set of routines commonly
referred to as presolve. Presolve can be viewed as a collection of
preprocessing techniques that reduce the size of and, more importantly,
improve the ``strength'' of the given model formulation, that is, the degree
to which the constraints of the formulation accurately describe the
underlying polyhedron of integer-feasible solutions. As our computational
results will show, presolve is a key factor in the speed with which we can
solve mixed-integer programs, and is often the difference between a model
being intractable and solvable, in some cases easily solvable. In this
paper we describe the presolve functionality in the Gurobi commercial
mixed-integer programming code.
This includes an overview, or taxonomy of the different methods that are
employed, as well as more-detailed descriptions of several of the techniques,
with some of them appearing, to our knowledge, for the first time in the
literature.
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.
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.
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.
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.