Ir al contenido

Documat

Constraint relaxation for the discrete ordered median problem

  • Luisa I. Martínez-Merino [1] ; Diego Ponce [2] ; Justo Puerto [2]
    1. [1] Universidad de Cádiz

      Universidad de Cádiz

      Cádiz, España

    2. [2] Universidad de Sevilla

      Universidad de Sevilla

      Sevilla, España

  • Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 31, Nº. 3, 2023, págs. 538-561
  • Idioma: inglés
  • DOI: 10.1007/s11750-022-00651-3
  • Enlaces
  • Resumen

    • This paper compares different exact approaches to solve the Discrete Ordered Median Problem (DOMP). In recent years, DOMP has been formulated using set packing constraints giving rise to one of its most promising formulations. The use of this family of constraints, known as strong order constraints (SOC), has been validated in the literature by its theoretical properties and because their linear relaxation provides very good lower bounds. Furthermore, embedded in branch-and-cut or branch-price-and-cut procedures as valid inequalities, they allow one to improve computational aspects of solution methods such as CPU time and use of memory. In spite of that, the above mentioned formulations require to include another family of order constraints, e.g., the weak order constraints (WOC), which leads to coefficient matrices with elements other than {0,1}. In this work, we develop a new approach that does not consider extra families of order constraints and furthermore relaxes SOC -in a branch-and-cut procedure that does not start with a complete formulation- to add them iteratively using row generation techniques to certify feasibility and optimality. Exhaustive computational experiments show that it is advisable to use row generation techniques in order to only consider {0,1}-coefficient matrices modeling the DOMP. Moreover, we test how to exploit the problem structure. Implementing an efficient separation of SOC using callbacks improves the solution performance. This allows us to deal with bigger instances than using fixed cuts/constraints pools automatically added by the solver in the branch-and-cut for SOC, concerning both the formulation based on WOC and the row generation procedure.

  • Referencias bibliográficas
    • Achterberg T (2009) SCIP: Solving constraint integer programs. Math Progr Comput 1(1):1–41. https://doi.org/10.1007/s12532-008-0001-1
    • Ackooij W, de Oliveira W (2014) Level bundle methods for constrained convex optimization with various oracles. Comput Opt Appl 57(3):555–597....
    • Aouad A, Segev D (2019) The ordered k-median problem: surrogate models and approximation algorithms. Math Progr 177:55–83. https://doi.org/10.1007/s10107-018-1259-3
    • Archetti C, Corberán A, Plana I, Sanchis JM, Speranza MG (2016) A branch-and-cut algorithm for the orienteering arc routing problem. Comput...
    • Benati S, Puerto J, Rodríguez-Chía AM (2017) Clustering data that are graph connected. Eur J Oper Res 261:43–53. https://doi.org/10.1016/j.ejor.201.02.009
    • Blado D, Toriello A (2021) A column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizes. Math...
    • Boland N, Domínguez-Marín P, Nickel S, Puerto J (2006) Exact procedures for solving the discrete ordered median problem. Comput Oper Res 33(11):3270–3300....
    • Calvino JJ, López-Haro M, Muñoz-Ocaña JM, Puerto J, Rodríguez-Chía AM (2022) Segmentation of scanning-transmission electron microscopy images...
    • CPLEX (last accessed November 13, 2022) Differences between user cuts and lazy constraints. https://www.ibm.com/docs/en/icos/20.1.0?topic=pools-differences-between-user-cuts-lazy-constraints
    • De Oliveira W, Sagastizábal C (2014) Level bundle methods for oracles with on-demand accuracy. Opt Methods Software 29(6):1180–1209. https://doi.org/10.1080/10556788.2013.871282
    • Deleplanque S, LabbéM Ponce D, Puerto J (2020) A branch-price-and-cut procedure for the discrete ordered median problem. Informs J Comput...
    • Deleplanque S, LabbéM, Ponce D, Puerto J (last accessed November 13, 2022) DOMP repository. https://gom.ulb.ac.be/gom/wp-content/uploads/2018/12/DOMP_Repository.zip
    • Domínguez E, Marín A (2020) Discrete ordered median problem with induced order. TOP 28:793–813. https://doi.org/10.1007/s11750-020-00570-1
    • Edmonds J, Johnson EL (1973) Matching, Euler tours and the Chinese postman. Math Progr 5(1):88–124. https://doi.org/10.1007/BF01580113
    • Espejo I, Marín A, Puerto J, Rodríguez-Chía AM (2009) A comparison of formulations and solution methods for the minimum-envy location problem....
    • Fernández E, Pozo MA, Puerto J, Scozzari A (2017) Ordered weighted average optimization in multiobjective spanning tree problem. Eur J Oper...
    • Focacci F, Lodi A, Milano M (2002) Embedding relaxations in global constraints for solving TSP and TSPTW. Ann Math Artif Intell 34:291–311....
    • Focacci F, Lodi A, Milano M (2002) Optimization-oriented global constraints. Constraints 7:351–365. https://doi.org/10.1023/A:1020589922418
    • Focacci F, Lodi A, Milano M, Vigo D (1999) Solving TSP through the integration of OR and CP techniques. Electron Notes Discrete Math 1:3–25....
    • Fourour S, Lebbah Y (2020) Equitable optimization for multicast communication. Int J Decis Support Syst Technol 12(3):1–25. https://doi.org/10.4018/IJDSST.2020070101
    • Gleixner A, Bastubbe M, Eifler L, Gally T, Gamrath G, Gottwald RL, Hendel G, Hojny C, Koch T, Lübbecke ME, Maher SJ, Miltenberger M, Müller...
    • Grötschel M, Holland O (1985) Solving matching problems with linear programming. Math Progr 33:243–259. https://doi.org/10.1007/BF01584376
    • Hakimi SL (1964) Optimum location of switching centers and the absolute centers and medians of a graph. Oper Res 12:450–459. https://doi.org/10.1287/opre.12.3.450
    • Kalcsics J, Nickel S, Puerto J, Rodríguez-Chía AM (2010) The ordered capacitated facility location problem. TOP 18:203–222. https://doi.org/10.1007/s11750-009-0089-0
    • Labbé M, Ponce D, Puerto J (2017) A comparative study of formulations and solution methods for the discrete ordered p-median problem. Comput...
    • Letchford AN, Reinelt G, Theis DO (2004) A faster exact separation algorithm for blossom inequalities. In: Bienstock D, Nemhauser G (eds)...
    • Magnanti TL, Wolsey LA (1995) Chapter 9 optimal trees. In: Ball MO, Magnanti TL, Monma CL, Nemhauser GL (eds) Network Models, volume 7 of...
    • Marín A, Martínez-Merino LI, Puerto J, Rodríguez-Chía AM (2022) The soft-margin support vector machine with ordered weighted average. Knowl...
    • Marín A, Nickel S, Puerto J, Velten S (2009) A flexible model and efficient solution strategies for discrete location problems. Discrete Appl...
    • Marín A, Nickel S, Velten S (2010) An extended covering model for flexible discrete and equity location problems. Math Methods Oper Res 71(1):125–163....
    • Marín A, Pelegrín M (2019) p-Median Problems In: Laporte, G., Nickel, S., Saldanha da Gama, F. (eds) Location Science. Springer, Cham, pp...
    • Martínez-Merino LI, Albareda-Sambola M, Rodríguez-Chía AM (2017) The probabilistic p-center problem: Planning service for potential customers....
    • Mazzi N, Grothey A, McKinnon K, Sugishita N (2021) Benders decomposition with adaptive oracles for large scale optimization. Math Progr Comput...
    • Nickel S (2001) Discrete ordered Weber problems. In: Fleischmann B, Lasch R, Derigs U, Domschke W, Rieder U (eds) Operations Research Proceedings....
    • Nickel S, Puerto J (2005) Location Theory: a unified approach. Springer-Verlag, Berlin Heidelberg
    • Ogryczak W, Perny P, Weng P (2011) On minimizing ordered weighted regrets in multiobjective Markov decision processes, volume 6992 LNAI of...
    • Ponce D, Puerto J, Ricca F, Scozzari A (2018) Mathematical programming formulations for the efficient solution of the k-sum approval voting...
    • Puerto J, Ramos AB, Rodríguez-Chía AM (2013) A specialized branch & bound & cut for single-allocation ordered median hub location...
    • ReVelle CS, Swain R (1970) Central facilities location. Geograph Anal 2:30–42. https://doi.org/10.1111/j.1538- 4632.1970.tb00142.x
    • SCIP (last accessed November 13, 2022a) When should I implement a constraint handler, when should I implement a separator? https://www.scipopt.org/doc/html/FAQ.php#conshdlrvsseparator
    • SCIP (last accessed November 13, 2022b) SCIPcreateCons(). https://www.scipopt.org/doc/html/group__PublicConstraintMethods.php#ga8d771b778ea2599827e84d01c0aceaf2
    • Tamir A (2001) The k-centrum multi-facility location problem. Discrete Appl Math 109(3):93–307. https://doi.org/10.1016/S0166-218X(00)00253-5
    • Wolf C, Fábián CI, Koberstein A, Suhl L (2014) Applying oracles of on-demand accuracy in two-stage stochastic programming-A computational...
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno