Retour aux activités
Séminaire du GERAD

Integer programming formulations for the k-way (strongly) stable exchange problem


24 jan. 2019   15h00 — 16h00

Ana Viana INESC TEC, Polytechnic of Porto, Portugal

Barter exchange markets can be represented as directed graphs where agents are vertices and arcs indicate exchange opportunities. A solution consists of a set of disjoint cycles and an exchange that contains no cycle with length more than k is a k-way exchange.

In this work we consider the case where agents have preferences, represented by ranks on the outgoing arcs of the graph, and search for a k-way (strongly) stable exchange. An exchange is called stable if there is no blocking cycle where all the agents involved strictly prefer the new solution. It is strongly stable if no weakly blocking cycle exists, where at least one agent improves and neither of them gets a worse allocation. The problem of deciding existence is NP-hard for both problems.

We present three novel integer programming formulations for the above mentioned problems, which is a novel approach for this solution concept.

Joint work with X. Klimentova, P. Biró, V. Costa and J. P. Pedroso

Entrée gratuite.
Bienvenue à tous!

Andrea Lodi responsable


Salle 4488
Pavillon André-Aisenstadt
Campus de l'Université de Montréal
2920, chemin de la Tour Montréal QC H3T 1J4 Canada

Organisme associé