Complexité et stratégies de résolution pour des problèmes d'affectation multidimensionnelle de vecteurs binaires

Guillerme Duvillié (LIRMM)

May 11, 2016 | 13h00-14h00 | Salle Von Neuman - Polytech Tours

Let us consider some variants of the multidimensional assignment problem, where weight of the hyperedges are locally encoded via node labels. In these problems, we are given an $m$-partite complete hypergraph $H = (V^1, V^2, ..., V^m)$. Each set $V^i$ contains exactly $n$ nodes labeled by a $p$-dimensional binary vector. To each hyperedge we associate a representative $p$-dimensional binary vector obtained by performing the bitwise-and between every label of the nodes in the hyperedge. The weight of the hyperedge is given by the number of zeros or the number of ones in the representative vector. The objective is then to select $n$ disjoint hyperedges  while maximizing the overall number of ones ($\max \sum 1$) or minimizing the overall number of zeros ($\min \sum 0$) in the representative vectors of the selected hyperedges.

In a first time I provide negative results for both of the variants. In a second time, we present ILP formulations that can be used to solve in practical these problems and provide experimentations results  based on these formulations.