Item


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

Other contributions: Universitat de Girona. Departament d’Informàtica, Matemàtica Aplicada i Estadística
Author: Losif, Panteleimon
Ploskas, Nikolaos
Sergiou, Kostas
Tsouros, Dimos
Date: 2024 September 3
Abstract: 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
Document access: http://hdl.handle.net/10256.1/7778
Language: eng
Publisher: Universitat de Girona. Departament d’Informàtica, Matemàtica Aplicada i Estadística
Collection: 30th International Conference on Principles and Practice of Constraint Programming
Rights: Attribution-NonCommercial-ShareAlike 4.0 International
Rights URI: http://creativecommons.org/licenses/by-nc-sa/4.0/
Subject: Programació per restriccions (Informàtica) -- Congressos
Constraint programming (Computer science) -- Congresses
Optimització amb restriccions -- Congressos
Constrained optimization -- Congresses
Title: A CP/LS heuristic method for maxmin and minmax location problems with distance constraints
Type: info:eu-repo/semantics/lecture
Repository: DUGiMedia

Subjects

Authors