ZIB-Report
Refine
Year of publication
- 2017 (14) (remove)
Document Type
- ZIB-Report (14)
Language
- English (14)
Has Fulltext
- yes (14) (remove)
Is part of the Bibliography
- no (14)
Keywords
Institute
- Mathematical Optimization Methods (14) (remove)
17-69
The analysis of infeasibility plays an important role in solving satisfiability problems (SAT) and mixed integer programs (MIPs). In mixed integer programming, this procedure is called conflict analysis. So far, modern MIP solvers use conflict analysis only for propagation and improving the dual bound, i.e., fathoming nodes that cannot contain feasible solutions. In this short paper, we present a new approach which uses conflict information to improve the primal bound during a MIP solve. To derive new improving primal solutions we use a conflict driven diving heuristic called conflict diving that uses the information obtained by conflict analysis. Conflict diving pursues a twofold strategy. By using conflict information the new diving approach is guided into parts of the search space that are usually not explored by other diving heuristics. At the same time, conflict diving has a fail-fast-strategy to reduce the time spent if it cannot find a new primal solution. As a byproduct, additional valid conflict constraints can be derived, from which a MIP solver can gain benefit to improve the dual bound as well. To show the added-value of conflict diving within a MIP solver, conflict diving has been implemented within the non-commercial MIP solver SCIP. Experiments are carried out on general MIP instances from standard public test sets, like MIPLIB2010 or Cor@l.
17-40
We consider the problem of pattern detection in large scale
railway timetables. This problem arises in rolling stock optimization planning
in order to identify invariant sections of the timetable for
which a cyclic rotation plan is adequate.
We propose a dual reduction technique which leads to an decomposition
and enumeration method. Computational results for real
world instances demonstrate that the method is able to
produce optimal solutions as fast as standard MIP solvers.
17-45
Borne out of a surprising variety of practical applications, the maximum-weight connected subgraph problem has attracted considerable interest during the past years. This interest has not only led to notable research on theoretical properties, but has also brought about several (exact) solvers-with steadily increasing performance. Continuing along this path, the following article introduces several new algorithms such as reduction techniques and heuristics and describes their integration into an exact solver.
The new methods are evaluated with respect to both their theoretical and practical properties. Notably, the new exact framework allows to solve common problem instances from the literature faster than all previous approaches. Moreover, one large-scale benchmark instance from the 11th DIMACS Challenge can be solved for the first time to optimality and the primal-dual gap for two other ones can be significantly reduced.
17-57
Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems
(2017)
This article introduces new preprocessing techniques for the Steiner tree problem in graphs and one of its most popular relatives, the maximum-weight connected subgraph problem. Several of the techniques generalize previous results from the literature. The correctness of the new methods is shown, but also their NP-hardness is demonstrated. Despite this pessimistic worst-case complexity, several relaxations are discussed that are expected to allow for a strong practical efficiency of these techniques in strengthening both exact and heuristic solving approaches.
17-35
Solving mixed-integer nonlinear programs (MINLPs) to global optimality efficiently requires fast solvers for continuous sub-problems. These appear in, e.g., primal heuristics, convex relaxations, and bound tightening methods. Two of the best performing algorithms for these sub-problems are Sequential Quadratic Programming (SQP) and Interior Point Methods. In this paper we study the impact of different SQP and Interior Point implementations on important MINLP solver components that solve a sequence of similar NLPs. We use the constraint integer programming framework SCIP for our computational studies.
17-58
PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve MIPs with a dual-block angular structure, which is characteristic of deterministic-equivalent Stochastic Mixed-Integer Programs (SMIPs). In this paper, we present two different parallelizations of Branch & Bound (B&B), implementing both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks, PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B&B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator (UG), a universal framework for parallelizing B&B tree search that has been successfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores.
17-43
We investigate how the numerical properties of the LP relaxations evolve
throughout the solution procedure in a solver employing the branch-and-cut
algorithm. The long-term goal of this work is to determine whether the effect
on the numerical conditioning of the LP relaxations resulting from the
branching and cutting operations can be effectively predicted
and whether such predictions can be used to make better algorithmic
choices. In a first step towards this goal, we discuss here the numerical
behavior of an existing solver in order to determine whether our
intuitive understanding of this behavior is correct.
17-12
The SCIP Optimization Suite is a powerful collection of optimization software that consists of the branch-cut-and-price framework and mixed-integer programming solver SCIP, the linear programming solver SoPlex, the modeling language Zimpl, the parallelization framework UG, and the generic branch-cut-and-price solver GCG. Additionally, it features the extensions SCIP-Jack for solving Steiner tree problems, PolySCIP for solving multi-objective problems, and SCIP-SDP for solving mixed-integer semidefinite programs. The SCIP Optimization Suite has been continuously developed and has now reached version 4.0. The goal of this report is to present the recent changes to the collection. We not only describe the theoretical basis, but focus on implementation aspects and their computational consequences.
17-07
Packing rings into a minimum number of rectangles is an optimization problem which appears naturally in the logistics operations of the tube industry. It encompasses two major difficulties, namely the positioning of rings in rectangles and the recursive packing of rings into other rings. This problem is known as the Recursive Circle Packing Problem (RCPP). We present the first dedicated method for solving RCPP that provides strong dual bounds based on an exact Dantzig–Wolfe reformulation of a nonconvex mixed-integer nonlinear programming formulation. The key idea of this reformulation is to break symmetry on each recursion level by enumerating one-level packings, i.e., packings of circles into other circles, and by dynamically generating packings of circles into rectangles. We use column generation techniques to design a “price-and-verify” algorithm that solves this reformulation to global optimality. Extensive computational experiments on a large test set show that our method not only computes tight dual bounds, but often produces primal solutions better than those computed by heuristics from the literature.
17-61
This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 % faster than SCIP 4.0 and over twice as fast on instances that take at least 100 seconds to solve. For MINLP, SCIP 5.0 is about 17 % faster overall and 23 % faster on instances that take at least 100 seconds to solve. This boost is due to algorithmic advances in several parts of the solver such as cutting plane generation and management, a new adaptive coordination of large neighborhood search heuristics, symmetry handling, and strengthened McCormick relaxations for bilinear terms in MINLPs. Besides discussing the theoretical background and the implementational aspects of these developments, the report describes recent additions for the other software packages connected to SCIP, in particular for the LP solver SoPlex, the Steiner tree solver SCIP-Jack, the MISDP solver SCIP-SDP, and the parallelization framework UG.