Previous Contents Next

3   Programmation linéaire en nombres entiers paramétrée

Nous présentons ici la façon dont l'interface à PIP a été réalisée et ce qu'elle apporte en facilité d'utilisation.

3.1   PIP

PIP est l'acronyme de Parameterized Integer Programming ou programmation linéaire paramétrée en nombres entiers. Cet outil permet de calculer le minimum lexicographique d'un domaine polyédrique paramétré.

La solution d'un tel problème est représentée par un QUAST (Quasi Affine Selection Tree), c'est-à-dire un arbre de sélection dont les prédicats sont des inégalités affines et les feuilles des listes de formes affines ou ^ signifiant qu'il n'y a pas de solution pour la branche considérée. Une branche de QUAST définit un domaine de paramètres et la valeur du minimum lexicographique du polyèdre pour des paramètres à valeurs dans ce domaine.

Étant donné que PIP peut travailler en nombres entiers, pour exprimer la solution, on peut avoir besoin de divisions entières. Pour conserver des formes affines dans les prédicats de sélection et les feuilles, PIP peut introduire des << nouveaux paramètres >> définis comme la division entière d'une forme affine par un entier.

Voici un exemple d'utilisation de PIP tiré de [16] : minimiser (i, j) tels que
ì
í
î
i£ n
j£ p
2i+j=2n+p-m
 ,     (1)
toutes les variables et tous les paramètres étant positifs ou nuls. Voici sous quelle forme il est traité par PIP :
problème posé réponse 
((commentaire)
 2 3 4 0 -1 1
 (#[-1 0 0 0 1 0]
  #[0 -1 0 0 0 1]
  #[-2 -1 0 -1 2 1]
  #[2 1 0 1 -2 -1])
 ()
)


((commentaire -1 )
 (if #[ -1 2 1 0]
  (if #[ 1 -2 0 0]
   (list #[ 0 0 0 0]
         #[ -1 2 1 0])
   (newparm 3 (div #[ 1 0 0 0] 2))
   (if #[ -1 0 1 2 0]
    (list #[ 0 1 0 -1 0]
          #[ -1 0 1 2 0])
    ()))
  ()))
L'interprétation de la réponse est
si -m+2n+p³ 0
alors
si m-2n³ 0
alors [0, -m+2n+p]
sinon
si -m+p+2(m/2)³ 0
alors [n-(m/2), -m+p+2(m/2)]
sinon ^
sinon ^
 .     (2)

3.2   Limitations de PIP

Comme on peut le voir sur l'exemple précédent, la syntaxe utilisée n'est pas très lisible, bien qu'efficace pour le calcul. Une autre limitation de PIP , qui tient à l'algorithme utilisé (et qui garantit une solution), est que toutes les variables et tous les paramètres sont considérés à valeurs positives. Ce qui peut amener l'utilisateur à faire des changements de variables pour pouvoir résoudre son problème. De même il est facile en utilisant cette même méthode de faire calculer à PIP des maxima lexicographiques et des minima et des maxima de fonctions objectives affines.

3.3   Interface à PIP

Ce que SPPoC propose dans son interface répond aux problèmes évoqués ci-dessus. En effet, la syntaxe proposée est complètement symbolique comme on peut le voir dans la version SPPoC de notre exemple1 : 
# let p = PIP.make <:s<i<=n, j<=p, 2*i+j=2*n+p-m>>
                   (Question.min_lex <:v<i, j>>);;               
val p : SPPoC.PIP.t =
  Solve : MIN(i, j)
  Under the constraints :
  {i <= n, j <= p, 2*i+j+m = 2*n+p}
# PIP.solve_pos p;;
- : SPPoC.EQuast.t =
Parameters :
np1 = m mod 2
Quast :
if m <= 2*n+p then
  if m >= 2*n then
    [0; -m+2*n+p]
  else if np1 <= p then [(-m+2*n+np1)/2; -np1+p] else _|_
else _|_
Le résultat obtenu est de forme légèrement différente (mais équivalente, bien sûr) de celle qui a été obtenue en utilisant PIP directement (voir équation (2)) car SPPoC représente les nouveaux paramètres sous forme de modulos plutôt que sous forme de divisions entières. Cela a pour effet de simplifier les expressions obtenues et en particulier de faciliter les changements de variables. Cette constatation est empirique et sa cause en est encore mal comprise.

1 Les changements de variables pour se libérer de la contrainte de positivité et permettre les maxima et les fonctions objectives sont faits automatiquement. Par exemple, pour calculer le maximum de i-j sur le domaine -n£ i £ n, 0£ j £ n-i, n³ 10, il suffit d'écrire: 
# PIP.solve (PIP.make <:s<-n<=i<=n; 0<=j<=n-i; n>=10>> 
                      (Question.max_fun <:f<i-j>>));;  
- : SPPoC.EQuast.t = [n]
Le dialogue entre SPPoC et PIP se fait à travers un appel de fonction C2. SPPoC autorise aussi la manipulation des QUAST et permet ainsi l'enchaînement de calculs avec plusieurs appels à PIP . Pour une description des opérations possibles sur les QUAST, voir la section 6.4. Le chapitre 7.1 présente une utilisation intensive de cette interface où plusieurs dizaines d'appels à PIP sont nécessaires pour produire un résultat.

Previous Contents Next