Constraint relaxation for the discrete ordered median problem

  1. Luisa I. Martínez-Merino 1
  2. Diego Ponce 2
  3. Justo Puerto 2
  1. 1 Universidad de Cádiz
    info

    Universidad de Cádiz

    Cádiz, España

    ROR https://ror.org/04mxxkb11

  2. 2 Universidad de Sevilla
    info

    Universidad de Sevilla

    Sevilla, España

    ROR https://ror.org/03yxnpp24

Revista:
Top

ISSN: 1863-8279,  1134-5764

Año de publicación: 2023

Volumen: 31

Número: 3

Páginas: 538-561

Tipo: Artículo

DOI: 10.1007/S11750-022-00651-3 DIALNET GOOGLE SCHOLAR lock_openAcceso abierto editor

Otras publicaciones en: Top

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.

€ Ver financiación

Información de financiación

Financiadores

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. https://doi.org/10.1007/s10589-013-9610-3
  • 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 Oper Res 66:95–104. https://doi.org/10.1016/j.cor.2015.08.003
  • 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 Progr Comput 13:85–223. https://doi.org/10.1007/s12532-020-00189-0
  • 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. https://doi.org/10.1016/j.cor.2005.03.025
  • 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 using the ordered median problem. Eur J Oper Res 302(2):671–687. https://doi.org/10.1016/j.ejor.2022.01.022
  • 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 32:582–599. https://doi.org/10.1287/ijoc.2019.0915
  • 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. Comput Oper Res 36(6):1966–1981. https://doi.org/10.1016/j.cor.2008.06.013
  • Fernández E, Pozo MA, Puerto J, Scozzari A (2017) Ordered weighted average optimization in multiobjective spanning tree problem. Eur J Oper Res 260(3):886–903. https://doi.org/10.1016/j.ejor.2016.10.016
  • Focacci F, Lodi A, Milano M (2002) Embedding relaxations in global constraints for solving TSP and TSPTW. Ann Math Artif Intell 34:291–311. https://doi.org/10.1023/A:1014492408220
  • 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. https://doi.org/10.1016/S1571-0653(04)00002-2
  • 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 B, Pfetsch ME, Puchert C, Rehfeldt D, Schlösser F, Schubert C, Serrano F, Shinano Y, Viernickel JM, Walter M, Wegscheider F, Witt JT, Witzig J (2018) The SCIP Optimization Suite 6.0. ZIB-Report 18-26, Zuse Institute Berlin
  • 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 Oper Res 78:230–242. https://doi.org/10.1016/j.cor.2016.06.004
  • Letchford AN, Reinelt G, Theis DO (2004) A faster exact separation algorithm for blossom inequalities. In: Bienstock D, Nemhauser G (eds) Integer Programming and Combinatorial Optimization. Springer, Berlin Heidelberg, pp 196–205
  • Magnanti TL, Wolsey LA (1995) Chapter 9 optimal trees. In: Ball MO, Magnanti TL, Monma CL, Nemhauser GL (eds) Network Models, volume 7 of Handbooks in Operations Research and Management Science. Elsevier, pp 503–615
  • 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 Based Syst 237:107705. https://doi.org/10.1016/j.knosys.2021.107705
  • Marín A, Nickel S, Puerto J, Velten S (2009) A flexible model and efficient solution strategies for discrete location problems. Discrete Appl Math 157(5):1128–1145. https://doi.org/10.1016/j.dam.2008.03.013
  • 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. https://doi.org/10.1007/s00186-009-0288-3
  • 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 25–50 https://doi.org/10.1007/978-3-030-32177-2_2
  • Martínez-Merino LI, Albareda-Sambola M, Rodríguez-Chía AM (2017) The probabilistic p-center problem: Planning service for potential customers. Eur J Oper Res 262(2):509–520. https://doi.org/10.1016/j.ejor.2017.03.043
  • Mazzi N, Grothey A, McKinnon K, Sugishita N (2021) Benders decomposition with adaptive oracles for large scale optimization. Math Progr Comput 13:683–703. https://doi.org/10.1007/s12532-020-00197-0
  • Nickel S (2001) Discrete ordered Weber problems. In: Fleischmann B, Lasch R, Derigs U, Domschke W, Rieder U (eds) Operations Research Proceedings. Springer, Berlin Heidelberg, pp 71–76
  • 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 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
  • Ponce D, Puerto J, Ricca F, Scozzari A (2018) Mathematical programming formulations for the efficient solution of the k-sum approval voting problem. Comput Oper Res 98:127–136. https://doi.org/10.1016/j.cor.2018.05.014
  • Puerto J, Ramos AB, Rodríguez-Chía AM (2013) A specialized branch & bound & cut for single-allocation ordered median hub location problems. Discrete Appl Math 16:2624–2646. https://doi.org/10.1016/j.dam.2013.05.035
  • 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 study. Eur J Oper Res 239(2):437–448. https://doi.org/10.1016/j.ejor.2014.05.010
Fuente de los datos: Dialnet