Refine
Year of publication
Document Type
- ZIB-Report (52)
- In Proceedings (28)
- Article (21)
- In Collection (4)
- Master's Thesis (2)
- Book chapter (1)
- Doctoral Thesis (1)
Keywords
- mixed integer programming (14)
- mixed-integer programming (6)
- primal heuristic (6)
- branch-and-cut (5)
- constraint integer programming (5)
- Ganzzahlige Programmierung (4)
- Large Neighborhood Search (4)
- Mixed Integer Programming (4)
- Primal Heuristic (4)
- domain propagation (4)
- integer programming (4)
- large neighborhood search (4)
- optimization software (4)
- primal heuristics (4)
- MINLP (3)
- MIP (3)
- MIQCP (3)
- Pseudo-Boolean (3)
- branch-and-bound (3)
- branching rule (3)
- conflict analysis (3)
- constraint programming (3)
- nonconvex (3)
- Branch-And-Cut (2)
- Constraint Programming (2)
- Gemischt-Ganzzahlige Programmierung (2)
- MIPLIB (2)
- Mixed-Integer Nonlinear Programming (2)
- Nachbarschaftssuche (2)
- Optimierungssoftware (2)
- ParaSCIP (2)
- Primalheuristik (2)
- Primalheuristiken (2)
- Ubiquity Generator Framework (2)
- chip verification (2)
- cumulative constraint (2)
- cutting plane selection (2)
- dual degeneracy (2)
- mixed integer nonlinear programming (2)
- mixed-integer quadratically constrained programming (2)
- search strategy (2)
- Branch and Cut (1)
- Chipverifikation (1)
- Constraint Integer Programming (1)
- Constraintprogrammierung (1)
- Distributed Memory (1)
- Feasibility Pump (1)
- Graphenisomorphie (1)
- IP (1)
- Konfliktanalyse (1)
- LP, MIP, CIP, MINLP, modeling, optimization, SCIP, SoPlex, Zimpl (1)
- MIPLIB2003 (1)
- Mengenüberdeckung (1)
- Mixed Integer Nonlinear Programming (1)
- Mixed Integer Programming, Parallel processing, Node merging, Racing, ParaSCIP, Ubiquity Generator Framework, MIPLIB (1)
- Mixed-Integer Quadratically Constrained Programming (1)
- Mixed-Integer Quadratically Constrained Programming (1)
- Mixed-Intger Programming (1)
- Newton barrier method (1)
- Node merging (1)
- Nonconvex Optimization (1)
- OBBT (1)
- Orbitope (1)
- Parallel Computing (1)
- Parallel processing (1)
- Problem Instances (1)
- Racing ParaSCIP (1)
- SCIP (1)
- SCIP, MIP, MINLP, CIP, LP, modeling, optimization (1)
- Supercomputer (1)
- Symmetrie-Brechung (1)
- Symmetrie-Erkennung (1)
- adaptive search behavior (1)
- analytic center (1)
- anlalytic center (1)
- bound tightening (1)
- branch and cut (1)
- computational (1)
- conflict learning (1)
- convex relaxation (1)
- cut selection (1)
- dual proof analysis (1)
- energetic reasoning (1)
- feasibility pump (1)
- fix-and-propagate (1)
- gas transport optimization (1)
- global optimization (1)
- graph ismorphism (1)
- interior point algorithm (1)
- linear relaxation (1)
- massive parallization (1)
- mixed integer quadratically constrained programming (1)
- mixed-integer nonlinear programming (1)
- mixed-integer programming, branch-and-bound, branching rule, strong branching (1)
- mixed-integer programming, large neighborhood search, primal heuristics, domain propagation (1)
- no-good learning (1)
- optimality prediction (1)
- optimality-based bound tightening (1)
- optimization-based bound tightening (1)
- orbitopes (1)
- parallel computing (1)
- performance measure (1)
- propagation (1)
- resource-constrained project Scheduling (1)
- resource-constrained project scheduling (1)
- rounding (1)
- scheduling (1)
- separation algorithm (1)
- set covering (1)
- solution learning (1)
- solver software (1)
- supercomputing (1)
- symmetry breaking (1)
- symmetry detection (1)
- variable selection (1)
Cutting planes and branching are two of the most important algorithms for solving mixed-integer linear programs. For both algorithms, disjunctions play an important role, being used both as branching candidates and as the foundation for some cutting planes. We relate branching decisions and cutting planes to each other through the underlying disjunctions that they are based on, with a focus on Gomory mixed-integer cuts and their corresponding split disjunctions. We show that selecting branching decisions based on quality measures of Gomory mixed-integer cuts leads to relatively small branch-and-bound trees, and that the result improves when using cuts that more accurately represent the branching decisions. Finally, we show how the history of previously computed Gomory mixed-integer cuts can be used to improve the performance of the state-of-the-art hybrid branching rule of SCIP. Our results show a $4\%$ decrease in solve time, and an $8\%$ decrease in number of nodes over affected instances of MIPLIB 2017.
Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.
The current cut selection algorithm used in mixed-integer programming solvers has remained largely unchanged since its creation. In this paper, we propose a set of new cut scoring measures, cut filtering techniques, and stopping criteria, extending the current state-of-the-art algorithm and obtaining a 5\% performance improvement for SCIP over the MIPLIB 2017 benchmark set.
The current cut selection algorithm used in mixed-integer programming solvers has remained largely unchanged since its creation. In this paper, we propose a set of new cut scoring measures, cut filtering techniques, and stopping criteria, extending the current state-of-the-art algorithm and obtaining a 5\% performance improvement for SCIP over the MIPLIB 2017 benchmark set.
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.
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.
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.
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.