This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Nace, D. Articles by Orlin, J. B. Search for Related Content

Lexicographically Minimum and Maximum Load Linear Programming Problems

Laboratoire Heudiasyc UMR CNRS 6599, Université de Technologie de Compiègne, 60205 Compiègne Cedex, France
Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
nace{at}utc.fr
jorlin{at}mit.edu

In this paper, we introduce the lexicographically minimum load linear programming problem, and we provide a polynomial approach followed by the proof of correctness. This problem has applications in numerous areas where it is desirable to achieve an equitable distribution or sharing of resources. We consider the application of our technique to the problem of lexicographically minimum load in capacitated multicommodity networks and discuss a special nonlinear case, the so-called Kleinrock load function. We next define the lexicographically maximum load linear programming problem and deduce a similar approach. An application in the lexicographically maximum concurrent flow problem is depicted followed by a discussion on the minimum balance problem as a special case of the lexicographically maximum load problem.

Subject classifications: networks/graphs; multicommodity; theory; programming; linear algorithms; multiple criteria; games/group decisions; cooperative.
History: Received August 2004; revision received November 2005; accepted December 2005.