Unpublished conference/Abstract (Scientific congresses and symposiums)
Selecting directed cycles: a polyhedral study
Baratto, Marie; Crama, Yves
2021ECCO 2021
 

Files


Full Text
ECCO Beamer.pdf
Author postprint (1.36 MB)
Slides of the presentation
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Optimization; Graphs and Network
Abstract :
[en] The following "cycle selection problem" is motivated by an application to kidney exchange problems. For a digraph G, a cycle selection is a subset of arcs of G forming a union of directed cycles. When the arcs are weighted, the Maximum Weighted Cycle Selection (MWCS) problem consists in finding a cycle selection of maximum total weight. We prove that MWCS is strongly NP-hard. Next, we focus on the cycle selection problem associated with a complete digraph. We provide four complete ILP formulations of the problem: a "natural" one, featuring an exponential number of constraints which can be separated in polynomial time, and three extended ones. We investigate the relative strength of these formulations. We next concentrate on the natural formulation and on the description of the associated polytope. We prove that it is full-dimensional, and that all the inequalities used in the ILP formulation are facet defining. Furthermore, we describe three new classes of facet-defining inequalities. We also study the problem when we include an additional constraint on the cardinality of a cycle selection. Most of the results proved for the original case remain valid.
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Baratto, Marie ;  Université de Liège - ULiège > HEC Liège : UER > UER Opérations: Rech. opérationnelle et gest. de la product.
Crama, Yves  ;  Université de Liège - ULiège > HEC Liège : UER > UER Opérations: Rech. opérationnelle et gest. de la product.
Language :
English
Title :
Selecting directed cycles: a polyhedral study
Publication date :
11 June 2021
Event name :
ECCO 2021
Event organizer :
European Chapter on Combinatorial Optimization (ECCO)
Event date :
du 10 juin 2021 au 11 juin 2021
Audience :
International
Available on ORBi :
since 25 June 2021

Statistics


Number of views
64 (11 by ULiège)
Number of downloads
22 (6 by ULiège)

Bibliography


Similar publications



Contact ORBi