EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1088. Extensions of Node-Depot Assignment Formulations for the Hamiltonian p-Median Problem

Invited abstract in session MA-26: Combinatorial optimization topics in transportation, stream Combinatorial Optimization.

Monday, 8:30-10:00
Room: 012 (building: 208)

Authors (first author is the speaker)

1. Francisco Canas
DEIO - Departamento de Estatística e Investigação Operacional / CEMS.UL - Center for Mathematical Studies, Universidade de Lisboa - Faculdade de Ciências
2. Luís Gouveia
DEIO - Departamento de Estatística e Investigação Operacional, Universidade de Lisboa - Faculdade de Ciências

Abstract

Given a weighted complete undirected graph with weights on the edges and a positive integer p, the symmetric Hamiltonian p-Median Problem (HpMP) is to find a minimum weight set of p elementary cycles partitioning the vertices of the graph. We focus on a variant of the HpMP (the HpMP>=) where solutions with strictly more than p cycles are also feasible.

We present new extensions of known node-depot assignment (NDA) compact formulations. NDA models are characterized by the inclusion of NDA variables, which are 1 if and only if node d acts as the depot of the cycle node i is in (or alternatively, if node i is ``assigned" to node d), in addition to edge variables, which are 1 if and only if the corresponding edge is in some cycle. We extend these formulations with edge-depot assignment (EDA) variables, which are 1 if and only if node d acts as the depot of the cycle edge {i,j} is in. In this talk, we:

1 - Propose new formulations which use the EDA variables;
2 - Relate these models with formulations including only the edge and NDA variables;
3 - Present new inequalities in the space of the edge and NDA variables that are derived from the new models using EDA variables;
4 - Present computational results obtained with the new models.

Preliminary computational results show that the new models produce very strong LP relaxation bounds and, when used in combination with a modern ILP solver, allow for the resolution of instances with over one-hundred nodes.

Keywords

Status: accepted

Back to the list of papers