Algorithmic Operations Research
Volume 2, numéro 1, summer 2007
Sommaire (7 articles)
Articles

Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms
Juraj Hromkovič, Tobias Mömke, Kathleen Steinhöfel et Peter Widmayer
p. 1–14
RésuméEN :
We consider the job shop scheduling problem unit–Jm, where each job is processed once on each of m given machines. Every job consists of a permutation of tasks for all machines. The execution of any task on its corresponding machine takes exactly one time unit. The objective is to minimize the overall completion time, called makespan. The contribution of this paper are the following results: (i) For any input instance of unit–Jm with d jobs, the makespan of an optimum schedule is at most m + o(m), for d = o(m1/2). This improves on the upper bound O(m + d) given in [5] where O hides a constant equal to two as shown in [7]. For d = 2 the upper bound is improved to m + ⌈ √m ⌉. (ii) There exist input instances of unit–Jm with d = 2 such that the makespan of an optimum schedule is at least m + ⌈ √m ⌉, i.e., our upper bound for d = 2, see result (i), cannot be improved. (iii) We present a randomized online approximation algorithm for unit–Jm with the best known approximation ratio for d = o(m1/2). (iv) There is no deterministic online algorithm with a competitive ratio better than 4/3 for unit–Jm with two jobs, and for three or more jobs, there is no deterministic online algorithm which is better than 1.5 competitive. Compared with the expected competitive ratio of (iii) which tends to 1, this shows that for unit–Jm randomization is very powerful compared with determinism. For two and three jobs, deterministic online algorithms with competitive ratios tending to 4/3 and 1.5 respectively are presented. (v) A deterministic approximation algorithm for unit–Jm is described that works in quadratic time for constant d and has an approximation ratio of 1 + 2d/⌊√m ⌋ for d ≤ 2 log2 m.

Vertex 3colorability of clawfree graphs
Marcin Kamiński et Vadim Lozin
p. 15–21
RésuméEN :
The 3COLORABILITY problem is NPcomplete in the class of clawfree graphs. In this paper we study the computational complexity of the problem in subclasses of clawfree graphs defined by forbidding finitely many additional subgraphs (line graphs and clawfree graphs of bounded vertex degree being examples of such classes). We prove a necessary condition for the polynomialtime solvability of the problem in such classes and propose a lineartime solution for an infinitely increasing hierarchy of classes that meet the condition. To develop such a solution for the basis of this hierarchy, we generalize the notion of locally connected graphs that has been recently studied in the context of the 3COLORABILITY

Some Necessary Conditions and a General Sufficiency Condition for the Validity of A GilmoreGomory Type Patching Scheme for the Traveling Salesman Problem
M. F. Baki et S. N. Kabadi
p. 22–32
RésuméEN :
One of the most celebrated polynomially solvable cases of the TSP is the GilmoreGomory TSP. The patching scheme for the problem developed by Gilmore and Gomory has several interesting features. Its generalization, called the GGscheme, has been studied by several researchers and polynomially testable sufficiency conditions for its validity have been given, leading to polynomial schemes for large subclasses of the TSP. A good characterization of the subclass of the TSP for which the GGscheme produces an optimal solution, is an outstanding open problem of both theoretical and practical significance. We give some necessary conditions and a new, polynomially testable sufficiency condition for the validity of the GGscheme that properly includes all previously known such conditions.

The Greedy Algorithm for the Symmetric TSP
Gregory Gutin et Anders Yeo
p. 33–36
RésuméEN :
We corrected proofs of two results on the greedy algorithm for the Symmetric TSP and answered a question in Gutin and Yeo, Oper. Res. Lett. 30 (2002), 97–99.

“Binarize and Project” to generate cuts for general mixedinteger programs
JeanSébastien Roy
p. 37–51
RésuméEN :
We consider mixedinteger linear programs with arbitrary bounded integer variables. We first describe a cutting plane approach based on the reformulation of integer variables into binary variables and describe a practical algorithm to compute these cuts for the original problem. We use the term “Binarize and Project” to highlight the similarity to the back onto the original space. Indeed, the interest of this approach lies in taking advantage of cutting plane approaches efficient for mixedbinary problems while keeping the problem in its nonbinary form for improving the efficiency of the branchandbound procedure.
We then propose a new strengthened reformulation into binary variables that answers some concerns and limitations raised in [9], by ensuring that only one application of the liftandproject convexification procedure to the binary reformulation of the problem is required to obtain a strengthening of the original problem.
Finally, the method is implemented inside the COIN optimization library and a preliminary experimentation is performed on problems from the MIPLIB library. The computational results confirm that the use of the proposed binary reformulation and cutting plane generation procedure leads to an improved integrality gap reduction albeit with an increased computing time.

Hybrid Continuous Interacting Ant Colony aimed at enhanced global optimization
J. Dréo et P. Siarry
p. 52–64
RésuméEN :
Ant colony algorithms are a class of metaheuristics which are inspired from the behaviour of real ants. The original idea consisted in simulating the stigmergic communication, therefore these algorithms are considered as a form of adaptive memory programming. A new formalization was proposed for the design of ant colony algorithms, introducing the biological notions of heterarchy and communication channels. We are interested in the way ant colonies handle the information. According to these issues, a heterarchical algorithm called “Continuous Interacting Ant Colony” (CIAC) was previously designed for the optimization of multiminima continuous functions. We propose in that paper an improvement of CIAC, by the way of a hybridization with the local search NelderMead algorithm. The new algorithm called “Hybrid Continuous Interacting Ant Colony” (HCIAC) compares favorably with some competing algorithms on a large set of standard test functions.

Online Network Synthesis
S. N. Kabadi et D. Du
p. 65–74
RésuméEN :
We consider online network synthesis problems. Let N = {1, , n} be a set of n sites. Traffic flow requirements between pairs of sites are revealed one by one. Whenever a new request rij = rji (i < j) between sites i and j is revealed, an online algorithm must install the additional necessary capacity without decreasing the existing network capacity such that all the traffic requirements are met. The objective is to minimize the total capacity installed by the algorithm. The performance of an online algorithm is measured by the competitive ratio, defined to be the worstcase ratio between the total capacity by the online algorithm and the total optimal (offline) capacity assuming we have priori information on all the requirements initially. We distinguish between two online versions of the problem depending on whether the entire set of sites is known a prior or not. For the first version where the entire set of site is unknown, we present a best possible algorithm along with a matching lower bound. For the second version where the entire set of sites is known a priori, we present a best possible algorithm for n ≤ 6.