Mathematical models and search algorithms for the capacitated p-center problem
From MaRDI portal
Publication:3386776
DOI10.1287/IJOC.2019.0889zbMATH Open1451.90087arXiv1803.04865OpenAlexW2979694257MaRDI QIDQ3386776FDOQ3386776
Authors: Raphael Kramer, Manuel Iori, T. Vidal 
Publication date: 7 January 2021
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Abstract: The capacitated p-center problem requires to select p facilities from a set of candidates to service a number of customers, subject to facility capacity constraints, with the aim of minimizing the maximum distance between a customer and its associated facility. The problem is well known in the field of facility location, because of the many applications that it can model. In this paper, we solve it by means of search algorithms that iteratively seek the optimal distance by solving tailored subproblems. We present different mathematical formulations for the subproblems and improve them by means of several valid inequalities, including an effective one based on a 0-1 disjunction and the solution of subset sum problems. We also develop an alternative search strategy that finds a balance between the traditional sequential search and binary search. This strategy limits the number of feasible subproblems to be solved and, at the same time, avoids large overestimates of the solution value, which are detrimental for the search. We evaluate the proposed techniques by means of extensive computational experiments on benchmark instances from the literature and new larger test sets. All instances from the literature with up to 402 vertices and integer distances are solved to proven optimality, including 13 open cases, and feasible solutions are found in 10 minutes for instances with up to 3038 vertices.
Full work available at URL: https://arxiv.org/abs/1803.04865
Recommendations
- An exact algorithm for the capacitated vertex \(p\)-center problem
- The capacitated single-source \(p\)-center problem in the presence of fixed cost and multilevel capacities using VNS and aggregation technique
- Minimax models for capacitated \(p\)-center problem in uncertain environment
- A new formulation and resolution method for the \(p\)-center problem
- A maximal client coverage algorithm for the \(p\)-center problem
Cites Work
- Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
- Title not available (Why is that?)
- A column generation approach to capacitated \(p\)-median problems
- Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem
- Title not available (Why is that?)
- LP models for bin packing and cutting stock problems
- A Best Possible Heuristic for the k-Center Problem
- An Algorithmic Approach to Network Location Problems. I: Thep-Centers
- Solution methods for thep-median problem: An annotated bibliography
- Disjunctive Programming
- Fenchel Cutting Planes for Integer Programs
- A heuristic for the p-center problem in graphs
- An exact algorithm for the capacitated vertex \(p\)-center problem
- Solving large \(p\)-median problems with a radius formulation
- New upper bounds for the two-dimensional orthogonal non-guillotine cutting stock problem
- Lagrangean duals and exact solution to the capacitated \(p\)-center problem
- A new formulation and resolution method for the \(p\)-center problem
- Capacitated \(p\)-center problem with failure foresight
- Double bound method for solving the \(p\)-center location problem
- Technical Note—A Polynomial Algorithm for the Equal Capacity p-Center Problem on Trees
- Solving thep-Center problem with Tabu Search and Variable Neighborhood Search
- Large-scale local search heuristics for the capacitated vertexp-center problem
- Formulations and valid inequalities for the heterogeneous vehicle routing problem
- Bin packing and cutting stock problems: mathematical models and exact algorithms
- Bee colony optimization for the \(p\)-center problem
- A cut and branch approach for the capacitated \(p\)-median problem based on Fenchel cutting planes
- An implementation of exact knapsack separation
- Improving the quality of heuristic solutions for the capacitated vertex \(p\)-center problem through iterated greedy local search with variable neighborhood descent
- Generating Fenchel Cutting Planes for Knapsack Polyhedra
- A branch‐and‐price algorithm for the capacitated p‐median problem
- The m-Center Problem
- New relaxation-based algorithms for the optimal solution of the continuous and discrete \(p\)-center problems
- Location science
- Approximation algorithms for the \(k\)-center problem: an experimental evaluation
- A branch decomposition algorithm for the \(p\)-median problem
Cited In (15)
- Exploiting flat subspaces in local search for \(p\)-center problem and two fault-tolerant variants
- The stratified \(p\)-center problem
- A maximal client coverage algorithm for the \(p\)-center problem
- A constructive heuristic for the uniform capacitated vertex \(k\)-center problem
- Large-scale local search heuristics for the capacitated vertexp-center problem
- Exact solution approaches for the discrete α‐neighbor p‐center problem
- A scaleable projection-based branch-and-cut algorithm for the \(p\)-center problem
- Lagrangean duals and exact solution to the capacitated \(p\)-center problem
- An exact framework for the discrete parallel machine scheduling location problem
- The multi-period \(p\)-center problem with time-dependent travel times
- Minimax models for capacitated \(p\)-center problem in uncertain environment
- The capacitated single-source \(p\)-center problem in the presence of fixed cost and multilevel capacities using VNS and aggregation technique
- Arc flow formulations based on dynamic programming: theoretical foundations and applications
- Dynamically second-preferred \(p\)-center problem
- An exact algorithm for the capacitated vertex \(p\)-center problem
Uses Software
This page was built for publication: Mathematical models and search algorithms for the capacitated \(p\)-center problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386776)
