Refine
Year of publication
Keywords
- Robust Optimization (4)
- FPTAS (2)
- Flows over Time (2)
- Knapsack Problem (2)
- Network Flow (2)
- Network Flows (2)
- Recovery (2)
- online optimization (2)
- Airline revenue management (1)
- Approximation (1)
Cyclic timetabling for public transportation companies is usually modeled by the periodic
event scheduling problem. To deduce a mixed-integer programming formulation, artificial integer
variables have to be introduced. There are many ways to define these integer variables.
We show that the minimal number of integer variables required to encode an instance is
achieved by introducing an integer variable for each element of some integral cycle basis. An
integral cycle basis consists of |A|-|V|+1 oriented cycles of a directed graph D = (V;A) that
enable any oriented cycle of the directed graph to be expressed as an integer linear combination.
The solution times for the originating application vary extremely with different integral
cycle bases. However, our computational studies show that the width of integral cycle bases
is a good empirical measure for the solution time of the MIP. Clearly, integral cycle bases
permit a much wider choice than the former standard approach, in which integer variables are
associated with the co-tree arcs of some spanning tree. Hence, to formulate better solvable
integer programs, we present algorithms that construct integral cycle bases of small width.
To that end, we investigate classes of directed cycle bases that are closely related to integral
cycle bases, namely (generalized) fundamental and undirected cycle bases. This gives rise to
both, a compact classification of directed cycle bases and notable reductions of running times
for cyclic timetabling.
Periodic timetabling for railway networks is usually modeled by the Periodic Event Scheduling
Problem (PESP). This model permits to express many requirements that practitioners impose
on periodic railway timetables. We discuss a requirement practitioners are asking for, but which,
so far, has not been the topic of mathematical studies: the concept of symmetry.
Several motivations why symmetric timetables might seem promising will be given. However,
we provide examples showing that symmetry leads to suboptimality.
To integrate symmetry into the graph model of the PESP, there are many obstacles to overcome.
Nevertheless, adding symmetry requirements to mixed-integer programming formulations
explicitly, enables MIP solvers such as CPLEX
to terminate earlier with good solutions.
We discuss the problem to count, or, more modestly, to estimate
the number f(m; n) of unimodular triangulations of the planar grid of
size m * n.
Among other tools, we employ recursions that allow one to compute
the (huge) number of triangulations for small m and rather large n by
dynamic programming; we show that this computation can be done in
polynomial time if m is fixed, and present computational results from
our implementation of this approach.
We also present new upper and lower bounds for large m and n,
and we report about results obtained from a computer simulation of
the random walk that is generated by
ips.
We consider the scheduling problem of minimizing the average-weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms.
Today's telecommunication networks are configured statically. Whenever a connection
is established, the customer has permanent access to it. However, it is
observed that usually the connection is not used continuously. At this point, dynamic
provisioning could increase the utilization of network resources. WDM
based Optical Transport Networks (OTNs) will shortly allow for fast dynamic
network reconfiguration. This enables optical broadband leased line services on
demand. Since service requests competing for network resources may lead to service
blocking, it is vital to use appropriate strategies for routing and wavelength
assignment in transparent optical networks. We simulate the service blocking
probabilities of various dynamic algorithms for this problem using a well-founded
traffic model for two realistic networks. One of the algorithms using shortest path
routings performs best on all instances. Surprisingly, the tie-breaking rule between
equally short paths in different wavelengths decides between success or
failure.
Given a set of service requests (events), a set of guided servers (units),
and a set of unguided service contractors (conts), the vehicle dispatching problem
VDP is the task to find an assignment of events to units and conts as well as tours
for all units starting at their current positions and ending at their home positions
(dispatch) such that the total cost of the dispatch is minimized.
The cost of a dispatch is the sum of unit costs, cont costs, and event costs. Unit
costs consist of driving costs, service costs and overtime costs; cont costs consist of
a fixed cost per service; event costs consist of late costs linear in the late time, which
occur whenever the service of the event starts later than its deadline.
The program ZIBDIP based on dynamic column generation and set partitioning
yields solutions on heavy-load real-world instances (215 events, 95 units) in less
than a minute that are no worse than 1% from optimum on state-of-the-art personal
computers.
We consider a model for scheduling under uncertainty. In this model, we combine the main characteristics of online and stochastic scheduling in a simple and natural way. Job processing times are assumed to be stochastic, but in contrast to traditional stochastic scheduling models, we assume that jobs arrive online, and there is no knowledge about the jobs that will arrive in the future. The model incorporates both, stochastic scheduling and online scheduling
as a special case. The particular setting we consider is non-preemptive parallel machine scheduling, with the objective to
minimize the total weighted completion times of jobs. We analyze
simple, combinatorial online scheduling policies for that model, and
derive performance guarantees that match performance guarantees previously
known for stochastic and online parallel machine scheduling, respectively.
For processing times that follow NBUE distributions, we
improve upon previously best known performance bounds from
stochastic scheduling, even though we consider a more general
setting.
Many online problems encountered in real-life involve a two-stage decision process: upon arrival of a new request, an irrevocable
first-stage decision (the assignment of a specific resource to the request) must be made immediately, while in a second stage process, certain ``subinstances'' (that is, the instances of all requests assigned to a particular resource) can be solved to optimality (offline) later.
We introduce the novel concept of an Online Target Date Assignment Problem (OnlineTDAP) as a general framework for online problems with this nature. Requests for the OnlineTDAP become known at certain dates. An online algorithm has to assign a target date to each request, specifying on which date the request should be processed (e.g., an appointment with a customer for a
washing machine repair). The cost at a target date is given by the downstream cost, the optimal cost of processing all requests
at that date w.r.t. some fixed downstream offline optimization problem (e.g., the cost of an optimal dispatch for service
technicians). We provide general competitive algorithms for the OnlineTDAP independently of the particular downstream problem,
when the overall objective is to minimize either the sum or the maximum of all downstream costs. As the first basic examples, we analyze the competitive ratios of our algorithms for the particular academic downstream problems of bin-packing, nonpreemptive scheduling on identical parallel machines, and routing a traveling salesman.
A multistage stochastic programming approach to airline network revenue management is presented. The objective is to determine seat protection levels for all itineraries, fare classes, point of sales of the airline network and all data collection points of the booking horizon such that the expected revenue is maximized. While the passenger demand and cancelation rate processes are the stochastic inputs of the model, the stochastic protection level process represents its output and allows to control the booking process. The stochastic passenger demand and cancelation rate processes are approximated by a nite number of tree structured scenarios. The scenario tree is generated from historical data using a stability-based recursive scenario reduction scheme. Numerical results for a small hub-and-spoke network are reported.
The standard computational methods for computing the optimal value functions of Markov Decision Problems (MDP) require the exploration of the entire state space. This is practically infeasible for applications with huge numbers of states as they arise, e.g., from modeling the decisions in online optimization problems by MDPs. Exploiting column generation techniques, we propose and apply an LP-based method to determine an epsilon-approximation of the optimal value function at a given state by inspecting only states in a small neighborhood. In the context of online optimization problems, we use these methods in order to evaluate the quality of concrete policies with respect to given initial states. Moreover, the tools can also be used to obtain evidence of the impact of single decisions. This way, they can be utilized in the design of policies.
Ein gemischt-ganzzahliges lineares Optimierungsmodell für ein Laserschweißproblem im Karosseriebau
(2006)
Wir betrachten das Problem der Betriebsplanung von Laserschweißrobotern im Karosseriebau. Gegeben ist eine Menge von Schweißnähten, die innerhalb einer Fertigungszelle an einem Karosserieteil gefertigt werden müssen. Die Schweißnähte werden durch mehrere parallel betriebene Roboter bearbeitet. Die Aufgabe besteht darin, für jeden Roboter eine Reihenfolge und eine zeitliche Koordinierung seiner Bewegungen zu finden, so dass alle Schweißnähte innerhalb der Taktzeit der Fertigungszelle bearbeitet werden und so wenig Laserquellen wie möglich eingesetzt werden. Dabei müssen einige Nebenbedingungen berücksichtigt werden. Für dieses spezielle Schweißproblem haben wir eine Formulierung als gemischt-ganzzahliges lineares Programm entwickelt, welches sich für die untersuchten praktischen Fälle sehr schnell lösen lässt.
The Bottleneck Shortest Path Problem is a basic problem
in network optimization. The goal is to determine the limiting capacity of any path between two specified vertices of the network. This is
equivalent to determining the unsplittable maximum flow between the
two vertices. In this note we analyze the complexity of the problem, its
relation to the Shortest Path Problem, and the impact of the underlying
machine/computation model.
We study a so-called static approach for the problem of routing vehicles conflict-free through a given street network. In fact, we assume that routes are computed without taking time-dependences into account
and collisions are avoided via a particular reservation procedure. In this context, the task is to cope with two arising problems: the appearance of congestion and detours on the one hand and the risk of deadlocks on the other.
We provide a two-stage routing approach for that problem. In the first phase we focus on balancing the load on the edges of the
given graph that models the underlying street network. Therefore, we consider the Online Load Balancing Problem with Bounded Stretch
Factor and give an optimal algorithm with respect to a specific performance ratio, the stretch factor restricted competitive ratio. Furthermore, in a second phase, we investigate the detection and avoidance of deadlock situations.
For the evaluation of the entire algorithm we consider the routing of Automated Guided Vehicles (AGVs) at HHLA Container Terminal
Altenwerder (CTA).
We consider scheduling on a single machine with one non-availability period to minimize the weighted sum of completion times. We provide a preemptive algorithm with an approximation ratio arbitrarily close to the Golden Ratio,~$(1+\sqrt{5})/2+\eps$, which improves on a previously best known~$2$-approximation. The non-preemptive version of the same algorithm yields a~$(2+\eps)$-approximation.
We consider the preemptive and non-preemptive problems of scheduling jobs with precedence constraints on parallel machines with the
objective to minimize the sum of~(weighted) completion times. We investigate an online model in which the scheduler learns about a
job when all its predecessors have completed. For scheduling on a single machine, we show matching lower and upper bounds of~$\Theta(n)$ and~$\Theta(\sqrt{n})$ for jobs with general and equal weights, respectively. We also derive corresponding results on parallel machines.
Our result for arbitrary job weights holds even in the more general stochastic online scheduling model where, in addition to the limited information about the job set, processing times are uncertain. For a
large class of processing time distributions, we derive also an improved performance guarantee if weights are equal.
We study Nash equilibria and the price of anarchy in the context of flows over time. Many results on static routing games have been obtained over the last ten years. In flows over time (also called dynamic flows), flow travels through a network over time and, as a consequence, flow values on edges
change over time. This more realistic setting has not been tackled from the viewpoint of algorithmic game theory yet; on the other hand, there is a rich literature on game theoretic aspects of flows over time in the traffic community.
In this paper, we present the first known results on the price of anarchy for flows over time. We also present algorithms for computing Nash flows over time. Those algorithms have to iteratively solve certain interesting and new static flow problems. Our results are based on a novel characterization of Nash equilibria for flows over time. The underlying flow over time model is a variant of the so-called deterministic queuing model that is very popular in road traffic simulation and related fields.
Mehta, Roughgarden, and Sundararajan recently introduced a new class of cost sharing mechanisms called acyclic mechanisms. These mechanisms achieve a slightly weaker notion of truthfulness than the well-known Moulin mechanisms, but provide additional freedom to improve budget balance and social cost approximation guarantees. In this paper, we investigate the potential of acyclic mechanisms for combinatorial optimization problems. In particular, we study a subclass of acyclic mechanisms which we term singleton acyclic mechanisms. We show that every rho-approximate algorithm that is partially increasing can be turned into a singleton acyclic mechanism that is weakly group-strategyproof and rho-budget balanced. Based on this result, we develop singleton acyclic mechanisms for parallel machine scheduling problems with completion time objectives, which perform extremely well both with respect to budget balance and social cost.
About 15 years ago, Goemans and Williamson formally introduced the primal-dual framework for approximation algorithms and applied it to a class of network design optimization problems. Since then literally hundreds of results appeared that extended, modified and applied the technique to a wide range of optimization problems.
In this paper we define a class of cost-sharing games arising from Goemans and Williamson's original network design problems. We then show how to derive a group-strategyproof (i.e., collusion resistant) mechanism for such a game, using an existing primal-dual algorithm for the underlying optimization problem as a black box. The budget-balance factor of this mechanism is proportional to the performance ratio of the primal-dual algorithm if the optimization problem satisfies an additional technical condition.
Most existing collusion-resistant cost-sharing mechanisms are obtained through skillful adaptation of existing primal-dual algorithms for the associated optimization problems. This paper shows that, at least for a large class of games arising from network design problems, no such adaptation is necessary.
This paper proposes a new mathematical model for the open pit mine planning problem,
based on continuous functional analysis. The traditional models for this problem have been
constructed by using discrete 0-1 decision variables, giving rise to large-scale combinatorial
and Mixed Integer Programming (MIP) problems. Instead, we use a continuous approach
which allows for a refined imposition of slope constraints associated with geotechnical stability.
The model introduced here is posed in a suitable functional space, essentially the
real-valued functions that are Lipschitz continuous on a given two dimensional bounded region.
We derive existence results and investigate some qualitative properties of the solutions
Systems of rail-mounted vehicles play a key role in many logistics applications, and the efficiency of their operation frequently has a significant impact on the overall performance of the surrounding production environment. In theory, assigning transport requests to the vehicles of such systems and scheduling their execution amounts to finding k tours on a common line, where tours may never cross each other in time--dynamic collision constraints need to be respected. The goal is to minimize the makespan for a given set of transport requests.
We establish a model capturing the core challenges in transport planning problems of this type and relate it to other models in literature. After proving NP-hardness for a basic version of the problem, the large part of the paper is dedicated to devising various fast heuristic algorithms suitable for practice. We present computational results regarding the performance of the algorithms proposed for several classes of problem instances.
Flows over time generalize classical ``static'' network flows by introducing a temporal dimension. They can thus be used to model non-instantaneous travel times for flow and variation of flow values over time, both of which are crucial characteristics in many real-world routing problems. There exist two different models of flows over time with respect to flow conservation: one where flow might be stored temporarily at intermediate nodes and a stricter model where flow entering an intermediate node must instantaneously progress to the next arc. While the first model is in general easier to handle, the second model is often more realistic since in applications like, e.\,g., road traffic, storage of flow at intermediate nodes is undesired or even prohibited. The main contribution of this paper is a fully polynomial time approximation scheme (FPTAS) for (min-cost) multi-commodity flows over time without intermediate storage. This improves upon the best previously known $(2+\varepsilon)$-approximation algorithm presented 10 years ago by Fleischer and Skutella (IPCO~2002).
During the last 15 years, there have been proposed many solution methods
for the important task of constructing periodic timetables for public transportation
companies. We first point out the importance of an objective function, where we
observe that in particular a linear objective function turns out to be a good compromise
between essential practical requirements and computational tractability. Then,
we enter into a detailed empirical analysis of various Mixed Integer Programming
procedures { such using nodes variables and such using arcs variables { genetic algorithms,
simulated annealing and constraint programming. To our knowledge, this
is the first comparison of five conceptually different solution approaches.
On rather small instances, an arc-based MIP formulation behaves best, when
refined by additional valid inequalities. On bigger instances, the solutions obtained
by a genetic algorithm are competitive to the solutions CPLEX was investigating
until it reached a time or memory limit. For Deutsche Bahn AG, the genetic algorithm
was most convincing on their various data sets, and it will become the first
automated timetable optimization software in use.
In the planning process of railway companies, we propose to integrate important
decisions of network planning, line planning, and vehicle scheduling into the task of periodic
timetabling. From such an integration, we expect to achieve an additional potential for
optimization.
Models for periodic timetabling are commonly based on the Periodic Event Scheduling
Problem (PESP). We show that, for our purpose of this integration, the PESP has to be extended
by only two features, namely a linear objective function and a symmetry requirement.
These extensions of the PESP do not really impose new types of constraints, because practitioners
have already required them even when only planning timetables autonomously without
interaction with other planning steps.
O&D revenue management (RM)
– either leg-based or PNR-based – has become
a standard in the airline industry. In this paper,
we present a new approach to O&D RM which
does not make any assumptions on demand distributions
or on the correlations of the booking
process. Protection levels are determined for all
origin destination itineraries, fare classes, points
of sale and data collection points (DCPs). This
approach to the seat inventory problem is modelled
as a multistage stochastic program, where
its stages correspond to the DCPs of the booking
horizon. The stochastic passenger demand
process is approximated by a scenario tree generated
from historical data by a recursive scenario
reduction procedure. The stochastic program
represents a specially structured large scale
LP that may be solved by standard LP software
(e.g. CPLEX). Preliminary numerical experience
is reported.
Under high load, the automated dispatching of service vehicles for
the German Automobile Association (ADAC) must reoptimize a dispatch for
100{150 vehicles and 400 requests in about ten seconds to near optimality. In
the presence of service contractors, this can be achieved by the column generation
algorithm ZIBDIP. In metropolitan areas, however, service contractors
cannot be dispatched automatically because they may decline. The problem:
a model without contractors yields larger optimality gaps within ten seconds.
One way out are simplified reoptimization models. These compute a shortterm
dispatch containing only some of the requests: unknown future requests
will in
uence future service anyway. The simpler the models the better the
gaps, but also the larger the model error. What is more significant: reoptimization
gap or reoptimization model error? We answer this question in
simulations on real-world ADAC data: only the new models ShadowPrice and
ZIBDIPdummy can keep up with ZIBDIP.
We consider a non-preemptive, stochastic parallel machine
scheduling model with the goal to minimize the weighted completion
times of jobs. In contrast to the classical stochastic model where jobs
with their processing time distributions are known beforehand, we assume
that jobs appear one by one, and every job must be assigned
to a machine online. We propose a simple online scheduling policy for
that model, and prove a performance guarantee that matches the currently
best known performance guarantee for stochastic parallel machine
scheduling. For the more general model with job release dates we derive
an analogous result, and for NBUE distributed processing times we
even improve upon the previously best known performance guarantee for
stochastic parallel machine scheduling. Moreover, we derive some lower
bounds on approximation.
Given a directed graph D = (V;A), we consider its cycle space CD, i.e. the vector
subspace of Q|A| spanned by the incidence vectors of the oriented cycles of D. An
oriented cycle of D is just any cycle of the underlying undirected graph of D along
with an orientation; its incidence vector is 0 on the arcs not included, while, for the
included arcs, it is +1 on the arcs oriented according to the orientation and -1 on
the arcs going backward. Assume a nonnegative weight wa ? R+ is associated to
each arc a of D. We can extend the weighting w to subsets F of A and to families F
of such subsets by dening w(F) := ?f?F w(f) and w(F) := ?F?F w(F). Given
the pair (D;w), we are interested in computing a minimum weight basis of CD.
This problem is strongly related to the classical problem of computing a minimum
cycle basis of an undirected graph. In 1987, Horton developed the first polynomial
time algorithm for computing a minimum cycle basis of an undirected graph. As for
directed graphs, the first algorithm for computing a minimum directed cycle basis
is due to Kavitha and Mehlhorn. Its asymptotic complexity is ~O (m4n).
In this paper, we show how the original approach of Horton can be actually pursued
also in the context of directed graphs, while retaining its simplicity. This both
allows for a practical ~O(m4n) adaptation of Horton's original algorithm requiring
only minor modifications in the actual code and for a more involved ~O(mw+1n)
solution. At the end, we discuss the applicability of this approach to more specialized
classes of directed cycle bases, namely, integral cycle bases and generalized
fundamental cycle bases.
Classes of Cycle Bases
(2005)
In the last years, new variants of the minimum cycle basis (MCB)
problem and new classes of cycle bases have been introduced, as motivated
by several applications from disparate areas of scientific and technological
inquiries. At present, the complexity status of the MCB problem has been
settled only for undirected, directed, and strictly fundamental cycle bases.
In this paper, we over an unitary classification accommodating these
3 classes and further including the following 4 relevant classes: 2-bases (or
planar bases), weakly fundamental cycle bases, totally unimodular cycle
bases, and integral cycle bases. The classification is complete in that, for
each ordered pair (A;B) of classes considered, we either prove that A ? B
holds for every graph or provide a counterexample graph for which A ? B.
The seven notions of cycle bases are distinct (either A ? B or B ? A is
exhibited for each pair (A;B)).
All counterexamples proposed have been designed to be ultimately effective
in separating the various algorithmic variants of the MCB problem
naturally associated to each one of these seven classes. We even provide
a linear time algorithm for computing a minimum 2-basis of a graph. Finally,
notice that the resolution of the complexity status of some of the
remaining three classes would have an immediate impact on practical applications,
as for instance in periodic railway timetabling, only integral
cycle bases are of direct use.
We consider the problem of satisfying the maximum number of constraints
of an instance of the Periodic Event Scheduling Problem (PESP). This is
a key issue in periodic railway timetable construction, and has many other applications,
e.g. for traffic light scheduling.
We generalize two (in-) approximability results, which are known for MAXIMUM-
K-COLORABLE-SUBGRAPH. Moreover, we present a deterministic combinatorial
polynomial time algorithm. Its output violates only very few constraints
for five real-world instances.
Tree spanner problems have important applications in network design, e.g. in the telecommunications industry. Mathematically, there have been considered quite a number of maxstretch tree spanner problems and of average stretch tree spanner problems. We propose a unified notation for 20 tree spanner problems, which we investigate for graphs with general positive weights, with metric weights, and with unit weights. This covers several prominent problems of combinatorial optimization. Having this notation at hand, we can clearly identify which problems coincide. In the case of unweighted graphs, the formally 20 problems collapse to only five different problems. Moreover, our systematic notation for tree spanner problems enables us to identify a tree spanner problem whose complexity status has not been solved so far. We are able to provide an NP-hardness proof. Furthermore, due to our new notation of tree spanner problems, we are able to detect that an inapproximability result that is due to Galbiati (2001, 2003) in fact applies to the classical max-stretch tree spanner problem. We conclude that the inapproximability factor for this problem thus is 2-ε, instead of only (1+sqrt(5))/2 ~ 1.618 according to Peleg and Reshef (1999).
Based on a recent work by Abraham, Bartal and Neiman (2007), we construct a strictly fundamental cycle basis of length O(n2) for any unweighted graph, whence proving the conjecture of Deo et al. (1982).
For weighted graphs, we construct cycle bases of length O(W log(n) log(log(n))), where W denotes the sum of the weights of the edges. This improves the upper bound that follows from the result of Elkin et al. (2005) by a logarithmic factor and, for comparison from below, some natural classes of large girth graphs are known to exhibit minimum cycle bases of length Ω(W log(n)).
We achieve this bound for weighted graphs by not restricting ourselves to strictly fundamental cycle bases - as it is inherent to the approach of Elkin et al. - but rather also considering weakly fundamental cycle bases in our construction. This way we profit from some nice properties of Hierarchically Well-Separated Trees that were introduced by Bartal (1998).
In the Minimum Strictly Fundamental Cycle Basis (MSFCB) problem one is looking for a spanning tree such that the sum of the lengths of its induced fundamental circuits is minimum.
We identify square planar grid graphs as being very challenging testbeds for the MSFCB. The best lower and upper bounds for this problem are due to Alon, Karp, Peleg, and West (1995) and to Amaldi et~al. (2004).
We improve significantly their bounds, both empirically and asymptotically. Ideally, these new benchmarks will serve as a reference for the performance of any new heuristic for the MSFCB problem which will be designed only in the future.
In the past, much research had been dedicated to compute optimum railway timetables. A typical objective was the minimization of passenger waiting times. But only the planned nominal waiting times were addressed, whereas delays, as they occur in daily operation, were neglected. Rather, conceptually, delays were treated mainly in an online-context, and solved as a separate optimization problem, called delay management.
We provide the first computational study which aims at computing delay resistant periodic timetables. In particular we assess the delay resistancy of a timetable by evaluating it subject to several delay scenarios, to which optimum delay management will be applied.
We arrive at computing delay resistant timetables by selecting a new objective function which we design to be in the middle of the traditional simple timetabling objective and the sophisticated delay management objective. This is a slight extension of the concept of "Light Robustness", as it was proposed by Fischetti and Monaci (2006). Moreover, in our application we are able to provide accurate interpretations for the ingredients of Light Robustness.
We apply this new technique to real-world data of a part of the German railway network of Deutsche Bahn AG. Our computational results suggest that a significant decrease of passenger delays could be obtained at a relatively small price of robustness.
We introduce new elevator group control algorithms that can be implemented to be real-time compliant on embedded microcontrollers. The algorithms operate a group of elevators in a destination call system, i.e. passengers specify the destination floor instead of the travel direction only. The aim is to achieve small waiting and travel times for the passengers. We provide evidence, using simulation, that the algorithms offer good performance. One of our algorithms has been implemented by our industry partner and is used in real-world systems.
In "classical optimization" it is assumed that full information about the problem to be solved is given. This, in particular, includes that all data are at hand. The real world may not be so "nice" to optimizers. Some problem constraints may not be known, the data may be corrupted, or some data may not be available at the moments when decisions have to be made. The last issue is the subject of "online optimization" which will be addressed here. We explain some theory that has been developed to cope with such situations and provide examples from practice where unavailable information is not
the result of bad data handling but an inevitable phenomenon.
We introduce a new technique for solving several sequencing problems. We consider Gilmore and Gomory's variant of the Traveling Salesman Problem and two variants of no-wait flowshop scheduling, the classical makespan minimization problem and a new problem arising in the multistage production process in steel manufacturing.
Our technique is based on an intuitive interpretation of sequencing problems as Eulerian Extension Problems. This view reveals new structural insights and leads to elegant and simple algorithms and proofs for this ancient type of problems. As a major effect, we compute not only a single solution; instead, we represent the entire space of optimal solutions. For the new flowshop scheduling problem we give a full complexity classification for any machine configuration.
We study two related problems in non-preemptive scheduling and packing of malleable tasks with precedence constraints to minimize the makespan. We distinguish the scheduling variant, in which we allow the free choice of processors, and the packing variant, in which a task must be assigned to a contiguous subset of processors.
For precedence constraints of bounded width, we completely resolve the complexity status for any particular problem setting concerning width bound and number of processors, and give polynomial-time algorithms with best possible performance. For both, scheduling and packing malleable tasks, we present an FPTAS for the NP-hard problem variants and exact algorithms for all remaining special cases. To obtain the positive results, we do not require the common monotonous penalty assumption on processing times, whereas our hardness results hold even when assuming this restriction.
With the close relation between contiguous scheduling and strip packing, our FPTAS
is the first (and best possible) constant factor approximation for (malleable) strip packing under special precedence constraints.
We give an introduction into the fascinating area of flows over time - also called "dynamic flows" in the literature. Starting from the early work of Ford and Fulkerson on maximum flows over time, we cover many exciting results that have been obtained over the last fifty years. One purpose of this paper is to serve as a possible basis for teaching network flows over time in an advanced course on combinatorial optimization.
We consider scheduling to minimize the weighted sum of completion
times on a single machine that may experience unexpected changes in
processing speed or even full breakdowns. We design a polynomial
time deterministic algorithm that finds a robust prefixed scheduling
sequence with a solution value within~$4$ times the value
an optimal clairvoyant algorithm can achieve, knowing the
disruptions in advance and even being allowed to interrupt jobs at
any moment. A randomized version of this algorithm attains in
expectation a ratio of~$e$ w.r.t. a clairvoyant optimum.
We show that such a ratio can never be achieved by any deterministic
algorithm by proving that the price of robustness of any such
algorithm is at least~$1+\sqrt{3} \approx 2.73205>e$.
As a direct consequence of our results, the question whether a
constant approximation algorithm exists for the problem with given
machine unavailability periods is answered affirmatively. We
complement this result by an FPTAS for the preemptive and non-preemptive special case with a single
non-available period.
We apply network flow techniques to find good exit selections for evacuees in an emergency evacuation. More precisely, we present two algorithms for computing exit distributions using both classical flows and flows over time which are well known from combinatorial optimization. The performance of these new proposals is compared to a simple shortest path approach and to a best response dynamics approach by using a
cellular automaton model.
In this paper we investigate two different recoverable robust models to deal with cost uncertainties in a shortest path problem. Recoverable robustness extends the classical concept of robustness to deal with uncertainties by incorporating limited recovery actions after the
full data are revealed. Our first model focuses on the case where the recovery actions are quite restricted: after a simple path is fixed in the first stage, in the second stage, after all data are revealed, any path containing at most k new arcs may be chosen.
Thus, the parameter k can be interpreted as a mediator between
robust optimization - no changes allowed - and optimization
on the fly - an arbitrary solution can be chosen. Considering three
classical scenario sets, which model uncertainties in the cost function,
we show that this new problem is strongly NP-hard in all
these cases and is not approximable, unless P=NP.
This is in contrast to the robust shortest path problem, where, for
example, an optimal solution can be computed efficiently for interval
and Gamma-scenarios. For series-parallel graphs and interval scenarios,
we present a polynomial time algorithm for this recoverable robust
setting.
In our second model the recovery set, i.e., the set of paths selectable
in the second stage is not limited, but deviating from the previous
choice comes at extra cost. Thus, a path chosen in the first stage
produces renting costs modeled as an alpha-fraction of the scenario
cost. For an arc taken in the second stage the remaining cost needs
to be paid in addition to some extra inflation cost modeled by a beta-fraction
of the scenario cost, if the arc was not reserved beforehand. The
complexity status of this problem is similar to the robust case. Yet,
for Gamma-scenarios the problem is again strongly NP-hard,
but can be approximated.
In multicriteria optimization, a compromise solution is a feasible solution whose
cost vector minimizes the distance to the ideal point w.r.t. a given norm. The coor-
dinates of the ideal point are given by the optimal values for the single optimization
problem for each criterion.
We show that the concept of compromise solutions ts nicely into the existing
notion of Pareto optimality: For a huge class of norms, every compromise solution
is Pareto optimal, and under certain conditions on the norm all Pareto optimal so-
lution are also a compromise solution, for an appropriate weighting of the criteria.
Furthermore, under similar conditions on the norm, the existence of an FPTAS for
compromise solutions guarantees the approximability of the Pareto set.
These general results are completed by applications to classical combinatorial
optimization problems. In particular, we study approximation algorithms for the
multicriteria shortest path problem and the multicriteria minimum spanning tree
problem. On the one hand, we derive approximation schemes for both problems, on
the other hand we show that for the latter problem simple approaches like local search
and greedy techniques do not guarantee good approximation factors.
We propose a new approach to competitive analysis by introducing the novel concept of online approximation schemes. Such scheme algorithmically constructs an online algorithm with a competitive ratio arbitrarily close to the best possible competitive ratio for any online algorithm. We study the problem of scheduling jobs online to minimize the weighted sum of completion times on parallel, related, and unrelated machines, and we derive both deterministic and randomized algorithms which are almost best possible among all online algorithms of the respective settings. Our method relies on an abstract characterization of online algorithms combined with various simplifications and transformations. We also contribute algorithmic means to compute the actual value of the best possible competitive ratio up to an arbitrary accuracy. This strongly contrasts all previous manually obtained competitiveness results for algorithms and, most importantly, it reduces the search for the optimal competitive ratio to a question that a computer can answer. We believe that our method can also be applied to many other problems and yields a completely new and interesting view on online algorithms.
In this paper, we investigate the recoverable robust knapsack problem,
where the uncertainty of the item weights follows the approach of Bertsimas and
Sim. In contrast to the robust approach, a limited recovery action is allowed,
i.e., up to k items may be removed when the actual weights are known. This problem
is motivated by the assignment of traffic nodes to antennas in wireless network
planning. Starting from an exponential min-max optimization model, we derive an
integer linear programming formulation of quadratic size. In a preliminary computational
study, we evaluate the gain of recovery using realistic planning data.
The knapsack problem is one of the basic problems in combinatorial optimization. In real-world applications it is often part of a more complex problem. Examples are machine capacities in production planning or bandwidth restrictions in telecommunication network design. Due to unpredictable future settings or erroneous data, parameters of such a subproblem are subject to uncertainties.
In high risk situations a robust approach should be chosen to deal with these uncertainties.
Unfortunately, classical robust optimization outputs solutions with little profit by prohibiting any adaption of the solution when the actual realization of the uncertain parameters is known.
This ignores the fact that in most settings minor changes to a previously determined solution are possible. To overcome these drawbacks we allow a limited recovery of a previously fixed item set as soon as the data are known by deleting at most k items and adding up to l new items.
We consider the complexity status of this recoverable robust knapsack problem and extend the classical concept of cover inequalities to obtain stronger polyhedral descriptions. Finally, we present two extensive computational studies to investigate the influence of parameters k and l to the objective and evaluate the effectiveness of our new class of valid inequalities.
We consider a sorting problem from railway optimization
called train classification: incoming trains are split up into their single
cars and reassembled to form new outgoing trains. Trains are subject
to delay, which may turn a prepared sorting schedule infeasible for the
disturbed situation. The classification methods applied today deal with
this issue by completely disregarding the input order of cars, which provides
robustness against any amount of disturbance but also wastes the
potential contained in the a priori knowledge about the input.
We introduce a new method that provides a feasible sorting schedule for
the expected input and allows to
flexibly insert additional sorting steps
if the schedule has become infeasible after revealing the disturbed input.
By excluding disruptions that almost never occur from our consideration,
we obtain a classification process that is quicker than the current railway
practice but still provides robustness against realistic delays. In fact, our
algorithm allows
flexibly trading off fast classification against high degrees
of robustness depending on the respective need. We further explore
this
flexibility in experiments on real-world traffic data, underlining our
algorithm improves on the methods currently applied in practice.
We consider a basic subproblem which arises in line planning,
and is of particular importance in the context of a high system
load or robustness: How much can be routed maximally along all possible
lines? The essence of this problem is the Path Constrained Network
Flow (PCN) problem. We explore the complexity of this problem and
its dual. In particular we show for the primal that it is as hard to
approximate as MAX CLIQUE and for the dual that it is as hard to
approximate as SET COVER. We also prove that the PCN problem is
hard for special graph classes, interesting both from a complexity and
from a practical perspective. Finally, we present a special graph class
for which there is a polynomial-time algorithm.
Flows over time and generalized flows are two advanced network flow models of utmost importance, as they incorporate two crucial features occurring in numerous real-life networks. Flows over time feature time as a problem dimension and allow to realistically model the fact that commodities (goods, information, etc.) are routed through a network over time. Generalized flows allow for gain/loss factors on the arcs that model physical transformations of a commodity due to leakage, evaporation, breeding, theft, or interest rates. Although the latter effects are usually time-bound, generalized flow models featuring a temporal dimension have never been studied in the literature.
In this paper we introduce the problem of computing a generalized maximum flow over time in networks with both gain factors and transit times on the arcs. While generalized maximum flows and maximum flows over time can be computed efficiently, our combined problem turns out to be NP-hard and even completely non-approximable. A natural special case is given by lossy networks where the loss rate per time unit is identical on all arcs. For this case we present a (practically efficient) FPTAS that also reveals a surprising connection to so-called earliest arrival flows.
We study the incremental facility location problem, wherein we are given an instance of the uncapacitated facility location problem. We seek an incremental sequence of opening facilities and an incremental sequence of serving customers along with their fixed assignments to facilities open in the partial sequence. Our aim is to have the solution obtained for serving the first l customers in the sequence be competitive with the optimal solution to serve any l customers. We provide an incremental framework that provides an overall competitive factor of 8 and a worst case instance that provides the lower bound of 3. The problem has applications in multi-stage network planning.
We study the fundamental problem of scheduling bidirectional traffic across machines arranged on a path. The main feature of the problem is that jobs traveling in the same direction can be scheduled in quick succession on a machine, while jobs in the other direction have to wait for an additional transit time. We show that this tradeoff makes the problem significantly harder than the related flow shop problem, by showing that it is NP-hard even for jobs with identical processing and transit times. We give polynomial algorithms for a single machine and any constant number of machines. In contrast, we show the problem to be NP-hard on a single machine and with identical processing and transit times if some pairs of jobs in different directions are allowed to run on the machine concurrently. We generalize a PTAS of Afrati et al. [1999] for one direction and a single machine to the bidirectional case on any constant number of machines.