Compact MILP formulations for the $p$-center problem
| Autor: | Sourour Elloumi, Zacharie Alès |
|---|---|
| Přispěvatelé: | Unité de Mathématiques Appliquées ( UMA ), École Nationale Supérieure de Techniques Avancées ( Univ. Paris-Saclay, ENSTA ParisTech ), Centre d'Etude et De Recherche en Informatique du Cnam ( CEDRIC ), Conservatoire National des Arts et Métiers [CNAM] ( CNAM ), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Optimisation et commande (OC), Unité de Mathématiques Appliquées (UMA), École Nationale Supérieure de Techniques Avancées (ENSTA Paris)-École Nationale Supérieure de Techniques Avancées (ENSTA Paris), Jon Lee, Giovanni Rinaldi, A. Ridha Mahjoub, Ales, Zacharie, École Nationale Supérieure de Techniques Avancées (ENSTA Paris) |
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: |
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] |
| Zdroj: | 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 |
| DOI: | 10.1007/978-3-319-96151-4_2⟩ |
| Popis: | 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. Lecture Notes in Computer Science 2018 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|