IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v143y2006i1p265-27510.1007-s10479-006-7387-9.html
   My bibliography  Save this article

Max-min sum minimization transportation problem

Author

Listed:
  • Sonia Puri
  • M. Puri

Abstract

A non-convex optimization problem involving minimization of the sum of max and min concave functions over a transportation polytope is studied in this paper. Based upon solving at most (g+1)(> p) cost minimizing transportation problems with m sources and n destinations, a polynomial time algorithm is proposed which minimizes the concave objective function where, p is the number of pairwise disjoint entries in the m× n time matrix {t ij } sorted decreasingly and T g is the minimum value of the max concave function. An exact global minimizer is obtained in a finite number of iterations. A numerical illustration and computational experience on the proposed algorithm is also included. Copyright Springer Science + Business Media, Inc. 2006

Suggested Citation

  • Sonia Puri & M. Puri, 2006. "Max-min sum minimization transportation problem," Annals of Operations Research, Springer, vol. 143(1), pages 265-275, March.
    • Handle: RePEc:spr:annopr:v:143:y:2006:i:1:p:265-275:10.1007/s10479-006-7387-9
    DOI: 10.1007/s10479-006-7387-9
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-006-7387-9
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-006-7387-9?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Éva Tardos, 1986. "A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs," Operations Research, INFORMS, vol. 34(2), pages 250-256, April.
    2. Sherali, Hanif D., 1982. "Equivalent weights for lexicographic multi-objective programs: Characterizations and computations," European Journal of Operational Research, Elsevier, vol. 11(4), pages 367-379, December.
    Full references (including those not matched with items on IDEAS)

    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. Ting Pong & Hao Sun & Ningchuan Wang & Henry Wolkowicz, 2016. "Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem," Computational Optimization and Applications, Springer, vol. 63(2), pages 333-364, March.
    2. Amitai Armon & Iftah Gamzu & Danny Segev, 2014. "Mobile facility location: combinatorial filtering via weighted occupancy," Journal of Combinatorial Optimization, Springer, vol. 28(2), pages 358-375, August.
    3. László A. Végh, 2017. "A Strongly Polynomial Algorithm for Generalized Flow Maximization," Mathematics of Operations Research, INFORMS, vol. 42(1), pages 179-211, January.
    4. Mao-Cheng Cai & Xiaoguang Yang & Yanjun Li, 1999. "Inverse Polymatroidal Flow Problem," Journal of Combinatorial Optimization, Springer, vol. 3(1), pages 115-126, July.
    5. Fanrong Xie & Anuj Sharma & Zuoan Li, 2022. "An alternate approach to solve two-level priority based assignment problem," Computational Optimization and Applications, Springer, vol. 81(2), pages 613-656, March.
    6. Ilan Adler & Martin Bullinger & Vijay V. Vazirani, 2024. "A Generalization of von Neumann's Reduction from the Assignment Problem to Zero-Sum Games," Papers 2410.10767, arXiv.org.
    7. Laura Laguna-Salvadó & Matthieu Lauras & Uche Okongwu & Tina Comes, 2019. "A multicriteria Master Planning DSS for a sustainable humanitarian supply chain," Annals of Operations Research, Springer, vol. 283(1), pages 1303-1343, December.
    8. Amir Akbari & Paul I. Barton, 2018. "An Improved Multi-parametric Programming Algorithm for Flux Balance Analysis of Metabolic Networks," Journal of Optimization Theory and Applications, Springer, vol. 178(2), pages 502-537, August.
    9. Sherali, Hanif D. & Van Goubergen, Dirk & Van Landeghem, Hendrik, 2008. "A quantitative approach for scheduling activities to reduce set-up in multiple machine lines," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1224-1237, June.
    10. Sharma, Anuj & Verma, Vanita & Kaur, Prabhjot & Dahiya, Kalpana, 2015. "An iterative algorithm for two level hierarchical time minimization transportation problem," European Journal of Operational Research, Elsevier, vol. 246(3), pages 700-707.
    11. Cai Mao-Cheng, 1999. "Inverse Problems of Matroid Intersection," Journal of Combinatorial Optimization, Springer, vol. 3(4), pages 465-474, December.
    12. Sonia & Puri, M.C., 2008. "Two-stage time minimizing assignment problem," Omega, Elsevier, vol. 36(5), pages 730-740, October.
    13. Podinovski, Victor V. & Bouzdine-Chameeva, Tatiana, 2016. "On single-stage DEA models with weight restrictions," European Journal of Operational Research, Elsevier, vol. 248(3), pages 1044-1050.
    14. Dipti Dubey & S. K. Neogy, 2020. "On solving a non-convex quadratic programming problem involving resistance distances in graphs," Annals of Operations Research, Springer, vol. 287(2), pages 643-651, April.
    15. Cai Mao-Cheng & Yanjun Li, 1997. "Inverse Matroid Intersection Problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 45(2), pages 235-243, June.
    16. Huang, Siming & Liu, Zhenhong, 1999. "On the inverse problem of linear programming and its application to minimum weight perfect k-matching," European Journal of Operational Research, Elsevier, vol. 112(2), pages 421-426, January.
    17. Hochbaum, Dorit S., 2002. "Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations," European Journal of Operational Research, Elsevier, vol. 140(2), pages 291-321, July.
    18. Fanrong Xie & Zuoan Li, 2022. "An iterative solution technique for capacitated two-stage time minimization transportation problem," 4OR, Springer, vol. 20(4), pages 637-684, December.
    19. Dorit Hochbaum, 2007. "Complexity and algorithms for nonlinear optimization problems," Annals of Operations Research, Springer, vol. 153(1), pages 257-296, September.
    20. Volgenant, A., 2002. "Solving some lexicographic multi-objective combinatorial problems," European Journal of Operational Research, Elsevier, vol. 139(3), pages 578-584, June.

    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:spr:annopr:v:143:y:2006:i:1:p:265-275:10.1007/s10479-006-7387-9. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.