Volume 1, numéro 1, summer 2006

EN :

In this paper we briefly review the importance of LP (linear programming), and Dantzig’s main contributions to OR (Operations Research), mathematics, and computer science. In [11, 3] gravitational methods for LP have been introduced. Several versions exist. The three main versions discussed there use a ball of (a): 0 radius, (b): small positive radius, and (c): the ball of largest possible radius with the given center that will completely fit within the polytope, with the option of changing its radius as the algorithm progresses. In versions (a) and (b), after the first move, the center of the ball always remains very close to the boundary (because the ball hugs the boundary), and hence these versions behave like other boundary algorithms such as the simplex algorithm in terms of exponential complexity in the worst case [9].

Here we discuss a gravitational method of type (c) that behaves like an interior point method [8,20, 21]. To guarantee that the ball has the largest possible radius, it uses a new centering strategy that moves any interior feasible solution x0 to the center of the intersection of the feasible region with the objective hyperplane through x0, before beginning the gravitational descent moves. We show that this strategy leads to a strongly polynomial algorithm for LP in terms of the number of centering steps. Also, using this centering strategy, we discuss a method that solves LPs efficiently using no matrix inversions.

EN :

This paper considers large-scale multistage stochastic linear programs. Sampling is incorporated into the nested decomposition algorithm in a manner which proves to be significantly more efficient than a previous approach. The main advantage of the method arises from maintaining a restricted set of solutions that substantially reduces computation time in each stage of the procedure.

EN :

We consider the problem of finding a cheapest Hamiltonian path of a complete graph satisfying a relaxed triangle inequality, i.e., such that for some parameter > 1, the edge costs satisfy the inequality c({x, y}) ≤ `c({x, z}) + c({z, y})´ for every triple of vertices x, y, z. There are three variants of this problem, depending on the number of prespecified endpoints: zero, one, or two. For metric graphs there exist approximation algorithms, with approximation ratio 32 for the first two variants and 53 for the latter one.

Using results on the approximability of the Travelling Salesman Problem with input graphs satisfying the relaxed triangle inequality, we obtain for our problem approximation algorithms with ratio min( 2 + , 32 2) for zero or one prespecified endpoints, and 53 2 for two endpoints.

EN :

Simplex Adjacency graphs represent the possible Simplex pivot operations (the edges) between pairs of feasible bases (the nodes) of linear optimization models. These graphs are mainly studied so far in the context of degeneracy. The more general point of view in this paper leads to a number of new results, mainly concerning the connectivity and the feasibility-optimality duality in these graphs. Among others, we present a very short proof of a result of P. Zörnig and T. Gall (1996) on the connectivity of subgraphs corresponding to optimal vertices, and we answer H.-J. Kruse’s (1993) question on the connectivity of graphs related to the negative pivots in optimal vertices.

EN :

The domination number, domn(A, n), of a heuristic A for the Asymmetric TSP is the maximum integer d = d(n) such that, for every instance I of the Asymmetric TSP on n cities, A produces a tour T which is not worse than at least d tours in I including T itself. Two upper bounds on the domination number are proved.

EN :

Most real optimization problems often involve multiple objectives to optimize. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined but rather a set of solutions, so called Pareto-optimal set. Thus, the goal of multi-objective strategies is to obtain an approximation to this set. However, the majority of this kind of problem cannot be solved exactly as they have very large and highly complex search spaces. In recent years, meta-heuristics have become important tools for solving multi-objective problems encountered in industry as well as in the theoretical field. Thus far, there exist many comparative studies about the performance of evolutionary algorithms, but are few the papers dealing with non-evolutionary strategies. The goal of this paper is to analyze the performance of both paradigms in a realistic problem. In concrete, we have adapted five multi-objective meta-heuristics, based on Simulated Annealing, Tabu Search, and Evolutionary Methods, to solve the Network Partitioning Problem.