Algorithmic Operations Research
Volume 4, numéro 2, fall 2009
Sommaire (7 articles)
Articles

Simple and Fast Reoptimizations for the Steiner Tree Problem
Bruno Escoffier, Martin Milanič et Vangelis Th. Paschos
p. 86–94
RésuméEN :
We address reoptimization issues for the Steiner tree problem. We assume that an optimal solution is given for some instance of the problem and the objective is to maintain a good solution when the instance is subject to minor modifications, the simplest such modifications being vertex insertions and deletions. We propose fast reoptimization strategies for the case of vertex insertions and we show that maintenance of a good solution for the “shrunk” instance, without ex nihilo computation, is impossible when vertex deletions occur. We also provide lower bounds for the approximation ratios of the reoptimization strategies studied.

Approximable 1Turn Routing Problems in AllOptical Mesh Networks
Guillaume Bagan, Olivier Cogis et Jérôme Palaysi
p. 95–101
RésuméEN :
In alloptical networks, several communications can be transmitted through the same fiber link provided that they use different wavelengths. The MINIMUM ALLOPTICAL ROUTING problem (given a list of pairs of nodes standing for as many point to point communication requests, assign to each request a route along with a wavelength so as to minimize the overall number of assigned wavelengths) has been paid a lot of attention and is known to be N P–hard. Rings, trees and meshes have thus been investigated as specific networks, but leading to just as many N P–hard problems.
This paper investigates 1turn routings in meshes (paths are allowed one turn only). We first show the MINIMUM LOAD 1TURN ROUTING problem to be N P–hard but 2APX (more generally, the MINIMUM LOAD kCHOICES ROUTING problem is N P–hard but kAPX), then that the MINIMUM 1TURN PATHS COLOURING problem is 4APX (more generally, any dsegmentable routing of load L in a hypermesh of dimension d can be coloured with 2d(L−1)+1 colours at most). >From there, we prove the MINIMUM ALLOPTICAL 1TURN ROUTING problem to be APX.

Recoverable Robustness for Train Shunting Problems
Serafino Cicerone, Gianlorenzo D’Angelo, Gabriele Di Stefano, Daniele Frigioni et Alfredo Navarra
p. 102–116
RésuméEN :
Several attempts have been done in the literature in the last years in order to provide a formal definition of the notions of robustness and recoverability for optimization problems. Recently, a new model of recoverable robustness has been introduced in the context of railways optimization. The basic idea of recoverable robustness is to compute solutions that are robust against a limited set of disturbances and for a limited recovery capabilities. The quality of the robust solution is measured by its price of robustness that determines the tradeoff between an optimal and a robust solution.
In this paper, within the recoverable robustness model, we emphasize algorithmic aspects and provide definitions of robust algorithm and price of robustness of a robust algorithm as a measure to evaluate its performance. A robust algorithm provides a solution that maintains feasibility by possibly applying available recovery capabilities in the case of changes to the input data. We study various settings in the context of shunting problems, i.e. the reordering of train cars over a hump yard. The considered shunting problems can be seen as the reordering of an integer vector by means of a set of available stacks with the further constraint that the pull operation does not involve only the element on top of a stack, but all the elements contained in the stack.
We provide efficient robust algorithms concerning specific shunting problems. In particular, we study algorithms able to cope with disturbances, as temporary and local unavailability and/or malfunctioning of key resources that can occur and affect planned operations. Various scenarios are considered, and robustness results are presented.

2Commodity Integer Network Synthesis Problem
S. N. Kabadi, R. Chandrasekaran et K. P.K. Nair
p. 117–132
RésuméEN :
We consider the following 2commodity, integer network synthesis problem: Given two n×n, nonnegative, symmetric, integervalued matrices R = (rij) and S = (sij) of minimum flow requirements of 2 different commodities, construct an undirected network G = [N, E, c] on node set N = {1, 2, . . . , n} with integer edge capacities {c(e) : e ∈ E}, such that: (i) for any two pairs (i, j) and (k, l), i ≠ j, k ≠ l, of nodes in N, we can simultaneously send rij units of flow of commodity 1 from i to j and skl units of flow of commodity 2 from k to l in G; and (ii) z = Σ {c(e) : e ∈ E} is minimum. We present strongly polynomial, combinatorial algorithms for certain special cases of the problem; and for the general problem, we present a strongly polynomial, combinatorial algorithm that produces a feasible solution with objective function value no more than (the optimal objective function value +3).

From Balls and Bins to Points and Vertices
Ralf Klasing, Zvi Lotker, Alfredo Navarra et Stéphane Pérennes
p. 133–143
RésuméEN :
Given a graph G = (V, E) with V  = n, we consider the following problem. Place m = n points on the vertices of G independently and uniformly at random. Once the points are placed, relocate them using a bijection from the points to the vertices that minimizes the maximum distance between the random place of the points and their target vertices.We look for an upper bound on this maximum relocation distance that holds with high probability (over the initial placements of the points). For general graphs and in the case m ≤ n, we prove the #P hardness of the problem and that the maximum relocation distance is O(√_{n}) with high probability. We present a Fully Polynomial Randomized Approximation Scheme when the input graph admits a polynomialsize family of witness cuts while for trees we provide a 2approximation algorithm. Many applications concern the variation in which m = (1 − ǫ)n for some 0 < ǫ < 1. We provide several bounds for the maximum relocation distance according to different graph topologies.

Generalized Traveling Salesman Problem Reduction Algorithms
Gregory Gutin et Daniel Karapetyan
p. 144–154
RésuméEN :
The generalized traveling salesman problem (GTSP) is an extension of the wellknown traveling salesman problem. In GTSP, we are given a partition of cities into groups and we are required to find a minimum length tour that includes exactly one city from each group. The aim of this paper is to present a problem reduction algorithm that deletes redundant vertices and edges, preserving the optimal solution. The algorithm’s running time is O(N^{3}) in the worst case, but it is significantly faster in practice. The algorithm has reduced the problem size by 15–20% on average in our experiments and this has decreased the solution time by 10–60% for each of the considered solvers.

A TwoPeriod Portfolio Selection Model for Assetbacked Securitization
Renata Mansini et Ulrich Pferschy
p. 155–170
RésuméEN :
AssetBacked Securitization (ABS) is a wellstated financial mechanism which allows an institution (either a commercial bank or a firm) to get funds through the conversion of assets into capital market products called notes or assetbacked securities. In this paper, we analyze the combinatorial problem faced by the financial institution which has to optimally select the set of assets to be converted into notes. We assume that assets follow an amortization rule characterized by constant periodic principal installments (Italian amortization). The particular shape of the assets outstanding principal is exploited both in the mathematical formulation of the problem and in its solution. In particular, we study a model formulation for the special case where assets selection occurs at two dates during the securitization process. We introduce two heuristic approaches based on Lagrangian relaxation and analyze their worstcase behavior compared to the optimal solution value. The performance of the algorithms is tested on a large set of problem instances generated according to two realworld scenarios provided by a leasing company. The proposed approximation algorithms turn out to yield solutions of high quality within very short computation time. The comparison to the solution approach applied by practitioners yields an average improvement of roughly 10% of the objective function value.