Titre :

A comparison of node‐based and arc‐based hop‐indexed formulations for the Steiner tree problem with hop constraints

Auteur(s) :

Fortz, Bernard [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Département d'Informatique [Bruxelles] [ULB]
Gouveia, Luis [Auteur]
Universidade de Lisboa = University of Lisbon = Université de Lisbonne [ULISBOA]
Moura, Pedro [Auteur]
Universidade de Lisboa = University of Lisbon = Université de Lisbonne [ULISBOA]

Titre de la revue :

Networks

Pagination :

178-192

Éditeur :

Wiley

Date de publication :

2022-09

ISSN :

0028-3045

Mot(s)-clé(s) en anglais :

Steiner tree
hop constraint
network design
linear programming relaxation
integer programming
hop-indexed model

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

We study the relation between the linear programming relaxation of two classes of models for the Steiner tree problem with hop constraints. One class is characterized by having hop-indexed arc variables. Although such ...
Lire la suite >We study the relation between the linear programming relaxation of two classes of models for the Steiner tree problem with hop constraints. One class is characterized by having hop-indexed arc variables. Although such models have proved to have a very strong linear programming bound, they are not easy to use because of the huge number of variables. This has motivated some studies with models involving fewer variables that use, instead of the hop-indexed arc variables, hop-indexed node variables. In this paper we contextualize the linear programming relaxation of these node-based models in terms of the linear programming relaxation of known arc-based models. We show that the linear programming relaxation of a general node-based model is implied by the linear programming relaxation of a straightforward arc-based model.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL