Solving some lexicographic multi-objective combinatorial problems

The lexicographic multi-objective optimization problem (r-LMOP) with r (sum or bottleneck) objectives optimizes a first objective, then as far as a choice remains, a second one, then a third one and so on. A general solution scheme from literature is based on scaling. for the case that only sum criteria are involved the complexity is O(r log n)T(n, m) with T(n, m) the complexity of optimization on combinatorial (sum) problem instances with m arcs and n nodes. For cases with at least one bottleneck criterion the complexity is at least O(rn log(2)n)T(n, m). We describe a solution scheme that is suited to solve the shortest path r-LMOP, the minimum spanning tree r-LMOP and the linear assignment r-LMOP; the complexity is in all cases O(r)T(n, m). (C) 2002 Elsevier Science B.V. All rights reserved.