IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v32y3i2020p582-599.html
   My bibliography  Save this article

A Branch-Price-and-Cut Procedure for the Discrete Ordered Median Problem

Author

Listed:
  • Samuel Deleplanque

    (Ifsttar, COSYS, ESTAS, Université Lille Nord de France, 59000 Lille, France)

  • Martine Labbé

    (Départament d’Informatique, Faculté des Sciences, Université Libre de Bruxelles, 1050 Bruxelles, Belgium)

  • Diego Ponce

    (Instituto de Matemáticas de la Universidad de Sevilla (IMUS), 41012 Sevilla, Spain; Department of Mechanical, Industrial and Aerospace Engineering, Concordia University, Montreal, Quebec H3G 1M8, Canada; Centre interuniversitaire de recherche sur les réseaux d’enterprise, la logistique et le transport (CIRRELT), Montreal, Quebec H3T 1J4, Canada)

  • Justo Puerto

    (Instituto de Matemáticas de la Universidad de Sevilla (IMUS), 41012 Sevilla, Spain)

Abstract

The discrete ordered median problem (DOMP) is formulated as a set-partitioning problem using an exponential number of variables. Each variable corresponds to a set of demand points allocated to the same facility with the information of the sorting position of their corresponding costs. We develop a column generation approach to solve the continuous relaxation of this model. Then we apply a branch-price-and-cut algorithm to solve small- to large-sized instances of DOMP in competitive computational time.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:orijoc:v:32:y:3:i:2020:p:582-599
    DOI: 10.1287/ijoc.2019.0915
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2019.0915
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2019.0915?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. Ivan Contreras & Juan A. Díaz & Elena Fernández, 2011. "Branch and Price for Large-Scale Capacitated Hub Location Problems with Single Assignment," INFORMS Journal on Computing, INFORMS, vol. 23(1), pages 41-55, February.
    2. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    3. Justo Puerto, 2008. "A New Formulation of the Capacitated Discrete Ordered Median Problems with {0, 1}-Assignment," Operations Research Proceedings, in: Jörg Kalcsics & Stefan Nickel (ed.), Operations Research Proceedings 2007, pages 165-170, Springer.
    4. 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.
    5. Seyed Hossein Hashemi Doulabi & Louis-Martin Rousseau & Gilles Pesant, 2016. "A Constraint-Programming-Based Branch-and-Price-and-Cut Approach for Operating Room Planning and Scheduling," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 432-448, August.
    6. Alfredo Marín & Stefan Nickel & Sebastian Velten, 2010. "An extended covering model for flexible discrete and equity location problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 71(1), pages 125-163, February.
    7. Patricia Domínguez-Marín & Stefan Nickel & Pierre Hansen & Nenad Mladenović, 2005. "Heuristic Procedures for Solving the Discrete Ordered Median Problem," Annals of Operations Research, Springer, vol. 136(1), pages 145-173, April.
    8. Elena Fernández & Justo Puerto & Antonio Rodríguez-Chía, 2013. "On discrete optimization with ordering," Annals of Operations Research, Springer, vol. 207(1), pages 83-96, August.
    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. Calvino, José J. & López-Haro, Miguel & Muñoz-Ocaña, Juan M. & Puerto, Justo & Rodríguez-Chía, Antonio M., 2022. "Segmentation of scanning-transmission electron microscopy images using the ordered median problem," European Journal of Operational Research, Elsevier, vol. 302(2), pages 671-687.
    2. Benati, Stefano & Ponce, Diego & Puerto, Justo & Rodríguez-Chía, Antonio M., 2022. "A branch-and-price procedure for clustering data that are graph connected," European Journal of Operational Research, Elsevier, vol. 297(3), pages 817-830.
    3. 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.
    4. Ponce, Diego & Puerto, Justo & Temprano, Francisco, 2024. "Mixed-integer linear programming formulations and column generation algorithms for the Minimum Normalized Cuts problem on networks," European Journal of Operational Research, Elsevier, vol. 316(2), pages 519-538.
    5. Ljubić, Ivana & Pozo, Miguel A. & Puerto, Justo & Torrejón, Alberto, 2024. "Benders decomposition for the discrete ordered median problem," European Journal of Operational Research, Elsevier, vol. 317(3), pages 858-874.
    6. 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.
    7. Alejandro Moya-Martínez & Mercedes Landete & Juan Francisco Monge, 2021. "Close-Enough Facility Location," Mathematics, MDPI, vol. 9(6), pages 1-17, March.
    8. Luisa I. Martínez-Merino & Diego Ponce & Justo Puerto, 2023. "Constraint relaxation for the discrete ordered median problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 31(3), pages 538-561, October.

    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. Víctor Blanco, 2019. "Ordered p-median problems with neighbourhoods," Computational Optimization and Applications, Springer, vol. 73(2), pages 603-645, June.
    2. Olender, Paweł & Ogryczak, Włodzimierz, 2019. "A revised Variable Neighborhood Search for the Discrete Ordered Median Problem," European Journal of Operational Research, Elsevier, vol. 274(2), pages 445-465.
    3. 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.
    4. Akbarzadeh, Babak & Moslehi, Ghasem & Reisi-Nafchi, Mohammad & Maenhout, Broos, 2019. "The re-planning and scheduling of surgical cases in the operating room department after block release time with resource rescheduling," European Journal of Operational Research, Elsevier, vol. 278(2), pages 596-614.
    5. 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.
    6. Ting L. Lei & Richard L. Church, 2014. "Vector Assignment Ordered Median Problem," International Regional Science Review, , vol. 37(2), pages 194-224, April.
    7. Zhang, Guowei & Jia, Ning & Zhu, Ning & Adulyasak, Yossiri & Ma, Shoufeng, 2023. "Robust drone selective routing in humanitarian transportation network assessment," European Journal of Operational Research, Elsevier, vol. 305(1), pages 400-428.
    8. Zheng Zhang & Brian T. Denton & Xiaolan Xie, 2020. "Branch and Price for Chance-Constrained Bin Packing," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 547-564, July.
    9. 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.
    10. Ljubić, Ivana & Pozo, Miguel A. & Puerto, Justo & Torrejón, Alberto, 2024. "Benders decomposition for the discrete ordered median problem," European Journal of Operational Research, Elsevier, vol. 317(3), pages 858-874.
    11. Jiachen Zhang & Youcef Magnouche & Pierre Bauguion & Sebastien Martin & J. Christopher Beck, 2024. "Computing Bipath Multicommodity Flows with Constraint Programming–Based Branch-and-Price-and-Cut," INFORMS Journal on Computing, INFORMS, vol. 36(6), pages 1634-1653, December.
    12. 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.
    13. 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.
    14. Paola Festa & Panos Pardalos, 2012. "Efficient solutions for the far from most string problem," Annals of Operations Research, Springer, vol. 196(1), pages 663-682, July.
    15. Maenhout, Broos & Vanhoucke, Mario, 2010. "A hybrid scatter search heuristic for personalized crew rostering in the airline industry," European Journal of Operational Research, Elsevier, vol. 206(1), pages 155-167, October.
    16. Hoogervorst, R. & Dollevoet, T.A.B. & Maróti, G. & Huisman, D., 2018. "Reducing Passenger Delays by Rolling Stock Rescheduling," Econometric Institute Research Papers EI2018-29, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    17. Arpan Rijal & Marco Bijvank & Asvin Goel & René de Koster, 2021. "Workforce Scheduling with Order-Picking Assignments in Distribution Facilities," Transportation Science, INFORMS, vol. 55(3), pages 725-746, May.
    18. Isabel Martins & Filipe Alvelos & Miguel Constantino, 2012. "A branch-and-price approach for harvest scheduling subject to maximum area restrictions," Computational Optimization and Applications, Springer, vol. 51(1), pages 363-385, January.
    19. James F. Campbell & Morton E. O'Kelly, 2012. "Twenty-Five Years of Hub Location Research," Transportation Science, INFORMS, vol. 46(2), pages 153-169, May.
    20. Shan Lan & John-Paul Clarke & Cynthia Barnhart, 2006. "Planning for Robust Airline Operations: Optimizing Aircraft Routings and Flight Departure Times to Minimize Passenger Disruptions," Transportation Science, INFORMS, vol. 40(1), pages 15-28, February.

    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:orijoc:v:32:y:3:i:2020:p:582-599. 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.