A New Formulation and Valid inequalities for the Ring Spur Assignment Problem

Session : SS1-1 / SS1 : Challenging Mixed-Integer Problems in Network Optimization
Mercredi 10 février 15:00 - 16:00 Salle : CI2-06
Shahin Gelareh, Bernard Fortz et Rahimeh Neamatian Monemi

A new mathematical model is proposed for a variant of hub location problem arising in telecommunications applications. This problem is referred to as Ring Spur Assignment Problem (RSAP) wherein a set of hub nodes is chosen as hub nodes from among a set of nodes in a graph. The non-hub nodes are then partitioned into parts : 1) the cluster of spoke nodes each of which allocated to a hub node which all together with the hub node form a (directed/undirected) cycle and 2) a set of spur nodes that are connected directly to the other spoke nodes or hub nodes but do not lie on any route connecting spoke nodes. We then introduce several classes of valid inequalities and separation routines that allows implementing a branch-and-cut solution method. Some preliminary computational experiments will be reported.

Mots clés :