1,721,118 research outputs found
Combinatorial and robust optimisation models and algorithms for railway applications
No full textThe following is a summary of the author’s Ph.D. thesis supervised by Alberto Caprara and Paolo Toth and defended on April 16, 2009 at the Università di Bologna. The thesis is written in English and is available from the author upon request. Railway systems represent a challenging area for operations research, especially when highly-complex and data-intensive applications, such as large-scale transportation networks, are at stake. One of the main issues concerns imperfect information. The classic notion of RobustOptimisation, as a way to represent and handle mathematically systems with not precisely known data, did not prove to be successfully applicable in the railway setting. For this reason a new paradigm has been defined recently in Liebchen et al. (2007): Recoverable robustness. Here we present our research on recoverable robust optimisation models for two important railway problems: Train platforming and Rolling stock planning
Modeling with stochastic programming, Alan J. King and Stein W. Wallace
No full textReview of the book "Modeling with Stochastic Programming" by Alan J. King and Stein W. Wallace
Modeling with stochastic programming, Alan J. King and Stein W. Wallace.
No full textReview of the book "Modeling with Stochastic Programming" by Alan J. King and Stein W. Wallace
A compact variant of the QCR method for quadratically constrained quadratic 0-1 programs
Full text linkQuadratic Convex Reformulation (QCR) is a technique that was originally proposed for quadratic 0-1 programs, and then extended to various other problems. It is used to convert non-convex instances into convex ones, in such a way that the bound obtained by solving the continuous relaxation of the reformulated instance is as strong as possible. In this paper, we focus on the case of quadratically constrained quadratic 0-1 programs. The variant of QCR previously proposed for this case involves the addition of a quadratic number of auxiliary continuous variables. We show that, in fact, at most one additional variable is needed. Some computational results are also presented
Delay-Constrained Shortest Paths: Approximation Algorithms and Second-Order Cone Models
Full text linkReal-time traffic with stringent Quality of Service requirements is becoming more and more prevalent in contemporary telecommunication networks. When maximum packet delay has to be considered, optimal delay-constrained routing requires not only choosing a path, but also reserving resources (transmission capacity) along its arcs, as the delay is a nonlinear function of both kinds of components. So far only simple versions of the problem have been considered in the literature where all arcs are reserved the same capacity (this is referred to as ERA, i.e., Equal Rate Allocations) and have the same capacity reservation cost, because in such a restricted case polynomial time exact algorithms can be devised, whereas the general problem is \Mcnp-hard. We first extend the polynomial-time approaches for the ERA version of the problem with unit arc costs by deriving a pseudo-polynomial time algorithm for the integer arc costs case and a FPTAS for the general arc costs case. We then show that, under the main latency models proposed in the literature, the general problem can be formulated as a mixed-integer Second-Order Cone (SOCP) program, and therefore solved with off-the-shelf technology. We compare two formulations: one based on standard big-M constraints, and an improved one where Perspective Reformulation techniques are used to tighten the continuous relaxation. Extensive computational experiments on both real-world networks and randomly-generated realistic ones show that the ERA approach is extremely fast and provides a surprisingly effective heuristic for the general problem whenever it manages to find a solution at all, but it fails for a significant fraction of the instances that the SOCP models can solve. We therefore propose a three-pronged approach that combines the fast running time of the ERA algorithm and the effectiveness of the SOCP models, and show that the combined approach is capable of solving realistic-sized instances at different levels of network load in a time compatible with real-time usage in an operating environment
A tutorial on non-periodic train timetabling and platforming problems
No full textIn this tutorial, we give an overview of two fundamental problems arising in the optimization of a railway system: the train timetabling problem (TTP), in its non-periodic version, and the train platforming problem (TPP). We consider for both problems the planning stage, i.e. we face them from a tactical point of view. These problems correspond to two main phases that are usually optimized in close sequence by the railway infrastructure manager. First, in the TTP phase, a schedule of the trains in a railway network is determined. A schedule consists of the arrival and departure times of each train at each (visited) station. Second, in the TPP phase, one needs to determine a stopping platform and a routing for each train inside each (visited) station, according to the schedule found in the TTP phase. Due to the complexity of the two problems, an integrated approach is generally hopeless for real-world instances. Hence, the two phases are considered separately and optimized in sequence. Although there exist several versions for both problems, depending on the infrastructure manager and train operators requirements, we do not aim at presenting all of them, but rather at introducing the reader to the topic using small examples. We present models and solution approaches for the two problems in a didactic way and always refer the reader to the corresponding papers for technical details
QoS Routing with worst-case delay constraints: models, algorithms and performance analysis
Full text linkIn a network where weighted fair-queueing schedulers are used at each link, a flow is guaranteed an end-to-end worst-case delays which depends on the rate reserved for it at each link it traverses. Therefore, it is possible to compute resource-constrained paths that meet target delay constraints, and optimize some key performance metrics (e.g., minimize the overall reserved rate, maximize the remaining capacity at bottleneck links, etc.). Despite the large amount of literature that has appeared on weighted fair-queueing schedulers since the mid '90s, this has so far been done only for a single type of scheduler, probably because the complexity of solving the problem in general appeared forbidding. In this paper, we formulate and solve the optimal path computation and resource allocation problem for a broad category of weighted fair-queueing schedulers, from those emulating a Generalized Processor Sharing fluid server to variants of Deficit Round Robin. We classify schedulers according to their latency expressions, and show that a significant divide exists between those where routing a new flow affects the performance of existing flows, and those for which this do not happen. For the former, explicit admission control constraints are required to ensure that existing flows still meet their deadline afterwards. However, despite this major difference and the differences among categories of schedulers, the problem can always be formulated as a Mixed-Integer Second-Order Cone problem (MI-SOCP), and be solved at optimality in split-second times even in fairly large networks
Delay-constrained Routing Problems: Accurate Scheduling Models and Admission Control
Full text linkAs shown in [1], the problem of routing a flow subject to a worst-case end-to-end delay constraint
in a packed-based network can be formulated as a Mixed-Integer Second-Order Cone Program,
and solved with general-purpose tools in real time on realistic instances. However, that result only
holds for one particular class of packet schedulers, Strictly Rate-Proportional ones, and implicitly
considering each link to be fully loaded, so that the reserved rate of a flow coincides with its
guaranteed rate. These assumptions make latency expressions simpler, and enforce perfect isolation
between flows, i.e., admitting a new flow cannot increase the delay of existing ones. Other
commonplace schedulers both yield more complex latency formulæ and do not enforce flow isolation.
Furthermore, the delay actually depends on the guaranteed rate of the flow, which can be
significantly larger than the reserved rate if the network is unloaded. In this paper we extend the
result to other classes of schedulers and to a more accurate representation of the latency, showing
that, even when admission control needs to be factored in, the problem is still efficiently solvable
for realistic instances, provided that the right modeling choices are made.
Keywords: Routing problems, maximum delay constraints, scheduling algorithms, admission
control, Second-Order Cone Programs, Perspective Reformulatio
Optimal joint path computation and rate allocation for real-time traffic
Full text linkComputing network paths under worst-case delay constraints has been the subject of abundant literature in the past two decades. Assuming Weighted Fair Queueing scheduling at the nodes, this translates to computing paths and reserving rates at each link. The problem is NP-hard in general, even for a single path; hence polynomial-time heuristics have been proposed in the past, that either assume equal rates at each node, or compute the path heuristically and then allocate the rates optimally on the given path. In this paper we show that the above heuristics, albeit finding optimal solutions quite often, can lead to failing of paths at very low loads, and that this could be avoided by solving the problem, i.e., path computation and rate allocation, jointly at optimality. This is possible by modeling the problem as a mixed-integer second-order cone program and solving it optimally in split-second times for relatively large networks on commodity hardware; this approach can also be easily turned into a heuristic one, trading a negligible increase in blocking probability for one order of magnitude of computation time. Extensive simulations show that these methods are feasible in today's ISPs networks and they significantly outperform the existing schemes in terms of blocking probability
- …
