90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Refine
Year of publication
Document Type
- ZIB-Report (175)
- Master's Thesis (17)
- Bachelor's Thesis (9)
- Doctoral Thesis (6)
- Article (2)
- In Proceedings (1)
Keywords
Institute
- Mathematical Optimization (156)
- Mathematical Optimization Methods (34)
- Network Optimization (29)
- Applied Algorithmic Intelligence Methods (14)
- AI in Society, Science, and Technology (9)
- Mathematics of Telecommunication (7)
- Mathematics of Transportation and Logistics (6)
- Mathematical Algorithmic Intelligence (4)
- Numerical Mathematics (4)
- ZIB Allgemein (4)
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Railway Track Allocation
(2012)
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.
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.
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.
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.
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.
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$.
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.
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.
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.
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.
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".
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.
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.
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.
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.
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.
Convergence Analysis of Smoothing Methods for Optimal Control of Stationary Variational Inequalities
(2011)
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.
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.
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.
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.
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.