Publications Scientifiques

[ Communication ] The Weighted Arborescence Constraint

Date de soumission: 16-02-2021
Année de Publication: 2017
Entité/Laboratoire
Document type : Communication
Discipline(s) :
Titre The Weighted Arborescence Constraint
Auteurs
Conference: Integration of AI and OR Techniques in Constraint Programming, CPAIOR 2017.
Lieu Conference:
Volume:
DOI:
Mots clés Arborescence, constrained arborescence problem, cost-based filtering, constraint programming
Resume For a directed graph, a Minimum Weight Arborescence (MWA) rooted at a vertex r is a directed spanning tree rooted at r with the minimum total weight. We define the MinArborescence constraint to solve constrained arborescence problems (CAP) in Constraint Programming (CP). A filtering based on the LP reduced costs requires O(|V|^2) where |V| is the number of vertices. We propose a procedure to strengthen the quality of the LP reduced costs in some cases, also running in O(|V|^2). Computational results on a variant of CAP show that the additional filtering provided by the constraint reduces the size of the search tree substantially.
Fichier

Publications par entité

  • Centre de Formation et de Recherche en matière de Population (CEFORP) (21)
  • Centre Interfacultaire de Formation et de Recherche en Environnement pour le Développement Durable (CIFRED) (43)
  • Chaire Internationale en Physique Mathématique et Applications (CIPMA-Chaire UNESCO) (45)
  • Ecole Doctorale Pluridisciplinaire <<Espaces, Culture et Développement>> (0)
  • Ecole Nationale d'Administration et de Magistrature (ENAM) (73)
  • Ecole Nationle d'Economie Appliquée et de Management (88)
  • Ecole Normale Supérieure (35)
  • Ecole Polytechnique d'Abomey-Calavi (EPAC) (1127)
  • Faculté de droit et de Science Politique (FADESP) (116)
  • Faculté des Lettres et Sciences Humaines (FLASH) (1382)
  • Faculté des Lettres, Langues, Arts et Communications (FLLAC) (0)
  • Faculté des Sciences Agronomiques (1947)
  • Faculté des Sciences de la Santé (FSS) (2344)
  • Faculté des Sciences Economiques et de Gestion (FASEG) (191)
  • Faculté des Sciences et Techniques (FAST) (1084)
  • Faculté des Sciences Humaines et Sociales (FASHS) (70)
  • Institut de Formation et de Recherche en Informatique (IFRI) (76)
  • Institut de Géographie de l'Aménagement du territoire et de l'Environnement (IGATE) (0)
  • Institut de Mathématiques et de Sciences Physiques (IMSP) (124)
  • Institut National de l'Eau (INE) (28)
  • INSTITUT NATIONAL DE LA JEUNESSE DE L’EDUCATION PHYSIQUE ET SPORT(INJEPS) (241)
  • Institut National des Métiers d'Art d'Archéologie et de la Culture (INMAAC) (11)
  • Institut National Médico Sanitaire ( INMeS) (0)
  • Institut Régional de Santé Publique (IRSP) (84)

Publications par sexe

  • Femme( 1411 )
  • Homme (