IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v77y2020i2d10.1007_s10898-019-00863-1.html
   My bibliography  Save this article

An exact completely positive programming formulation for the discrete ordered median problem: an extended version

Author

Listed:
  • J. Puerto

    (Universidad de Sevilla)

Abstract

This paper presents a first continuous, linear, conic formulation for the discrete ordered median problem (DOMP). Starting from a binary, quadratic formulation in the original space of location and allocation variables that are common in location analysis (L.A.), we prove that there exists a transformation of that formulation, using the same space of variables, that allows us to cast DOMP as a continuous, linear programming problem in the space of completely positive matrices. This is the first positive result that states equivalence between the family of continuous, convex problems and some hard combinatorial problems in L.A. The result is of theoretical interest because it allows us to share the tools from continuous optimization to shed new light into the difficult combinatorial structure of the class of ordered median problems that combines elements of the p-median, quadratic assignment and permutation polytopes.

Suggested Citation

  • J. Puerto, 2020. "An exact completely positive programming formulation for the discrete ordered median problem: an extended version," Journal of Global Optimization, Springer, vol. 77(2), pages 341-359, June.
    • Handle: RePEc:spr:jglopt:v:77:y:2020:i:2:d:10.1007_s10898-019-00863-1
    DOI: 10.1007/s10898-019-00863-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-019-00863-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-019-00863-1?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. Burkard, Rainer E., 1984. "Quadratic assignment problems," European Journal of Operational Research, Elsevier, vol. 15(3), pages 283-289, March.
    2. Bomze, Immanuel M., 2012. "Copositive optimization – Recent developments and applications," European Journal of Operational Research, Elsevier, vol. 216(3), pages 509-520.
    3. Stanimirovic, Zorica & Kratica, Jozef & Dugosija, Djordje, 2007. "Genetic algorithms for solving the discrete ordered median problem," European Journal of Operational Research, Elsevier, vol. 182(3), pages 983-1001, November.
    4. Kalcsics, Jörg & Nickel, Stefan & Puerto, Justo & Rodríguez-Chía, Antonio M., 2010. "Distribution systems design with role dependent objectives," European Journal of Operational Research, Elsevier, vol. 202(2), pages 491-501, April.
    5. Jörg Kalcsics & Stefan Nickel & Justo Puerto & Antonio Rodríguez-Chía, 2010. "The ordered capacitated facility location problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 18(1), pages 203-222, July.
    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. Marín, Alfredo & Ponce, Diego & Puerto, Justo, 2020. "A fresh view on the Discrete Ordered Median Problem based on partial monotonicity," European Journal of Operational Research, Elsevier, vol. 286(3), pages 839-848.
    2. Blanco, Víctor & Gázquez, Ricardo & Ponce, Diego & Puerto, Justo, 2023. "A branch-and-price approach for the continuous multifacility monotone ordered median problem," European Journal of Operational Research, Elsevier, vol. 306(1), pages 105-126.

    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. Puerto, Justo & Pérez-Brito, Dionisio & García-González, Carlos G., 2014. "A modified variable neighborhood search for the discrete ordered median problem," European Journal of Operational Research, Elsevier, vol. 234(1), pages 61-76.
    2. Schnepper, Teresa & Klamroth, Kathrin & Stiglmayr, Michael & Puerto, Justo, 2019. "Exact algorithms for handling outliers in center location problems on networks using k-max functions," European Journal of Operational Research, Elsevier, vol. 273(2), pages 441-451.
    3. Víctor Blanco, 2019. "Ordered p-median problems with neighbourhoods," Computational Optimization and Applications, Springer, vol. 73(2), pages 603-645, June.
    4. Torki, Abdolhamid & Yajima, Yatsutoshi & Enkawa, Takao, 1996. "A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 94(2), pages 384-391, October.
    5. Bolte, Andreas & Thonemann, Ulrich Wilhelm, 1996. "Optimizing simulated annealing schedules with genetic programming," European Journal of Operational Research, Elsevier, vol. 92(2), pages 402-416, July.
    6. Andrey Afonin & Roland Hildebrand & Peter J. C. Dickinson, 2021. "The extreme rays of the $$6\times 6$$ 6 × 6 copositive cone," Journal of Global Optimization, Springer, vol. 79(1), pages 153-190, January.
    7. Samuel Deleplanque & Martine Labbé & Diego Ponce & Justo Puerto, 2020. "A Branch-Price-and-Cut Procedure for the Discrete Ordered Median Problem," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 582-599, July.
    8. Behrooz Alizadeh & Somayeh Bakhteh, 2017. "A modified firefly algorithm for general inverse p-median location problems under different distance norms," OPSEARCH, Springer;Operational Research Society of India, vol. 54(3), pages 618-636, September.
    9. Xin Tang & Ameur Soukhal & Vincent T’kindt, 2014. "Preprocessing for a map sectorization problem by means of mathematical programming," Annals of Operations Research, Springer, vol. 222(1), pages 551-569, November.
    10. Pentico, David W., 2007. "Assignment problems: A golden anniversary survey," European Journal of Operational Research, Elsevier, vol. 176(2), pages 774-793, January.
    11. Immanuel M. Bomze & Bo Peng, 2023. "Conic formulation of QPCCs applied to truly sparse QPs," Computational Optimization and Applications, Springer, vol. 84(3), pages 703-735, April.
    12. Broekmeulen, Rob A. C. M. & van Weert, Arjen & Saedt, Anton P. H., 2002. "Comparing three alternative optimisation methods for the treatment planning of bulbs," Agricultural Systems, Elsevier, vol. 72(1), pages 59-71, April.
    13. Vittorio Maniezzo, 1999. "Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 11(4), pages 358-369, November.
    14. Deng, Zhibin & Fang, Shu-Cherng & Jin, Qingwei & Xing, Wenxun, 2013. "Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme," European Journal of Operational Research, Elsevier, vol. 229(1), pages 21-28.
    15. Immanuel M. Bomze & Michael Kahr & Markus Leitner, 2021. "Trust Your Data or Not—StQP Remains StQP: Community Detection via Robust Standard Quadratic Optimization," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 301-316, February.
    16. D. J. White, 1993. "A parametric‐based heuristic program for the quadratic assignment problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(4), pages 553-568, June.
    17. Wong, Man Hong & Zhang, Shuzhong, 2014. "On distributional robust probability functions and their computations," European Journal of Operational Research, Elsevier, vol. 233(1), pages 23-33.
    18. Tian, Peng & Ma, Jian & Zhang, Dong-Mo, 1999. "Application of the simulated annealing algorithm to the combinatorial optimisation problem with permutation property: An investigation of generation mechanism," European Journal of Operational Research, Elsevier, vol. 118(1), pages 81-94, October.
    19. Bomze, Immanuel M. & Gabl, Markus, 2023. "Optimization under uncertainty and risk: Quadratic and copositive approaches," European Journal of Operational Research, Elsevier, vol. 310(2), pages 449-476.
    20. Anwa Zhou & Jinyan Fan, 2015. "Interiors of completely positive cones," Journal of Global Optimization, Springer, vol. 63(4), pages 653-675, December.

    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:jglopt:v:77:y:2020:i:2:d:10.1007_s10898-019-00863-1. 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.