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)
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.
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.
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.
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.
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.