IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v55y2007i1p182-187.html
   My bibliography  Save this article

Lexicographically Minimum and Maximum Load Linear Programming Problems

Author

Listed:
  • Dritan Nace

    (Laboratoire Heudiasyc UMR CNRS 6599, Université de Technologie de Compiègne, 60205 Compiègne Cedex, France)

  • James B. Orlin

    (Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

Abstract

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.

Suggested Citation

  • Dritan Nace & James B. Orlin, 2007. "Lexicographically Minimum and Maximum Load Linear Programming Problems," Operations Research, INFORMS, vol. 55(1), pages 182-187, February.
    • Handle: RePEc:inm:oropre:v:55:y:2007:i:1:p:182-187
    DOI: 10.1287/opre.1060.0341
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1060.0341
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1060.0341?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Hans Schneider & Michael H. Schneider, 1991. "Max-Balancing Weighted Directed Graphs and Matrix Scaling," Mathematics of Operations Research, INFORMS, vol. 16(1), pages 208-222, February.
    2. SCHMEIDLER, David, 1969. "The nucleolus of a characteristic function game," LIDAM Reprints CORE 44, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. Freund, Robert Michael. & Roundy, Robin. & Todd, Michael J., 1947-, 1985. "Identifying the set of always-active constraints in a system of linear inequalities by a single linear program," Working papers 1674-85., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    4. Walter Kern & Daniël Paulusma, 2003. "Matching Games: The Least Core and the Nucleolus," Mathematics of Operations Research, INFORMS, vol. 28(2), pages 294-308, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Lehuédé, Fabien & Péton, Olivier & Tricoire, Fabien, 2020. "A lexicographic minimax approach to the vehicle routing problem with route balancing," European Journal of Operational Research, Elsevier, vol. 282(1), pages 129-147.
    2. Dukkanci, Okan & Karsu, Özlem & Kara, Bahar Y., 2022. "Planning sustainable routes: Economic, environmental and welfare concerns," European Journal of Operational Research, Elsevier, vol. 301(1), pages 110-123.
    3. Letsios, Dimitrios & Mistry, Miten & Misener, Ruth, 2021. "Exact lexicographic scheduling and approximate rescheduling," European Journal of Operational Research, Elsevier, vol. 290(2), pages 469-478.
    4. Karsu, Özlem & Morton, Alec, 2015. "Inequity averse optimization in operational research," European Journal of Operational Research, Elsevier, vol. 245(2), pages 343-359.
    5. Mohammadmehdi Hakimifar & Vera C. Hemmelmayr & Fabien Tricoire, 2022. "A Bi-Objective Field-Visit Planning Problem for Rapid Needs Assessment under Travel-Time Uncertainty," Sustainability, MDPI, vol. 14(5), pages 1-16, March.
    6. Mohammadmehdi Hakimifar & Vera C. Hemmelmayr & Fabien Tricoire, 2023. "A lexicographic maximin approach to the selective assessment routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 45(1), pages 205-249, March.
    7. Christ, Quentin & Dauzère-Pérès, Stéphane & Lepelletier, Guillaume, 2019. "An Iterated Min–Max procedure for practical workload balancing on non-identical parallel machines in manufacturing systems," European Journal of Operational Research, Elsevier, vol. 279(2), pages 419-428.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Tamas Solymosi & Balazs Sziklai, 2015. "Universal Characterization Sets for the Nucleolus in Balanced Games," CERS-IE WORKING PAPERS 1512, Institute of Economics, Centre for Economic and Regional Studies.
    2. Peter Biro & Walter Kern & Daniel Paulusma, 2011. "Computing Solutions for Matching Games," CERS-IE WORKING PAPERS 1142, Institute of Economics, Centre for Economic and Regional Studies.
    3. Vijay V. Vazirani, 2022. "New Characterizations of Core Imputations of Matching and $b$-Matching Games," Papers 2202.00619, arXiv.org, revised Dec 2022.
    4. Qizhi Fang & Bo Li & Xiaohan Shan & Xiaoming Sun, 2018. "Path cooperative games," Journal of Combinatorial Optimization, Springer, vol. 36(1), pages 211-229, July.
    5. Karla Hoffman & Dinesh Menon, 2010. "A Practical Combinatorial Clock Exchange for Spectrum Licenses," Decision Analysis, INFORMS, vol. 7(1), pages 58-77, March.
    6. Xiaotie Deng & Qizhi Fang & Xiaoxun Sun, 2009. "Finding nucleolus of flow game," Journal of Combinatorial Optimization, Springer, vol. 18(1), pages 64-86, July.
    7. Ulrich Faigle & Walter Kern & Jeroen Kuipers, 2006. "Computing an Element in the Lexicographic Kernel of a Game," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 63(3), pages 427-433, July.
    8. Walter Kern & Daniël Paulusma, 2009. "On the Core and f -Nucleolus of Flow Games," Mathematics of Operations Research, INFORMS, vol. 34(4), pages 981-991, November.
    9. Péter Biró & Walter Kern & Daniël Paulusma, 2012. "Computing solutions for matching games," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(1), pages 75-90, February.
    10. Vazirani, Vijay V., 2022. "The general graph matching game: Approximate core," Games and Economic Behavior, Elsevier, vol. 132(C), pages 478-486.
    11. F.Javier Martínez-de-Albéniz & Carles Rafels & Neus Ybern, 2015. "Insights into the nucleolus of the assignment game," UB School of Economics Working Papers 2015/333, University of Barcelona School of Economics.
    12. Frits Hof & Walter Kern & Sascha Kurz & Kanstantsin Pashkovich & Daniël Paulusma, 2020. "Simple games versus weighted voting games: bounding the critical threshold value," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(4), pages 609-621, April.
    13. Mario Guajardo & Kurt Jörnsten & Mikael Rönnqvist, 2016. "Constructive and blocking power in collaborative transportation," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(1), pages 25-50, January.
    14. Peter Knudsen & Lars Østerdal, 2012. "Merging and splitting in cooperative games: some (im)possibility results," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(4), pages 763-774, November.
    15. Sylvain Béal & Marc Deschamps & Philippe Solal, 2014. "Balanced collective contributions, the equal allocation of non-separable costs and application to data sharing games," Working Papers hal-01377926, HAL.
    16. Skorin-Kapov, Darko & Skorin-Kapov, Jadranka, 2005. "Threshold based discounting networks: The cost allocation provided by the nucleolus," European Journal of Operational Research, Elsevier, vol. 166(1), pages 154-159, October.
    17. Gianfranco Gambarelli, 1999. "Maximax Apportionments," Group Decision and Negotiation, Springer, vol. 8(6), pages 441-461, November.
    18. H. Andrew Michener & Daniel J. Myers, 1998. "Probabilistic Coalition Structure Theories," Journal of Conflict Resolution, Peace Science Society (International), vol. 42(6), pages 830-860, December.
    19. Gonzalez, Stéphane & Rostom, Fatma Zahra, 2022. "Sharing the global outcomes of finite natural resource exploitation: A dynamic coalitional stability perspective," Mathematical Social Sciences, Elsevier, vol. 119(C), pages 1-10.
    20. Platz, T.T. & Hamers, H.J.M. & Quant, M., 2011. "Characterizing Compromise Stability of Games Using Larginal Vectors," Discussion Paper 2011-058, Tilburg University, Center for Economic Research.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:55:y:2007:i:1:p:182-187. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.