Le problème de l'arrondi cohérent

Soit $D$ une $n\times m$ matrice de nombres réels. On note respectivement $\alpha_i,\quad i\,\in\, 1..n$ et $\beta_j,\quad j\,\in\,1..m$ les sommes des éléments sur les lignes et les colonnes. Le but de ce problème est d'arrondir chacun des nombres stocké dans la matrice de manière à ce que, pour chaque ligne et pour chaque colonne, la somme des nombres arrondis soit l'arrondi de la somme. En d'autres termes, et si l'on note $\eta^*$ l'arrondi du nombre $\eta$, on doit avoir :

$$\left\{ \begin{array}{@{\forall\,}c@{\,\in\,}c@{\quad}l@{=... ...um\limits_{i=1}^n d_{ij}^* & \beta_j^* \end{array} \right.$$

Contrairement à de nombreuses applications où l'arrondi est imposé à l'entier le plus proche, ici $\eta^*$ est choisi librement parmi $\lfloor \eta \rfloor$ et $\lceil \eta \rceil$. Il est possible de modéliser ce problème très facilement à l'aide d'un réseau. Il suffit de considérer, en plus des sommets $s$ et $t$, deux ensembles de sommets $L$ et $C$ modélisant respectivement les lignes et les colonnes de la matrice. Chaque sommet $l_i \in L$ est ainsi associé à la i $^{\text{\\lq eme}}$ ligne de la matrice. Les arcs $(s,\,l_i)$ ont pour capacités le couple $(\lfloor \alpha_i \rfloor,\,\lceil \alpha_i \rceil)$. Réciproquement, chaque sommet $c_j \in C$ étant associé à la j $^{\text{\\lq eme}}$ colonne de $D$, les arcs $(c_j,\,t)$ ont pour capacités $(\lfloor \beta_j \rfloor,\,\lceil \beta_j \rceil)$. Reste à modéliser chacun des éléments de la matrice par un arc reliant sa ligne et sa colonne. Ainsi, l'élément $d_{ij}$ est représenté par l'arc $(l_i,\,c_j)$ de capacités $(\lfloor \eta \rfloor,\, \lceil \eta \rceil)$. D'ordinaire, il existe plusieurs solutions à ce problème, chacune étant associée à un flot compatible sur ce réseau. Toutefois, le flot max est associé à la solution utilisant le plus de valeurs supérieures alors que le flot min est associé à la solution utilisant le plus de valeurs inférieures. La figure suivante illustre ce modèle sur un exemple simple.

Figure 5.5: Modélisation du problème de l'arrondi cohérent d'une matrice par un réseau