ZIB-Report
Refine
Year of publication
Document Type
- ZIB-Report (425)
- Habilitation (4)
Keywords
- mixed integer programming (25)
- integer programming (21)
- constraint integer programming (13)
- branch-and-bound (11)
- mixed-integer programming (11)
- Mixed Integer Programming (9)
- Optimierung (9)
- MINLP (8)
- combinatorial optimization (8)
- line planning (8)
Institute
- Mathematical Optimization (429) (remove)
18-60
Large Neighborhood Search (LNS) heuristics are among the most powerful but also most expensive heuristics for mixed integer programs (MIP). Ideally, a solver learns adaptively which LNS heuristics work best for the MIP problem at hand in order to concentrate its limited computational budget.
To this end, this work introduces Adaptive Large Neighborhood Search (ALNS) for MIP, a primal heuristic that acts a framework for eight popular LNS heuristics such as Local Branching and Relaxation Induced Neighborhood Search (RINS). We distinguish the available LNS heuristics by their individual search domains, which we call neighborhoods. The decision which neighborhood should be executed is guided by selection strategies for the multi armed bandit problem, a related optimization problem during which suitable actions have to be chosen to maximize a reward function. In this paper, we propose an LNS-specific reward function to learn to distinguish between the available neighborhoods based on successful calls and failures. A second, algorithmic enhancement is a generic variable fixing priorization, which ALNS employs to adjust the subproblem complexity as needed. This is particularly useful for some neighborhoods which do not fix variables by themselves. The proposed primal heuristic has been implemented
within the MIP solver SCIP. An extensive computational study is conducted to compare different LNS strategies within our ALNS framework on a large set of publicly available MIP instances from the MIPLIB and Coral benchmark sets. The results of this simulation are used to calibrate the parameters of the bandit selection strategies. A second computational experiment shows the computational benefits of the proposed ALNS framework within the MIP solver SCIP.
18-61
The perfect matching polytope, i.e. the convex hull of (incidence vectors of) perfect matchings of a graph is used in many combinatorial algorithms. Kotzig, Lovász and Plummer developed a decomposition theory for graphs with perfect matchings and their corresponding polytopes known as the tight cut decomposition which breaks down every graph into a number of indecomposable graphs, so called bricks. For many properties that are of interest on graphs with perfect matchings, including the description of the perfect matching polytope, it suffices to consider these bricks. A key result by Lovász on the tight cut decomposition is that the list of bricks obtained is the same independent of the choice of tight cuts made during the tight cut decomposition procedure. This implies that finding a tight cut decomposition is polynomial time equivalent to finding a single tight cut.
We generalise the notions of a tight cut, a tight cut contraction and a tight cut decomposition to hypergraphs. By providing an example, we show that the outcome of the tight cut decomposition on general hypergraphs is no longer unique. However, we are able to prove that the uniqueness of the tight cut decomposition is preserved on a slight generalisation of uniform hypergraphs. Moreover, we show how the tight cut decomposition leads to a decomposition of the perfect matching polytope of uniformable hypergraphs and that the recognition problem for tight cuts in uniformable hypergraphs is polynomial time solvable.
18-58
SCIP-JACK is a customized, branch-and-cut based solver for Steiner tree and related problems. ug [SCIP-JACK, MPI] extends SCIP-JACK to a massively par- allel solver by using the Ubiquity Generator (UG) framework. ug [SCIP-JACK, MPI] was the only solver that could run on a distributed environment at the (latest) 11th DIMACS Challenge in 2014. Furthermore, it could solve three well-known open instances and updated 14 best known solutions to instances from the bench- mark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been con- siderably improved. However, the improvements were not reflected on ug [SCIP- JACK, MPI]. This paper describes an updated version of ug [SCIP-JACK, MPI], especially branching on constrains and a customized racing ramp-up. Furthermore, the different stages of the solution process on a supercomputer are described in detail. We also show the latest results on open instances from the STEINLIB.
18-59
Given a factorable function f, we propose a procedure that constructs a concave underestimor of f that is tight at a given point. These underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection cuts that exploits the bounds of the domain. Finally, we propose an extension of monoidal strengthening to take advantage of the integrality of the non-basic variables.
18-45
18-51
Calculation of clinch and elimination numbers for sports leagues with multiple tiebreaking criteria
(2018)
The clinch (elimination) number is a minimal number of future wins (losses) needed to clinch (to be eliminated from) a specified place in a sports league. Several optimization models and computational results are shown in this paper for calculating clinch and elimination numbers in the presence of predefined multiple tiebreaking criteria. The main subject of this paper is to provide a general algorithmic framework based on integer programming with utilizing possibly multilayered upper and lower bounds.
18-47
Dieses Dokument fasst den Stand der mathematischen Modellierung von
Preissystemen des öV mittels eines am ZIB entwickelten Tarifgraphenmodells zusammen. Damit sind sehr einfache und konzise
Beschreibungen von Tarifstrukturen möglich, die sich algorithmisch
behandeln lassen: Durch das zeitgleiche Tracken eines Pfades im
Routinggraphen im Tarifgraphen kann schon während einer Routenberechnung der Preis bestimmt werden. Wir beschreiben
zunächst das Konzept. Die konkrete Realisierung wird im Folgenden
beispielhaft an den Tarifsystemen der Verkehrsverbünde Warnow,
MDV, Vogtland, Bremen/Niedersachsen, Berlin/Brandenburg und Mittelsachsen erläutert. Anschließend folgen Überlegungen zur konkreten Implementierung von Kurzstrecken-Tarifen und zur Behandlung des Verbundübergriffs.
18-24
We present an extension of Taylor’s theorem towards nonsmooth evalua-
tion procedures incorporating absolute value operaions. Evaluations procedures are
computer programs of mathematical functions in closed form expression and al-
low a different treatment of smooth operations and calls to the absolute value value
function. The well known classical Theorem of Taylor defines polynomial approx-
imation of sufficiently smooth functions and is widely used for the derivation and
analysis of numerical integrators for systems of ordinary differential or differential
algebraic equations, for the construction of solvers for the continuous nonlinear op-
timization of finite dimensional objective functions and for root solving of nonlinear
systems of equations. The herein provided proof is construtive and allow efficiently
designed algorithms for the execution and computation of generalized piecewise
polynomial expansions. As a demonstration we will derive a k-step method on the
basis of polynomial interpolation and the proposed generalized expansions.
18-43
Recent research has shown that piecewise smooth (PS) functions can be approximated by piecewise linear functions with second order error in the distance to
a given reference point. A semismooth Newton type algorithm based on successive application of these piecewise linearizations was subsequently developed
for the solution of PS equation systems. For local bijectivity of the linearization
at a root, a radius of quadratic convergence was explicitly calculated in terms
of local Lipschitz constants of the underlying PS function. In the present work
we relax the criterium of local bijectivity of the linearization to local openness.
For this purpose a weak implicit function theorem is proved via local mapping
degree theory. It is shown that there exist PS functions f:IR^2 --> IR^2 satisfying the weaker
criterium where every neighborhood of the root of f contains a point x such that
all elements of the Clarke Jacobian at x are singular. In such neighborhoods
the steps of classical semismooth Newton are not defined, which establishes
the new method as an independent algorithm. To further clarify the relation between a PS function and its piecewise linearization,
several statements about structure correspondences between the two are proved.
Moreover, the influence of the specific representation of the local piecewise linear models
on the robustness of our method is studied.
An example application from cardiovascular mathematics is given.
18-49
We establish a general computational framework for Chvátal’s conjecture based on exact rational integer programming. As a result we prove Chvátal’s conjecture holds for all downsets whose union of sets contains seven elements or less. The computational proof relies on an exact branch-and-bound certificate that allows for elementary verification and is independent of the integer programming solver used.
18-16
Cycle inequalities play an important role in the polyhedral study of the periodic
timetabling problem. We give the first pseudo-polynomial time separation algo-
rithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial
time separability of the change-cycle inequalities. Moreover, we provide several
NP-completeness results, indicating that pseudo-polynomial time is best possible.
The efficiency of these cutting planes is demonstrated on real-world instances of the
periodic timetabling problem.
18-44
In commodity transport networks such as natural gas, hydrogen and water networks, flows arise from nonlinear potential differences between the nodes, which can be represented by so-called "potential-driven" network models. When operators of these networks face increasing demand or the need to handle more diverse transport situations, they regularly seek to expand the capacity of their network by building new pipelines parallel to existing ones ("looping").
The paper introduces a new mixed-integer non-linear programming (MINLP) model and a new non-linear programming (NLP) model and compares these with existing models for the looping problem and related problems in the literature, both theoretically and experimentally.
On this basis, we give recommendations about the circumstances under which a certain model should be used. In particular, it turns out that one of our novel models outperforms the existing models.
Moreover, the paper is the first to include the practically relevant option that a particular pipeline may be looped several times.
18-38
A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable
(2018)
We consider the following planning problem in public transportation: Given a
periodic timetable, how many vehicles are required to operate it?
In [9], for this sequential approach, it is proposed to first expand the periodic
timetable over time, and then answer the above question by solving a flow-based
aperiodic optimization problem.
In this contribution we propose to keep the compact periodic representation of
the timetable and simply solve a particular perfect matching problem. For practical
networks, it is very much likely that the matching problem decomposes into several
connected components. Our key observation is that there is no need to change any
turnaround decision for the vehicles of a line during the day, as long as the timetable
stays exactly the same.
18-31
All feasible flows in potential-driven networks
induce an orientation on the undirected graph underlying the network.
Clearly, these orientations must satisfy two conditions: they are acyclic and there are no "dead ends" in the network, i.e. each source requires outgoing flows, each sink requires incoming flows, and each transhipment vertex requires both an incoming and an outgoing flow. In this paper we will call orientations that satisfy these conditions acyclic source-transhipment-sink orientations (ASTS-orientation) and study their structure. In particular, we characterize graphs that allow for such an orientation, describe a way to enumerate all possible ASTS-orientations of a given graph, present an algorithm to simplify and decompose a graph before such an enumeration and shed light on the role of zero flows in the context of ASTS-orientations.
18-30
Improving relaxations for potential-driven network flow problems via acyclic flow orientations
(2018)
The class of potential-driven network flow problems provides important models for a range of infrastructure networks. For real-world applications, they need to be combined with integer
models for switching certain network elements, giving rise to hard-to-solve MINLPs. We observe that on large-scale real-world meshed networks the usually employed relaxations are rather weak due to cycles in the network.
We propose acyclic flow orientations as a combinatorial relaxation of feasible solutions of potential-driven flow problems and show how they can be used to strengthen existing relaxations. First computational results indicate that the strengthend model is much tighter than the original relaxation, thus promising a computational advantage.
18-36
State-of-the-art solvers for mixed integer programs (MIP) govern a variety of algorithmic components. Ideally, the solver adaptively learns to concentrate its computational budget on those components that perform well on a particular problem, especially if they are time consuming.
We focus on three such algorithms, namely the classes of large neighborhood search and diving heuristics as well as Simplex pricing strategies.
For each class we propose a selection strategy that is updated based on the observed runtime behavior, aiming to ultimately select only the best algorithms for a given instance.
We review several common strategies for such a selection scenario under uncertainty, also known as Multi Armed Bandit Problem.
In order to apply those bandit strategies, we carefully design reward functions to rank and compare each individual heuristic or pricing algorithm within its respective class.
Finally, we discuss the computational benefits of using the proposed adaptive selection within the \scip Optimization Suite on publicly available MIP instances.
18-37
Optimization models often feature disjunctions of polytopes as
submodels. Such a disjunctive set is initially (at best) relaxed to
its convex hull, which is then refined by branching.
To measure the error of the convex relaxation, the (relative)
difference between the volume of the convex hull and the volume of the
disjunctive set may be used. This requires a method to compute the
volume of the disjunctive set. Naively, this can be done via
inclusion/exclusion and leveraging the existing code for the volume
of polytopes. However, this is often inefficient.
We propose a revised variant of an old algorithm by Bieri and Nef
(1983) for this purpose. The algorithm uses a sweep-plane to
incrementally calculate the volume of the disjunctive set as a
function of the offset parameter of the sweep-plane.
18-35
The amazing success of computational mathematical optimization over the last decades has been driven more by insights into mathematical structures than by the advance of computing technology. In this vein, we address applications, where nonconvexity in the model poses principal difficulties.
This paper summarizes the dissertation of Jonas Schweiger for the occasion of the GOR dissertation award 2018. We focus on the work on non-convex quadratic programs and show how problem specific structure can be used to obtain tight relaxations and speed up Branch&Bound methods. Both a classic general QP and the Pooling Problem as an important practical application serve as showcases.
18-26
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion for cutting planes, one focus of this release are decomposition algorithms. Both SCIP and the automatic decomposition solver GCG now include advanced functionality for performing Benders’ decomposition in a generic framework. GCG’s detection loop for structured matrices and the coordination of pricing routines for Dantzig-Wolfe decomposition has been significantly revised for greater flexibility. Two SCIP extensions have been added
to solve the recursive circle packing problem by a problem-specific column generation scheme and to demonstrate the use of the new Benders’ framework for stochastic capacitated facility location. Last, not least, the report presents updates and additions to the other components and extensions of the SCIP Optimization Suite: the LP solver SoPlex, the modeling language Zimpl, the parallelization framework UG, the Steiner tree solver SCIP-Jack, and the mixed-integer semidefinite programming solver SCIP-SDP.