Help
Cart
Skip main navigation

Available Issues

April 12, 2013 - April 13, 2026

Available Issues

April 12, 2013 - April 13, 2026

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

Published Online:2 Jul 2020https://doi.org/10.1287/ijoc.2019.0915

References

  • Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper. Res. Lett. 33(1):42–54.Crossref, Google Scholar
  • Applegate D, Bixby R, Chvátal V, Cook W (1995) Finding cuts in the TSP (a preliminary report). DIMACS Technical Report 95-05, DIMACS, Rutgers University, New Brunswick, NJ.Google Scholar
  • Avella P, Sassano A, Vasil’ev I (2006) Computational study of large-scale p-median problems. Math. Programming 109(1):89–114.Crossref, Google Scholar
  • Barnhart C, Johnson E, Nemhauser G, Savelsbergh M, Vance P (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
  • Beale E, Tomlin J (1970) Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. Lawrence J, ed. Proc. 5th Internat. Conf. Oper. Res. (Tavistock Publications, London), 447–454.Google Scholar
  • Benichou M, Gauthier J, Girodet P, Hentges G, Ribiere G, Vincent O (1971) Experiments in mixed-integer programming. Math. Programming 1(1):71–94.Crossref, Google Scholar
  • 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.Crossref, Google Scholar
  • Ceselli A, Righini G (2005) A branch-and-price algorithm for the capacitated p-median problem. Networks 45(3):125–142.Crossref, Google Scholar
  • Ceselli A, Liberatore F, Righini G (2008) A computational evaluation of a general branch-and-price framework for capacitated network location problems. Ann. Oper. Res. 167(1):209–251.Crossref, Google Scholar
  • Chvátal V (1983) Linear Programming (W. H. Freeman and Company, New York).Google Scholar
  • Contreras I, Díaz J, Fernández E (2011) Branch and price for large-scale capacitated hub location problems with single assignment. INFORMS J. Comput. 23(1):41–55.Link, Google Scholar
  • Deleplanque S, Labbé M, Ponce D, Puerto J (2018) An extended version of a branch-price-and-cut procedure for the discrete ordered median problem. Preprint, submitted February 9, https://arxiv.org/abs/1802.03191.Google Scholar
  • Desrosiers J, Lübecke M (2005) A primer in column generation. Desaulniers G, Desrosiers J, Salomon MM, eds. Column Generation (Springer, Boston), 1–32.Crossref, Google Scholar
  • Domínguez-Marín P, Nickel S, Hansen P, Mladenovic N (2005) Heuristic procedures for solving the discrete ordered median problem. Ann. Oper. Res. 136(1):145–173.Crossref, Google Scholar
  • Doulabi SHH, Rousseau LM, Pesant G (2016) A constraint-programming-based branch-and-price-and-cut approach operating room planning and scheduling. INFORMS J. Comput. 28(3):432–448.Link, Google Scholar
  • du Merle O, Vial J (2002) Proximal ACCPM, a cutting plane method for column generation and Lagrangean relaxation: Application to the p-median problem. Technical report, HEC Genève, Université de Genève, Geneva, Switzerland.Google Scholar
  • du Merle O, Villenueve D, Desrosiers J, Hansen P (1999) Stabilized column generation. Discrete Math. 194(1–3):229–237.Crossref, Google Scholar
  • Farkas G (1894) A Fourier-féle mechanikai elv alkalmazásai. Mathematikai és Természettudományi Érstesitö 12:457–472.Google Scholar
  • Feo TA, Resende MGC (1989) A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8(2):67–71.Crossref, Google Scholar
  • Feo TA, Resende MGC (1995) Greedy randomized adaptive search procedures. J. Global Optim. 6(2):109–133.Crossref, Google Scholar
  • Fernández E, Pozo MA, Puerto J (2014) Ordered weighted average combinatorial optimization: Formulations and their properties. Discrete Appl. Math. 169(31):97–118.Crossref, Google Scholar
  • Fernández E, Puerto J, Rodríguez-Chía AM (2013) On discrete optimization with ordering. Ann. Oper. Res. 207(1):83–96.Crossref, Google Scholar
  • Fernández E, Pozo MA, Puerto J, Scozzari A (2017) Ordered weighted average optimization in multiobjective spanning tree problems. Eur. J. Oper. Res. 260(31):886–903.Crossref, Google Scholar
  • Gamrath G (2010) Generic branch-cut-and-price. Master's thesis, Institut für Mathematik, Technische Universität Berlin, Berlin.Google Scholar
  • Gamrath G, Fischer T, Gally T, Gleixner AM, Hendel G, Koch T, Maher SJ, Miltenberger M, Müller B, Pfetsch ME, et al.. (2016) The SCIP optimization suite 3.2. Technical report 15-60, ZIB, Berlin.Google Scholar
  • Günlük O, Ladányi L, de Vries S (2005) A branch-and-price algorithm and new test problems for spectrum auctions. Management Sci. 51(3):391–406.Link, Google Scholar
  • Johnson EL (1989) Modeling and strong linear programs for mixed integer programming. Wallace S, ed. Algorithms and Model Formulations in Mathematical Programming, NATO ASI Series, vol. 51 (Springer, Berlin Heidelberg), 1–43.Crossref, Google Scholar
  • 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.Crossref, Google Scholar
  • Lorena L, Senne E (2004) A column generation approach to capacitated p-median problems. Comput. Oper. Res. 31(6):863–876.Crossref, Google Scholar
  • 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.Crossref, Google Scholar
  • 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.Crossref, Google Scholar
  • Nickel S (2001) Discrete ordered Weber problems. Oper. Res. Proc. 2000:71–76.Crossref, Google Scholar
  • Nickel S, Puerto J (1999) A unified approach to network location problems. Networks 34(4):283–290.Crossref, Google Scholar
  • Nickel S, Puerto J (2005) Location Theory: A Unified Approach (Springer, Berlin, Heidelberg).Google Scholar
  • Olender P, Ogryczak W (2018) A revised variable neighborhood search for the discrete ordered median problem. Eur. J. Oper. Res. 274(2):445–465.Crossref, Google Scholar
  • Perea F, Puerto J (2013) Finding the nucleolus of any n–person cooperative game by a single linear program. Comput. Oper. Res. 40(10):2308–2313.Crossref, Google Scholar
  • Pessoa A, Uchoa E, Aragão MP, Rodrigues R (2010) Exact algorithm over an arctime-indexed formulation for parallel machine scheduling problems. Math. Programming Comput. 2(3–4):259–290.Crossref, Google Scholar
  • 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.Crossref, Google Scholar
  • Puerto J (2008) A new formulation of the capacitated discrete ordered median problem with {0, 1}-assignment. Kalcsics J, Nickel S, eds. Oper. Res. Proc. 2007 (Springer, Berlin Heidelberg), 165–170.Google Scholar
  • Puerto J, Fernández F (2000) Geometrical properties of the symmetrical single facility location problem. J. Nonlinear Convex Anal. 1(3):321–342.Google Scholar
  • Puerto J, Rodríguez-Chía AM (2015) Ordered median location problems. Laporte G, Nickel S, Saldanha da Gama F, eds. Location Science (Springer) Heidelberg: 249–288.Crossref, Google Scholar
  • Puerto J, Pérez-Brito D, García-González CG (2014) A modified variable neighborhood search for the discrete ordered median problem. Eur. J. Oper. Res. 234(1):61–76.Crossref, Google Scholar
  • Puerto J, Ramos AB, Rodríguez-Chía AM (2011) Single-allocation ordered median hub location problems. Comput. Oper. Res. 38(2):559–570.Crossref, Google Scholar
  • 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. 161(16–17):2624–2646.Crossref, Google Scholar
  • Puerto J, Rodríguez-Chía AM, Tamir A (2009) Minimax regret single-facility ordered median location problems on networks. INFORMS J. Comput. 21(1):77–87.Link, Google Scholar
  • Puerto J, Ramos AB, Rodríguez-Chía AM, Sánchez-Gil MC (2016) Ordered median hub location problems with capacity constraints. Transportation Res., Part C Emerging Tech. 70:142–156.Crossref, Google Scholar
  • Ryan DM, Foster A (1981) An integer programming approach to scheduling. Wren A, ed. Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling (North-Holland, Amsterdam), 269–280.Google Scholar
  • Senne E, Lorena L, Pereira MA (2005) A branch-and-price approach to p-median location problems. Comput. Oper. Res. 32(6):1655–1664.Crossref, Google Scholar
  • Stanimirovic Z, Kratica J, Dugosija D (2007) Genetic algorithms for solving the discrete ordered median problem. Eur. J. Oper. Res. 182(3):983–1001.Crossref, Google Scholar
  • Wolsey LA (1998) Integer Programming (John Wiley & Sons, New York).Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree