Back to Search
Start Over
Compact MILP formulations for the $p$-center problem
- Source :
- International Symposium on Combinatorial Optimization ISCO 2018, International Symposium on Combinatorial Optimization ISCO 2018, Apr 2018, Marrakech, Morocco. 2018, Combinatorial Optimization, Jon Lee; Giovanni Rinaldi; A. Ridha Mahjoub. Combinatorial Optimization, 10856, Springer, pp.14-25, 2018, Lecture Notes in Computer Science, 978-3-319-96151-4. ⟨10.1007/978-3-319-96151-4_2⟩, ISCO (International Symposium on Combinatorial Optimization) 2018, ISCO (International Symposium on Combinatorial Optimization) 2018, Apr 2018, Marrakesh, France, Lecture Notes in Computer Science ISBN: 9783319961507, ISCO
- Publication Year :
- 2023
-
Abstract
- The p-center problem consists in selecting p centers among M to cover N clients, such that the maximal distance between a client and its closest selected center is minimized. For this problem we propose two new and compact integer formulations. Our first formulation is an improvement of a previous formulation. It significantly decreases the number of constraints while preserving the optimal value of the linear relaxation. Our second formulation contains less variables and constraints but it has a weaker linear relaxation bound. We besides introduce an algorithm which enables us to compute strong bounds and significantly reduce the size of our formulations. Finally, the efficiency of the algorithm and the proposed formulations are compared in terms of quality of the linear relaxation and computation time over instances from OR-Library.<br />Lecture Notes in Computer Science 2018
- Subjects :
- Discrete mathematics
021103 operations research
p-center
equivalent formulations
0211 other engineering and technologies
discrete location
02 engineering and technology
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
Optimization and Control (math.OC)
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
0202 electrical engineering, electronic engineering, information engineering
FOS: Mathematics
020201 artificial intelligence & image processing
Center (algebra and category theory)
Cover (algebra)
Integer programming
integer programming
Mathematics - Optimization and Control
ComputingMilieux_MISCELLANEOUS
Mathematics
Integer (computer science)
[ INFO.INFO-RO ] Computer Science [cs]/Operations Research [cs.RO]
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-319-96151-4
978-3-319-96150-7 - ISBNs :
- 9783319961514 and 9783319961507
- Database :
- OpenAIRE
- Journal :
- International Symposium on Combinatorial Optimization ISCO 2018, International Symposium on Combinatorial Optimization ISCO 2018, Apr 2018, Marrakech, Morocco. 2018, Combinatorial Optimization, Jon Lee; Giovanni Rinaldi; A. Ridha Mahjoub. Combinatorial Optimization, 10856, Springer, pp.14-25, 2018, Lecture Notes in Computer Science, 978-3-319-96151-4. ⟨10.1007/978-3-319-96151-4_2⟩, ISCO (International Symposium on Combinatorial Optimization) 2018, ISCO (International Symposium on Combinatorial Optimization) 2018, Apr 2018, Marrakesh, France, Lecture Notes in Computer Science ISBN: 9783319961507, ISCO
- Accession number :
- edsair.doi.dedup.....80d86949e157e11cb3bb93da6cee7ca7