Ítem


A CP/LS heuristic method for maxmin and minmax location problems with distance constraints

Panteleimon Losif from the University of Western Macedonia, in Greece, tells that in facility location problems we seek to locate a set of facilities so that some criterion is optimized. In the p-center problem we minimize the maximum distance between clients and their closest facilities, whereas in p-dispersion we maximize the minimum distance between facilities. Recently, a variant of p-dispersion with distance constraints between facilities was studied, and an incomplete CP solver that heuristically prunes branches was shown to be faster than Gurobi and OR-Tools, but often failed to discover optimal/near-optimal solutions. We enhance this work in two directions, regarding effectiveness and applicability. We first show how local search can be used to achieve more focused branch pruning with little extra cost, resulting in optimal or near-optimal solutions being discovered in many more instances. Then, we demonstrate how the framework can be applied on the p-center problem with distance constraints, comparing it to ILP and CP models implemented in Gurobi and OR-Tools

7778.mp4 7778.mp3

Universitat de Girona. Departament d’Informàtica, Matemàtica Aplicada i Estadística

Altres contribucions: Universitat de Girona. Departament d’Informàtica, Matemàtica Aplicada i Estadística
Autor: Losif, Panteleimon
Ploskas, Nikolaos
Sergiou, Kostas
Tsouros, Dimos
Data: 3 setembre 2024
Resum: Panteleimon Losif from the University of Western Macedonia, in Greece, tells that in facility location problems we seek to locate a set of facilities so that some criterion is optimized. In the p-center problem we minimize the maximum distance between clients and their closest facilities, whereas in p-dispersion we maximize the minimum distance between facilities. Recently, a variant of p-dispersion with distance constraints between facilities was studied, and an incomplete CP solver that heuristically prunes branches was shown to be faster than Gurobi and OR-Tools, but often failed to discover optimal/near-optimal solutions. We enhance this work in two directions, regarding effectiveness and applicability. We first show how local search can be used to achieve more focused branch pruning with little extra cost, resulting in optimal or near-optimal solutions being discovered in many more instances. Then, we demonstrate how the framework can be applied on the p-center problem with distance constraints, comparing it to ILP and CP models implemented in Gurobi and OR-Tools
7778.mp4 7778.mp3
Format: audio/mpeg
video/mp4
Accés al document: http://hdl.handle.net/10256.1/7778
Llenguatge: eng
Editor: Universitat de Girona. Departament d’Informàtica, Matemàtica Aplicada i Estadística
Col·lecció: 30th International Conference on Principles and Practice of Constraint Programming
Drets: Attribution-NonCommercial-ShareAlike 4.0 International
URI Drets: http://creativecommons.org/licenses/by-nc-sa/4.0/
Matèria: Programació per restriccions (Informàtica) -- Congressos
Constraint programming (Computer science) -- Congresses
Optimització amb restriccions -- Congressos
Constrained optimization -- Congresses
Títol: A CP/LS heuristic method for maxmin and minmax location problems with distance constraints
Tipus: info:eu-repo/semantics/lecture
Repositori: DUGiMedia

Matèries

Autors