An improved general procedure for lexicographic bottleneck problems

Della Croce, Federico; Paschos, Vangelis; Tsoukiàs, Alexis

Della Croce, Federico; Paschos, Vangelis; Tsoukiàs, Alexis (1999), An improved general procedure for lexicographic bottleneck problems, Operations Research Letters, 24, 4, p. 187-194. http://dx.doi.org/10.1016/S0167-6377(99)00013-9

View/Open

bottlene.pdf (211.9Kb)

Type

Article accepté pour publication ou publié

Date

1999

Journal name

Operations Research Letters

Volume

Number

Publisher

Elsevier

Pages

187-194

Abstract (EN)

In combinatorial optimization, the bottleneck (or minmax) problems are those problems where the objective is to find a feasible solution such that its largest cost coefficient elements have minimum cost. Here we consider a generalization of these problems, where under a lexicographic rule we want to minimize the cost also of the second largest cost coefficient elements, then of the third largest cost coefficients, and so on. We propose a general rule which leads, given the considered problem, to a vectorial version of the solution procedure for the underlying sum optimization (minsum) problem. This vectorial procedure increases by a factor of k (where k is the number of different cost coefficients) the complexity of the corresponding sum optimization problem solution procedure.

Subjects / Keywords

Combinatorial optimization; Bottleneck problem; Lexicographic problem