Revisiting a Cornuéjols-Nemhauser-Wolsey formulation for the p-median problem
We revisit a formulation for the simple plant facility location and p-median problems introduced by Cornuéjols, Nemhauser and Wolsey (1980). Despite being the smallest known formulation regarding the number of variables, this formulation is barely used or cited in the literature. Here, we reintroduc...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-01-01
|
| Series: | EURO Journal on Computational Optimization |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2192440623000254 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1846123417797918720 |
|---|---|
| author | Agostinho Agra Cristina Requejo |
| author_facet | Agostinho Agra Cristina Requejo |
| author_sort | Agostinho Agra |
| collection | DOAJ |
| description | We revisit a formulation for the simple plant facility location and p-median problems introduced by Cornuéjols, Nemhauser and Wolsey (1980). Despite being the smallest known formulation regarding the number of variables, this formulation is barely used or cited in the literature. Here, we reintroduce the formulation for the p-median problem from a different perspective, resulting from the intersection of a selection problem with an additional family of optimality constraints to define the costs correctly. An alternative proof that the linear relaxation of the formulation is equivalent to the linear relaxation of the well-known classical formulation is provided. By exploring the optimality constraints we discuss approaches to derive bounds for large-size instances. These approaches are based on relaxations obtained by eliminating optimality constraints and can be seen as a simple matheuristic to solve large size instances. In particular, we characterize relaxations which provide the optimal solution, and therefore, can be seen as new formulations for the p-median problem. Computational tests are reported showing that the renewed formulation can be used efficiently to solve p-median instances. |
| format | Article |
| id | doaj-art-6507ded25e514dc592932cc7cf443a7f |
| institution | Kabale University |
| issn | 2192-4406 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | EURO Journal on Computational Optimization |
| spelling | doaj-art-6507ded25e514dc592932cc7cf443a7f2024-12-14T06:30:51ZengElsevierEURO Journal on Computational Optimization2192-44062024-01-0112100081Revisiting a Cornuéjols-Nemhauser-Wolsey formulation for the p-median problemAgostinho Agra0Cristina Requejo1Departamento de Matemática, Universidade de Aveiro, Campus Universitário de Santiago, 3810-193 Aveiro, Portugal; Centro de Investigação e Desenvolvimento em Matemática e Aplicações (CIDMA), Portugal; Corresponding author.Lisbon School of Economics & Management, Universidade de Lisboa, Rua do Quelhas, 6, 1200-781 Lisboa, Portugal; Centro de Investigação e Desenvolvimento em Matemática e Aplicações (CIDMA), PortugalWe revisit a formulation for the simple plant facility location and p-median problems introduced by Cornuéjols, Nemhauser and Wolsey (1980). Despite being the smallest known formulation regarding the number of variables, this formulation is barely used or cited in the literature. Here, we reintroduce the formulation for the p-median problem from a different perspective, resulting from the intersection of a selection problem with an additional family of optimality constraints to define the costs correctly. An alternative proof that the linear relaxation of the formulation is equivalent to the linear relaxation of the well-known classical formulation is provided. By exploring the optimality constraints we discuss approaches to derive bounds for large-size instances. These approaches are based on relaxations obtained by eliminating optimality constraints and can be seen as a simple matheuristic to solve large size instances. In particular, we characterize relaxations which provide the optimal solution, and therefore, can be seen as new formulations for the p-median problem. Computational tests are reported showing that the renewed formulation can be used efficiently to solve p-median instances.http://www.sciencedirect.com/science/article/pii/S2192440623000254Locationp-medianSimple plant facility locationMixed integer formulation |
| spellingShingle | Agostinho Agra Cristina Requejo Revisiting a Cornuéjols-Nemhauser-Wolsey formulation for the p-median problem EURO Journal on Computational Optimization Location p-median Simple plant facility location Mixed integer formulation |
| title | Revisiting a Cornuéjols-Nemhauser-Wolsey formulation for the p-median problem |
| title_full | Revisiting a Cornuéjols-Nemhauser-Wolsey formulation for the p-median problem |
| title_fullStr | Revisiting a Cornuéjols-Nemhauser-Wolsey formulation for the p-median problem |
| title_full_unstemmed | Revisiting a Cornuéjols-Nemhauser-Wolsey formulation for the p-median problem |
| title_short | Revisiting a Cornuéjols-Nemhauser-Wolsey formulation for the p-median problem |
| title_sort | revisiting a cornuejols nemhauser wolsey formulation for the p median problem |
| topic | Location p-median Simple plant facility location Mixed integer formulation |
| url | http://www.sciencedirect.com/science/article/pii/S2192440623000254 |
| work_keys_str_mv | AT agostinhoagra revisitingacornuejolsnemhauserwolseyformulationforthepmedianproblem AT cristinarequejo revisitingacornuejolsnemhauserwolseyformulationforthepmedianproblem |