IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v189y2008i3p920-938.html
   My bibliography  Save this article

Polyhedral combinatorics of multi-index axial transportation problems

Author

Listed:
  • Kravtsov, M.K.
  • Lukshin, E.V.

Abstract

This paper studies integer points (IP) and integer vertices (IV) of the p-index axial transportation polytope (p-ATP) of order n1ín2í...ínp, n1,n2,...,np[greater-or-equal, slanted]2, p[greater-or-equal, slanted]2, defined by integer vectors, as well as noninteger vertices of the 3-ATP. In particular, for the p-ATP, we establish criteria for the minimum and maximum number of IPs and describe the class of polytopes for which the number of IPs coincides with the number of IVs. For the 3-ATP of order nínín, we prove the theorem on the exponential growth of denominators of fractional components of the polytope vertices. Three conjectures are stated regarding the maximum number of vertices of the p-ATP, the maximum number of IVs, and the structure of the nondegenerate polytopes with the maximum number of IPs.

Suggested Citation

  • Kravtsov, M.K. & Lukshin, E.V., 2008. "Polyhedral combinatorics of multi-index axial transportation problems," European Journal of Operational Research, Elsevier, vol. 189(3), pages 920-938, September.
    • Handle: RePEc:eee:ejores:v:189:y:2008:i:3:p:920-938
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(07)00667-4
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. K. B. Haley, 1963. "The Multi-Index Problem," Operations Research, INFORMS, vol. 11(3), pages 368-379, June.
    2. Frieze, A. M., 1983. "Complexity of a 3-dimensional assignment problem," European Journal of Operational Research, Elsevier, vol. 13(2), pages 161-164, June.
    3. Junginger, Werner, 1993. "On representatives of multi-index transportation problems," European Journal of Operational Research, Elsevier, vol. 66(3), pages 353-371, May.
    4. John Current & Akio Imai & Hasan Pirkul, 1994. "The Capacitated Carrier Transportation Problem: An Application of the Axial Three-Dimensional Transportation Problem with Heuristic," Transportation Science, INFORMS, vol. 28(4), pages 328-336, November.
    5. Tzeng, Gwo-Hshiung & Teodorovic, Dusan & Hwang, Ming-Jiu, 1996. "Fuzzy bicriteria multi-index transportation problems for coal allocation planning of Taipower," European Journal of Operational Research, Elsevier, vol. 95(1), pages 62-72, November.
    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. Abd Elazeem M. Abd Elazeem & Abd Allah A. Mousa & Mohammed A. El-Shorbagy & Sayed K. Elagan & Yousria Abo-Elnaga, 2021. "Detecting All Non-Dominated Points for Multi-Objective Multi-Index Transportation Problems," Sustainability, MDPI, vol. 13(3), pages 1-18, January.
    2. Dalbinder Kaur & Sathi Mukherjee & Kajla Basu, 2015. "Solution of a Multi-Objective and Multi-Index Real-Life Transportation Problem Using Different Fuzzy Membership Functions," Journal of Optimization Theory and Applications, Springer, vol. 164(2), pages 666-678, February.
    3. Jimenez, F. & Verdegay, J. L., 1999. "Solving fuzzy solid transportation problems by an evolutionary algorithm based parametric approach," European Journal of Operational Research, Elsevier, vol. 117(3), pages 485-510, September.
    4. Arora, Shalini & Puri, M. C., 1998. "A variant of time minimizing assignment problem," European Journal of Operational Research, Elsevier, vol. 110(2), pages 314-325, October.
    5. Sadeghi, Mehdi & Mirshojaeian Hosseini, Hossein, 2006. "Energy supply planning in Iran by using fuzzy linear programming approach (regarding uncertainties of investment costs)," Energy Policy, Elsevier, vol. 34(9), pages 993-1003, June.
    6. Teodorovic, Dus[caron]an, 1999. "Fuzzy logic systems for transportation engineering: the state of the art," Transportation Research Part A: Policy and Practice, Elsevier, vol. 33(5), pages 337-364, June.
    7. Boštjan Gabrovšek & Tina Novak & Janez Povh & Darja Rupnik Poklukar & Janez Žerovnik, 2020. "Multiple Hungarian Method for k -Assignment Problem," Mathematics, MDPI, vol. 8(11), pages 1-18, November.
    8. Singh, Bikramjit & Singh, Amarinder, 2023. "Hybrid particle swarm optimization for pure integer linear solid transportation problem," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 207(C), pages 243-266.
    9. Drexl, Andreas & Salewski, Frank, 1997. "Distribution requirements and compactness constraints in school timetabling," European Journal of Operational Research, Elsevier, vol. 102(1), pages 193-214, October.
    10. Chan, Felix T. S. & Chung, S. H. & Wadhwa, Subhash, 2005. "A hybrid genetic algorithm for production and distribution," Omega, Elsevier, vol. 33(4), pages 345-355, August.
    11. Briskorn, Dirk & Drexl, Andreas & Spieksma, Frits C. R., 2005. "Round robin tournaments and three index assignment," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 604, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    12. Gimadi, Edward Kh., 2015. "Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph," Applied Mathematics and Computation, Elsevier, vol. 255(C), pages 84-91.
    13. Kim, Bum-Jin & Hightower, William L. & Hahn, Peter M. & Zhu, Yi-Rong & Sun, Lu, 2010. "Lower bounds for the axial three-index assignment problem," European Journal of Operational Research, Elsevier, vol. 202(3), pages 654-668, May.
    14. Yokoya, Daisuke & Duin, Cees W. & Yamada, Takeo, 2011. "A reduction approach to the repeated assignment problem," European Journal of Operational Research, Elsevier, vol. 210(2), pages 185-193, April.
    15. Tzeng, Gwo-Hshiung & Teodorovic, Dusan & Hwang, Ming-Jiu, 1996. "Fuzzy bicriteria multi-index transportation problems for coal allocation planning of Taipower," European Journal of Operational Research, Elsevier, vol. 95(1), pages 62-72, November.
    16. Khurana, Archana & Adlakha, Veena & Lev, Benjamin, 2018. "Multi-index constrained transportation problem with bounds on availabilities, requirements and commodities," Operations Research Perspectives, Elsevier, vol. 5(C), pages 319-333.
    17. Penn, M.L. & Potts, C.N. & Harper, P.R., 2017. "Multiple criteria mixed-integer programming for incorporating multiple factors into the development of master operating theatre timetables," European Journal of Operational Research, Elsevier, vol. 262(1), pages 194-206.
    18. A. T. Ernst & R. G. J. Mills & P. Welgama, 2003. "Scheduling Appointments at Trade Events for the Australian Tourist Commission," Interfaces, INFORMS, vol. 33(3), pages 12-23, June.
    19. Renata M. Aiex & Mauricio G. C. Resende & Panos M. Pardalos & Gerardo Toraldo, 2005. "GRASP with Path Relinking for Three-Index Assignment," INFORMS Journal on Computing, INFORMS, vol. 17(2), pages 224-247, May.
    20. Loiola, Eliane Maria & de Abreu, Nair Maria Maia & Boaventura-Netto, Paulo Oswaldo & Hahn, Peter & Querido, Tania, 2007. "A survey for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 176(2), pages 657-690, January.

    More about this item

    Statistics

    Access and download statistics

    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:eee:ejores:v:189:y:2008:i:3:p:920-938. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.