344
eng
reportzib
0
1998-01-19
1998-01-19
--
A Study of Genetic Algorithms solving a combinatorial Puzzle
The suitability of Genetic Algorithms (GAs) to solve a combinatorial problem with only one solution is investigated. The dependence of the performance is studied for GA-hard and GA-soft fitness functions, both with a range of different parameter values and different encodings.
SC-98-01
345
urn:nbn:de:0297-zib-3445
Thomas Wolf
ZIB-Report
SC-98-01
Informatik, Informationswissenschaft, allgemeine Werke
COMBINATORICS (For finite fields, see 11Txx)
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
ZIB Allgemein
https://opus4.kobv.de/opus4-zib/files/344/SC-98-01.ps
https://opus4.kobv.de/opus4-zib/files/344/SC-98-01.pdf
1312
eng
reportzib
0
2011-06-16
2011-06-16
--
Convergence Analysis of Smoothing Methods for Optimal Control of Stationary Variational Inequalities
In the article an optimal control problem subject to a stationary variational inequality
is investigated. The optimal control problem is complemented with pointwise control constraints.
The convergence of a smoothing scheme is analyzed. There, the variational inequality
is replaced by a semilinear elliptic equation. It is shown that solutions of the regularized optimal
control problem converge to solutions of the original one. Passing to the limit in the
optimality system of the regularized problem allows to prove C-stationarity of local solutions of the original problem.
Moreover, convergence rates with respect to the regularization parameter for the error in the control are obtained.
These rates coincide with rates obtained by numerical experiments, which are included in the paper.
11-23
urn:nbn:de:0297-zib-13125
Anton Schiela
Anton Schiela
Daniel Wachsmuth
ZIB-Report
11-23
deu
uncontrolled
Variational inequalities
deu
uncontrolled
optimal control
deu
uncontrolled
control constraints
deu
uncontrolled
path-following
deu
uncontrolled
C-stationarity
CALCULUS OF VARIATIONS AND OPTIMAL CONTROL; OPTIMIZATION [See also 34H05, 34K35, 65Kxx, 90Cxx, 93-XX]
NUMERICAL ANALYSIS
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Numerical Mathematics
https://opus4.kobv.de/opus4-zib/files/1312/ZR-11-23.pdf
1332
eng
95
bachelorthesis
0
2011-07-13
2011-07-13
2011-05-10
New Rounding and Propagation Heuristics for Mixed Integer Programming
Die vorliegende Arbeit befasst sich mit Primalheuristiken für gemischt-ganzzahlige, lineare Optimierungsprobleme (engl.: mixed integer program MIP).
Zahlreiche Optimierungsprobleme aus der Praxis lassen sich als MIP modellieren, Beispiele hierfür sind u. a.
Optimierungsprobleme
im öffentlichen Nah- und Fernverkehr, bei logistischen Fragestellungen oder im Bereich der Chip-Verifikation.
Das Lösen von MIP ist NP-schwer und wird heutzutage meistens mit Hilfe von Branch-and-Bound-basierenden
Algorithmen versucht. Das Branch-and-Bound-Ver\-fah\-ren profitiert unter Umständen von bereits frühzeitig
zur Verfügung stehenden Lösungen, daher
sind wir sehr an heuristischen Verfahren interessiert, die in der Praxis schnell eine gute Lösung für eine große Zahl an
MIPs liefern und somit die Lösezeit des Branch-and-Bound-Verfahrens erheblich beschleunigen können.
Primalheuristiken sind Suchverfahren zum Auffinden zulässiger Lösungen eines MIP. Verschiedene Typen von Primalheuristiken
sollen dabei den jeweiligen Bedarf des Anwenders zu unterschiedlichen Zeiten während der Branch-and-Bound-Suche decken. Während Start- und
Rundeheuristiken zu Beginn des Löseprozesses eine große Rolle bei der Suche nach der ersten zulässigen Lösung
haben, arbeiten Verbesserungs-heuristiken auf schon bekannten Lösungen, um neue, bessere Lösungen zu produzieren.
Diese Arbeit beschäftigt sich mit Primalheuristiken, welche Teil des MIP-Lösers SCIP sind. Im ersten Kapitel werden
nach der Erarbeitung grundlegender Definitionen viele der durch Tobias Achterberg und Timo Berthold in SCIP integrierten
heuristischen Verfahren vorgestellt und kategorisiert. Auf dieser Grundlage bauen dann die
Kapitel 2-4 der Arbeit auf. In diesen werden drei zusätzliche Heuristiken vorgestellt,
im Einzelnen sind dies ZI Round, eine Rundeheuristik, welche zuerst von Wallace beschrieben wurde, außerdem eine
2-Opt-Heuristik für MIP und eine neue Startheuristik, Shift-And-Propagate.
Großer Wert wird in jedem Kapitel auf die algorithmische Beschreibung der Heuristiken gelegt, die stets anhand von motivierenden
Beispielen eingeführt und anhand von Pseudocode-Algorithmen begleitet werden. Zusätzlich enthält jedes Kapitel Auswertungen der
mit den neuen Heuristiken gemessenen Ergebnisse von SCIP.
Eine kurze Zusammenfassung in Kapitel 5 schließt diese Arbeit ab.
Many practically relevant problems can be formulated in terms of a mixed integer programming (MIP) model. MIP denotes the
optimization of a linear objective function under a certain number of linear side constraints including the need for
some of the involved variables to take integral solution values.
Applications of MIP based optimization can be found in the area of public transit,
scheduling, automatic vehicle routing,
network design, etc.
From a complexity point of view, MIP solving is known to be NP-hard and most commonly tried to be solved via
Branch-and-Bound based algorithms. Branch-and-Bound algorithms benefit from early and good feasible solutions of a MIP
in various ways.
Primal heuristics are aimed at finding new solutions during the MIP solving process. There are different types of primal heuristics:
while start heuristics are particularly
valuable to find an early solution, improvement heuristics hopefully drive a given solution further towards optimality.
This thesis focusses on primal heuristics which are part of the MIP-solving framework SCIP.
The first chapter comes with basic definitions and a brief description of SCIP and the test set which we used.
The remainder of the first chapter is an overview of the existing heuristics in SCIP which have been implemented by Achterberg
and Berthold.
In the following chapters we introduce three new heuristics which apply rounding or propagation techniques for their specific purpose,
namely the new rounding heuristic ZI Round, taken from Wallace, a 2-Opt improvement
heuristic for MIP and the propagation heuristic Shift-and-Propagate.
It is characteristic of all three heuristics that they mainly apply computationally inexpensive algorithms.
Each of them is presented in an own chapter, starting with an algorithmic description, followed by implementational details.
All chapters close with a discussion of the computational results obtained with the respective implementations in SCIP.
urn:nbn:de:0297-zib-13322
Gregor Hendel
Gregor Hendel
deu
uncontrolled
Primal Heuristics, MIP, mixed integer programming, ZI Round, Shift-and-Propagate, optimization
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Studienabschlussarbeiten
Mathematical Optimization
Hendel, Gregor
Zuse Institute Berlin (ZIB)
Technische Universität Berlin
https://opus4.kobv.de/opus4-zib/files/1332/bachelor_thesis_main.pdf
1408
eng
reportzib
0
2011-09-29
2011-09-29
--
Solving steel mill slab design problems
The steel mill slab design problem from the CSPLIB is a combinatorial
optimization problem motivated by an application of the steel industry. It
has been widely studied in the constraint programming community. Several
methods were proposed to solve this problem. A steel mill slab library was
created which contains 380 instances. A closely related binpacking problem
called the multiple knapsack problem with color constraints, originated
from the same industrial problem, was discussed in the integer programming
community. In particular, a simple integer program for this problem has
been given by Forrest et al. The aim of this paper is to bring these
different studies together. Moreover, we adapt the model of Forrest et
al. for the steel mill slab design problem. Using this model and a
state-of-the-art integer program solver all instances of the steel mill
slab library can be solved efficiently to optimality. We improved,
thereby, the solution values of 76 instances compared to previous results.
Finally, we consider a recently introduced variant of the steel mill slab
design problem, where within all solutions which minimize the leftover one
is interested in a solution which requires a minimum number of slabs. For
that variant we introduce two approaches and solve all instances of the
steel mill slab library with this slightly changed objective function to
optimality.
1438-0064
11-38
urn:nbn:de:0297-zib-14089
10.1007/s10601-011-9113-8
Appeared in: Constraints 17 (2012) 39-50
Stefan Heinz
Stefan Heinz
Thomas Schlechte
Rüdiger Stephan
Michael Winkler
ZIB-Report
11-38
eng
uncontrolled
steel mill slab design problem
eng
uncontrolled
multiple knapsack problem with color constraints
eng
uncontrolled
integer programming
eng
uncontrolled
set partitioning
eng
uncontrolled
binpacking with side constraints
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical programming [See also 49Mxx, 65Kxx]
Applications of mathematical programming
Mathematical Optimization
Heinz, Stefan
Schlechte, Thomas
Winkler, Michael
https://opus4.kobv.de/opus4-zib/files/1408/ZR-11-38.pdf
1486
deu
reportzib
0
2012-03-19
2012-03-19
--
Schätze heben bei der Planung von FTTx-Netzen: optimierte Nutzung von existierenden Leerrohren - eine Praxisstudie
Das vom BMBF geförderte Projekt FTTX-PLAN entwickelt mathematische Modelle und Optimierungsverfahren, um automatisiert kostenoptimierte FTTx-Netze berechnen zu können. Wir zeigen anhand einer Praxisstudie in Zusammenarbeit mit der Regensburger R-KOM, wie ein Planer von diesen Verfahren profitieren kann, um die Auswirkungen bestimmter Entscheidungen auf die Netzstruktur und -kosten zu untersuchen. Wir illustrieren dies am Beispiel eines FTTB/FTTH-Vergleichs, der Variation von Kundenanbindungsraten und der gezielten Ausnutzung existierender Leerrohre, um Tiefbau zu vermeiden.
1438-0064
http://www.vde-verlag.de/buecher/453339/breitbandversorgung-in-deutschland-itg-fb-227.html
urn:nbn:de:0297-zib-14861
Ersch. in: ITG (Hrsg.) Breitbandversorgung in Deutschland (ITG-FB 227) Vorträge der 5. ITG-Fachkonferenz vom 29. bis 30. März 2011 in Berlin ITG-Fachbericht Band 227, 2011, ISBN 978-3-8007-3339-2
Axel Werner
Roland Wessäly
Axel Werner
Klaus Eckel
Julia Seibel
Sebastian Orlowski
Hadrian Louchet
Erwin Patzak
Winfried Bentz
ZIB-Report
11-47
deu
uncontrolled
Praxisstudie
deu
uncontrolled
Optische Zugangsnetze
deu
uncontrolled
Optimierung
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
https://opus4.kobv.de/opus4-zib/files/1486/ITG-2011.pdf
1487
deu
reportzib
0
2012-03-19
2012-03-19
--
Kombinatorische Optimierung und die 40-Punkte-Regel
Wieviele Punkte braucht eine Mannschaft in der Fußball-Bundesliga mindestens, um sicher dem Abstieg zu entgehen? Wir benutzen kombinatorische Optimierung, um diese und ähnliche Fragen zu beantworten.
1438-0064
urn:nbn:de:0297-zib-14871
Ersch. in: Mitteilungen der DMV, 19 (2011) 153-157
Axel Werner
Axel Werner
ZIB-Report
11-48
deu
uncontrolled
Kombinatorische Optimierung
deu
uncontrolled
Sport
deu
uncontrolled
Bundesliga
GENERAL
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
https://opus4.kobv.de/opus4-zib/files/1487/ZIB-Report-40-punkte.pdf
1488
eng
reportzib
0
2012-03-19
2012-03-19
--
Estimating trenching costs in FTTx network planning
In this paper we assess to which extent trenching costs of an FTTx network are unavoidable, even if technical side constraints are neglected. For that purpose we present an extended Steiner tree model. Using a variety of realistic problem instances we demonstrate that the total trenching cost can only be reduced by about 5 percent in realistic scenarios. This work has been funded by BMBF (German Federal Ministry of Education and Research) within the program "KMU-innovativ".
1438-0064
urn:nbn:de:0297-zib-14884
10.1007/978-3-642-29210-1_15
Appeared in: Operations Research Proceedings 2011. D. Klatte, H.-J. Lüthi, K. Schmedders (eds.) 2012, pp. 89-94
Axel Werner
Sebastian Orlowski
Axel Werner
Roland Wessäly
ZIB-Report
11-49
eng
uncontrolled
Optical access networks
eng
uncontrolled
Optimization
eng
uncontrolled
Steiner trees
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
https://opus4.kobv.de/opus4-zib/files/1488/OR-Proc-2011.pdf
1493
eng
reportzib
0
2012-03-27
2012-03-27
--
A Class of Semidefinite Programs with rank-one solutions
We show that a class of semidefinite programs (SDP) admits a solution that is a positive semidefinite
matrix of rank at most $r$, where $r$ is the rank of the matrix involved in the objective function of the SDP.
The optimization problems of this class are semidefinite packing problems,
which are the SDP analogs to vector packing problems.
Of particular interest is the case in which our result guarantees the existence of a solution
of rank one: we show that the computation of this solution actually reduces to a
Second Order Cone Program (SOCP).
We point out an application in statistics, in the optimal design of experiments.
1438-0064
10.1016/j.laa.2011.03.027
urn:nbn:de:0297-zib-14933
Appeared in: Linear Algebra and its Applications 435 (2011) pp. 1446-1463
Guillaume Sagnol
Guillaume Sagnol
ZIB-Report
11-51
eng
uncontrolled
SDP
eng
uncontrolled
Semidefinite Packing Problem
eng
uncontrolled
rank 1-solution
eng
uncontrolled
Low-rank solutions
eng
uncontrolled
SOCP
eng
uncontrolled
Optimal Experimental Design
eng
uncontrolled
Multiresponse experiments
Mathematics of Computing
STATISTICS
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Sagnol, Guillaume
ZIB-OptDes
https://opus4.kobv.de/opus4-zib/files/1493/ZR-11-51.pdf
1494
eng
161
171
51
51
reportzib
0
2012-03-27
2012-03-27
--
Network-related problems in Optimal Experimental Design and Second Order Cone Programming
In the past few years several applications of optimal
experimental designs have emerged to optimize the measurements
in communication networks. The optimal design problems arising from
this kind of applications share three interesting properties:
(i) measurements are only available at a small number of locations of the network;
(ii) each monitor can simultaneously measure several quantities, which
can be modeled by ``multiresponse experiments";
(iii) the observation matrices depend on the topology of the network.
In this paper, we give an overview of these experimental design
problems and recall recent results for the computation of optimal
designs by Second Order Cone Programming (SOCP). New results for the
network-monitoring of a discrete time process are presented. In particular, we show
that the optimal design problem for the monitoring of an AR1 process can be reduced
to the standard form and we give experimental results.
1438-0064
urn:nbn:de:0297-zib-14942
10.2478/v10127-012-0016-x
Appeared in: Tatra Mountains Mathematical Publications (Proceedings of PROBASTAT'2011)
Guillaume Sagnol
Guillaume Sagnol
ZIB-Report
11-52
eng
uncontrolled
Optimal Experimental Design
eng
uncontrolled
Second Order Cone Programming
eng
uncontrolled
Network measurements
STATISTICS
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Sagnol, Guillaume
TOLLCONTROLOPT
ZIB-OptDes
Zuse Institute Berlin (ZIB)
https://opus4.kobv.de/opus4-zib/files/1494/ZR-11-52.pdf
1495
eng
258
276
1--2
151
reportzib
0
2012-03-27
2012-03-27
--
Approximation of a Maximum-Submodular-Coverage problem involving spectral functions, with application to Experimental Design
We study a family of combinatorial optimization problems
defined by a parameter $p\in[0,1]$, which involves spectral
functions applied to positive semidefinite matrices, and has
some application in the theory of optimal experimental design.
This family of problems tends to a generalization of the classical
maximum coverage problem as $p$ goes to $0$, and to a trivial instance
of the knapsack problem as $p$ goes to $1$.
In this article, we establish a matrix inequality which shows that the objective function is submodular for all $p\in[0,1]$, from which it follows
that the greedy approach, which has often been used for this problem, always gives a design within $1-1/e$ of the optimum.
We next study the design found by rounding the solution of the continuous relaxed problem, an approach which has been applied by several authors.
We prove an inequality which generalizes a classical result from the theory
of optimal designs, and allows us to give a rounding procedure with an approximation
factor which tends to $1$ as $p$ goes to $1$.
1438-0064
urn:nbn:de:0297-zib-14956
10.1016/j.dam.2012.07.016
Appeared in: Discrete Applied Mathematics
Guillaume Sagnol
Guillaume Sagnol
ZIB-Report
11-53
eng
uncontrolled
Maximum Coverage
eng
uncontrolled
Optimal Experimental Design
eng
uncontrolled
Polynomial Time Approximability
eng
uncontrolled
Kiefer's p-criterion
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Sagnol, Guillaume
https://opus4.kobv.de/opus4-zib/files/1495/submodular_zib.pdf
1298
eng
reportzib
0
2011-05-31
2011-05-31
--
Large Neighborhood Search beyond MIP
Large neighborhood search (LNS) heuristics are an important component of modern branch-and-cut algorithms for solving mixed-integer linear programs (MIPs). Most of these LNS heuristics use the LP relaxation as the basis for their search, which is a reasonable choice in case of MIPs. However, for more general problem classes, the LP relaxation alone may not contain enough information about the original problem to find feasible solutions with these heuristics, e.g., if the problem is nonlinear or not all constraints are present in the current relaxation.
In this paper, we discuss a generic way to extend LNS heuristics that have been developed for MIP to constraint integer programming (CIP), which is a generalization of MIP in the direction of constraint programming (CP). We present computational results of LNS heuristics for three problem classes: mixed-integer quadratically constrained programs, nonlinear pseudo-Boolean optimization instances, and resource-constrained project scheduling problems. Therefore, we have implemented extended versions of the following LNS heuristics in the constraint integer programming framework SCIP: Local Branching, RINS, RENS, Crossover, and DINS. Our results indicate that a generic generalization of LNS heuristics to CIP considerably improves the success rate of these heuristics.
11-21
urn:nbn:de:0297-zib-12989
Appeared in: Proceedings of the 9th Metaheuristics International Conference (MIC 2011). 2011. Luca di Gaspar et al. eds. ISBN 978-88-900984-3-7, pp. 51-60
Timo Berthold
Timo Berthold
Stefan Heinz
Marc E. Pfetsch
Stefan Vigerske
ZIB-Report
11-21
deu
uncontrolled
Large Neighborhood Search
deu
uncontrolled
Primal Heuristic
deu
uncontrolled
MIP
deu
uncontrolled
MIQCP
deu
uncontrolled
Pseudo-Boolean
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Berthold, Timo
Heinz, Stefan
Vigerske, Stefan
https://opus4.kobv.de/opus4-zib/files/1298/lns4cip.pdf
1499
eng
reportzib
0
2012-04-10
2012-04-10
--
A Stackelberg game to optimize the distribution of controls in transportation networks
We propose a game theoretic model for the spatial distribution of inspectors on a
transportation network.
The problem is to spread out the controls so as to enforce the payment of a transit
toll. We formulate a linear program to find
the control distribution which maximizes the expected toll revenue,
and a mixed integer program for the problem of minimizing
the number of evaders. Furthermore, we show that the problem of finding an optimal
mixed strategy for a coalition of $N$ inspectors can be solved
efficiently by a column generation procedure. Finally, we give experimental results
from an application to the truck toll on German motorways.
1438-0064
urn:nbn:de:0297-zib-14995
10.1007/978-3-642-35582-0_17
A rev. vers. appeared in: Proceedings of the 3rd International Conference on Game Theory for Networks (GAMENETS 2012), volume 105 of Lecture Notes of the ICST, pp. 224 – 235, Vancouver, Canada, May 2012
Ralf Borndörfer
Guillaume Sagnol
Bertrand Omont
Guillaume Sagnol
Elmar Swarat
ZIB-Report
12-15
eng
uncontrolled
Stackelberg game
eng
uncontrolled
Polymatrix game
eng
uncontrolled
Controls in transportation networks
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Sagnol, Guillaume
Swarat, Elmar
TOLLCONTROLOPT
https://opus4.kobv.de/opus4-zib/files/1499/zib_report_12_15.pdf
1770
eng
reportzib
0
2012-12-21
2012-12-21
--
Improving strong branching by propagation
Strong branching is an important component of most variable selection rules in branch-and-bound based mixed-integer linear programming solvers.
It predicts the dual bounds of potential child nodes by solving auxiliary LPs and thereby helps to keep the branch-and-bound tree small.
In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching.
Computational experiments on standard MIP instances indicate that this is beneficial in three aspects: It helps to reduce the average number of LP iterations per strong branching call, the number of branch-and-bound nodes, and the overall solving time.
1438-0064
urn:nbn:de:0297-zib-17701
Gerald Gamrath
Gerald Gamrath
ZIB-Report
12-46
eng
uncontrolled
mixed-integer programming
eng
uncontrolled
branch-and-bound
eng
uncontrolled
branching rule
eng
uncontrolled
strong branching
eng
uncontrolled
domain propagation
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Gamrath, Gerald
ASTfSCM
MIP-ZIBOPT
https://opus4.kobv.de/opus4-zib/files/1770/ZR-12-46.pdf
1739
eng
reportzib
0
2012-12-19
2012-12-19
--
Picos Documentation. Release 0.1.1.
PICOS is a user friendly interface
to several conic and integer programming solvers,
very much like YALMIP
under MATLAB.
The main motivation for PICOS is to have the possibility to
enter an optimization problem as a high level model,
and to be able to solve it with several different solvers.
Multidimensional and matrix variables are handled in a natural fashion,
which makes it painless to formulate a SDP or a SOCP.
This is very useful for educational purposes,
and to quickly implement some models and
test their validity on simple examples.
Furthermore, with PICOS you can take advantage of the
python programming language to read and write data,
construct a list of constraints by using python list comprehensions,
take slices of multidimensional variables, etc.
1438-0064
urn:nbn:de:0297-zib-17396
Guillaume Sagnol
Guillaume Sagnol
ZIB-Report
12-48
eng
uncontrolled
mathematical programming
eng
uncontrolled
SDP
eng
uncontrolled
SOCP
eng
uncontrolled
python
Software
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Sagnol, Guillaume
MIP-ZIBOPT
ZIB-OptDes
https://opus4.kobv.de/opus4-zib/files/1739/zib_report_12_48.pdf
1751
eng
2829
2843
439
reportzib
0
2012-12-20
2012-12-20
--
On the semidefinite representations of real functions applied to symmetric matrices
We present a new semidefinite representation for the trace of
a real function f applied to symmetric matrices, when a
semidefinite representation of the convex function f is known. Our construction
is intuitive, and yields a representation that is more compact than the previously known one.
We also show with the help of matrix geometric means and the Riemannian metric of the set of positive definite matrices
that for a rational number p in the interval (0,1],
the matrix X raised to the exponent p is the largest element
of a set represented by linear matrix inequalities.
We give numerical results for a problem inspired from the theory
of experimental designs, which show that the new semidefinite programming formulation
yields a speed-up factor in the order of 10.
1438-0064
urn:nbn:de:0297-zib-17511
10.1016/j.laa.2013.08.021
Appear in: Linear Algebra and its Applications
Guillaume Sagnol
Guillaume Sagnol
ZIB-Report
12-50
eng
uncontrolled
semidefinite representability
eng
uncontrolled
optimal experimental designs
eng
uncontrolled
SDP
eng
uncontrolled
matrix geometric mean
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Sagnol, Guillaume
https://opus4.kobv.de/opus4-zib/files/1751/ZR-12-50.pdf
https://opus4.kobv.de/opus4-zib/files/1751/ZR-12-50revised.pdf
https://opus4.kobv.de/opus4-zib/files/1751/sdp_ratpow_zib_final-1.pdf
921
eng
reportzib
0
2006-05-30
2006-05-30
--
Competitive Online Multicommodity Routing
We study online multicommodity minimum cost routing problems in networks, where commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining the routing weights. We discuss an online algorithm that routes each commodity by minimizing a convex cost function that depends on the demands that are previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is $4K/2+K$-competitive, where $K$ is the number of commodities. For the parallel arc case this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably.
06-27
921
urn:nbn:de:0297-zib-9212
Appeared in: T. Erlebach and C. Kaklamanis (eds.) Approximation and Online Algorithms (WAOA 2006). LNCS 4368, pp. 240-252, 2007
Tobias Harks
Stefan Heinz
Marc E. Pfetsch
ZIB-Report
06-27
eng
uncontrolled
Online Optimization
eng
uncontrolled
Routing
eng
uncontrolled
Telecommunications
Informatik, Informationswissenschaft, allgemeine Werke
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
ZIB Allgemein
Heinz, Stefan
https://opus4.kobv.de/opus4-zib/files/921/ZR-06-27.pdf
https://opus4.kobv.de/opus4-zib/files/921/ZR-06-27.ps
959
eng
reportzib
0
2007-06-14
2007-06-14
--
Competitive Online Multicommodity Routing
In this paper we study online multicommodity routing problems in networks, in which commodities have to be routed sequentially. The flow of each commodity can be split on several paths. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes each commodity by minimizing a convex cost function that only depends on the demands previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is 4K2 (1+K)2 -competitive, where K is the number of commodities. For the single-source single-destination case, this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably.
07-16
959
urn:nbn:de:0297-zib-9599
Appeared in: Theory of Computing Systems 45, No. 3 (2009), 533-554
Tobias Harks
Stefan Heinz
Marc E. Pfetsch
ZIB-Report
07-16
eng
uncontrolled
Online Optimization
eng
uncontrolled
Routing
eng
uncontrolled
Telecommunications
Informatik, Informationswissenschaft, allgemeine Werke
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
ZIB Allgemein
Heinz, Stefan
https://opus4.kobv.de/opus4-zib/files/959/ZR_07_16.pdf
https://opus4.kobv.de/opus4-zib/files/959/ZR-07-16.pdf
https://opus4.kobv.de/opus4-zib/files/959/ZR-07-16.ps
https://opus4.kobv.de/opus4-zib/files/959/ZR_07_16.ps
937
eng
reportzib
0
2006-10-10
2006-10-10
--
Nash Equilibria in Online Sequential Routing Games
In this paper, we study the efficiency of Nash equilibria for a sequence of nonatomic routing games. We assume that the games are played consecutively in time in an online fashion: by the time of playing game $i$, future games $i+1,\dots,n$ are not known, and, once players of game $i$ are in equilibrium, their corresponding strategies and costs remain fixed. Given a sequence of games, the cost for the sequence of Nash equilibria is defined as the sum of the cost of each game. We analyze the efficiency of a sequence of Nash equilibria in terms of competitive analysis arising in the online optimization field. Our main result states that the online algorithm $\sl {SeqNash}$ consisting of the sequence of Nash equilibria is $\frac{4n}{2+n}$-competitive for affine linear latency functions. For $n=1$, this result contains the bound on the price of anarchy of $\frac{4}{3}$ for affine linear latency functions of Roughgarden and Tardos [2002] as a special case. Furthermore, we analyze a problem variant with a modified cost function that reflects the total congestion cost, when all games have been played. In this case, we prove an upper bound of $\frac{4n}{2+n}$ on the competitive ratio of $\sl {SeqNash}$. We further prove a lower bound of $\frac{3n-2}{n}$ of $\sl {SeqNash}$ showing that for $n=2$ our upper bound is tight.
06-43
937
urn:nbn:de:0297-zib-9376
Appeared as: Tobias Harks and Laslo Vegh: Nonadaptive Selfish Routing with Online Demands in: CAAN 2007, Combinatorial and Algorithmic Aspects of Networking Workshop, Halifax, Canada, 2007. Jeannette C. M. Janssen and Pawel Pralat (eds.) LNCS, 4852. Springer 2007, pp. 27-45
Tobias Harks
ZIB-Report
06-43
eng
uncontrolled
Congestion Game
eng
uncontrolled
Online Optimization
eng
uncontrolled
Nash equilibria
Informatik, Informationswissenschaft, allgemeine Werke
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES
ZIB Allgemein
https://opus4.kobv.de/opus4-zib/files/937/ZR-06-43.pdf
https://opus4.kobv.de/opus4-zib/files/937/ZR_06_43.orig.Vers.pdf
https://opus4.kobv.de/opus4-zib/files/937/ZR_06_43.orig.Vers.ps
5754
2010
eng
208
masterthesis
0
--
--
2010-03-16
Generic Branch-Cut-and-Price
In this thesis, we present the theoretical background, implementational details and computational results concerning the generic branch-cut-and-price solver GCG.
urn:nbn:de:0297-zib-57543
Marco Lübbecke
Gerald Gamrath
Gerald Gamrath
Martin Grötschel
eng
uncontrolled
mixed-integer programming
eng
uncontrolled
column generation
eng
uncontrolled
branch-and-price
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical programming [See also 49Mxx, 65Kxx]
Mixed integer programming
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
MIP-ZIBOPT
Technische Universität Berlin
https://opus4.kobv.de/opus4-zib/files/5754/gamrath2010_genericBCP.pdf
5709
2015
eng
reportzib
0
--
2015-12-21
--
Exploiting Solving Phases for Mixed-Integer Programs
Modern MIP solving software
incorporates dozens of auxiliary algorithmic components for supporting
the branch-and-bound search in finding and improving solutions and in strengthening the relaxation.
Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process.
We propose an adaptive solver behavior that dynamically reacts
on transitions between the three typical phases of a MIP solving process:
The first phase objective is to find a feasible solution. During the second phase,
a sequence of incumbent solutions gets constructed
until the incumbent is eventually optimal. Proving
optimality is the central objective of the remaining third phase.
Based on the MIP-solver SCIP, we demonstrate
the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide
heuristic alternatives to make use of the concept in practice.
1438-0064
urn:nbn:de:0297-zib-57098
10.1007/978-3-319-42902-1_1
Appeared in: Operations Research Proceedings 2015
Gregor Hendel
Gregor Hendel
ZIB-Report
15-64
eng
uncontrolled
Branch-and-Bound, Mixed-Integer Programming
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Hendel, Gregor
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/5709/Hendel_ExploitingSolvingPhases.pdf
6049
eng
reportzib
0
--
2016-04-10
--
A Re-optimization Approach for Train Dispatching
The Train Dispatching Problem (TDP) is to schedule trains through a network in a cost optimal way. Due to disturbances during operation existing track allocations often have to be re-scheduled and integrated into the timetable. This has to be done in seconds and with minimal timetable changes to guarantee smooth and conflict free operation.
We present an integrated modeling approach for the re-optimization task using Mixed Integer Programming. Finally, we provide computational results for scenarios provided by the INFORMS RAS Problem Soling Competition 2012.
1438-0064
urn:nbn:de:0297-zib-60493
Frank Fischer
Thomas Schlechte
Boris Grimm
Torsten Klug
Thomas Schlechte
ZIB-Report
16-49
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Grimm, Boris
Klug, Torsten
Schlechte, Thomas
KOSMOS
MODAL-RailLab
https://opus4.kobv.de/opus4-zib/files/6049/ZR-16-49.pdf
5459
eng
reportzib
0
--
2015-04-21
--
Enhancing MIP branching decisions by using the sample variance of pseudo-costs
The selection of a good branching variable is crucial for small search trees in Mixed Integer Programming. Most modern solvers employ a strategy guided by history information, mainly the variable pseudo-costs, which are used to estimate the objective gain. At the beginning
of the search, such information is usually collected via an expensive look-ahead strategy called strong-branching until variables are considered reliable.
The reliability notion is thereby mostly based on fixed-number thresholds, which may lead to ineffective branching decisions on problems with highly varying objective gains.
We suggest two new notions of reliability motivated by mathematical statistics that take into account the sample variance of the past observations on each variable individually. The first method prioritizes additional strong-branching look-aheads on variables whose pseudo-costs
show a large variance by measuring the relative error of a pseudo-cost confidence interval. The second method performs a two-sample Student-t test for filtering branching candidates with a high probability to be better than the best history candidate.
Both methods were implemented in the MIP-solver SCIP and computational results on standard MIP test sets are presented.
1438-0064
10.1007/978-3-319-18008-3_14
urn:nbn:de:0297-zib-54591
Appeared in: Integration of AI and OR Techniques in Constraint Programming. Lecture Notes in Computer Science 9075. 2015 pp. 199-214
urn:nbn:de:0297-zib-54591
Gregor Hendel
Gregor Hendel
ZIB-Report
15-28
eng
uncontrolled
mixed-integer programming
eng
uncontrolled
reliability branching
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Hendel, Gregor
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/5459/paper.pdf
5355
2015
eng
reportzib
0
--
2015-02-02
--
Optimal Battery Controlling for Smart Grid Nodes
Energy storages can be of great value when added to power grids. They introduce the possibility to store and release energy whenever this is favorable. This is particularly relevant, for example, if power supply is volatile (as is the case with renewable energy) and the network is small (so that there are few other nodes that might balance fluctuations in consumption or production). We present models and methods from mathematical optimization for computing an optimized storage schedule for this purpose. We look at alternative optimization objectives, such as smallest possible peak load, low energy costs, or the close approximation of a prescribed load curve. The optimization needs to respect general operational and economic constraints as well as limitations in the use of storage, which are imposed by the chosen storage technology. We therefore introduce alternative approaches for modeling the non-linear properties of energy storages and study their impact on the efficiency of the optimization process. Finally, we present a computational study with batteries as storage devices. We use this to highlight the trade-off between solution quality and computational tractability. A version of the model for the purpose of leveling peaks and instabilities has been implemented into a control system for an office-building smart grid scenario.
1438-0064
urn:nbn:de:0297-zib-53550
10.1007/978-4-431-55420-2_6
Appeared in: Optimization in the Real World - Towards Solving Real-World Optimization Problems, volume 13 of Mathematics for Industry, p. 97-113, Springer, 2015
Andreas Draegert
Axel Werner
Andreas Eisenblätter
Inken Gamrath
Axel Werner
ZIB-Report
15-06
eng
uncontrolled
energy optimization, non-linear optimization, smart grid
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
DESI
Gamrath, Inken
https://opus4.kobv.de/opus4-zib/files/5355/smart-grid-batteries.pdf
5364
eng
reportzib
0
--
2015-12-02
--
Computing D-optimal experimental designs for estimating treatment contrasts under the presence of a nuisance time trend
We prove a mathematical programming characterisation of approximate partial D-optimality under general linear constraints. We use this characterisation with a branch-and-bound method to compute a list of all exact D-optimal designs for estimating a pair of treatment contrasts in the presence of a nuisance time trend up to the size of 24 consecutive trials.
1438-0064
10.1007/978-3-319-13881-7_10
urn:nbn:de:0297-zib-53640
Appeared in: Stochastic Models, Statistics and Their ApplicationsSpringer Proceedings in Mathematics & Statistics Volume 122, 2015, pp 83-91
Radoslav Harman
Guillaume Sagnol
Guillaume Sagnol
ZIB-Report
15-02
eng
uncontrolled
optimal design of experiments
eng
uncontrolled
nuisance trend
eng
uncontrolled
branch and bound
STATISTICS
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Transportation and Logistics
Sagnol, Guillaume
ZIB-OptDes
https://opus4.kobv.de/opus4-zib/files/5364/POP-SMSA-ZIB.pdf
5375
eng
reportzib
0
--
2015-02-25
--
A Two-Phase Method for the Biobjective k-Architecture Connected Facility Location Problem and Hypervolume Computation
We apply customized versions of the ε-constraint Method and the Two-Phase Method to a problem originating in access network planning. We introduce various notions of quality measures for approximated/partial sets of nondominated points, utilizing the concept of hypervolume for biobjective problems. We report on computations to assess the performance of the two methods in terms of these measures.
1438-0064
urn:nbn:de:0297-zib-53753
Svenja Uslu
Axel Werner
Axel Werner
ZIB-Report
15-08
eng
uncontrolled
Biobjective Optimization
eng
uncontrolled
Connected Facility Location
eng
uncontrolled
Hypervolume
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
ECMath-MI4
Multi-FTTx
https://opus4.kobv.de/opus4-zib/files/5375/twophase-hypervol-ZR.pdf
6156
eng
reportzib
0
--
2016-12-22
--
Optimal Looping of Pipelines in Gas Networks
In this paper, we compare several approaches for the problem of gas network expansions using loops, that is, to build new pipelines in parallel to existing ones. We present different model formulations for the problem of continuous loop expansions as well as discrete loop expansions. We then analyze problem properties, such as the structure and convexity of the underlying feasible regions. The paper concludes with a computational study comparing the continuous and the discrete formulations.
1438-0064
urn:nbn:de:0297-zib-61564
Ralf Lenz
Ralf Lenz
Robert Schwarz
ZIB-Report
16-67
eng
uncontrolled
Mixed Integer Nonlinear Programming
deu
uncontrolled
Gas Network Applications
deu
uncontrolled
Expansion Planning
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Lenz, Ralf
MODAL-GasLab
https://opus4.kobv.de/opus4-zib/files/6156/ZR-16-67.pdf
6124
eng
reportzib
0
--
2016-11-30
--
The Shortest Path Problem with Crossing Costs
We introduce the shortest path problem with crossing costs (SPPCC), a shortest path problem in a directed graph, in which the objective function is the sum of arc weights and crossing costs. The former are independently paid for each arc used by the path, the latter need to be paid every time the path intersects certain sets of arcs, which we call regions.
The SPPCC generalizes not only the classical shortest path problem but also variants such as the resource constrained shortest path problem and the minimum label path problem. We use the SPPCC to model the flight trajectory optimization problem with overflight costs.
In this paper, we provide a comprehensive analysis of the problem. In particular,
we identify efficient exact and approximation algorithms for the cases that are most relevant in practice.
1438-0064
urn:nbn:de:0297-zib-61240
Marco Blanco
Nam Dung Hoang
Ralf Borndörfer
Nam Dung Hoang
Anton Kaier
Thomas Schlechte
Swen Schlobach
ZIB-Report
16-70
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Blanco, Marco
Borndörfer, Ralf
Schlechte, Thomas
LHS-ATN
https://opus4.kobv.de/opus4-zib/files/6124/ZR-16-70.pdf
6134
eng
reportzib
0
--
2016-01-12
--
PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite
SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP.
1438-0064
urn:nbn:de:0297-zib-61348
10.1007/978-3-319-42432-3_37
Appeared in: Mathematical Software – ICMS 2016, Volume 9725, Pages 301-307
Stephen Maher
Matthias Miltenberger
Matthias Miltenberger
Joao Pedro Pedroso
Daniel Rehfeldt
Robert Schwarz
Felipe Serrano
ZIB-Report
16-64
eng
uncontrolled
SCIP, Mathematical optimization, Python, Modeling
Computer Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Miltenberger, Matthias
Rehfeldt, Daniel
Serrano, Felipe
Maher, Stephan
ASTfSCM
MIP-ZIBOPT
MODAL-GasLab
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6134/PySCIPOpt.pdf
5540
eng
reportzib
0
--
2015-06-18
--
An Extended Network Interdiction Problem for Optimal Toll Control
We study an extension of the shortest path network interdiction problem and present a novel real-world application in this area. We consider the problem of determining optimal locations for toll control stations on the arcs of a transportation network. We handle the fact that drivers can avoid control stations on parallel secondary roads. The problem is formulated as a mixed integer program and solved using Benders decomposition. We present experimental results for the application of our models to German motorways.
1438-0064
urn:nbn:de:0297-zib-55405
10.1016/j.endm.2016.03.040
Appeared in: Electronic Notes in Discrete Mathematics Volume 52, June 2016, Pages 301–308 INOC 2015 – 7th International Network Optimization Conference
Ralf Borndörfer
Stephan Schwartz
Guillaume Sagnol
Stephan Schwartz
ZIB-Report
15-32
eng
uncontrolled
network interdiction
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Sagnol, Guillaume
Schwartz, Stephan
TOLLCONTROLOPT
https://opus4.kobv.de/opus4-zib/files/5540/ZIB_Report_15_32.pdf
5625
eng
reportzib
0
--
2015-09-30
--
Two algorithms for solving 3-objective k-ArchConFL and IPs in general
We present two algorithms to solve a 3-objective optimization problem arising in telecommunications access network planning, the k-Architecture Connected Facility Location Problem. The methods can also be used to solve any 3-objective integer linear programming model and can be extended to the multiobjective case. We give some exemplary computations using small and medium-sized instances for our problem.
1438-0064
urn:nbn:de:0297-zib-56259
Markus Leitner
Axel Werner
Ivana Ljubic
Markus Sinnl
Axel Werner
ZIB-Report
15-48
eng
uncontrolled
multiobjective optimization
eng
uncontrolled
integer programming
eng
uncontrolled
telecommunications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Multi-FTTx
https://opus4.kobv.de/opus4-zib/files/5625/3obj-kArch-ZR.pdf
5606
eng
reportzib
0
--
2015-04-09
--
Comparing two dual relaxations of large scale train timetabling problems
Railway transportation and in particular train timetabling is one of the basic and source application areas of combinatorial optimization and integer programming. We will discuss two well established modeling techniques for the train timetabling problem. In this paper we focus on one major ingredient - the bounding by dual relaxations. We compare two classical dual relaxations of large scale time expanded train timetabling problems - the Lagrangean Dual and Lagrangean Decomposition. We discuss the convergence behavior and show limitations of the Lagrangean Decomposition approach for a configuration based model. We introduce a third dualization approach to overcome those limitations. Finally, we present promising preliminary computational experiments that show that our new approach indeed has superior convergence properties.
1438-0064
urn:nbn:de:0297-zib-56068
Frank Fischer
Thomas Schlechte
Thomas Schlechte
ZIB-Report
15-43
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Schlechte, Thomas
MODAL-RailLab
Trassenbörse
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/5606/ZR-15-43.pdf
5607
2015
eng
reportzib
0
2015-07-09
2015-07-09
--
Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue
Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics
can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and
airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively.
1438-0064
urn:nbn:de:0297-zib-56070
Ralf Borndörfer
Thomas Schlechte
Markus Reuther
Thomas Schlechte
Christof Schulz
Elmar Swarat
Steffen Weider
ZIB-Report
15-44
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Schlechte, Thomas
Schulz, Christof
Swarat, Elmar
Weider, Steffen
LHS-CS
MODAL-RailLab
TOLLCONTROLOPT
MODAL-Gesamt
Reuther, Markus
https://opus4.kobv.de/opus4-zib/files/5607/ZR-15-44.pdf
5642
2015
2015
eng
reportzib
1
2015-10-29
2015-10-29
--
Rolling Stock Rotation Optimization in Days of Strike: An Automated Approach for Creating an Alternative Timetable
The operation of a railway network as large as Deutsche Bahn's Intercity Express (ICE) hinges on a number of factors, such as the availability of personnel and the assignment of physical vehicles to a timetable schedule, a problem known as the rolling stock rotation problem (RSRP). In this paper, we consider the problem of creating an alternative timetable in the case that there is a long-term disruption, such as a strike, and the effects that this alternative timetable has on the resulting vehicle rotation plan. We define a priority measure via the Analytic Hierarchy Process (AHP) to determine the importance of each trip in the timetable and therefore which trips to cancel or retain. We then compare our results with those of a limited timetable manually designed by Deutsche Bahn (DB). We find that while our timetable results in a more expensive rotation plan, its flexibility lends itself to a number of simple improvements. Furthermore, our priority measure has the potential to be integrated into the rolling stock rotation optimization process, in particular, the Rotation Optimizer for Railways (ROTOR) software, via the cost function. Ultimately, our method provides the foundation for an automated way of creating a new timetable quickly, and potentially in conjunction with a new rotation plan, in the case of a limited scenario.
1438-0064
urn:nbn:de:0297-zib-56425
no
Sepideh Ahmadi
Stanley Schade
Sascha F. Gritzbach
Kathryn Lund-Nguyen
Devita McCullough-Amal
ZIB-Report
15-52
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
MODAL-RailLab
Schade, Stanley
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/5642/ZR_15-52.pdf
5554
eng
reportzib
0
--
2015-07-10
--
Adaptive telecommunication network operation with a limited number of reconfigurations
Rising traffic in telecommunication networks lead to rising energy costs for the network operators. Meanwhile, increased flexibility of the networking hardware may help to realize load-adaptive operation of the networks to cut operation costs. To meet network operators’ concerns over stability, we propose to switch network configurations only a limited number of times per day. We present a method for the integrated computation of optimal switching times and network configurations that alternatingly solves mixed-integer programs and constrained shortest cycle problems in a certain graph. Similarly to the Branch & Bound Algorithm, it uses lower and upper bounds on the optimum value and allows for pivoting strategies to guide the computation and avoid the solution of irrelevant subproblems. The algorithm can act as a framework to be adapted and applied to suitable problems of different origin.
1438-0064
urn:nbn:de:0297-zib-55547
Frank Pfeuffer
Axel Werner
Axel Werner
ZIB-Report
15-36
eng
uncontrolled
Telecommunication
eng
uncontrolled
Network Design
eng
uncontrolled
Dynamic Traffic
eng
uncontrolled
Branch and Bound
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
SASER-Siegfried
https://opus4.kobv.de/opus4-zib/files/5554/lim-reconf-ZR.pdf
https://opus4.kobv.de/opus4-zib/files/5554/lim-reconf-ZR-v2.pdf
6551
2017
eng
ZIB-Report 17-58
reportzib
0
2017-07-11
2017-07-11
--
Parallel PIPS-SBB: Multi-Level Parallelism For Stochastic Mixed-Integer Programs
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.
1438-0064
urn:nbn:de:0297-zib-65517
Lluis-Miquel Munguia
Yuji Shinano
Geoffrey Oxberry
Deepak Rajan
Yuji Shinano
ZIB-Report
17-58
eng
uncontrolled
PIPS-SBB, UG, Parallel Branch and Bound
eng
psyndex
PIPS-SBB, UG, Parallel Branch and Bound
Mathematics of Computing
Computing Methodologies
GENERAL
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Shinano, Yuji
MODAL-SynLab
https://opus4.kobv.de/opus4-zib/files/6551/ZIB-Report-17-58.pdf
1512
deu
reportzib
0
2012-04-19
2012-04-19
--
Optimierung Technischer Kapazitäten in Gasnetzen
Die mittel- und längerfristige Planung für den Gastransport hat sich durch
Änderungen in den regulatorischen Rahmenbedingungen stark verkompliziert.
Kernpunkt ist die Trennung von Gashandel und -transport. Dieser Artikel
diskutiert die hieraus resultierenden mathematischen Planungsprobleme,
welche als Validierung von Nominierungen und Buchungen, Bestimmung der
technischen Kapazität und Topologieplanung bezeichnet werden. Diese
mathematischen Optimierungsprobleme werden vorgestellt und Lösungsansätze
skizziert.
1438-0064
urn:nbn:de:0297-zib-15121
Alexander Martin
Benjamin Hiller
Björn Geißler
Christine Hayn
Benjamin Hiller
Jesco Humpola
Thorsten Koch
Thomas Lehmann
Antonio Morsi
Marc Pfetsch
Lars Schewe
Martin Schmidt
Rüdiger Schultz
Robert Schwarz
Jonas Schweiger
Marc Steinbach
Bernhard Willert
ZIB-Report
11-56
deu
uncontrolled
Gasnetzplanung
deu
uncontrolled
Technische Kapazitäten
deu
uncontrolled
Nominierungsvalidierung
deu
uncontrolled
Buchungsvalidierung
deu
uncontrolled
Topologieplanung
Computer Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Hiller, Benjamin
Koch, Thorsten
MODAL-GasLab
ForNe
MODAL-Gesamt
Schweiger, Jonas
https://opus4.kobv.de/opus4-zib/files/1512/ZR-11-56.pdf
6384
eng
reportzib
0
--
2017-05-03
--
Conflict-Free Railway Track Assignment at Depots
Managing rolling stock with no passengers aboard is a critical component of railway operations. In particular, one problem is to park the rolling stock on a given set of tracks at the end of a day or service. Depending on the parking assignment, shunting may be required in order for a parked train to depart or for an incoming train to park. Given a collection of tracks M and a collection of trains T with fixed arrival-departure timetable, the train assignment problem (TAP) is to determine the maximum number of trains from T that can be parked on M according to the timetable and without the use of shunting. Hence, efficiently solving the TAP allows to quickly compute feasible parking schedules that do not require further shunting adjustments. In this paper, we present two integer programming models for solving the TAP. To our knowledge, this is the first integrated approach that considers track lengths along with the three most common types of parking tracks. We compare these models on a theoretical level. We also prove that a decision version of the TAP is NP-complete, justifying the use of integer programming techniques. Using stochastic and robust modelling techniques, both models produce parking assignments that are optimized and robust according to random train delays. We conclude with computational results for both models, observing that they perform well on real timetables.
1438-0064
urn:nbn:de:0297-zib-63843
Brady Gilg
Alexander Tesch
Torsten Klug
Rosemarie Martienssen
Joseph Paat
Thomas Schlechte
Christof Schulz
Sinan Seymen
Alexander Tesch
ZIB-Report
17-23
eng
uncontrolled
Depot Planning
eng
uncontrolled
Railway Track Assignment
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Klug, Torsten
Schlechte, Thomas
Schulz, Christof
MODAL-RailLab
Tesch, Alexander
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6384/ZR-17-23.pdf
6339
eng
reportzib
1
--
2017-11-04
--
Pattern Detection For Large-Scale Railway Timetables
We consider railway timetables of our industrial partner DB Fernverkehr AG that operates the ICE high speed trains in the long-distance passenger railway network of Germany. Such a timetable covers a whole year with 364 days and, typically, includes more than 45,000 trips. A rolling stock rotation plan is not created for the whole timetable at once. Instead the timetable is divided into regular invariant sections and irregular deviations (e.g. for public holidays). A separate rotation plan with a weekly period can then be provided for each of the different sections of the timetable. We present an algorithmic approach to automatically recognize these sections. Together with the supplementing visualisation of the timetable this method has shown to be very relevant for our industrial partner.
1438-0064
urn:nbn:de:0297-zib-63390
Appeared in: Proceedings of the IAROR conference RailLille 2017
Stanley Schade
Stanley Schade
Ralf Borndörfer
Matthias Breuer
Boris Grimm
Markus Reuther
Thomas Schlechte
Patrick Siebeneicher
ZIB-Report
17-17
eng
uncontrolled
railway timetables
eng
uncontrolled
visualization
eng
uncontrolled
pattern detection
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Grimm, Boris
Schlechte, Thomas
MODAL-RailLab
Schade, Stanley
MODAL-Gesamt
Reuther, Markus
https://opus4.kobv.de/opus4-zib/files/6339/ZR-17-17.pdf
6474
eng
reportzib
0
--
2017-10-08
--
Strong Relaxations for the Train Timetabling Problem using Connected Configurations
The task of the train timetabling problem or track allocation problem is to find conflict free schedules for a set of trains with predefined routes in a railway network. Especially for non-periodic instances models based on time expanded networks are often used. Unfortunately, the linear programming relaxation of these models is often extremely weak because these models do not describe combinatorial relations like overtaking possibilities very well. In this paper we extend the model by so called connected configuration subproblems. These subproblems perfectly describe feasible schedules of a small subset of trains (2-3) on consecutive track segments. In a Lagrangian relaxation approach we solve several of these subproblems together in order to produce solutions which consist of combinatorially compatible schedules along the track segments. The computational results on a mostly single track corridor taken from the INFORMS RAS Problem Solving Competition 2012 data indicate that our new solution approach is rather strong. Indeed, for this instance the solution of the Lagrangian relaxation is already integral.
1438-0064
urn:nbn:de:0297-zib-64743
Appeared in: 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)
Frank Fischer
Thomas Schlechte
Thomas Schlechte
ZIB-Report
17-46
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Schlechte, Thomas
MODAL-RailLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6474/ZR-17-46.pdf
6481
eng
reportzib
0
--
2017-08-30
--
Cost Projection Methods for the Shortest Path Problem with Crossing Costs
Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms’ performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds.
1438-0064
urn:nbn:de:0297-zib-64817
Appeared in: 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)
Marco Blanco
Thomas Schlechte
Ralf Borndörfer
Nam Dung Hoang
Anton Kaier
Pedro Maristany de las Casas
Thomas Schlechte
Swen Schlobach
ZIB-Report
17-48
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Blanco, Marco
Borndörfer, Ralf
Schlechte, Thomas
LHS-ATN
Maristany de las Casas, Pedro
https://opus4.kobv.de/opus4-zib/files/6481/ZR-17-48.pdf
1899
eng
reportzib
0
2013-07-19
2013-07-19
--
The Freight Train Routing Problem
We consider the following freight train routing problem (FTRP). Given is a
transportation network with fixed routes for passenger trains and a
set of freight trains (requests), each defined by an origin and
destination station pair. The objective is to calculate a feasible
route for each freight train such that a sum of all expected delays and
all running times is minimal. Previous research concentrated on
microscopic train routings for junctions or inside major stations. Only
recently approaches were developed to tackle larger corridors or even
networks. We investigate the routing problem from a strategic
perspective, calculating the routes in a macroscopic transportation
network of Deutsche Bahn AG. Here macroscopic refers to an aggregation of
complex real-world structures are into fewer network elements. Moreover, the
departure and arrival times of freight trains are approximated.
The problem has a strategic
character since it asks only for a coarse routing through the network
without the precise timings. We give a mixed-integer nonlinear programming~(MINLP)
formulation for FTRP, which is a multi-commodity flow model on a time-expanded
graph with additional routing constraints. The model's nonlinearities are due to
an algebraic approximation of the delays of the trains on the arcs of
the network
by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model~(MILP)
by piecewise linear approximation. The latter is solved by a state of the art MILP solver for various real-world test instances.
urn:nbn:de:0297-zib-18991
Ralf Borndörfer
Torsten Klug
Armin Fügenschuh
Torsten Klug
Thilo Schang
Thomas Schlechte
Hanno Schülldorf
ZIB-Report
13-36
eng
uncontrolled
Mixed-Integer Nonlinear Programming
eng
uncontrolled
multi-commodity flows
eng
uncontrolled
freight train routing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Fügenschuh, Armin
Klug, Torsten
Schlechte, Thomas
KOSMOS
https://opus4.kobv.de/opus4-zib/files/1899/ZR-13-36.pdf
1777
eng
reportzib
0
2013-02-16
2013-02-16
--
A New Class of Valid Inequalities for Nonlinear Network Design Problems
We consider a nonlinear nonconvex network design problem that arises in the extension of natural gas transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides flow conservation constraints in the nodes the flow must fulfill nonlinear nonconvex pressure loss constraints on the arcs subject to potential values (i.e., pressure levels) in both end nodes of each arc. Assume that there does not exist a feasible flow that fulfills all physical constraints and meets the desired entry and exit amounts. Then a natural question is where to extend the network by adding pipes in the most economic way such that this flow becomes feasible. Answering this question is computationally demanding because of the difficult problem structure. We use mixed-integer nonlinear programming techniques that rely on an outer approximation of the overall problem, and a branching on decision variables. We formulate a new class of valid inequalities (or cutting planes) which reduce the overall solution time when added to the formulation. We demonstrate the computational merits of our approach on test instances.
1438-0064
urn:nbn:de:0297-zib-17771
10.1007/s00291-015-0390-2
Appeared in: OR Spectrum 2015
Jesco Humpola
Armin Fügenschuh
Armin Fügenschuh
ZIB-Report
13-06
eng
uncontrolled
Network Design
eng
uncontrolled
Mixed-Integer Nonlinear Programming
eng
uncontrolled
Cutting Planes
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Fügenschuh, Armin
MODAL-GasLab
ForNe
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/1777/FuegenschuhHumpola2012__dual_var_cuts.pdf
https://opus4.kobv.de/opus4-zib/files/1777/ZR-13-06revisedversion.pdf
1686
eng
reportzib
0
2012-11-27
2012-11-27
--
Mixed-Integer Linear Methods for Layout-Optimization of Screening Systems in Recovered Paper Production
The industrial treatment of waste paper in order to regain valuable
fibers from which recovered paper can be produced, involves several
steps of preparation. One important step is the separation of stickies
that are normally attached to the paper. If not properly separated,
remaining stickies reduce the quality of the recovered paper or even
disrupt the production process. For the mechanical separation process
of fibers from stickies a separator screen is used. This machine has
one input feed and two output streams, called the accept and the
reject. In the accept the fibers are concentrated, whereas the reject
has a higher concentration of stickies. The machine can be controlled
by setting its reject rate. But even when the reject rate is set
properly, after just a single screening step, the accept still has too
many stickies, or the reject too many fibers. To get a proper
separation, several separators have to be assembled into a
network. From a mathematical point of view this problem can be seen as
a multi-commodity network flow design problem with a nonlinear,
controllable distribution function at each node. We present a
nonlinear mixed-integer programming model for the simultaneous
selection of a subset of separators, the network's topology, and the
optimal setting of each separator.
Numerical results are obtained via
different types of linearization of the nonlinearities and the use of
mixed-integer linear solvers, and compared with state-of-the-art
global optimization software.
1438-0064
urn:nbn:de:0297-zib-16862
Armin Fügenschuh
Armin Fügenschuh
Christine Hayn
Dennis Michaels
ZIB-Report
12-44
eng
uncontrolled
Mixed-Integer Linear Programming
eng
uncontrolled
Nonlinear Programming
eng
uncontrolled
Piecewise Linear Approximation
eng
uncontrolled
Topology Optimization
eng
uncontrolled
Network Design
Computer Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Fügenschuh, Armin
https://opus4.kobv.de/opus4-zib/files/1686/ZR-12-44.pdf
1794
eng
reportzib
0
2013-03-04
2013-03-04
--
A Direct Comparison of Physical Block Occupancy Versus Timed Block Occupancy in Train Timetabling Formulations
Two fundamental mathematical formulations for railway timetabling are compared on a common set of sample problems, representing both multiple track high density services in Europe and single track bidirectional operations in North America. One formulation, ACP, enforces against conflicts by constraining time intervals between trains, while the other formulation, HGF, monitors physical occupation of controlled track segments. The results demonstrate that both ACP and HGF return comparable solutions in the aggregate, with some significant differences in select instances, and a pattern of significant differences in performance and constraint enforcement overall.
1438-0064
urn:nbn:de:0297-zib-17946
10.1016/j.tre.2013.04.003
To appear in: Transportation Research Part E: Logistics and Transportation Review.
Steven Harrod
Thomas Schlechte
Thomas Schlechte
ZIB-Report
13-18
eng
uncontrolled
Railway Scheduling
eng
uncontrolled
Train Timetabling
eng
uncontrolled
Track Allocation
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Schlechte, Thomas
https://opus4.kobv.de/opus4-zib/files/1794/ZR-13-18.pdf
1650
eng
reportzib
0
2012-11-15
2012-11-15
--
Stochastic dominance analysis of Online Bin Coloring algorithms
This paper proposes a new method for probabilistic analysis of online algorithms. It is based on the notion of stochastic dominance. We develop the method for
the online bin coloring problem introduced by Krumke et al (2008). Using methods for the stochastic
comparison of Markov chains we establish the result that the performance of the online algorithm GreedyFit is stochastically better than the performance of the algorithm OneBin for any number of items processed. This result gives a more realistic
picture than competitive analysis and explains the behavior observed in simulations.
1438-0064
urn:nbn:de:0297-zib-16502
Benjamin Hiller
Benjamin Hiller
Tjark Vredeveld
ZIB-Report
12-42
eng
uncontrolled
online algorithms, stochastic dominance, algorithm analysis, Markov chains
PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX)
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Hiller, Benjamin
MATHEON-B14:Comb-Log
https://opus4.kobv.de/opus4-zib/files/1650/ZR-12-42.pdf
1814
eng
reportzib
0
2013-04-23
2013-04-23
--
System Dynamic Optimization in the Sustainability Assessment of a World-Model
The System Dynamics (SD) methodology is a framework for modeling and simulating
the dynamic behavior of socioeconomic systems. Characteristic for the
description of such systems is the occurrence of feedback loops together with
stocks and flows. The mathematical equations that describe the system are
usually nonlinear. Therefore seemingly simple systems can show a nonintuitive,
nonpredictable behavior over time. Controlling a dynamical system means to
define a desired final state in which the system should be, and to specify
potential interventions from outside that should keep the system on the right
track. The central question is how to compute such globally optimal control for
a given SD model. We propose a branch-and-bound approach that is based on a
bound propagation method, primal heuristics, and spatial branching. We apply our
new SD-control method to a small System Dynamics model, that describes the
evolution of a social-economic system over time. We examine the problem of
steering this system on a sustainable consumption path.
1438-0064
urn:nbn:de:0297-zib-18148
http://opus4.kobv.de/opus4-tuberlin/frontdoor/index/index/docId/4026
Appeared in: Proceedings of the 11th Global Conference on Sustainable Manufacturing (GCSM2013), G. Seliger (Hrsg.), Universitätsverlag der TU Berlin, Seite 582 -- 587
Armin Fügenschuh
Armin Fügenschuh
Ingmar Vierhaus
ZIB-Report
13-23
eng
uncontrolled
System Dynamics; Mixed-Integer Nonlinear Optimization
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Fügenschuh, Armin
CRC1026
https://opus4.kobv.de/opus4-zib/files/1814/ZR-13-23.pdf
1806
eng
reportzib
0
2013-04-18
2013-04-18
--
Integer Programming and Sports Rankings
Sports rankings are obtained by applying a system of rules to evaluate the
performance of the participants in a competition.
We consider rankings that result from assigning an ordinal rank to each
competitor according to their performance.
We develop an integer programming model for rankings that allows us
to calculate the number of points needed to guarantee
a team the ith position, as well as the minimum number of points
that could yield the ith place.
The model is very general and can thus be applied to many types of sports.
We discuss examples coming from football (soccer), ice hockey, and
Formula~1. We answer various questions and debunk a few myths along the way.
Are 40 points enough to avoid relegation in the Bundesliga?
Do 95 points guarantee the participation of a team in the NHL playoffs?
Moreover, in the season restructuration currently under consideration in the NHL,
will it be easier or harder to access the playoffs?
Is it possible to win the Formula~1 World Championship without winning at least one race
or without even climbing once on the podium?
Finally, we observe that the optimal solutions of the aforementioned model
are associated to extreme situations which are unlikely to happen. Thus,
to get closer to realistic scenarios, we enhance the model by adding some
constraints inferred from the results of the previous years.
1438-0064
urn:nbn:de:0297-zib-18068
10.1515/jqas-2013-0111
Christian Raack
Thomas Schlechte
Annie Raymond
Axel Werner
Thomas Schlechte
ZIB-Report
13-19
eng
uncontrolled
sport ranking
eng
uncontrolled
integer programming
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Schlechte, Thomas
https://opus4.kobv.de/opus4-zib/files/1806/ZR-13-19.pdf
5347
2015
2015
eng
reportzib
1
2015-01-22
2015-01-22
--
G-RIPS 2014 RailLab - Towards robust rolling stock rotations
The Graduate-Level Research in Industrial Projects (G-RIPS) Program provides an
opportunity for high-achieving graduate-level students to work in teams on a
real-world research project proposed by a sponsor from industry or the public
sector. Each G-RIPS team consists of four international students (two from
the US and two from European universities), an academic mentor, and an industrial sponsor.
This is the report of the Rail-Lab project on the definition and integration of
robustness aspects into optimizing rolling stock schedules. In general, there is
a trade-off for complex systems between robustness and efficiency. The ambitious
goal was to explore this trade-off by implementing numerical simulations and
developing analytic models.
In rolling stock planning a very large set of industrial railway requirements,
such as vehicle composition, maintenance constraints, infrastructure capacity,
and regularity aspects, have to be considered in an integrated model. General
hypergraphs provide the modeling power to tackle those requirements.
Furthermore, integer programming approaches are able to produce high quality
solutions for the deterministic problem.
When stochastic time delays are considered, the mathematical programming problem
is much more complex and presents additional challenges. Thus, we started with a
basic variant of the deterministic case, i.e., we are only considering
hypergraphs representing vehicle composition and regularity.
We transfered solution approaches for robust optimization
from the airline industry to the setting of railways and attained a
reasonable measure of robustness. Finally, we present and discuss different
methods to optimize this robustness measure.
1438-0064
urn:nbn:de:0297-zib-53475
ZIB-Report 14-34
Charles Brett
Thomas Schlechte
Rebecca Hoberg
Meritxell Pacheco
Kyle Smith
Ralf Borndörfer
Ricardo Euler
Gerwin Gamrath
Boris Grimm
Olga Heismann
Markus Reuther
Thomas Schlechte
Alexander Tesch
ZIB-Report
14-34
eng
uncontrolled
robust optimization, rolling stock planning
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Euler, Ricardo
Grimm, Boris
Schlechte, Thomas
MODAL-RailLab
Tesch, Alexander
MODAL-Gesamt
Reuther, Markus
https://opus4.kobv.de/opus4-zib/files/5347/ZR-14-34.pdf
4267
eng
reportzib
0
2013-10-03
2013-10-03
--
Biobjective Optimization of Radio Access Technology Selection and Resource Allocation in Heterogeneous Wireless Networks
We propose a novel optimization model for resource assignment in heterogeneous wireless network. The model adopts two objective functions maximizing the number of served users and the minimum granted utility at once. A distinctive feature of our new model is to consider two consecutive time slots, in order to include handover as an additional decision dimension.
Furthermore, the solution algorithm that we propose refines a heuristic solution approach recently proposed in literature, by considering a real joint optimization of the considered resources. The simulation study shows that the new model leads to a significant reduction in handover frequency, when compared to a traditional scheme based on maximum SNR.
1438-0064
urn:nbn:de:0297-zib-42675
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6576416&isnumber=6576384
Appeared in: Proceedings of the 11th International Symposium on Modeling & Optimization in Mobile, Ad Hoc & Wireless Networks (WiOpt 2013) - RAWNET/WNC3’13, pp.652-658, 13-17 May 2013, Tsukuba Science City, Japan
Anna Zakrzewska
Fabio D'Andreagiovanni
Fabio D'Andreagiovanni
Sarah Ruepp
Michael S. Berger
ZIB-Report
13-63
eng
uncontrolled
Heterogeneous Wireless Networks, Biobjective Optimization, Mixed Integer Linear Programming, Simulation
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
INFORMATION AND COMMUNICATION, CIRCUITS
Mathematical Optimization
Mathematics of Telecommunication
https://opus4.kobv.de/opus4-zib/files/4267/ZR-13-63.pdf
4293
eng
reportzib
0
2013-10-22
2013-10-22
--
A Global Approach to the Control of an Industry Structure System Dynamics Model
We consider a system dynamics model that describes the effect of human activity on natural resources. The central stocks are the accumulated profit, the industry structures, and the water resources. The model can be controlled through two time-dependent parameters. The goal in this paper is to find a parameter setting that leads to a maximization of a performance index, which reflects both environmental and economic aspects. Thus, the goal is to identify the most sustainable stock of industry structures within the model's constraints and assumptions. In order to find a proven global optimal parameter set, we formulate the System Dynamics Optimization model as a mixed-integer nonlinear problem that is accessible for numerical solvers. Due to the dynamic structure of the model, certain steps of the solution process must be handled with greater care, compared to standard non-dynamic problems. We describe our approach of solving the industry structure model and present computational results. In addition, we discuss the limitations of the approach and next steps.
1438-0064
urn:nbn:de:0297-zib-42932
Armin Fügenschuh
Armin Fügenschuh
Stefan N. Grösser
Ingmar Vierhaus
ZIB-Report
13-67
eng
uncontrolled
System Dynamics; Mixed-Integer Nonlinear Optimization
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
SYSTEMS THEORY; CONTROL (For optimal control, see 49-XX)
Mathematical Optimization
Fügenschuh, Armin
CRC1026
https://opus4.kobv.de/opus4-zib/files/4293/ZR-13-67.pdf
4265
eng
reportzib
0
2013-10-03
2013-10-03
--
Scheduling technology migration in WDM Networks
The rapid technological evolution of telecommunication networks demands service providers to regularly update their technology, with the aim of remaining competitive in the marketplace. However, upgrading the technology in a network is not a trivial task. New hardware components need to be installed in the network and during the installation network connectivity may be temporarily compromised. The Wavelength Division Multiplexing (WDM) technology, whose upgrade is considered in here, shares fiber links among several optical connections and tearing down a single link may disrupt several optical connections at once. When the upgrades involve large parts of a network, typically not all links can be upgraded in parallel, which may lead to an unavoidable longer disruption of some connections. A bad scheduling of the overall endeavor, however, can dramatically increase the disconnection time of parts of the networks, causing extended service disruption. In this contribution, we study the problem of finding a schedule of the fiber link upgrades that minimizes the total service disruption time. To the best of our knowledge, this problem has not yet been formalized and investigated. The aim of our work is to close this gap by presenting a mathematical optimization model for the problem and an innovative solution algorithm that tackles the intrinsic difficulties of the problem. Computational experience on realistic instances completes our study. Our original investigations have been driven by real needs of DFN, operator of the German National Research and Education Network and our partner in the BMBF research project ROBUKOM (http://www.robukom.de/).
1438-0064
urn:nbn:de:0297-zib-42654
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6507677&isnumber=6507670
Appeared in: Proceedings of the 14th ITG Symposium on Photonic Networks 2013, pp. 1-5, 6-7 May 2013, Leipzig, Germany
Andreas Bley
Fabio D'Andreagiovanni
Fabio D'Andreagiovanni
Daniel Karch
ZIB-Report
13-62
eng
uncontrolled
Scheduling, Extended Formulations, Network Migration, WDM Networks
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Telecommunication
https://opus4.kobv.de/opus4-zib/files/4265/ZR-13-62.pdf
4264
eng
reportzib
0
2013-10-03
2013-10-03
--
A new theoretical framework for Robust Optimization under multi-band uncertainty
We provide an overview of our main results about studying Linear Programming Problems whose coefficient matrix is subject to uncertainty and the uncertainty is modeled through a multi-band set. Such an uncertainty set generalizes the classical one proposed by Bertsimas and Sim and is particularly suitable in the common case of arbitrary non-symmetric distributions of the parameters. Our investigations were inspired by practical needs of our industrial partner in ongoing projects with focus on the design of robust telecommunications networks.
1438-0064
urn:nbn:de:0297-zib-42644
http://www.springer.com/business+%26+management/operations+research/book/978-3-319-00794-6
10.1007/978-3-319-00795-3_17
To appear in Operations Research Proceedings 2012 - Selected Papers of the International Annual Conference of the German Operations Research Society (GOR), Leibniz University of Hannover, Germany, September 5-7, 2012, Helber, S. et al. (Eds.), Springer, Heidelberg.
Christina Büsing
Fabio D'Andreagiovanni
Fabio D'Andreagiovanni
ZIB-Report
13-61
eng
uncontrolled
Robust Optimization, Uncertainty Set, Multiband Robustness, Network Design
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Telecommunication
https://opus4.kobv.de/opus4-zib/files/4264/ZR-13-61.pdf
4271
eng
reportzib
0
2013-10-15
2013-10-15
--
Analysis of Micro-Macro Transformations of Railway Networks
A common technique in the solution of large or complex optimization problems is the use of micro-macro transformations. In this paper, we carry out a theoretical analysis of such transformations for the track allocation problem in railway networks. We prove that the cumulative rounding technique of Schlechte et al. satisfies two of three natural optimality criteria and that this performance cannot be improved. We also show that under extreme circumstances, this technique can perform inconvieniently by underestimating the global optimal value.
urn:nbn:de:0297-zib-42710
Marco Blanco
Thomas Schlechte
Thomas Schlechte
ZIB-Report
13-65
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Blanco, Marco
Schlechte, Thomas
KOSMOS
Trassenbörse
https://opus4.kobv.de/opus4-zib/files/4271/ZR-13-65.pdf
6648
2017
eng
74
masterthesis
0
--
--
--
Mixed-Integer Programming for Clustering in Non-reversible Markov Processes
The topic of this thesis is the examination of an optimization model
which stems from the clustering process of non-reversible markov processes.
We introduce the cycle clustering problem und formulate it as a mixed
integer program (MIP).
We prove that this problem is N P-hard and discuss polytopal aspects
such as facets and dimension. The focus of this thesis is the development of
solving methods for this clustering problem. We develop problem specific
primal heuristics, as well as separation methods and an approximation
algorithm. These techniques are implemented in practice as an application
for the MIP solver SCIP.
Our computational experiments show that these solving methods result
in an average speedup of ×4 compared to generic solvers and that our
application is able to solve more instances to optimality within the given
time limit of one hour.
urn:nbn:de:0297-zib-66486
Thorsten Koch
Leon Eifler
Leon Eifler
eng
uncontrolled
Markov State Models
eng
uncontrolled
NESS
eng
uncontrolled
Non-reversible Markov Processes
eng
uncontrolled
Mixed-Integer Programming
PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX)
STATISTICAL MECHANICS, STRUCTURE OF MATTER
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Eifler, Leon
SparseApproxiTN
Technische Universität Berlin
https://opus4.kobv.de/opus4-zib/files/6648/main.pdf
6393
2017
eng
reportzib
0
2017-05-05
2017-05-05
--
A Propagation Approach to Acyclic Rolling Stock Rotation Optimization
The rolling stock, i.e., railway vehicles, are one of the key ingredients of a running railway system. As it is well known, the offer of a railway company to their customers, i.e., the railway timetable, changes from time to time. Typical reasons for that are different timetables associated with different seasons, maintenance periods or holidays. Therefore, the regular lifetime of a timetable is split into (more or less) irregular periods where parts of the
timetable are changed. In order to operate a railway timetable most railway companies set up sequences that define the operation of timetabled trips by a single physical railway vehicle called (rolling stock) rotations. Not surprisingly, the individual parts of a timetable also affect the rotations. More precisely, each of the parts brings up an acyclic rolling stock rotation problem with start and end conditions associated with the beginning and ending of the corresponding period. In this paper, we propose a propagation approach to deal with large planning horizons that are composed of many timetables with shorter individual lifetimes. The approach is based on an integer linear programming formulation that propagates rolling stock rotations through the irregular parts of the timetable while taking a large variety of operational requirements into account. This approach is implemented within the rolling stock rotation optimization framework ROTOR used by DB Fernverkehr AG, one of the leading railway operators in Europe. Computational results for real world scenarios are presented to evaluate the approach.
1438-0064
urn:nbn:de:0297-zib-63930
Appeared in: Proceedings of the IAROR conference RailLille 2017
Boris Grimm
Boris Grimm
Ralf Borndörfer
Markus Reuther
Stanley Schade
Thomas Schlechte
ZIB-Report
17-24
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Transportation and Logistics
Borndörfer, Ralf
Grimm, Boris
Schlechte, Thomas
MODAL-RailLab
Schade, Stanley
MODAL-Gesamt
Reuther, Markus
https://opus4.kobv.de/opus4-zib/files/6393/ZR-17-24.pdf
6611
eng
reportzib
0
--
2017-12-13
--
Conflict Driven Diving for Mixed Integer Programming
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.
1438-0064
urn:nbn:de:0297-zib-66116
Jakob Witzig
Jakob Witzig
ZIB-Report
17-69
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Witzig, Jakob
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6611/ZR-17-49-revised.pdf
1489
eng
239
doctoralthesis
Südwestdeutscher Verlag für Hochschulschriften
Saarbrücken, Germany
0
2012-03-21
2012-03-21
2012-02-15
Railway Track Allocation: Models and Algorithms
This thesis is about mathematical optimization for the efficient use of railway infrastructure. We address the
optimal allocation of the available railway track capacity - the track allocation problem.
This track allocation problem is a major challenge for a railway company, independent of
whether a free market, a private monopoly, or a public monopoly is given.
Planning and operating railway transportation systems is extremely hard due
to the combinatorial complexity of the underlying discrete optimization problems,
the technical intricacies, and the immense sizes of the problem instances. Mathematical models and optimization
techniques can result in huge gains for both railway customers and operators, e.g.,
in terms of cost reductions or service quality improvements.
We tackle this challenge by developing novel mathematical models and associated innovative algorithmic
solution methods for large scale instances. This allows us to produce for the first time reliable
solutions for a real world instance, i.e., the Simplon corridor in Switzerland.
The opening chapter gives a comprehensive overview on railway planning problems.
This provides insights into the regulatory and technical framework,
it discusses the interaction of several planning steps, and identifies optimization potentials in
railway transportation. The remainder of the thesis is comprised of two major parts.
The first part is concerned with modeling railway systems to allow for resource and capacity analysis.
Railway capacity has basically two dimensions, a space dimension which are the physical
infrastructure elements as well as a time dimension that refers to the train movements, i.e.,
occupation or blocking times, on the physical infrastructure. Railway safety systems operate
on the same principle all over the world. A train has to reserve infrastructure blocks for some time to pass through.
Two trains reserving the same block of the infrastructure within the same point in time is called block conflict.
Therefore, models for railway capacity involve the definition
and calculation of reasonable running and associated reservation and
blocking times to allow for a conflict free allocation.
In the second and main part of the thesis, the optimal track
allocation problem for macroscopic models of the railway system is considered.
The literature for related problems is surveyed.
A graph-theoretic model for the track allocation problem is
developed. In that model optimal track allocations correspond to
conflict-free paths in special time-expanded graphs.
Furthermore, we made considerable progress on solving track allocation problems by two
main features - a novel modeling approach for the macroscopic track
allocation problem and algorithmic improvements based on the
utilization of the bundle method.
Finally, we go back to practice and present in the last chapter several case
studies using the tools netcast and tsopt.
We provide a computational comparison of
our new models and standard packing models used in the literature.
Our computational experience indicates that our approach, i.e.,
``configuration models'', outperforms other models. Moreover, the rapid branching
heuristic and the bundle method enable us to produce high quality solutions for very large scale
instances, which has not been possible before.
In addition, we present results for a theoretical and rather visionary auction framework
for track allocation. We discuss several auction design questions and analyze experiments of
various auction simulations.
The highlights are results for the Simplon corridor in Switzerland.
We optimized the train traffic through this tunnel using our models and
software tools.
To the best knowledge of the author and confirmed by several railway
practitioners this was the first time that fully automatically produced
track allocations on a macroscopic scale fulfill the requirements
of the originating microscopic model, withstand the evaluation in the
microscopic simulation tool OpenTrack, and exploit the infrastructure capacity.
This documents the success of our approach in practice and the usefulness
and applicability of mathematical optimization to railway track allocation.
978-3-8381-3222-8
http://opus.kobv.de/tuberlin/volltexte/2012/3427/pdf/schlechte_thomas.pdf
urn:nbn:de:kobv:83-opus-34272
Prof.Dr.Dr.h.c.mult. Martin Grötschel
Thomas Schlechte
Thomas Schlechte
eng
uncontrolled
railway track allocation
eng
uncontrolled
large-scale integer programming
eng
uncontrolled
network aggregation
eng
uncontrolled
rapid branching
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Dissertationen
Mathematical Optimization
Schlechte, Thomas
Technische Universität Berlin
Technische Universität Berlin
https://opus4.kobv.de/opus4-zib/files/1489/thesisFinal.pdf
4233
eng
81
masterthesis
0
2013-09-04
2013-09-04
2013-06-07
Optimizing control in a transportation network when users may choose their OD-path
This thesis represents a game-theoretic investigation of the allocation of inspectors in a transportation network, comparing Nash and Stackelberg equilibrium strategies to a strategy in which inspections are conducted proportionally to the traffic volume. It contains specifications for the integration of space and time dependencies and extensive experimental tests for the application on the transportation network of German motorways using real data. Main results are that - although the formulated spot-checking game is not zero-sum - we are able to compute a Nash equilibrium using linear programming and secondly, that experimental results yield that a Nash equilibrium strategy represents a good trade-off for the Stackelberg equilibrium strategy between efficiency of controls and computation time.
urn:nbn:de:0297-zib-42330
Martin Grötschel
Julia Buwaya
Julia Buwaya
Ralf Borndörfer
eng
uncontrolled
Optimization
eng
uncontrolled
Transportation Network
eng
uncontrolled
Game Theory
eng
uncontrolled
Stackelberg Equilibrium
eng
uncontrolled
Mixed Integer Programming
eng
uncontrolled
Security Game
eng
uncontrolled
Linear Programming
eng
uncontrolled
Nash Equilibrium
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Studienabschlussarbeiten
Mathematical Optimization
Zuse Institute Berlin (ZIB)
Technische Universität Berlin
https://opus4.kobv.de/opus4-zib/files/4233/buwaya_diplomarbeit_online.pdf
5348
2015
eng
reportzib
0
--
--
--
Sufficient Pruning Conditions for MINLP in Gas Network Design
One quarter of Europe’s energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi billion Euro business. Therefore, automatic planning tools that support the decision process are desired. We model the topology extension problem in gas networks by a mixed-integer nonlinear program (MINLP). This gives rise to a so-called active transmission problem, a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by ﬁxing all integral variables. In this article we offer novel sufficient conditions for proving the infeasibility of this active transmission problem. These conditions can be expressed in the form of a mixed-integer program (MILP), i.e., the infeasibility of a non-convex NLP can be certiﬁed by solving an MILP. These results provide an efficient bounding procedure in a branch-and-bound algorithm. Our computational results demonstrate a substantial speed-up for the necessary computations.
urn:nbn:de:0297-zib-53489
10.1007/s13675-016-0077-8
Appeared in: EURO Journal on Computational Optimization
Jesco Humpola
Jesco Humpola
ZIB-Report
15-04
eng
uncontrolled
Network Design
deu
uncontrolled
Mixed-Integer Nonlinear Programming
deu
uncontrolled
Infeasibility Detection
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
MODAL-GasLab
ForNe
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/5348/ZR-15-04.pdf
4311
eng
reportzib
0
2013-11-21
2013-11-21
--
A Primal Heuristic for MINLP based on Dual Information
We present a novel heuristic algorithm to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network's capacity to a desired level in a cost-efficient way. We solve this problem in a linear programming based branch-and-cut approach, where we deal with the nonlinearities by linear outer approximation and spatial branching. At certain nodes of the branching tree, we compute a KKT point for a nonlinear relaxation. Based on the information from the KKT point we alter some of the integer variables in a locally promising way. We describe this heuristic for general MINLPs and then show how to tailor the heuristic to exploit our problem-specific structure. On a test set of real-world instances, we are able to increase the chance of identifying feasible solutions by some order of magnitude compared to standard MINLP heuristics that are already built in the general-purpose MINLP solver SCIP.
1438-0064
urn:nbn:de:0297-zib-43110
10.1007/s13675-014-0029-0
Appeared under the title "A primal heuristic for optimizing the topology of gas networks based on dual information" in: EURO Journal on Computational Optimization 2014
Jesco Humpola
Armin Fügenschuh
Armin Fügenschuh
Thomas Lehmann
ZIB-Report
13-49
eng
uncontrolled
Mixed-Integer Nonlinear Programming
eng
uncontrolled
Relaxations
eng
uncontrolled
Heuristics
eng
uncontrolled
Duality
eng
uncontrolled
Nonlinear Network Design Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Fügenschuh, Armin
MODAL-GasLab
ForNe
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/4311/ZR-13-49.pdf
4255
eng
reportzib
0
2013-09-25
2013-09-25
--
Network Planning under Demand Uncertainty with Robust Optimization
The planning of a communication network is inevitably depending on the quality of both the planning tool and the demand forecast used. In this article, we show exemplarily how the emerging area of Robust Optimization can advance the network planning by a more accurate mathematical description of the demand uncertainty. After a general introduction of the concept and its application to a basic network design problem, we present two applications: multi-layer and mixed-line-rate network design. We conclude with a discussion of extensions of the robustness concept to increase the accuracy of handling uncertainties.
1438-0064
urn:nbn:de:0297-zib-42557
10.1109/MCOM.2014.6736760
Accepted for publication in IEEE Communications Magazine, special issue Advances in Network Planning, on September 8th 2013
Thomas Bauschert
Fabio D'Andreagiovanni
Christina Büsing
Fabio D'Andreagiovanni
Arie M. C. A. Koster
Manuel Kutschka
Uwe Steglich
ZIB-Report
13-59
eng
uncontrolled
Network Design, Demand Uncertainty, Robust Optimization, Telecommunications
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Telecommunication
https://opus4.kobv.de/opus4-zib/files/4255/ZR-13-59.pdf
4256
eng
reportzib
0
2013-09-26
2013-09-26
--
Re-optimization of Rolling Stock Rotations
The Rolling Stock Rotation Problem is to schedule rail vehicles in order to cover timetabled trips by a cost optimal set of vehicle rotations. The problem integrates several facets of railway optimization, i.e., vehicle composition, maintenance constraints, and regularity aspects.
In industrial applications existing schedules often have to be re-optimized to integrate timetable changes or construction sites.
We present an integrated modeling and algorithmic approach for this task as well as computational results for industrial problem instances of DB Fernverkehr AG.
1438-0064
urn:nbn:de:0297-zib-42569
10.1007/978-3-319-07001-8_8
Ralf Borndörfer
Thomas Schlechte
Julika Mehrgardt
Markus Reuther
Thomas Schlechte
Kerstin Waas
ZIB-Report
13-60
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Schlechte, Thomas
MODAL-RailLab
MODAL-Gesamt
Reuther, Markus
https://opus4.kobv.de/opus4-zib/files/4256/ZR.pdf
1787
eng
reportzib
0
2013-03-20
2013-03-20
--
Reoptimization in branch-and-bound algorithms with an application to elevator control
We consider reoptimization (i.e. the solution of a problem based on information available from solving a similar problem) for branch-and-bound algorithms and propose a generic framework to construct a reoptimizing branch-and-bound algorithm.
We apply this to an elevator scheduling algorithm solving similar subproblems to generate columns using branch-and-bound. Our results indicate that reoptimization techniques can substantially reduce the running times of the overall algorithm.
1438-0064
urn:nbn:de:0297-zib-17876
10.1007/978-3-642-38527-8_33
Appeared in: Proceedings of the 12th International Symposium on Experimental Algorithms, 2013, LNCS 7933, pp. 378-389
Benjamin Hiller
Benjamin Hiller
Torsten Klug
Jakob Witzig
ZIB-Report
13-15
eng
uncontrolled
reoptimization
eng
uncontrolled
branch-and-bound
eng
uncontrolled
column generation
eng
uncontrolled
elevator control
Computer Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Hiller, Benjamin
Klug, Torsten
Witzig, Jakob
https://opus4.kobv.de/opus4-zib/files/1787/ZR-13-15.pdf
1862
eng
reportzib
0
2013-05-30
2013-05-30
--
Towards optimizing the deployment of optical access networks
In this paper we study the cost-optimal deployment of optical access networks considering variants of the problem such as fiber to the home (FTTH), fiber to the building (FTTB), fiber to the curb (FTTC), or fiber to the neighborhood (FTTN). We identify the combinatorial structures of the most important sub-problems arising in this area and model these, e.g., as capacitated facility location, concentrator location, or Steiner tree problems. We discuss modeling alternatives as well. We finally construct a “unified” integer programming model that combines all sub-models and provides a global view of all these FTTx problems. We also summarize computational studies of various special cases.
1438-0064
urn:nbn:de:0297-zib-18627
10.1007/s13675-013-0016-x
Martin Grötschel
Axel Werner
Christian Raack
Axel Werner
ZIB-Report
13-11
eng
uncontrolled
FTTx, FTTH, FTTB, FTTC, FTTN, telecommunications, access networks, passive optical networks, network design, routing, energy efficiency
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Grötschel, Martin
https://opus4.kobv.de/opus4-zib/files/1862/fttx-zib-report.pdf
https://opus4.kobv.de/opus4-zib/files/1862/ZR-13-11revisedversion.pdf
1885
eng
reportzib
0
2013-07-01
2013-07-01
--
A Unified View on Relaxations for a Nonlinear Network Flow Problem
We consider a nonlinear nonconvex network flow problem that arises, for example, in natural gas or water transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides flow conservation constraints in the nodes the flow must fulfill nonlinear nonconvex pressure loss constraints on the arcs subject to potential values (i.e., pressure levels) in both end nodes of each arc. The problem is how to numerically compute this flow and pressures. We review an existing approach of Maugis (1977) and extend it to the case of networks with active elements (for example, compressors). We further examine different ways of relaxations for the nonlinear network flow model. We compare different approaches based on nonlinear optimization numerically on a set of test instances.
urn:nbn:de:0297-zib-18857
Armin Fügenschuh
Armin Fügenschuh
Jesco Humpola
ZIB-Report
13-31
eng
uncontrolled
Nonlinear Network Flow
eng
uncontrolled
Mixed-Integer Nonlinear Programming
eng
uncontrolled
Relaxations
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Fügenschuh, Armin
MODAL-GasLab
ForNe
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/1885/ZR-13-31.pdf
1860
eng
reportzib
0
2013-05-27
2013-05-27
--
A Global Approach to the Optimal Control of System Dynamics Models
The System Dynamics (SD) methodology is a framework for modeling and simulating the dynamic behavior of socioeconomic systems. Characteristic for the description of such systems is the occurrence of feedback loops together with stocks and flows. The mathematical equations that describe the system are usually ordinary differential equations and nonlinear algebraic constraints. Therefore seemingly simple systems can show a nonintuitive, unpredictable behavior over time. Controlling a dynamical system means to specify potential interventions from outside that should keep the system on the desired track, and to define an evaluation schema to compare different controls among each other, so that a "best" control can be defined in a meaningful way. The central question is how to compute such globally optimal control for a given SD model, that allows the transition of the system into a desired state with minimum effort. We propose a mixed-integer nonlinear programming (MINLP) reformulation of the System Dynamics Optimization (SDO) problem. MINLP problems can be solved by linear programming based branch-and-bound approach. We demonstrate that standard MINLP solvers are not able to solve SDO problem. To overcome this obstacle, we introduce a special-tailored bound propagation method. We apply our new method to a predator-prey model with additional hunting activity as control, and to a mini-world model with the consumption level as control. Numerical results for these test cases are presented.
1438-0064
urn:nbn:de:0297-zib-18600
Armin Fügenschuh
Armin Fügenschuh
Ingmar Vierhaus
ZIB-Report
13-28
eng
uncontrolled
System Dynamics
eng
uncontrolled
Global Optimal Control
eng
uncontrolled
Mixed-Integer Nonlinear Optimization
eng
uncontrolled
Bounds Strengthening
ORDINARY DIFFERENTIAL EQUATIONS
DYNAMICAL SYSTEMS AND ERGODIC THEORY [See also 26A18, 28Dxx, 34Cxx, 34Dxx, 35Bxx, 46Lxx, 58Jxx, 70-XX]
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Fügenschuh, Armin
https://opus4.kobv.de/opus4-zib/files/1860/ZR-13-28.pdf
1815
eng
reportzib
0
2013-04-23
2013-04-23
--
A System Dynamic Enhancement for the Scenario Technique
The Scenario Technique is a strategic planning method that aims to describe and analyze potential developments of a considered system in the future. Its application consists of several steps, from an initial problem analysis over an influence analysis to projections of key factors and a definition of the scenarios to a final interpretation of the results. The technique itself combines qualitative and quantitative methods and is an enhancement of the standard Scenario Technique. We use the numerical values gathered during the influence analysis, and embed them in a System Dynamics framework. This yields a mathematically rigorous way to achieve predictions of the system‘s future behavior from an initial impulse and the feedback structure of the factors. The outcome of our new method is a further way of projecting the present into the future, which enables the user of the Scenario Technique to obtain a validation of the results achieved by the standard method.
1438-0064
urn:nbn:de:0297-zib-18150
http://opus4.kobv.de/opus4-tuberlin/frontdoor/index/index/docId/4026
Appeared in: Proceedings of the 11th Global Conference on Sustainable Manufacturing (GCSM2013), G. Seliger (Hrsg.), Universitätsverlag der TU Berlin, Seite 613 -- 618
Achim Brose
Armin Fügenschuh
Armin Fügenschuh
Pia Gausemeier
Ingmar Vierhaus
Günther Seliger
ZIB-Report
13-24
eng
uncontrolled
Scenario Technique; System Dynamics
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Fügenschuh, Armin
CRC1026
https://opus4.kobv.de/opus4-zib/files/1815/ZR-13-24.pdf
1861
eng
reportzib
0
2013-05-30
2013-05-30
--
On the Two-Architecture Connected Facility Location Problem
We introduce a new variant of the connected facility location problem that allows for modeling mixed deployment strategies (FTTC/FTTB/FTTH) in the design of local access telecommunication networks. Several mixed integer programming models and valid inequalities are presented. Computational studies on realistic instances from three towns in Germany are provided.
1438-0064
urn:nbn:de:0297-zib-18610
Markus Leitner
Axel Werner
Ivana Ljubic
Markus Sinnl
Axel Werner
ZIB-Report
13-29
eng
uncontrolled
Connected Facility Location, Branch-and-Cut, FTTx Deployment
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
https://opus4.kobv.de/opus4-zib/files/1861/kConFL.pdf
1642
eng
reportzib
0
2012-11-06
2012-11-06
--
Integrated Optimization of Rolling Stock Rotations for Intercity Railways
This paper provides a highly integrated solution approach for rolling stock
planning problems in the context of intercity passenger traffic. The main
contributions are a generic hypergraph based mixed integer programming
model and an integrated algorithm for the considered rolling stock rotation
planning problem. The new developed approach is able to handle a very large
set of industrial railway requirements, such as vehicle composition,
maintenance constraints, infrastructure capacity, and regularity aspects.
By the integration of this large bundle of technical railway aspects, we show
that our approach has the power to produce implementable rolling stock
rotations for our industrial cooperation partner DB Fernverkehr.
This is the first time that the rolling stock rotations at DB Fernverkehr
could be optimized by an automated system utilizing advanced mathematical
programming techniques.
1438-0064
urn:nbn:de:0297-zib-16424
Markus Reuther
Markus Reuther
Ralf Borndoerfer
Thomas Schlechte
Steffen Weider
ZIB-Report
12-39
eng
uncontrolled
Mixed Integer Programming
eng
uncontrolled
Railway Optimization
eng
uncontrolled
Rolling Stock Rostering
Mathematics of Computing
GENERAL
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Schlechte, Thomas
Weider, Steffen
MODAL-RailLab
ROTOR
MODAL-Gesamt
Reuther, Markus
https://opus4.kobv.de/opus4-zib/files/1642/vrp.pdf
4815
eng
reportzib
0
--
2014-03-20
--
Modern Nonlinear Optimization Techniques for an Optimal Control of System Dynamics Models
We study System Dynamics models with several free parameters that can be altered by the user. We assume that the user's goal is to achieve a certain dynamic behavior of the model by varying these parameters. In order to the find best possible combination of parameter settings, several automatic parameter tuning methods are described in the literature and readily available within existing System Dynamic software packages. We give a survey on the available techniques in the market and describe their theoretical background. Some of these methods are already six decades old, and meanwhile newer and more powerful optimization methods have emerged in the mathematical literature. One major obstacle for their direct use are tabled data in System Dynamics models, which are usually interpreted as piecewise linear functions. However, modern optimization methods usually require smooth functions which are twice continuously differentiable. We overcome this problem by a smooth spline interpolation of the tabled data. We use a test set of three complex System Dynamic models from the literature, describe their individual transition into optimization problems, and demonstrate the applicability of modern optimization algorithms to these System Dynamics Optimization problems.
1438-0064
urn:nbn:de:0297-zib-48159
Ingmar Vierhaus
Armin Fügenschuh
Armin Fügenschuh
Robert Lion Gottwald
Stefan N. Grösser
ZIB-Report
14-08
eng
uncontrolled
System Dynamics
eng
uncontrolled
Optimal Control
eng
uncontrolled
Nonlinear Optimization
eng
uncontrolled
Spline Interpolation
ORDINARY DIFFERENTIAL EQUATIONS
DYNAMICAL SYSTEMS AND ERGODIC THEORY [See also 26A18, 28Dxx, 34Cxx, 34Dxx, 35Bxx, 46Lxx, 58Jxx, 70-XX]
CALCULUS OF VARIATIONS AND OPTIMAL CONTROL; OPTIMIZATION [See also 34H05, 34K35, 65Kxx, 90Cxx, 93-XX]
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES
Mathematical Optimization
Gottwald, Robert
CRC1026
https://opus4.kobv.de/opus4-zib/files/4815/ZR-14-08.pdf
4338
eng
reportzib
0
2013-12-18
2013-12-18
--
Multiband Robust Optimization and its Adoption in Harvest Scheduling
A central assumption in classical optimization is that all the input data of a
problem are exact. However, in many real-world problems, the input data are subject
to uncertainty. In such situations, neglecting uncertainty may lead to nominally optimal
solutions that are actually suboptimal or even infeasible. Robust optimization
offers a remedy for optimization under uncertainty by considering only the subset of
solutions protected against the data deviations. In this paper, we provide an overview
of the main theoretical results of multiband robustness, a new robust optimization
model that extends and refines the classical theory introduced by Bertsimas and Sim.
After introducing some new results for the special case of pure binary programs, we
focus on the harvest scheduling problem and show how multiband robustness can
be adopted to tackle the uncertainty affecting the volume of produced timber and
grant a reduction in the price of robustness.
1438-0064
urn:nbn:de:0297-zib-43380
Fabio D'Andreagiovanni
Fabio D'Andreagiovanni
Annie Raymond
ZIB-Report
13-76
eng
uncontrolled
Data Uncertainty
eng
uncontrolled
Robust Optimization
eng
uncontrolled
Multiband Robustness
eng
uncontrolled
Harvest Scheduling
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Telecommunication
https://opus4.kobv.de/opus4-zib/files/4338/ZR-13-76_RobustHarvestScheduling_DAndreagiovanniRaymond.pdf
4408
eng
reportzib
0
2014-02-12
2013-12-30
--
A hybrid primal heuristic for Robust Multiperiod Network Design
We investigate the Robust Multiperiod Network Design Problem, a generalization of the classical Capacitated Network Design Problem that additionally considers multiple design periods and provides solutions protected against traffic uncertainty.
Given the intrinsic difficulty of the problem, which proves challenging even for state-of-the art commercial solvers, we propose a hybrid primal heuristic based on the combination of ant colony optimization and an exact large neighborhood search. Computational experiments on a set of realistic instances from the SNDlib show that our heuristic can find solutions of extremely good quality with low optimality gap.
1438-0064
urn:nbn:de:0297-zib-44081
To appear in EvoApplications - Proc. of EvoStar 2014, Esparcia-Alcazar, A. et al. (Eds.), Lecture Notes in Computer Science, Springer, Heidelberg
Fabio D'Andreagiovanni
Fabio D'Andreagiovanni
Jonatan Krolikowski
Jonad Pulaj
ZIB-Report
13-78
eng
uncontrolled
Multiperiod Network Design, Traffic Uncertainty, Robust Optimization, Multiband Robustness, Hybrid Heuristics
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Telecommunication
Pulaj, Jonad
https://opus4.kobv.de/opus4-zib/files/4408/ZR-13-78_RobustMultiperiodNetworkDesign_DAndreatiovanniEtAl.pdf
4409
eng
reportzib
0
2014-02-12
2013-12-30
--
0-1 Multiband Robust Optimization
We provide an overview of new theoretical results that we obtained while further investigating multiband robust optimization, a new model for robust optimization that we recently proposed to tackle uncertainty in mixed-integer linear programming. This new model extends and refines the classical Gamma-robustness model of Bertsimas and Sim and is particularly useful in the common case of arbitrary asymmetric distributions of the uncertainty. Here, we focus on uncertain 0-1 programs and we analyze their robust counterparts when the uncertainty is represented through a multiband set. Our investigations were inspired by the needs of our industrial partners in the research project ROBUKOM.
1438-0064
urn:nbn:de:0297-zib-44093
To appear in: Operations Research Proceedings 2013 - Selected Papers of the International Annual Conference of the German Operations Research Society (GOR), Erasmus University Rotterdam, The Netherlands, September 3-6, 2013, Springer, Heidelberg
Christina Büsing
Fabio D'Andreagiovanni
Fabio D'Andreagiovanni
Annie Raymond
ZIB-Report
13-77
eng
uncontrolled
Combinatorial Optimization, Robust Optimization, Multiband Robustness, Network Design
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Telecommunication
https://opus4.kobv.de/opus4-zib/files/4409/ZR-13-77_01MultibandRobustOptimizationGOR2013.pdf
1640
eng
reportzib
0
2012-11-05
2012-11-05
--
Railway Track Allocation
This article gives an overview of the results of the author's PhD thesis. The thesis deals with the
mathematical optimization for the efficient use of
railway infrastructure. We address the optimal allocation of the available
railway track capacity - the track allocation problem. This track allocation
problem is a major challenge for a railway company, independent of whether
a free market, a private monopoly, or a public monopoly is given. Planning
and operating railway transportation systems is extremely hard due to the
combinatorial complexity of the underlying discrete optimization problems,
the technical intricacies, and the immense sizes of the problem instances.
Mathematical models and optimization techniques can result in huge gains
for both railway customers and operators, e.g., in terms of cost reductions or
service quality improvements. We tackle this challenge by developing novel
mathematical models and associated innovative algorithmic solution methods
for large scale instances. We made considerable progress on solving track
allocation problems by two main features - a novel modeling approach for the
macroscopic track allocation problem and algorithmic improvements based on the
utilization of the bundle method. This allows us to produce for the first time reliable solutions for a real world instance, i.e., the Simplon corridor in Switzerland.
1438-0064
urn:nbn:de:0297-zib-16402
Thomas Schlechte
Thomas Schlechte
ZIB-Report
12-38
eng
uncontrolled
large-scale integer programming
eng
uncontrolled
network aggregation
eng
uncontrolled
configuration models
eng
uncontrolled
rapid branching
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Schlechte, Thomas
Trassenbörse
https://opus4.kobv.de/opus4-zib/files/1640/ZR-12-38.pdf
5640
2015
eng
reportzib
0
2015-10-27
2015-10-27
--
Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores
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.
1438-0064
urn:nbn:de:0297-zib-56404
10.1109/IPDPS.2016.56
Appeared in: Proc. of 30th IEEE International Parallel & Distributed Processing Symposium
Yuji Shinano
Yuji Shinano
Tobias Achterberg
Timo Berthold
Stefan Heinz
Thorsten Koch
Michael Winkler
ZIB-Report
15-53
eng
uncontrolled
Mixed Integer Programming
eng
uncontrolled
Parallel processing
eng
uncontrolled
Node merging
eng
uncontrolled
Racing ParaSCIP
eng
uncontrolled
Ubiquity Generator Framework
eng
uncontrolled
MIPLIB
Software
Computing Methodologies
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Achterberg, Tobias
Koch, Thorsten
Shinano, Yuji
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/5640/ZR-15-53.pdf
https://opus4.kobv.de/opus4-zib/files/5640/ZR-15-53-rev.pdf
5437
eng
reportzib
0
--
2015-09-04
--
Reoptimization Techniques in MIP Solvers
Recently, there have been many successful applications of optimization algorithms that solve a sequence of quite similar mixed-integer programs (MIPs) as subproblems. Traditionally, each problem in the sequence is solved from scratch. In this paper we consider reoptimization techniques that try to benefit from information obtained by solving previous problems of the sequence. We focus on the case that subsequent MIPs differ only in the objective function or that the feasible region is reduced. We propose extensions of the very complex branch-and-bound algorithms employed by general MIP solvers based on the idea to ``warmstart'' using the final search frontier of the preceding solver run. We extend the academic MIP solver SCIP by these techniques to obtain a reoptimizing branch-and-bound solver and report computational results which show the effectiveness of the approach.
1438-0064
urn:nbn:de:0297-zib-54375
10.1007/978-3-319-20086-6_14
Lecture Notes in Computer Science
urn:nbn:de:0297-zib-54375
Jakob Witzig
Jakob Witzig
Gerald Gamrath
Benjamin Hiller
ZIB-Report
15-24
Computer Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
Hiller, Benjamin
Witzig, Jakob
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
TRR154-A04
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/5437/zibreport.pdf
6629
eng
reportzib
0
--
2017-12-21
--
The SCIP Optimization Suite 5.0
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.
1438-0064
urn:nbn:de:0297-zib-66297
Ambros Gleixner
Gregor Hendel
Leon Eifler
Tristan Gally
Gerald Gamrath
Patrick Gemander
Robert Lion Gottwald
Gregor Hendel
Christopher Hojny
Thorsten Koch
Matthias Miltenberger
Benjamin Müller
Marc E. Pfetsch
Christian Puchert
Daniel Rehfeldt
Franziska Schlösser
Felipe Serrano
Yuji Shinano
Jan Merlin Viernickel
Stefan Vigerske
Dieter Weninger
Jonas T. Witt
Jakob Witzig
ZIB-Report
17-61
eng
uncontrolled
constraint integer programming
eng
uncontrolled
linear programming
eng
uncontrolled
mixed-integer linear programming
eng
uncontrolled
mixed-integer nonlinear programming
eng
uncontrolled
optimization solver
eng
uncontrolled
branch-and-cut
eng
uncontrolled
branch-and-price
eng
uncontrolled
column generation framework
eng
uncontrolled
parallelization
eng
uncontrolled
mixed-integer semidefinite programming
eng
uncontrolled
Steiner tree optimization
NUMERICAL ANALYSIS
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
Gleixner, Ambros
Gottwald, Robert
Hendel, Gregor
Koch, Thorsten
Miltenberger, Matthias
Rehfeldt, Daniel
Serrano, Felipe
Shinano, Yuji
Vigerske, Stefan
Witzig, Jakob
Müller, Benjamin
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
Eifler, Leon
MODAL-Gesamt
Schlösser, Franziska
Viernickel, Jan Merlin
https://opus4.kobv.de/opus4-zib/files/6629/scipopt-50.pdf
6151
eng
reportzib
0
--
2016-12-22
--
Using Bilevel Optimization to find Severe Transport Situations in Gas Transmission Networks
In the context of gas transmission in decoupled entry-exit systems, many approaches to determine the network capacity are based on the evaluation of realistic and severe transport situations. In this paper, we review the Reference Point Method, which is an algorithm used in practice to generate a set of scenarios using the so-called transport moment as a measure for severity. We introduce a new algorithm for finding severe transport situations that considers an actual routing of the flow through the network and is designed to handle issues arising from cyclic structures in a more dynamical manner. Further, in order to better approximate the physics of gas, an alternative, potential based flow formulation is proposed. The report concludes with a case study based on data from the benchmark library GasLib.
1438-0064
urn:nbn:de:0297-zib-61519
Kai Hennig
Kai Hennig
Robert Schwarz
ZIB-Report
16-68
eng
uncontrolled
bilevel optimization
eng
uncontrolled
gas networks
eng
uncontrolled
network flow
CALCULUS OF VARIATIONS AND OPTIMAL CONTROL; OPTIMIZATION [See also 34H05, 34K35, 65Kxx, 90Cxx, 93-XX]
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES
Mathematical Optimization
Hoppmann, Kai
MODAL-GasLab
https://opus4.kobv.de/opus4-zib/files/6151/ZR-16-68.pdf
5278
eng
reportzib
0
--
2014-10-15
--
The Cycle Embedding Problem
Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach.
1438-0064
urn:nbn:de:0297-zib-52788
10.1007/978-3-319-28697-6_65
Appeared in: Operations Research Proceedings 2014
Ralf Borndörfer
Thomas Schlechte
Marika Karbstein
Julika Mehrgardt
Markus Reuther
Thomas Schlechte
ZIB-Report
14-37
eng
uncontrolled
cycle embedding problem
eng
uncontrolled
railway vehicle rotation scheduling
eng
uncontrolled
sequential coarse-first-fine-second planning approach
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Schlechte, Thomas
MODAL-RailLab
ROTOR
MODAL-Gesamt
Reuther, Markus
https://opus4.kobv.de/opus4-zib/files/5278/ZR-14-37.pdf
6160
2016
eng
reportzib
1
--
2016-12-30
--
The Three Phases of MIP Solving
Modern MIP solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound.
Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three different phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behavior of the MIP solver SCIP at the predicted phase transition points.
1438-0064
urn:nbn:de:0297-zib-61607
10.1080/10556788.2017.1392519
Optimization Methods and Software
Timo Berthold
Gregor Hendel
Gregor Hendel
Thorsten Koch
ZIB-Report
16-78
eng
uncontrolled
optimization software
eng
uncontrolled
mixed-integer programming
eng
uncontrolled
branch-and-bound
eng
uncontrolled
adaptive search behavior
eng
uncontrolled
optimality prediction
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Berthold, Timo
Hendel, Gregor
Koch, Thorsten
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6160/zib-paper.pdf
6138
eng
reportzib
0
--
2016-12-07
--
Distributed domain propagation
Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite it's simplicity portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after a variables domain has been reduced. This paper investigates the impact of distributed domain propagation in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers.
1438-0064
urn:nbn:de:0297-zib-61380
10.4230/LIPIcs.SEA.2017.6
16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics, Volume 75, SEA 2017, June 21–23, 2017 - London, UK Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman (Eds.)
Robert Lion Gottwald
Robert Lion Gottwald
Stephen J. Maher
Yuji Shinano
ZIB-Report
16-71
eng
uncontrolled
mixed integer programming
eng
uncontrolled
parallelization
eng
uncontrolled
domain propagation
eng
uncontrolled
portfolio solvers
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Gottwald, Robert
Shinano, Yuji
Maher, Stephan
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6138/16-71.pdf
4259
eng
reportzib
0
2013-09-27
2013-09-27
--
FiberSCIP - A shared memory parallelization of SCIP
Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a MIP solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, the basic concept of having two parallel extensions and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator) is presented, including an implementation of deterministic parallelization. Second, the difficulties to achieve a good performance that utilizes all resources on an actual computing environment and the difficulties of performance evaluation of the parallel solvers are discussed. Third, a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions is presented. Finally, current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer non-linear programs (MINLPs) in parallel is demonstrated.
1438-0064
urn:nbn:de:0297-zib-42595
10.1287/ijoc.2017.0762
INFORMS Journal on Computing
Yuji Shinano
Yuji Shinano
Stefan Heinz
Stefan Vigerske
Michael Winkler
ZIB-Report
13-55
eng
uncontrolled
parallel
eng
uncontrolled
branch-and-bound
eng
uncontrolled
deterministic parallelism
eng
uncontrolled
constraint integer programming
eng
uncontrolled
mixed integer programming
eng
uncontrolled
mixed integer nonlinear programming
eng
uncontrolled
SCIP
eng
uncontrolled
MIP
eng
uncontrolled
MINLP
Software
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Heinz, Stefan
Shinano, Yuji
Vigerske, Stefan
Winkler, Michael
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/4259/fiberscip-zib.pdf
https://opus4.kobv.de/opus4-zib/files/4259/fiberscip-zib-rev.pdf
https://opus4.kobv.de/opus4-zib/files/4259/fiberscip-zib-rev3.pdf
6554
eng
reportzib
0
--
2017-07-11
--
The Ubiquity Generator Framework: 7 Years of Progress in Parallelizing Branch-and-Bound
Mixed integer linear programming (MIP) is a general form to model combinatorial optimization problems and has many industrial applications. The performance of MIP solvers has improved tremendously in the last two decades and these solvers have been used to solve many real-word problems. However, against the backdrop of modern computer technology, parallelization is of pivotal importance. In this way, ParaSCIP is the most successful parallel MIP solver in terms of solving previously unsolvable instances from the well-known benchmark instance set MIPLIB by using supercomputers. It solved two instances from MIPLIB2003 and 12 from MIPLIB2010 for the first time to optimality by using up to 80,000 cores on supercomputers. ParaSCIP has been developed by using the Ubiquity Generator (UG) framework, which is a general software package to parallelize any state-of-the-art branch-and-bound based solver. This paper discusses 7 years of progress in parallelizing branch-and-bound solvers with UG.
1438-0064
urn:nbn:de:0297-zib-65545
Yuji Shinano
Yuji Shinano
ZIB-Report
17-60
eng
uncontrolled
Parallelization, Branch-and-bound, Mixed Integer Programming, UG, ParaSCIP, FiberSCIP, ParaXpress, FiberXpress, SCIP-Jack
Software
GENERAL
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Shinano, Yuji
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6554/ZIB-Report-17-60.pdf
1648
eng
reportzib
0
2012-11-15
2012-11-15
--
An Exact Reoptimization Algorithm for the Scheduling of Elevator Groups
The task of an elevator control is to schedule the elevators of a group such
that small waiting and travel times for the passengers are obtained. We present an exact
reoptimization algorithm for this problem. A reoptimization algorithm computes a
new schedule for the elevator group each time a new passenger arrives. Our algorithm
uses column generation techniques and is, to the best of our knowledge, the first exact
reoptimization algorithms for a group of passenger elevators. To solve the column
generation problem, we propose a Branch & Bound method.
1438-0064
urn:nbn:de:0297-zib-16485
10.1007/s10696-013-9175-6
Appeared in: Flexible Services and Manufacturing Journal, April 2013
Benjamin Hiller
Benjamin Hiller
Torsten Klug
Andreas Tuchscherer
ZIB-Report
12-43
eng
uncontrolled
elevator control, online optimization, reoptimization algorithms, column generation
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Hiller, Benjamin
Klug, Torsten
https://opus4.kobv.de/opus4-zib/files/1648/ZR-12-43.pdf
https://opus4.kobv.de/opus4-zib/files/1648/ZR-12-43revisedversion.pdf
1491
eng
reportzib
0
2012-03-26
2012-03-26
--
Characterization of Facets of the Hop Constrained Chain Polytope via Dynamic Programming
In this paper, we study the hop constrained chain polytope, that is, the convex hull of the incidence vectors of (s,t)-chains using at most k arcs of a given digraph, and its dominant. We use extended formulations (implied by the inherent structure of the Moore-Bellman-Ford algorithm) to derive facet defining inequalities for these polyhedra via projection. Our findings result into characterizations of all facet defining {0,+1,-1}-inequalities for the hop constrained chain polytope and all facet defining {0,1}-inequalities
for its dominant. Although the derived inequalities are already known, such classifications were not previously given to the best of our knowledge. Moreover, we use this approach to generalize so called jump inequalities, which have been introduced in a paper of Dahl and Gouveia in 2004.
1438-0064
urn:nbn:de:0297-zib-14914
Rüdiger Stephan
Martin Grötschel
Rüdiger Stephan
ZIB-Report
11-54
eng
uncontrolled
hop constraints
eng
uncontrolled
chains
eng
uncontrolled
dynamic programming
eng
uncontrolled
facets
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Grötschel, Martin
https://opus4.kobv.de/opus4-zib/files/1491/GroetschelStephan_ZIB.pdf
1515
eng
reportzib
0
2012-04-24
2012-04-24
--
The set of solutions to nomination validation in passive gas transportation networks with a generalized flow formula
In this paper we give an analytical description on the structure of
solutions to the gas nomination validation problem in gas
transportation networks. These networks are assumed to contain no
active devices, only certain hypothetical pipelines, where the flow
of gas is modeled by a generalized version of the quadratic
Weymouth's equation. The purpose of considering generalized flow
formulas is to be able to adapt our results to various gas network
optimization problems involving gas flow formulas beyond Weymouth's
equation. Such formulas can appear in leaves of branch and bound
trees, or they can stem from discretization and linearization
carried out at active devices. We call a balanced supply-demand
vector a nomination, and the passive nomination validation problem
is to decide whether there exist pressures at the nodes generating a
given nomination. We prove that in our setup the pressure square
vectors generating a given nomination form a one-dimensional
connected and continuous curve in the pressure square space, and
this curve is a line for the classical Weymouth's equation. We also
present a visual approach for the easy comprehension of how this
solution curve arises; we give a short investigation of the set of
feasible nominations; and finally we give a proof that the
nomination validation problem in gas networks with active devices is
NP-complete.
1438-0064
urn:nbn:de:0297-zib-15151
Jácint Szabó
Benjamin Hiller
ZIB-Report
11-44
eng
uncontrolled
pressure drop equation
eng
uncontrolled
gas networks
eng
uncontrolled
generalized flow formula
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
MODAL-GasLab
ForNe
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/1515/ZR-11-44.pdf
1513
eng
reportzib
0
2012-04-19
2012-04-19
--
Probabilistic alternatives for competitive analysis
In the last 20 years competitive analysis has become the main tool for
analyzing the quality of online algorithms. Despite of this,
competitive analysis has also been criticized: It sometimes cannot
discriminate between algorithms that exhibit significantly different
empirical behavior, or it even favors an algorithm that is worse from
an empirical point of view. Therefore, there have been several
approaches to circumvent these drawbacks. In this survey, we discuss
probabilistic alternatives for competitive analysis.
1438-0064
urn:nbn:de:0297-zib-15131
10.1007/s00450-011-0149-1
Appeared In: Computer Science - Research and Development August 2012, Volume 27, Issue 3, pp 189-196
Benjamin Hiller
Benjamin Hiller
Tjark Vredeveld
ZIB-Report
11-55
eng
uncontrolled
online algorithms
eng
uncontrolled
probabilistic analysis
eng
uncontrolled
competitive analysis
eng
uncontrolled
survey
Mathematics of Computing
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Hiller, Benjamin
https://opus4.kobv.de/opus4-zib/files/1513/ZR-11-55.pdf
5372
eng
reportzib
0
--
2015-02-18
--
Recent Success Stories on Optimization of Railway Systems
Planning and operating railway transportation systems is an extremely
hard task due to the combinatorial complexity of the underlying discrete
optimization problems, the technical intricacies, and the immense size of
the problem instances. Because of that, however, mathematical models
and optimization techniques can result in large gains for both railway cus-
tomers and operators, e.g., in terms of cost reductions or service quality
improvements. In the last years a large and growing group of researchers
in the OR community have devoted their attention to this domain devel-
oping mathematical models and optimization approaches to tackle many
of the relevant problems in the railway planning process. However, there
is still a gap to bridge between theory and practice, with
a few notable exceptions. In this paper we address three success stories,
namely, long-term freight train routing (part I), mid-term rolling stock
rotation planning (part II), and real-time train dispatching (part III). In
each case, we describe real-life, successful implementations. We will dis-
cuss the individual problem setting, survey the optimization literature,
and focus on particular aspects addressed by the mathematical models.
We demonstrate on concrete applications how mathematical optimization
can support railway planning and operations. This gives proof that math-
ematical optimization can support the planning of rolling stock resources.
Thus, mathematical models and optimization can lead to a greater effi-
ciency of railway operations and will serve as a powerful and innovative
tool to meet recent challenges of the railway industry.
1438-0064
urn:nbn:de:0297-zib-53726
Appeared in: Proceedings of the IAROR conference RailTokyo
Ralf Borndörfer
Markus Reuther
Torsten Klug
Leonardo Lamorgese
Carlo Mannino
Markus Reuther
Thomas Schlechte
ZIB-Report
14-47
eng
uncontrolled
railway planning
eng
uncontrolled
railway operations
eng
uncontrolled
capacity optimization
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Transportation and Logistics
Borndörfer, Ralf
Klug, Torsten
Schlechte, Thomas
KOSMOS
MODAL-RailLab
ROTOR
MODAL-Gesamt
Reuther, Markus
https://opus4.kobv.de/opus4-zib/files/5372/ZR-14-47.pdf
1363
eng
reportzib
0
2011-07-27
2011-07-27
--
Railway Track Allocation - Simulation and Optimization
Today the railway timetabling process and the track allocation
is one of the most challenging problems to solve by a railway infrastructure provider.
Especially due to the deregulation of the transport market in the recent years several
suppliers of railway traffic have entered the market. This leads to an increase of slot requests
and then it is natural that conflicts occur among them.
Furthermore, railway infrastructure networks consist of very expensive assets, even more
they are rigid due to the long-term upgrade process.
In order to make best use of these valuable infrastructure and to ensure economic operation,
efficient planning of the railway operation is indispensable.
Mathematical optimization models and algorithmic methodology can help
to automatize and tackle these challenges.
Our contribution in this paper is to present a renewed planning process
due to the liberalization in Europe and a general framework to
support the integration of simulation and optimization for
railway capacity allocation.
1438-0064
11-32
urn:nbn:de:0297-zib-13632
Appeared in: Proceedings of 4th International Seminar on Railway Operations Modelling and Analysis (IAROR), I.A. Hansen et al. (eds.) 2011, vol. 4,
Thomas Schlechte
Thomas Schlechte
ZIB-Report
11-32
eng
uncontrolled
railway models
eng
uncontrolled
railway capacity
eng
uncontrolled
track allocation framework
Software
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Schlechte, Thomas
Trassenbörse
https://opus4.kobv.de/opus4-zib/files/1363/ZR-11-32.pdf
1405
eng
reportzib
0
2011-09-22
2011-09-22
--
A Hypergraph Model for Railway Vehicle Rotation Planning
We propose a model for the integrated optimization of vehicle
rotations and vehicle compositions in long distance railway passenger
transport. The main contribution of the paper is a hypergraph model
that is able to handle the challenging technical requirements as
well as very general stipulations with respect to the ``regularity''
of a schedule. The hypergraph model directly generalizes network
flow models, replacing arcs with hyperarcs. Although NP-hard in
general, the model is computationally well-behaved in practice. High
quality solutions can be produced in reasonable time using high
performance Integer Programming techniques, in particular, column
generation and rapid branching. We show that, in this way,
large-scale real world instances of our cooperation partner DB
Fernverkehr can be solved.
1438-0064
11-36
/10.4230/OASIcs.ATMOS.2011.146
urn:nbn:de:0030-drops-32746
Appeared in: 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Alberto Caprara and Spyros Kontogiannis (eds.) 2011, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, ISBN 978-3-939897-33-0, pp. 146-155, OpenAccess Series in Informatics (OASIcs), 20
Ralf Borndörfer
Thomas Schlechte
Markus Reuther
Thomas Schlechte
Steffen Weider
ZIB-Report
11-36
eng
uncontrolled
Rolling Stock Planning, Hypergraph Modeling, Integer Programming, Column Generation, Rapid Branching
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Schlechte, Thomas
Weider, Steffen
MATHEON-B22
MODAL-RailLab
ROTOR
MODAL-Gesamt
Reuther, Markus
https://opus4.kobv.de/opus4-zib/files/1405/ZR-11-36.pdf
5100
eng
reportzib
0
--
2014-09-07
--
A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem
We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design
efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor
details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.
1438-0064
urn:nbn:de:0297-zib-51009
Ralf Borndörfer
Thomas Schlechte
Markus Reuther
Thomas Schlechte
ZIB-Report
14-26
eng
uncontrolled
column generation
eng
uncontrolled
coarse-to-fine approach
eng
uncontrolled
multi-layer approach
eng
uncontrolled
rolling stock rotation problem
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Transportation and Logistics
Borndörfer, Ralf
Schlechte, Thomas
MODAL-RailLab
ROTOR
MODAL-Gesamt
Reuther, Markus
https://opus4.kobv.de/opus4-zib/files/5100/ZR-14-26.pdf
6017
eng
reportzib
0
--
2016-08-16
--
SCIP-Jack – A solver for STP and variants with parallelization extensions
The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different
Steiner tree problem variants can be observed, solution approaches employed so far have been
prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that
can be used to solve both the classical Steiner tree problem and many of its variants without
modification. This versatility is achieved by transforming various problem variants into a
general form and solving them by using a state-of-the-art MIP-framework. The result is
a high-performance solver that can be employed in massively parallel environments and is
capable of solving previously unsolved instances.
1438-0064
urn:nbn:de:0297-zib-60170
10.1007/s12532-016-0114-x
Mathematical Programming Computation, Vol. 9 (2)
Gerald Gamrath
Daniel Rehfeldt
Thorsten Koch
Stephen J. Maher
Daniel Rehfeldt
Yuji Shinano
ZIB-Report
16-41
eng
uncontrolled
Steiner tree problem
eng
uncontrolled
SCIP-Jack
eng
uncontrolled
Steiner tree variants
deu
uncontrolled
maximum-weight connected subgraph
deu
uncontrolled
prize-collecting Steiner tree
Software
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
Koch, Thorsten
Rehfeldt, Daniel
Shinano, Yuji
Maher, Stephan
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6017/scipjack_ZIBreport.pdf
6543
eng
reportzib
0
--
2017-10-27
--
Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems
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.
1438-0064
urn:nbn:de:0297-zib-65439
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
ZIB-Report
17-57
eng
uncontrolled
Steiner tree
eng
uncontrolled
maximum-weight connected subgraph
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Koch, Thorsten
Rehfeldt, Daniel
MIP-ZIBOPT
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6543/note.pdf
6641
eng
reportzib
0
--
2018-01-18
--
SCIP-Jack—a solver for STP and variants with parallelization extensions: An update
The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. Although the different Steiner tree problem variants are usually strongly related, solution approaches employed so far have been prevalently problem-specific. Against this backdrop, the solver SCIP-Jack was created as a general-purpose framework that can be used to solve the classical Steiner tree problem and 11 of its variants. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. Furthermore, SCIP-Jack includes various newly developed algorithmic components such as preprocessing routines and heuristics. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. After the introduction of SCIP-Jack at the 2014 DIMACS Challenge on Steiner problems, the overall performance of the solver has considerably improved. This article provides an overview on the current state.
1438-0064
urn:nbn:de:0297-zib-66416
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
ZIB-Report
18-05
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Koch, Thorsten
Rehfeldt, Daniel
MIP-ZIBOPT
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6641/scipjack-zibreport.pdf
6760
2017
eng
doctoralthesis
0
--
--
--
Cutting Planes for Union-Closed Families
Frankl’s (union-closed sets) conjecture states that for any nonempty finite union-closed (UC) family of distinct sets there exists an element in at least half of the sets. Poonen’s Theorem characterizes the existence of weights which determine
whether a given UC family ensures Frankl’s conjecture holds for all UC families which contain it. The weight systems are nontrivial to identify for a given UC family, and methods to determine such weight systems have led to several other open questions and conjectures regarding structures in UC families.
We design a cutting-plane method that computes the explicit weights which imply the existence conditions of Poonen’s Theorem using computational integer programming coupled with redundant verification routines that ensure correctness. We find over one hundred previously unknown families of sets which ensure Frankl’s conjecture holds for all families that contain any of them. This improves significantly on all previous results of the kind.
Our framework allows us to answer several open questions and conjectures regarding structural properties of UC families, including proving the 3-sets conjecture of Morris from 2006 which characterizes the minimum number of 3-sets that ensure Frankl’s conjecture holds for all families that contain them. Furthermore, our method provides a general algorithmic road-map for improving other known results and uncovering structures in UC families.
https://depositonce.tu-berlin.de//handle/11303/7258
Martin Grötschel
Jonad Pulaj
Ambros Gleixner
Ralf Borndörfer
COMBINATORICS (For finite fields, see 11Txx)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Pulaj, Jonad
MODAL-SynLab
MODAL-Gesamt
Technische Universität Berlin
6108
eng
reportzib
0
--
2016-11-22
--
Experiments with Conflict Analysis in Mixed Integer Programming
The analysis of infeasible subproblems plays an import role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications obtained by domain propagation that led to infeasibility. The result of the analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept has its origin in solving satisfiability problems and is similarly used in constraint programming. The second concept is to analyze infeasible linear programming (LP) relaxations. The dual LP solution provides a set of multipliers that can be used to generate a single new globally valid linear constraint. The main contribution of this short paper is an empirical evaluation of two ways to combine both approaches. Experiments are carried out on general MIP instances from standard public test sets such as Miplib2010; the presented algorithms have been implemented within the non-commercial MIP solver SCIP. Moreover, we present a pool-based approach to manage conflicts which addresses the way a MIP solver traverses the search tree better than aging strategies known from SAT solving.
1438-0064
urn:nbn:de:0297-zib-61087
10.1007/978-3-319-59776-8_17
Experiments with Conflict Analysis in Mixed Integer Programming, Proceedings of CPAIOR 2017
Jakob Witzig
Jakob Witzig
Timo Berthold
Stefan Heinz
ZIB-Report
16-63
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Berthold, Timo
Heinz, Stefan
Witzig, Jakob
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6108/conflict_analysis_witzig_berthold_heinz_report_16-63.pdf
https://opus4.kobv.de/opus4-zib/files/6108/ZR-16-63-revised.pdf
6193
eng
reportzib
0
--
2017-02-09
--
A System to Evaluate Gas Network Capacities: Concepts and Implementation
Since 2005, the gas market in the European Union is liberalized and the trading of natural gas is decoupled from its transport. The transport is done by so-called transmissions system operators or TSOs. The market model established by the European Union views the gas transmission network as a black box, providing shippers (gas traders and consumers) the opportunity to transport gas from any entry to any exit. TSOs are required to offer maximum independent capacities at each entry and exit such that the resulting gas flows can be realized by the network without compromising security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs.
This paper gives an overview of the toolset for evaluating gas network capacities that has been developed within the ForNe project, a joint research project of seven research partners initiated by Open Grid Europe, Germany's biggest TSO. While most of the relevant mathematics is described in the book "Evaluating Gas Network Capacities", this article sketches the system as a whole, describes some developments that have taken place recently, and gives some details about the current implementation.
1438-0064
urn:nbn:de:0297-zib-61931
A revised and extended version is available as ZIB-Report 18-11.
Benjamin Hiller
Benjamin Hiller
Thorsten Koch
Lars Schewe
Robert Schwarz
Jonas Schweiger
ZIB-Report
17-03
eng
uncontrolled
operations research in energy
eng
uncontrolled
gas network optimization
eng
uncontrolled
entry-exit model
eng
uncontrolled
freely allocable capacity
eng
uncontrolled
large-scale mixed-integer nonlinear programming
Computer Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Hiller, Benjamin
Koch, Thorsten
MODAL-GasLab
ForNe
TRR154-A04
Schweiger, Jonas
https://opus4.kobv.de/opus4-zib/files/6193/euro2016_eepa_FORNE_2017-02-09_ZR.pdf
6586
eng
reportzib
0
--
2017-11-16
--
Polyhedral 3D Models for compressors in gas networks
Compressor machines are crucial elements in a gas transmission network, required to compensate for the pressure loss caused by friction in the pipes. Modelling all physical and technical details of a compressor machine involves a large amount of nonlinearity, which makes it hard to use such models in the optimization of large-scale gas networks. In this paper, we are going to describe a modelling approach for the operating range of a compressor machine, starting from a physical reference model and resulting in a polyhedral representation in the 3D space of mass flow throughput as well as in- and outlet pressure.
1438-0064
urn:nbn:de:0297-zib-65864
Tom Walther
Benjamin Hiller
Benjamin Hiller
René Saitenmacher
ZIB-Report
17-66
eng
uncontrolled
gas compressor modeling, polyhedral model, accuracy, z factor
Computer Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Hiller, Benjamin
MODAL-GasLab
TRR154-A04
https://opus4.kobv.de/opus4-zib/files/6586/ZR-17-66.pdf
6029
2018
eng
248
265
1
16
article
0
2018-02-15
--
--
Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes
In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst.
Multiscale Modeling and Simulation
1438-0064
10.1137/16M1091162
yes
urn:nbn:de:0297-zib-60353
Multiscale Modeling and Simulation
2017-10-18
Jakob Witzig
Witzig
Isabel Beckenbach
Leon Eifler
Konstantin Fackeldey
Ambros Gleixner
Andreas Grever
Marcus Weber
eng
uncontrolled
Markov State Models
eng
uncontrolled
NESS
eng
uncontrolled
Non-reversible Markov Processes
eng
uncontrolled
Mixed-Integer Programming
PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX)
STATISTICAL MECHANICS, STRUCTURE OF MATTER
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Numerical Mathematics
Mathematical Optimization
Computational Molecular Design
Mathematical Optimization Methods
Fackeldey, Konstantin
Gleixner, Ambros
Weber, Marcus
Witzig, Jakob
Beckenbach, Isabel
MIP-ZIBOPT
MODAL-SynLab
Eifler, Leon
SparseApproxiTN
MODAL-Gesamt
6823
2017
eng
doctoralthesis
0
--
--
2016-07-05
Mathematical Optimization of Rolling Stock Rotations
We show how to optimize rolling stock rotations that are required for the operation of a passenger timetable. The underlying mathematical ptimization problem is called rolling stock rotation problem (RSRP) and the leitmotiv of the thesis is RotOR, i.e., a highly integrated optimization algorithm for the RSRP. RotOR is used by DB Fernverkehr AG (DBF) in order to optimize intercity express (ICE) rotations for the European high-speed network. In this application, RSRPs have to be solved which (A) require many different aspects to be simultaneously considered, (B) are typically of large scale, and (C) include constraints that have a difficult combinatorial structure. This thesis suggests answers to these issues via the following concepts.
(A) The main model, which RotOR uses, relies on a hypergraph. The hypergraph provides an easy way to model manifold industrial railway requirements in great detail. This includes well known vehicle composition requirements as well as relatively unexplored regularity stipulations. At the same time, the hypergraph directly leads to a mixed-integer programming (MIP) model for the RSRP.
(B) The main algorithmic ingredient to solve industrial instances of the RSRP is a coarse-to-fine (C2F) column generation procedure. In this approach, the hypergraph is layered into coarse and fine layers that distinguish different levels of detail of the RSRP. The coarse layers are algorithmically utilized while pricing fine columns until proven optimality. Initially, the C2F approach is presented in terms of pure linear programming in order to provide an interface for other applications.
(C) Rolling stock rotations have to comply to resource constraints in order to ensure, e.g., enough maintenance inspections along the rotations. These constraints are computationally hard, but are well known in the literature on the vehicle routing problem (VRP). We define an interface problem in order to bridge between the RSRP and the VRP and derive a straightforward algorithmic concept, namely regional search (RS), from their common features and, moreover, differences. Our RS algorithms show promising results for classical VRPs and RSRPs.
In the first part of the thesis we present these concepts, which encompass its main mathematical contribution. The second part explains all modeling and solving components of RotOR that turn out to be essential in its industrial application. The thesis concludes with a solution to a complex re-optimization RSRP that RotOR has computed successfully for DBF. In this application all ICE vehicles of the ICE-W fleets of DBF had to be redirected past a construction site on a high-speed line in the heart of Germany.
https://depositonce.tu-berlin.de/handle/11303/6309
Ralf Borndörfer
Markus Reuther
Markus Reuther
Martin Grötschel
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
MODAL-RailLab
ROTOR
MODAL-Gesamt
Reuther, Markus
Technische Universität Berlin
6011
eng
reportzib
0
--
2016-09-08
--
Line Planning on Path Networks with Application to the Istanbul Metrobüs
Bus rapid transit systems in developing and newly
industrialized countries often consist of a trunk with a path
topology. On this trunk, several overlapping lines are operated
which provide direct connections. The demand varies heavily over the
day, with morning and afternoon peaks typically in reverse
directions. We propose an integer programming
model for this problem, derive a structural property of line plans
in the static (or single period) ``unimodal demand'' case, and
consider approaches to the solution of the multi-period version that
rely on clustering the demand into peak and off-peak service
periods. An application to the Metrobüs system of Istanbul is
discussed.
1438-0064
urn:nbn:de:0297-zib-60119
Ralf Borndörfer
Thomas Schlechte
Oytun Arslan
Ziena Elijazyfer
Hakan Güler
Malte Renken
Güvenc Sahin
Thomas Schlechte
ZIB-Report
16-38
eng
uncontrolled
line planning
eng
uncontrolled
unimodal demand
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Schlechte, Thomas
ECMath-MI3
https://opus4.kobv.de/opus4-zib/files/6011/ZR-16-38.pdf
6075
eng
reportzib
0
--
2016-01-11
--
The Graph Segmentation Problem
We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest.
1438-0064
urn:nbn:de:0297-zib-60750
INOC 2017 – 8th International Network Optimization Conference
Stephan Schwartz
Stephan Schwartz
Ralf Borndörfer
Gerald Bartz
ZIB-Report
16-53
eng
uncontrolled
toll billing
eng
uncontrolled
graph segmentation
eng
uncontrolled
combinatorial optimization
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Transportation and Logistics
Borndörfer, Ralf
Schwartz, Stephan
no-project
https://opus4.kobv.de/opus4-zib/files/6075/ZR-16-53.pdf
6999
2018
eng
masterthesis
0
--
--
--
Optimization of a Master Surgery Schedule
During the past years hospitals saw themselves confronted with increasing economical pressure (WB06, p. V). Therefore, optimizing the general operational procedures has gained in importance. The revenue of a hospital depends on the kinds and quantity of treatments performed and on the effcient use and utilization of the corresponding resources. About 25 − 50% of the treatment costs of a patient needing surgery incurs in the operating rooms (WB06, p. 58). Hence skillful management of the operating rooms can have a large impact on the overall revenue of a hospital. Belien and Demeulemeester (BD07) describe the planning of operating room (OR) schedules as a multi-stage process. In the first stage OR time is allocated to the hospitals specialties and capacities and resources are adjusted. In the second stage a master surgery schedule (MSS) is developed, that is a timetable for D days that specifies the amount of OR time assigned to the specialties on every individual day. After D days this schedule will be repeated without any changes. Hence, developing an MSS is a long-term problem. Finally, specialties will schedule specific surgeries within their assigned OR time. In this work we will focus on the development of the MSS that maximizes the revenue of the hospital. Our main focus will be to ensure that the capacities of the downstream resources, i.e. the bed capacities in the ICU and ward, will not be exceeded. Additionally, we hope that our formulation of the problem will lead to a leveled bed demand without significant peaks. We will incorporate the uncertainty of patient demand and case mix in our model. There have been several approaches on this subject, for example in (Fü15) and (BD07) and this work is in part in� uenced by these advances.
urn:nbn:de:0297-zib-69996
Guillaume Sagnol
Lisa Mattrisch
Alexander Tesch
eng
uncontrolled
Master Surgery Scheduling
eng
uncontrolled
Conic Programming
Mathematics of Computing
CONVEX AND DISCRETE GEOMETRY
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
BMBF-IBOSS
Freie Universität Berlin
https://opus4.kobv.de/opus4-zib/files/6999/MA_Mattrisch.pdf
6974
eng
reportzib
0
--
2018-07-31
--
Separation of Cycle Inequalities in Periodic Timetabling
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.
1438-0064
urn:nbn:de:0297-zib-69746
Ralf Borndörfer
Niels Lindner
Heide Hoppmann
Marika Karbstein
Niels Lindner
ZIB-Report
18-16
eng
uncontrolled
Periodic timetabling
eng
uncontrolled
Cycle inequality
eng
uncontrolled
Change-cycle inequality
Mathematics of Computing
Computer Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Lindner, Niels
ECMath-MI7
https://opus4.kobv.de/opus4-zib/files/6974/sepa_cycle.pdf
7024
eng
reportzib
0
--
2018-08-28
--
Chvátal’s Conjecture Holds for Ground Sets of Seven Elements
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.
1438-0064
urn:nbn:de:0297-zib-70240
Leon Eifler
Leon Eifler
Ambros Gleixner
Jonad Pulaj
ZIB-Report
18-49
eng
uncontrolled
extremal combinatorics
eng
uncontrolled
exact rational integer programming
COMBINATORICS (For finite fields, see 11Txx)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Gleixner, Ambros
Pulaj, Jonad
MIP-ZIBOPT
MODAL-SynLab
Eifler, Leon
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/7024/chvatal.pdf
6143
eng
reportzib
0
--
2016-12-17
--
Optimization of Handouts for Rolling Stock Rotations Visualization
A railway operator creates (rolling stock) rotations in order to have a precise master plan for the
operation of a timetable by railway vehicles. A rotation is considered as a cycle that multiply
traverses a set of operational days while covering trips of the timetable. As it is well known,
the proper creation of rolling stock rotations by, e.g., optimization algorithms is challenging
and still a topical research subject. Nevertheless, we study a completely different but strongly
related question in this paper, i.e.: How to visualize a rotation? For this purpose, we introduce
a basic handout concept, which directly leads to the visualization, i.e., handout of a rotation. In
our industrial application at DB Fernverkehr AG, the handout is exactly as important as the
rotation itself. Moreover, it turns out that also other European railway operators use exactly the
same methodology (but not terminology). Since a rotation can have many handouts of different
quality, we show how to compute optimal ones through an integer program (IP) by standard
software. In addition, a construction as well as an improvement heuristic are presented. Our
computational results show that the heuristics are a very reliable standalone approach to quickly
find near-optimal and even optimal handouts. The efficiency of the heuristics is shown via a
computational comparison to the IP approach.
1438-0064
urn:nbn:de:0297-zib-61430
Ralf Borndörfer
Thomas Schlechte
Boris Grimm
Markus Reuther
Thomas Schlechte
ZIB-Report
ZR-16-73
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Transportation and Logistics
Borndörfer, Ralf
Grimm, Boris
Schlechte, Thomas
MODAL-RailLab
ROTOR
MODAL-Gesamt
Reuther, Markus
https://opus4.kobv.de/opus4-zib/files/6143/ZR-16-73.pdf
6956
eng
reportzib
1
--
2018-07-20
--
Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms
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.
1438-0064
urn:nbn:de:0297-zib-69563
Creative Commons - CC BY - Namensnennung 4.0 International
Gregor Hendel
Gregor Hendel
Matthias Miltenberger
Jakob Witzig
ZIB-Report
18-36
eng
uncontrolled
mixed integer programming
eng
uncontrolled
primal heuristics
eng
uncontrolled
multi armed bandit
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Hendel, Gregor
Miltenberger, Matthias
Witzig, Jakob
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6956/paper.pdf
7116
eng
reportzib
0
--
2018-12-18
--
Adaptive Large Neighborhood Search for Mixed Integer Programming
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.
1438-0064
urn:nbn:de:0297-zib-71167
Gregor Hendel
Gregor Hendel
ZIB-Report
18-60
eng
uncontrolled
mixed integer programming
eng
uncontrolled
primal heuristics
eng
uncontrolled
large neighborhood search
eng
uncontrolled
multi armed bandit problem
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Hendel, Gregor
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/7116/adaptive-lns-master.pdf
6618
eng
reportzib
0
--
2017-12-18
--
Optimizing Large-Scale Linear Energy System Problems with Block Diagonal Structure by Using Parallel Interior-Point Methods
Current linear energy system models (ESM) acquiring to provide sufficient detail and reliability frequently bring along problems of both high intricacy and increasing scale. Unfortunately, the size and complexity of these problems often prove to be intractable even for commercial state-of-the-art linear programming solvers. This article describes an interdisciplinary approach to exploit the intrinsic structure of these large-scale linear problems to be able to solve them on massively parallel high-performance computers. A key aspect are extensions to the parallel interior-point solver PIPS-IPM originally developed for stochastic optimization problems. Furthermore, a newly developed GAMS interface to the solver as well as some GAMS language extensions to model block-structured problems will be described.
1438-0064
urn:nbn:de:0297-zib-66183
10.1007/978-3-319-89920-6_85
Operations Research Proceedings 2017
Thomas Breuer
Daniel Rehfeldt
Michael Bussieck
Karl-Kien Cao
Felix Cebulla
Frederik Fiand
Hans Christian Gils
Ambros Gleixner
Dmitry Khabi
Thorsten Koch
Daniel Rehfeldt
Manuel Wetzel
ZIB-Report
17-75
eng
uncontrolled
energy system models
eng
uncontrolled
interior-point methods
eng
uncontrolled
high-performance computing
Software
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Gleixner, Ambros
Koch, Thorsten
Rehfeldt, Daniel
BEAM-ME
https://opus4.kobv.de/opus4-zib/files/6618/zibreport.pdf
6968
eng
reportzib
0
--
2018-07-30
--
A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable
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.
1438-0064
urn:nbn:de:0297-zib-69688
10.4230/OASIcs.ATMOS.2018.16
appeared in: 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)
Ralf Borndörfer
Niels Lindner
Marika Karbstein
Christian Liebchen
Niels Lindner
ZIB-Report
18-38
eng
uncontrolled
Vehicle scheduling
eng
uncontrolled
Periodic timetabling
eng
uncontrolled
Bipartite matching
Computer Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Lindner, Niels
ECMath-MI7
https://opus4.kobv.de/opus4-zib/files/6968/PeriodicVehicleScheduling.pdf
6454
eng
reportzib
0
--
2017-07-17
--
Demand-Driven Line Planning with Selfish Routing
Bus rapid transit systems in developing and newly industrialized countries are often operated at the limits of passenger capacity. In particular, demand during morning and afternoon peaks is hardly or even not covered with available line plans. In order to develop demand-driven line plans, we use two mathematical models in the form of integer programming problem formulations. While the actual demand data is specified with origin-destination pairs, the arc-based model considers the demand over the arcs derived from the origin-destination demand. In order to test the accuracy of the models in terms of demand satisfaction, we simulate the optimal solutions and compare number of transfers and travel times. We also question the effect of a selfish route choice behavior which in theory results in a Braess-like paradox by increasing the number of transfers when system capacity is increased with additional lines.
1438-0064
urn:nbn:de:0297-zib-64547
10.1007/978-3-319-89920-6_91
appeared in: Operations Research Proceedings 2017
Malte Renken
Thomas Schlechte
Amin Ahmadi
Ralf Borndörfer
Guvenc Sahin
Thomas Schlechte
ZIB-Report
17-38
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Schlechte, Thomas
ECMath-MI3
ECMath-MI7
https://opus4.kobv.de/opus4-zib/files/6454/ZR-17-38.pdf
6104
eng
reportzib
0
--
2016-11-20
--
Verifying Integer Programming Results
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MILP solution algorithms, the ideal form of such a certificate is not entirely clear. This paper proposes such a certificate format, illustrating its capabilities and structure through examples. The certificate format is designed with simplicity in mind and is composed of a list of statements that can be sequentially verified using a limited number of simple yet powerful inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of mixed-integer linear programming instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates.
1438-0064
urn:nbn:de:0297-zib-61044
10.1007/978-3-319-59250-3_13
F. Eisenbrand and J. Koenemann, eds., Integer Programming and Combinatorial Optimization: 19th International Conference, IPCO 2017
Kevin K. H. Cheung
Ambros Gleixner
Ambros Gleixner
Daniel E. Steffy
ZIB-Report
16-58
eng
uncontrolled
correctness, verification, proof, certificate, optimality, infeasibility, mixed-integer linear programming
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mixed integer programming
Mathematical Optimization
Mathematical Optimization Methods
Gleixner, Ambros
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6104/ZR-16-58.pdf
https://opus4.kobv.de/opus4-zib/files/6104/ZR-16-58-revised.pdf
6035
eng
reportzib
0
--
2016-05-09
--
Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes
In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst.
1438-0064
urn:nbn:de:0297-zib-60353
10.1137/16M1091162
Jakob Witzig
Jakob Witzig
Isabel Beckenbach
Leon Eifler
Konstantin Fackeldey
Ambros Gleixner
Andreas Grever
Marcus Weber
ZIB-Report
16-39
eng
uncontrolled
Non-reversible Markov Processes
eng
uncontrolled
NESS
eng
uncontrolled
Mixed-Integer Programming
eng
uncontrolled
Markov State Models
PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX)
STATISTICS
STATISTICAL MECHANICS, STRUCTURE OF MATTER
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Numerical Mathematics
Mathematical Optimization
Computational Molecular Design
Mathematical Optimization Methods
Fackeldey, Konstantin
Gleixner, Ambros
Weber, Marcus
Witzig, Jakob
Beckenbach, Isabel
MIP-ZIBOPT
MODAL-SynLab
Eifler, Leon
SparseApproxiTN
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6035/ZR-16-39-revised2.pdf
5780
eng
reportzib
0
--
2016-03-08
--
Three Enhancements for Optimization-Based Bound Tightening
Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efficient implementation of OBBT.
Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs.
We conduct extensive computational experiments on MINLPLib2. Our results indicate that OBBT is most beneficial on hard instances, for which we observe a speedup of 17% to 19% on average. Most importantly, more instances can be solved when using OBBT.
1438-0064
urn:nbn:de:0297-zib-57803
10.1007/s10898-016-0450-4
Journal of Global Optimization
Ambros M. Gleixner
Benjamin Müller
Timo Berthold
Benjamin Müller
Stefan Weltge
ZIB-Report
15-16
eng
uncontrolled
MINLP
eng
uncontrolled
optimization-based bound tightening
eng
uncontrolled
optimality-based bound tightening
eng
uncontrolled
OBBT
eng
uncontrolled
propagation
eng
uncontrolled
bound tightening
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Berthold, Timo
Gleixner, Ambros
Müller, Benjamin
MIP-ZIBOPT
MODAL-SynLab
Siemens
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/5780/ZR-15-16.pdf
6967
deu
reportzib
0
--
2018-07-30
--
Kombilösung: Optimierung des Liniennetzes in Karlsruhe
Wir beschreiben die Optimierung des Nahverkehrsnetzes der Stadt Karlsruhe im Zusammmenhang mit den Baumaßnahmen der sogenannten Kombilösung.
1438-0064
urn:nbn:de:0297-zib-69677
Der Nahverkehr 1-2, 2019
07.11.2018
Ralf Borndörfer
Ralf Borndörfer
Ascan Egerer
Marika Karbstein
Ralf Messerschmidt
Marc Perez
Steven Pfisterer
Petra Strauß
ZIB-Report
18-45
deu
uncontrolled
ÖPNV
deu
uncontrolled
Linienplanung
Mathematics of Computing
GENERAL
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
ECMath-MI3
MATHEON-B15
https://opus4.kobv.de/opus4-zib/files/6967/ZR-18-45.pdf
6972
eng
reportzib
0
--
2018-07-31
--
Optimization of Capacity Expansion in Potential-driven Networks including Multiple Looping - A comparison of modelling approaches
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.
1438-0064
urn:nbn:de:0297-zib-69726
under review
Ralf Lenz
Ralf Lenz
Kai Helge Becker
ZIB-Report
18-44
eng
uncontrolled
OR in energy
eng
uncontrolled
Network expansion
eng
uncontrolled
MINLP
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Lenz, Ralf
MODAL-GasLab
MODAL-Gesamt
Becker, Kai-Helge
ECMATH-MI10
https://opus4.kobv.de/opus4-zib/files/6972/ZR_18_44.pdf
7059
eng
reportzib
1
--
2018-09-27
--
Calculation of clinch and elimination numbers for sports leagues with multiple tiebreaking criteria
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.
1438-0064
urn:nbn:de:0297-zib-70591
Satoshi Ito
Yuji Shinano
Yuji Shinano
ZIB-Report
18-51
eng
uncontrolled
Sports league
eng
uncontrolled
Round-robin tournament
eng
uncontrolled
Tiebreaking criteria
eng
uncontrolled
Clinch number
eng
uncontrolled
Elimination number
eng
uncontrolled
Combinatorial optimization
eng
uncontrolled
Integer programming
Computing Methodologies
GENERAL
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Shinano, Yuji
MODAL-SynLab
MODAL-Gesamt
Zuse Institute Berlin (ZIB)
https://opus4.kobv.de/opus4-zib/files/7059/ZIB-Report-18-51.pdf
7095
eng
reportzib
0
--
2018-11-21
--
Reduction-based exact solution of prize-collecting Steiner tree problems
1438-0064
urn:nbn:de:0297-zib-70958
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
ZIB-Report
18-55
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Koch, Thorsten
Rehfeldt, Daniel
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/7095/pcstpZIB.pdf
6962
eng
reportzib
0
--
2018-07-25
--
Improving relaxations for potential-driven network flow problems via acyclic flow orientations
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.
1438-0064
urn:nbn:de:0297-zib-69622
Benjamin Hiller
Benjamin Hiller
Kai Helge Becker
ZIB-Report
18-30
eng
uncontrolled
potential-driven network flows
eng
uncontrolled
acyclic orientations
eng
uncontrolled
flow orientations
eng
uncontrolled
MINLPs
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Hiller, Benjamin
MODAL-GasLab
MODAL-Gesamt
Becker, Kai-Helge
ECMATH-MI10
https://opus4.kobv.de/opus4-zib/files/6962/ZR-18-30.pdf
6746
eng
reportzib
0
--
2018-03-01
--
Improving branching for disjunctive polyhedral models using approximate convex decompositions
Disjunctive sets arise in a variety of optimization models and much esearch has been devoted to obtain strong relaxations for them. This paper focuses on the evaluation of the relaxation during the branch-and-bound search process. We argue that the branching possibilities (\ie binary variables) of the usual formulations are unsuitable to obtain strong bounds early in the search process as they do not capture the overall shape of the the entire disjunctive set. To analyze and exploit the shape of the disjunctive set we propose to compute a hierarchy of approximate convex decompositions and show how to extend the known formulations to obtain improved branching behavior.
1438-0064
urn:nbn:de:0297-zib-67462
Benjamin Hiller
Benjamin Hiller
Tom Walther
ZIB-Report
17-68
eng
uncontrolled
approximate convex decomposition
eng
uncontrolled
branch-and-bound
eng
uncontrolled
convex hull reformulation
eng
uncontrolled
disjunctive set
Computer Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Hiller, Benjamin
MODAL-GasLab
TRR154-A04
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6746/ZR-17-68.pdf
6817
eng
reportzib
0
--
2018-03-20
--
Analysis of operating modes of complex compressor stations
We consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. In particular, we propose a refined model that allows to precompute tighter relaxations for each operation mode. These relaxations may be used to strengthen the compressor station submodels in gas network optimization problems. We provide a procedure to obtain the refined model from the input data for the original model. This procedure is based on a nontrivial reduction of the graph representing the gas flow through the compressor station in an operation mode.
1438-0064
urn:nbn:de:0297-zib-68179
under review
Benjamin Hiller
Benjamin Hiller
René Saitenmacher
Tom Walther
ZIB-Report
17-65
eng
uncontrolled
bound tightening
eng
uncontrolled
flow patterns
eng
uncontrolled
model reformulation
eng
uncontrolled
multi-way compressor station
Computer Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Hiller, Benjamin
MODAL-GasLab
TRR154-A04
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6817/ZR-17-65.pdf
7162
2018
eng
51
bachelorthesis
0
--
--
--
Bidirectional A* Search on Time-Dependent Airway Networks
This thesis deals with a new algorithm for finding Shortest Paths on Airway Networks. It is about a Bidirectional A* Search, a Greedy algorithm exploring a network from two sides instead of one. We will use it to solve the so-called 'Horizontal Flight Trajectory Problem', where one searches for an aircraft trajectory between two airports of minimal costs on an Airway Network. The given network will be modeled as a directed graph and in order to reflect reality we concentrate on the dynamic version. Here a timedependent cost function for all arcs is integrated, that shall represent the winds blowing. This way we model the Horizontal Flight Trajectory Problem mathematically as a Time-Dependent Shortest Path Problem.
The basic algorithm idea derives from the algorithm presented in 'Bidirectional A* Search on Time-Dependent Road Networks' [1], where a similar setting is elaborated for road networks. The algorithm procedure bears on a modified generalization of Dijkstra's algorithm, made bidirectional and improved in several aspects. As for the backwards search the arrival times are not known in advance, the reversed graph it occurs on has to be weighted by a lower bound. Contrary to the static case the forwards search still has to go on, when they 'meet' in one node. In the static case, the shortest path would have been found at this point.
For road networks the TDSPP is well-studied, for airway networks cannot be found as much in literature. In order to test efficiency, we implement Dijkstra's algorithm, unidirectional A* Search and Bidirectional A* Search. We draw up how potential functions for the static case could look like and that with a suitable potential A* Search with works approx. 7 times faster than Dijkstra in the dynamic case. Our computations lead also to the result, that the unidirectional A* Search works even better on the network than our new bidirectional approach does. On average it labels fewer nodes and also yields 1,7 times faster to the solutions.
For assessing the efficiency of the different algorithms we compare the running times and to exclude processor characteristics we consider also the set labels relative to the labels on the resulting optimal path. In addition, we present examples of routes visually
and explain shortly why there appear local differences regarding performance of A* Search and Bidirectional A* Search.
false
true
Martin Skutella
Celine Nöckel
Ralf Borndörfer
Ralf Borndörfer
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
LHS-ATN
Technische Universität Berlin
7161
2018
deu
76
masterthesis
0
--
--
--
Über die optimale Platzierung von Ladestationen für Elektrobusse
In dieser Arbeit wird die Platzierung von Ladestationen für Elektrobusse untersucht. Dabei soll für eine Menge an gegebenen Linien eine Menge an Ladestationen gefunden werden, sodass jede Linie mit Nutzung der Ladestationen befahren werden kann und gleichzeitig die Kosten minimal sind. Zunächst wird der Fall betrachtet, dass die Batterie an jeder Station komplett vollgeladen werden könnte. Dieses Problem stellt sich als NP-schwer heraus. Für einige einfachere Fällewerden zudem Algorithmen entwickelt und untersucht. Anschließend wird der Fall einer unbegrenzt großen Batterie betrachtet, wobei an jeder Station derselbe Wert geladen werden kann. Auch dieses Problem ist NP-schwer. Erneut werden Algorithmen zur Lösung vereinfachter Problemstellungen gegeben und analysiert. Wird zudem angenommen, an jeder Station würde ein individueller Wert geladen, so ist das Problem schon für nur eine einzige Linie NP-schwer. Dennoch werden zwei exakte und ein approximierender Algorithmus entwickelt. Schließlich wird eine Batteriekapazität hinzugefügt und die zuvor entwickelten Algorithmen
werden entsprechend angepasst. Für die abschließende Problemdefinition werden verschiedene Batteriegrößen betrachtet und es werden zwei gemischt-ganzzahlige Programme aufgestellt. Anhand von existierenden Buslinien aus Berlin werden diese untersucht. Dabei stellt sich heraus, dass die Batteriekosten einen deutlich größeren Teil der Kosten ausmachen als die Ladestationen. Zudem sollten kleinere Batterien statt größerer und mehr Ladestationen genutzt werden.
false
true
Ralf Borndörfer
Fabian Mett
Ralf Borndörfer
Natalia Kliewer
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
ECMath-MI3
Freie Universität Berlin
7158
2018
deu
45
bachelorthesis
0
--
--
--
Multimodales Routing mit Leihfahrradsystemen am Beispiel Berlins
The aim of multimodal routing is to extract the best integrated journey of multiple
transportation networks. The integration of bike rental networks is challenging
particularly with respect to recognizing a valid path dependent on real-time
availability of bike boarding and alighting places. In this work a common model
for station-based bike rental networks extended with boarding possibilities for
free floating bikes is presented. Moreover a new model for alighting inside a free
floating area is introduced. In addition, a prototype of multimodal routing with
a bike rental network in Berlin is developed by extending the OpenTripPlanner
software. Due to recent public dispute about bike rental networks in Berlin, an
examination about speed-up potential of an integrated bike rental network in the
public transit of Berlin is provided.
Ralf Borndörfer
Christoph Husemann
Ralf Borndörfer
Günter Rote
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
MOIN
Freie Universität Berlin
7160
2018
eng
37
bachelorthesis
0
--
--
--
Analysis of the Shortest Path Problem with Piecewise Constant Crossing Costs
Ralf Borndörfer
Matthias Krug
Ralf Borndörfer
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
LHS-ATN
Freie Universität Berlin
5395
eng
reportzib
0
--
2015-03-12
--
An affine covariant composite step method for optimization with PDEs as equality constraints
We propose a composite step method, designed for equality constrained optimization with partial differential equations. Focus is laid on the construction of a globalization scheme, which is based on cubic regularization of the objective and an affine covariant damped Newton method for feasibility. We show finite termination of the inner loop and fast local convergence of the algorithm. We discuss preconditioning strategies for the iterative solution of the arising linear systems with projected conjugate gradient. Numerical results are shown for optimal control problems subject to a nonlinear heat equation and subject to nonlinear elastic equations arising from an implant design problem in craniofacial surgery.
1438-0064
urn:nbn:de:0297-zib-53954
Optimization Methods and Software, DOI 10.1080/10556788.2016.1241783
Lars Lubkoll
Lubkoll
Anton Schiela
Martin Weiser
ZIB-Report
15-09
eng
uncontrolled
composite step methods
eng
uncontrolled
cubic regularization
eng
uncontrolled
affine covariant
eng
uncontrolled
optimization with PDEs
CALCULUS OF VARIATIONS AND OPTIMAL CONTROL; OPTIMIZATION [See also 34H05, 34K35, 65Kxx, 90Cxx, 93-XX]
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Numerical Mathematics
Computational Medicine
Weiser, Martin
ECMath-CH9
MATHEON-A17
https://opus4.kobv.de/opus4-zib/files/5395/ZR-15-09.pdf
7190
eng
reportzib
0
--
2019-02-04
--
A Concurrent Approach to the Periodic Event Scheduling Problem
We introduce a concurrent solver for the periodic event scheduling problem (PESP). It combines mixed integer programming techniques, the modulo network simplex method, satisfiability approaches, and a new heuristic based on maximum cuts. Running these components in parallel speeds up the overall solution process. This enables us to significantly improve the current upper and lower bounds for all benchmark instances of the library PESPlib.
1438-0064
urn:nbn:de:0297-zib-71907
Ralf Borndörfer
Niels Lindner
Niels Lindner
Sarah Roth
ZIB-Report
19-07
eng
uncontrolled
Periodic Event Scheduling Problem
eng
uncontrolled
Periodic Timetabling
eng
uncontrolled
Mixed Integer Programming
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
Lindner, Niels
Roth, Sarah
ECMath-MI7
https://opus4.kobv.de/opus4-zib/files/7190/concurrent-pesp.pdf
6936
eng
reportzib
0
--
2018-07-02
--
The SCIP Optimization Suite 6.0
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.
1438-0064
urn:nbn:de:0297-zib-69361
Ambros Gleixner
Matthias Miltenberger
Michael Bastubbe
Leon Eifler
Tristan Gally
Gerald Gamrath
Robert Lion Gottwald
Gregor Hendel
Christopher Hojny
Thorsten Koch
Marco E. Lübbecke
Stephen J. Maher
Matthias Miltenberger
Benjamin Müller
Marc E. Pfetsch
Christian Puchert
Daniel Rehfeldt
Franziska Schlösser
Christoph Schubert
Felipe Serrano
Yuji Shinano
Jan Merlin Viernickel
Matthias Walter
Fabian Wegscheider
Jonas T. Witt
Jakob Witzig
ZIB-Report
18-26
eng
uncontrolled
constraint integer programming
eng
uncontrolled
linear programming
eng
uncontrolled
mixed-integer linear programming
eng
uncontrolled
mixed-integer nonlinear programming
eng
uncontrolled
optimization solver
eng
uncontrolled
branch-and-cut
eng
uncontrolled
branch-and-price
eng
uncontrolled
column generation framework
eng
uncontrolled
parallelization
eng
uncontrolled
mixed-integer semidefinite programming
eng
uncontrolled
Steiner tree optimization
NUMERICAL ANALYSIS
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
Gleixner, Ambros
Gottwald, Robert
Hendel, Gregor
Koch, Thorsten
Miltenberger, Matthias
Rehfeldt, Daniel
Serrano, Felipe
Shinano, Yuji
Vigerske, Stefan
Witzig, Jakob
Müller, Benjamin
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
Eifler, Leon
MODAL-Gesamt
Schlösser, Franziska
Viernickel, Jan Merlin
Plan4res
https://opus4.kobv.de/opus4-zib/files/6936/scipopt-60.pdf
6963
eng
reportzib
0
--
2018-07-25
--
ASTS Orientations on Undirected Graphs: Structural analysis and enumeration
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.
1438-0064
urn:nbn:de:0297-zib-69632
Kai Helge Becker
Benjamin Hiller
Benjamin Hiller
ZIB-Report
18-31
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Hiller, Benjamin
MODAL-GasLab
MODAL-Gesamt
Becker, Kai-Helge
ECMATH-MI10
https://opus4.kobv.de/opus4-zib/files/6963/ZR-18-31.pdf
6744
eng
reportzib
0
--
2018-03-01
--
Modelling compressor stations in gas networks
Gas networks are an important application area for optimization. When considering long-range transmission, compressor stations play a crucial role in these applications. The purpose of this report is to collect and systematize the models used for compressor stations in the literature. The emphasis is on recent work on simple yet accurate polyhedral models that may replace more simplified traditional models without increasing model complexity. The report also describes an extension of the compressor station data available in GasLib (http://gaslib.zib.de/) with the parameters of these models.
1438-0064
urn:nbn:de:0297-zib-67443
Benjamin Hiller
Benjamin Hiller
Tom Walther
ZIB-Report
17-67
eng
uncontrolled
MINLP model
eng
uncontrolled
compressor station
eng
uncontrolled
gas compressor modeling
eng
uncontrolled
nonlinear model
eng
uncontrolled
polyhedral model
Computer Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Hiller, Benjamin
MODAL-GasLab
TRR154-A04
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6744/ZR-17-67.pdf
7154
2018
eng
60
masterthesis
0
--
--
--
Mathematical optimization of joint order batching and picker routing problems
In this thesis we study order picking optimization problems for a two-blocks rectangle warehouse layout. We present combinatorial formulations and linear programming models based on the Steiner graph representation for order batching, picker routing, and joint order batching and picker routing problems. A special case of the latter is
considered. This case assumes that each order contains exactly one item and each item can be picked from different possible locations in a warehouse. The underlying optimization problem is called joint multi-location order batching and picker routing problem (JMLOBPRP).
Since having only one-item orders turns the JMLOBPRP into a special case of a capacitated vehicle routing problem, we suggest to implement algorithmic approaches for those to solve the JMLOBPRP. In particular, we define the JMLOBPRP as a generalization of the resource constrained assignment problem, for which a regional search method exists. The intention of the thesis is to investigate how a relaxation of the JMLOBPRP, a so-called group assignment problem (GrAP), can be solved following the ideas of regional search. We present a mathematical model of the GrAP and prove that it is NP-hard. Furthermore, we propose a novel heuristic algorithm for the GrAP. We call this method a network search algorithm, as it is based on a Lagrangian relaxation
of the GrAP, which is solved by the network simplex method. On each its iteration network search examines a solution region suggested by the network simplex algorithm and improves the incumbent solution.
Numerical experiments are conducted to assess a performance of the network search method. We create more realistic problem instances. The proposed algorithm is compared to the integer optimal solution of the GrAP and optimal fractional solution of its linear relaxation. Both computed using the commercial linear solver Gurobi. Our experiments
show that the developed network search algorithm leads to the hight-quality solution within a short computing time. The results obtained testing large problem instances which cannot be solved by Gurobi within a reasonable computing time, show that the network search method provides a solution approach which can be used in practice.
Ralf Borndörfer
Ekaterina Oleynikova
Ralf Borndörfer
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
MODAL-RailLab
MODAL-Gesamt
Freie Universität Berlin
7153
2017
deu
74
masterthesis
0
--
--
--
Alternativen zum Dijkstra Algorithmus in der (Nah-) Verkehrsoptimierung
In dieser Arbeit betrachten wir das Problem, für den Fahrplan eines (Nah-) Verkehrsnetzes schnellste Wege zu berechnen. Da die Verkehrsmittel zu unterschiedlichen Zeiten von den einzelnen Haltestellen/Bahnhöfen abfahren, kann das Problem nicht ohne Weiteres mit einem „statischen“ Graphen modelliert werden. Es gibt zwei unterschiedliche Ansätze für dieses zeitabhängige Problem: Erstens können die verschiedenen An-/Abfahrtereignisse an einem Halt durch „Kopien“ dargestellt werden, das ist das zeit-expandierte Modell. Zweitens können die Gewichte der Kanten zeitabhängig sein, das ist
das zeitabhängige Modell. Wir untersuchen in dieser Arbeit, wie der „klassische“ Dijkstra-Algorithmus und der A* Algorithmus mit einer geeigneten Heuristik im Vergleich abschneiden. Die gewählte Heuristik ist der Abstand zum Zielknoten, wenn die Abfahrtszeiten ignoriert werden. Nach unseren Untersuchungen zeigt sich, dass der A* Algorithmus dem Dijkstra-Algorithmus weit überlegen ist für genügend große Nahverkehrsnetze. Wir testen anhand der echten Verkehrsnetze von Berlin und Aachen. Unsere Berechnungen zeigen, dass die gewählte Heuristik besonders gut ist für Start- und Zielknoten, welche unabhängig von ihrer Distanz nur 1–2 verschiedene mögliche kürzeste Pfade für alle Zeitschritte haben. Dort ist der A* Algorithmus bis zu 20-mal schneller. Dies kommt aber nicht häufig in unseren Testinstanzen vor. Die einzelnen Laufzeitvergleich zeigen, dass
der A* Algorithmus durchschnittlich 7-mal so schnell ist wie der Dikstra-Algorithmus.
false
true
Ralf Borndörfer
Björn Jeschke
Ralf Borndörfer
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
ECMath-MI3
Freie Universität Berlin
7150
2018
eng
73
masterthesis
0
--
--
--
The Bienstock Zuckerberg Algorithm for the Rolling Stock Rotation Problem
The design of rolling stock rotations is an important task in large-scale railway planning. This so-called rolling stock rotation problem (RSRP) is usually tackled using an integer programming approach. Markus Reuther did so in his dissertation [15] for the ICE railway network of DB ("Deutsche Bahn"). Due to the size of the network and the complexity of further technical requirements, the resulting integer problems tend to become very large and computationally involved. In this thesis, we tackle the linear programming relaxation of the RSRP integer program. We will do so by applying a modified version of an algorithm recently proposed by Dan Bienstock and Mark Zuckerberg [2] for the precedence constrained production scheduling
problem that arises in open pit mine scheduling. This problem contains a large number of "easy" constraints and a relatively small number of "hard" constraints. We will see that a similar problem structure can also be found in the RSRP. The Bienstock-Zuckerberg algorithm relies on applying Lagrangian relaxation to the hard constraints as well as on partitioning the variable set. We propose three different partition schemes which try to exploit the specific problem structure of the RSRP. Furthermore, we will discuss the influence of primal degeneracy on the algorithm's performance, as well as possible merits of perturbating the right-hand side of the constraint matrix. We provide computational results to assess the performance of those approaches.
false
true
Ralf Borndörfer
Ricardo Euler
Ralf Borndörfer
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Euler, Ricardo
MOIN
Freie Universität Berlin
7151
2018
deu
59
bachelorthesis
0
--
--
--
Der Einfluss von Langzahlarithmetik auf das Gewichtsraumpolyeder in mehrkriterieller Optimierung
Die Arbeit befasst sich mit einem gewichtsraumbasierten Algorithmus, der ganzzahlige und lineare Optimierungsprobleme mit mehreren Zielfunktionen
löst und die Menge der unterstützt nicht dominierten Punkte ermittelt. Die dabei erzeugten Gewichtsraumpolyeder sind das entscheidende Mittel, um die gesuchte Lösungsmenge zu bestimmen. Aus softwaretechnischer Sicht sind numerische Ungenauigkeiten potentielle Fehlerquellen, die sich negativ auf das Endergebnis auswirken. Aus diesem Grund untersuchen wir anhand von Zuweisungs- und Rucksackinstanzen mit 3 Zielfunktionen, inwieweit der Gebrauch von Langzahlarithmetik die Gewichtsraumpolyeder und die damit verbundene Menge der unterstützt nicht dominierten Punkte beeinflusst.
false
true
Martin Skutella
Marie Wirsching
Ralf Borndörfer
Ralf Borndörfer
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
CRC1026
Technische Universität Berlin
6848
eng
reportzib
0
--
2018-04-27
--
A Polyhedral Study of Event-Based Models for the Resource-Constrained Project Scheduling Problem
We consider event-based Mixed-Integer Programming (MIP) models for the Resource-Constrained Project Scheduling Problem (RCPSP) that represent an alternative to the common time-indexed model (DDT) of Pritsker et al. (1969) for the case where the underlying time horizon is large or job processing times are subject to huge variations. In contrast to the time-indexed model, the size of event-based models does not depend on the time horizon. For two event-based formulations OOE and SEE of Koné et al. (2011) we present new valid inequalities that dominate the original formulation. Additionally, we introduce a new event-based model: the Interval Event-Based Model (IEE). We deduce linear transformations between all three models that yield the strict domination order IEE > SEE > OOE for their linear programming (LP) relaxations, meaning that IEE has the strongest linear relaxation among the event-based models. We further show that the popular DDT formulation can be retrieved from IEE by certain polyhedral operations, thus giving a unifying view on a complete branch of MIP formulations for the RCPSP. In addition, we analyze the computational performance of all presented models on test instances of the PSPLIB (Kolisch and Sprecher 1997).
1438-0064waoa
urn:nbn:de:0297-zib-68485
under review
Alexander Tesch
Alexander Tesch
ZIB-Report
17-79
eng
uncontrolled
Scheduling
eng
uncontrolled
Mixed-Integer Programming
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Tesch, Alexander
BMBF-IBOSS
https://opus4.kobv.de/opus4-zib/files/6848/compactMIP.pdf
6933
eng
reportzib
0
--
2018-06-26
--
Improving Energetic Propagations for Cumulative Scheduling
We consider the Cumulative Scheduling Problem (CuSP) in which a set of $n$ jobs must be scheduled according to release dates, due dates and cumulative resource constraints. In constraint programming, the CuSP is modeled as the cumulative constraint. Among the most common propagation algorithms for the CuSP there is energetic reasoning (Baptiste et al., 1999) with a complexity of O(n^3) and edge-finding (Vilim, 2009) with O(kn log n) where k <= n is the number of different resource demands. We consider the complete versions of the propagators that perform all deductions in one call of the algorithm. In this paper, we introduce the energetic edge-finding rule that is a generalization of both energetic reasoning and edge-finding. Our main result is a complete energetic edge-finding algorithm with a complexity of O(n^2 log n) which improves upon the complexity of energetic reasoning. Moreover, we show that a relaxation of energetic edge-finding with a complexity of O(n^2) subsumes edge-finding while performing stronger propagations from energetic reasoning. A further result shows that energetic edge-finding reaches its fixpoint in strongly polynomial time. Our main insight is that energetic schedules can be interpreted as a single machine scheduling problem from which we deduce a monotonicity property that is exploited in the algorithms. Hence, our algorithms improve upon the strength and the complexity of energetic reasoning and edge-finding whose complexity status seemed widely untouchable for the last decades.
1438-0064
urn:nbn:de:0297-zib-69331
Alexander Tesch
Alexander Tesch
ZIB-Report
18-29
eng
uncontrolled
Cumulative Scheduling
eng
uncontrolled
Constraint Programming
eng
uncontrolled
Propagation Algorithm
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Tesch, Alexander
BMBF-IBOSS
https://opus4.kobv.de/opus4-zib/files/6933/enef.pdf
7110
eng
reportzib
0
--
2018-12-07
--
Intersection cuts for factorable MINLP
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.
1438-0064
urn:nbn:de:0297-zib-71105
Felipe Serrano
Felipe Serrano Musalem
ZIB-Report
18-59
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Serrano, Felipe
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/7110/intercuts.pdf
7155
2018
deu
44
masterthesis
0
--
--
--
Optimierung von Deployment- und Umgebungs-Integrität durch ein dezentrales Konfigurationsrepository auf Basis einer Blockchain
Viele Firmen nutzen für ihre eigenen Softwareentwicklungen verschiedene Server mit unterschiedlichen Konfigurationen. Manche Server werden dazu eingestzt das Verhalten einer Software in einer bestimmten Umgebung zu testen und andere dienen zur Bereitstellung der Software für den Endnutzer. Hierbei ist es wichtig, dass die Konfiguration der Server regelmäßig überprüft wird. Eine solche Sicherstellung der Deployment- und Umgebungs-Integrität wird meistens durch eine Mitarbeiter der Firma oder durch einen externen Dienstleister erbracht. D.h. die Firma muss sich auf die Zuverlässigkeit eines Mitarbeiters oder einer externen Dienstleistung verlassen, bie zunehmender Komplexität ist sie sogar abhängig.
Das Ziel dieser Masterarbeit ist es, zu untersuchen, ob die Sicherstellung der Deployment- und Umgebungs-Integrität durch automatisierte kryptografische Beweise, anstelle externer Dienstleistungen oder anderer Mitarbeiter, gewährleistet werden kann. Als Anwendungsfall dient die Toll Collect GmbH. Im ersten Teil dieser Arbeit wird das Matheamtische Modell einer Blockchain erläutert. die Blockchain wurde erstmals in einem Dokument, welches unter dem Pseudonym Satoshi Nakamoto veröffentlicht wurde, beschrieben. Die erste große Anwendungen der Blockchain ist das dezentrale Zahlungssystem Bitcoin. Im zweiten Teil dieser Arbeit wird die Softwareimplementierung vorgestellt, welche im Rahmen dieser Arbeit entstanden ist. Mithilfe dieses Programms kann die Deployment- und Umgebungs-Integrität durch eine heirführ entwickelte Blockchainlösung dezentralisiert werden. Es wird außerdem der Übergang vom Mathematischen Modell zur Implementierung gezeigt.
Thorsten Koch
Christopher Wyczik
Ralf Borndörfer
Ralf Borndörfer
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
MODAL-SynLab
MODAL-Gesamt
Technische Universität Berlin
6836
eng
reportzib
0
--
2018-04-10
--
Feature-Based Algorithm Selection for Mixed Integer Programming
Mixed integer programming is a versatile and valuable optimization tool. However, solving specific problem instances can be computationally demanding even for cutting-edge solvers. Such long running times are often significantly reduced by an appropriate change of the solver's parameters. In this paper we investigate "algorithm selection", the task of choosing among a set of algorithms the ones that are likely to perform best for a particular instance.
In our case, we treat different parameter settings of the MIP solver SCIP as different algorithms to choose from. Two peculiarities of the MIP solving process have our special attention. We address the well-known problem of performance variability by using multiple random seeds. Besides solving time, primal dual integrals are recorded as a second performance measure in order to distinguish solvers that timed out.
We collected feature and performance data for a large set of publicly available MIP instances. The algorithm selection problem is addressed by several popular, feature-based methods, which have been partly extended for our purpose. Finally, an analysis of the feature space and performance results of the selected algorithms are presented.
1438-0064
urn:nbn:de:0297-zib-68362
Alexander Georges
Gregor Hendel
Ambros Gleixner
Gorana Gojic
Robert Lion Gottwald
David Haley
Gregor Hendel
Bartlomiej Matejczyk
ZIB-Report
18-17
eng
uncontrolled
algorithm selection
eng
uncontrolled
mixed integer programming
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Gleixner, Ambros
Gottwald, Robert
Hendel, Gregor
ASTfSCM
MODAL-SynLab
Siemens
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6836/main.pdf
7111
eng
reportzib
0
--
2018-12-07
--
Building Optimal Steiner Trees on Supercomputers by using up to 43,000 Cores
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.
1438-0064
urn:nbn:de:0297-zib-71118
Yuji Shinano
Yuji Shinano
Daniel Rehfeldt
Thorsten Koch
ZIB-Report
18-58
Computing Methodologies
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Koch, Thorsten
Rehfeldt, Daniel
Shinano, Yuji
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/7111/ZIB-Report-18-58.pdf
https://opus4.kobv.de/opus4-zib/files/7111/ZIB-Report-18-58-rev.pdf
6464
eng
reportzib
0
--
2017-07-20
--
Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization
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.
Operations Research Proceedings 2017
1438-0064
urn:nbn:de:0297-zib-64645
Matthias Miltenberger
Matthias Miltenberger
Ted Ralphs
Daniel Steffy
ZIB-Report
17-43
eng
uncontrolled
Mixed Integer Programming
eng
uncontrolled
Linear Programming
eng
uncontrolled
Algorithm Analysis
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Miltenberger, Matthias
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6464/ZR-17-43-published.pdf
7157
2018
deu
49
bachelorthesis
0
--
--
--
Approximation von Windkomponenten in der Luftfahrt durch lineare Interpolation
Das Wind-Interpolation-Problem (WIP) ist ein bisher selten diskutiertes Problem der Flugplanungsoptimierung, bei dem es darum geht, Wind-Komponenten auf einer Luftstraße zu approximieren. Anhand von Winddaten, die vektoriell an den Gitterpunkten eines den Globus umspannenden Gitters vorliegen, soll bestimmt werden, wie viel Wind entlang der Luftstraße und quer zu ihr weht. Thema dieser Arbeit ist ein Spezialfall des WIP, nämlich das statische WIP auf einer Planfläche (SWIPP). Dazu wird zuerst ein Algorithmus besprochen, der das SWIPP zwar löst, aber einem Ansatz zugrunde liegt, der bei genauerem Hinsehen nicht sinnvoll erscheint: hier wird Wind zwischen vier Punkten interpoliert, wozu es keine triviale Methode gibt. Ähnlich zu diesem Algorithmus, der heute als State-of-the-Art gilt, wird als Ergebnis dieser Arbeit ein neuer Algorithmus vorgestellt, der das SWIPP akkurater und schneller löst. Hier wird deutlich seltener
auf die Interpolation zwischen vier Punkten zurückgegriffen - stattdessen wird fast immer linear zwischen zwei Punkten interpoliert. Die Algorithmen zum Lösen des SWIPP werden auf ihre Genauigkeit,
asymptotische Laufzeit und Geschwindigkeit untersucht und verglichen. Als Testareal dienen zum einen echte Wetterdaten sowie das Luftstraßennetz, das die Erde umspannt, und zum anderen ein eigens generiertes Windfeld und fiktive Luftstraßen. Es wird gezeigt, dass der hier vorgestellte Algorithmus die State-of-the-Art-Variante in allen genannten Aspekten übertrifft.
urn:nbn:de:0297-zib-71570
false
true
Ralf Borndörfer
Leo Vornberger
Ralf Borndörfer
Thorsten Koch
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
LHS-ATN
Freie Universität Berlin
https://opus4.kobv.de/opus4-zib/files/7157/Vornberger2018.Approximation von Windkomponenten in der Luftfahrt durch lineare Interpolation (Bachelor's thesis).pdf
7156
2018
deu
52
bachelorthesis
0
--
--
--
Lineare Gleichungssysteme modulo T
Mit dem Voranschreiten der Technologie erhalten die öffentlichen Verkehrsmittel eine größere Bedeutung. Die Beförderung mehrerer Personen eröffnet der Gesellschaft viele Möglichkeiten, unter Anderem den Vorteil der Zeitersparnis. Die Dauer des Verkehrswegs mit öffentlichen Verkehrsmitteln ist häufig geringer, als die mit individuellen Verkehrsmitteln. Jedes öffentliche Transportmittel ist mit einem Fahrplan versehen. Dieser bietet Passagieren, die öffentliche Verkehrsmittel öfter nutzen, eine Strukturierung und Planung ihrer Zeit. Dabei lassen sich Taktfahrpläne aufgrund ihres periodischen Verhaltens leicht einprägen. Dieses periodische Verhalten ist durch mathematische Modellierungen darstellbar. Das persönliche Nutzverhalten vieler Bürger im Personenverkehr ist auf die öffentlichen Verkehrsmittel beschränkt. Diese beinhalten im Gegensatz zum individuellen Verkehrsmittel eine Wartezeit. Dabei stellt sich die Frage, ob man anhand mathematischer Modelle diese Wartezeit minimieren kann. Eine bekannte mathematische Modellierung dieses Problems ist das Periodic Event Scheduling Problem (PESP). Die optimale Planung eines periodischen Taktfahrplanes steht im Vordergrund.
Während ich dieses Problem betrachtet habe, wurde ich auf das Rechnen mit linearen Gleichungssystemen modulo T aufmerksam. Bei periodischen Taktfahrplänen wird ein einheitliches zeitliches Muster, welches sich nach T Minuten wiederholt, betrachtet. Das dabei zu betrachtende Lösungsproblem eröffnet ein Teilgebiet der Mathematik, welches bislang nicht im Vordergrund stand: Das Lösen linearer Gleichungen modulo T, wobei T für die Zeit in Minuten steht und somit 60 ist. Da 60 keine Primzahl ist, kann – wie im Laufe der Arbeit präsentiert – das lineare Gleichungssystem nicht mehr über einen Körper gelöst werden. Lineare Gleichungssysteme werden nun über Nicht-Körpern betrachtet. Die Literatur weist sowohl im deutschsprachigem als auch im englischsprachigen Raum wenig Umfang bezüglich linearer Gleichungssysteme über Nicht-Körper auf. Der Bestand an Fachliteratur bezüglich den Themen lineare diophantische Gleichungssysteme, Hermite-
Normalform und Smith-Normalform ist zurzeit gering, dennoch erreichbar, beispielsweise in [1], welches in dieser Bachelorarbeit genutzt wurde. Insbesondere wurde ich bei der Suche nach geeigneter Literatur zu linearen Gleichungssystemen über Restklassenringe, die keinen Körper bilden, nicht fündig. Dabei recherchierte ich sowohl in den Universitätsbibliotheken als auch in webbasierenden Suchmaschinen.
Aufgrund dem geringen Bestand an Fachliteratur in diesem Kontext, war ich gezwungen, an vielen Stellen eigene logische Verknüpfungen zu konzipieren und zu beweisen. Dies brachte viele Schwierigkeiten mit sich, die mit bestmöglichem Verständnis bearbeitet wurden.
Abseits der Zugänglichkeit der Literatur, finde ich es sehr überraschend, dass sich viele Professoren der Mathematik mit diesem Themenbereich nicht beschäftigten. Insbesondere gingen von den Dozenten, die ich um Literaturempfehlung bat, kein Werk aus. Damit
wurde das Thema "Lineare Gleichungssysteme Modulo T" einerseits eine große Herausforderung, andererseits eine große Motivation, da ich mit dieser Bachelorarbeit vielen Interessenten der Mathematik als Sekundärliteratur dienen kann.
urn:nbn:de:0297-zib-71560
false
true
Ralf Borndörfer
Fatima Akil
Ralf Borndörfer
Nils Lindner
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
ECMath-MI3
Freie Universität Berlin
https://opus4.kobv.de/opus4-zib/files/7156/Akil2018.Lineare Gleichungssysteme modulo T (Bachelor's thesis).pdf
6042
eng
reportzib
0
--
2016-09-23
--
Reduction Techniques for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem
The concept of reduction has frequently distinguished itself as a pivotal ingredient of exact solving approaches for the Steiner tree problem in graphs. In this paper we broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical applications: The prize-collecting Steiner tree problem, the rooted prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem.
By introducing and subsequently deploying numerous new reduction methods, we are able to drastically decrease the size of a large number of benchmark instances, already solving more than 90 percent of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the state-of-the-art Steiner problem solver SCIP-Jack.
1438-0064
urn:nbn:de:0297-zib-60420
10.1002/net.21857
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
Stephen Maher
ZIB-Report
16-47
eng
uncontrolled
Steiner tree problems
eng
uncontrolled
reduction techniques
eng
uncontrolled
prize-collecting Steiner tree problem
eng
uncontrolled
maximum-weight connected subgraph problem
Software
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Koch, Thorsten
Rehfeldt, Daniel
Maher, Stephan
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6042/PcMwReductions.pdf