optimisation combinatoire, deuxième semestre, maîtrise MASS 2004--2005

vendredi 11 février 2005 : programmation dynamique : sac à dos
vendredi 18 février 2005 : programmation dynamique : tâches à l'heure
vendredi 25 février 2005 : mutations dans l'ADN et séparation et évaluation
vendredi 11 mars 2005 : séparation et évaluation
mardi 15 mars 2005 : séparation et évaluation : sac à dos
mardi 22 mars 2005 : programmation dynamique : voyageur de commerce
vendredi 1er avril 2005 : méthode de Jackson
vendredi 8 avril 2005 : contrôle
vendredi 15 avril 2005 : algorithmes approchés : bin-packing
vendredi 22 avril 2005 :
vendredi 13 mai 2005 :
vendredi 20 mai 2005 :
vendredi 27 mai 2005 : sac à dos NP-complet

suivant sommaire

vendredi 11 février 2005 : programmation dynamique : sac à dos

On veut remplir un sac à dos en prenant des objets dans une liste de n objets numérotés de 0 à n-1. L'objet i a un poids p[i] et une une utilité u[i]. La somme des poids des objets mis dans le sac ne doit pas dépasser psac, et on veut que la somme de leur utilité soit la plus grande possible.
On définit f[k][E] comme l'utilité maximale que l'on peut atteindre en mettant des objets pris parmi les objets de numéro k, k+1, ..., n-1 dans un sac de capacité E. On a f[k][E]=max(f[k+1][E],f[k+1][E-p[k]]+u[k]). Le nombre qui nous intéresse est f[0][psac]. On pourrait le calculer à partir de f[1][psac] et f[1][psac-p[0]], que l'on pourrait calculer à partir de f[2][psac], f[2][psac-p[0]], f[2][psac-p[1]] et f[2][psac-p[0]-p[1]], que l'on pourrait calculer à partir de 8 nombres de la forme f[3][E], que l'on pourrait calculer à partir de 16 nombres de la forme f[4][E], que l'on pourrait calculer à partir de 32 nombres de la forme f[5][E], etc.. On utiliserait ainsi 2n nombres de la forme p[n][E] (qui sont tous égaux à 0). Si on calcule f[0][psac] en utilisant une procédure qui fait deux appels récursifs à elle-même, on aura donc un temps de calcul en O(2n). Parmi tous ces nombres calculés par la procédure récursive, certains le sont plusieurs fois, c'est une perte de temps. Si (n+1)(psac+1) est plus petit que 2n, il est plus astucieux, de prendre un grand tableau dans lequel on range tous les f[k][E]. De cette façon, chacun d'eux n'est calculé qu'une fois. D'abord on range tous les f[n][E] qui valent tous 0. Puis on calcule tous les autres f[k][E] en le faisant dans l'ordre des k décroissants. Ainsi quand on calcule f[k][E] on peut utiliser f[k+1][E] et f[k+1][E-p[k]] qui ont déjà été calculés et rangés dans le tableau. 
pour tout E dans {0,1,..., psac} faire
  f[n][E]=0
fait
pour k=n-1, n-2, ..., 1, 0 faire
  pour tout E dans {0,1,..., psac} faire
    f[k][E]:=max(f[k+1][E],f[k+1][E-p[k]]+u[k]).
  fait
fait
E=psac
pour k=0, 1, ..., n-1 faire
  si f[k][E]==f[k+1][E] alors
     l'objet k n'est pas mis dans le sac
  sinon
     l'objet k est mis dans le sac
     E-=p[k]
  finsi
fait
Dans la deuxième partie du calcul, on cherche à savoir comment on a obtenu l'utilité maximale f[k][E]. (En partant de k=0 et E=psac)
Si f[k][E]=f[k+1][E], on peut obtenir cette utilité sans prendre l'objet k. A l'itération suivante on va donc chercher comment on a obtenu f[k+1][E].
Si f[k][E]≠f[k+1][E], alors forcément f[k][E]=f[k+1][E-p[k]]+u[k]. On doit prendre l'objet k et à l'itération suivante on va donc chercher comment on a obtenu f[k+1][E-p[k]]. Il faut donc remplacer E par E-p[k], avant d'augmenter k de 1.
Cet algorithme est utilisé dans la fonction remplit du programme C suivant : 
#include<stdio.h>
int remplit(int n,int psac,int p[n],int u[n],int pris[n])
{ int E,k,a,f[n+1][psac+1];
  for(E=psac;E>=0;E--) f[n][E]=0;
  for(k=n-1 ;k>=0;k--)
  for(E=psac;E>=0;E--)
  { a=f[k+1][E];
    if(E>=p[k]) {int b=f[k+1][E-p[k]]+u[k]; if(b>a) a=b;}
    f[k][E]=a;
  }
  E=psac;
  for(k=0;k<n;k++) if(f[k][E]==f[k+1][E]) pris[k]=0;
                   else                   pris[k]=1, E-=p[k];
  return f[0][psac];
}
int main()
{ int p[]={3,7,8,9,6,7}, n=6, psac=20, pris[n],
      u[]={2,4,9,7,8,8}, uttot=remplit(n,psac,p,u,pris), k;
  printf("poids   ");    for(k=0;k<n;k++) printf("%3d",p[k]        ); printf("\n");
  printf("%6d  ",psac);  for(k=0;k<n;k++) printf("%3d",p[k]*pris[k]); printf("\n");
  printf("utilité ");    for(k=0;k<n;k++) printf("%3d",u[k]        ); printf("\n");
  printf("%6d  ",uttot); for(k=0;k<n;k++) printf("%3d",u[k]*pris[k]); printf("\n");
  return 0;
}
Ce programme écrit : 
poids     3  7  8  9  6  7
    20    0  7  0  0  6  7
utilité   2  4  9  7  8  8
    20    0  4  0  0  8  8
suivant précédent sommaire

vendredi 18 février 2005 : programmation dynamique : tâches à l'heure

On considère le problème d'ordonnancement suivant : On a n tâches à effectuer dans l'ordre 1, 2, ..., n sur une machine qui ne peut en faire qu'une à la fois. Chaque tâche i est caractérisée par plusieurs paramètres entiers : sa durée, notée pi, sa date d'échéance, notée di, une pénalité d'avance, notée ai, et une pénalité de retard, notée ri. on cherche à ordonnancer les tâches de sorte que la durée totale (c'est-à-dire la date de la fin de la tâche n) soit inférieure à une valeur T donnée, en minimisant la somme des pénalités des tâches calculées comm suit : En notant fi la date de fin de la tâche i (à définir), si fi<di alors la pénalité de i est ai, si fi=di alors la pénalité de i est 0, et si fi>di alors la pénalité de i est ri.
Définissons pour 1≤i≤n et t≤T, Fi(t) la somme minimale des pénalités d'un ordonnancement des tâches {1,...,i} de durée inférieure ou égale à t.
Question 1 : Montrer que si t<di, les ordonnancements où fi=t sont dominants pour le sous-problème dont la solution est Fi(t). De même, si t≥di et que l'ensemble des ordonnancements valides est non vide, il existe une solution optimale du sous-problème où soit fi=t soit fi=di.
Question 2 : Etablir et prouver l'équation de récurrence satisfaite par les Fi(t).
Que vaut F1(t) ?
Question 3 : En déduire un algorithme de programmation dynamique pour résoudre ce problème. Quelle est sa complexité ? Est-elle polynômiale ?

corrigé

Question 1 : Si t1<t2 alors toutes les solutions valides du sous-problème correspondant à Fi(t1), sont aussi des solutions valides du sous-problème correspondant à Fi(t2), car si les i premières tâches sont exécutées dans l'intervalle de temps [0,t1], elles le sont aussi dans l'intervalle de temps [0,t2] qui est plus grand. Cela montre que Fi(t1)≥Fi(t2). Autrement dit, la fonction Fi est décroissante.
Lorsque l'on calcule Fi(t) on peut choisir fi(≤t) puis remarquer que les i-1 premières tâches se répartissent de manière optimale dans l'intervalle de temps [0,fi-pi] et la somme de leur pénalité est donc Fi-1(fi-pi). Il faut y ajouter la pénalité éventuelle de la tâche i (qui dépend de la position de fi par rapport à di. Fi(t) s'obtient en prenant le plus petit de ces nombres.
Si t<di alors fi<di donc la tâche i est en avance et sa pénalité est ai. Donc Fi(t) = min{ai+Fi-1(fi-pi) | fi≤t} = ai+min{Fi-1(t') | t'≤t-pi} = ai+Fi-1(t-pi).
De même si t=di, un choix de fi<di donnera au mieux ai+Fi-1(di-pi-1) qui est plus grand que Fi-1(di-pi) que l'on obtient pour fi=di. Donc Fi(di)=Fi-1(di-pi).
Enfin si t>di, la tâche i peut être en avance ce qui donne au mieux Fi-1(di-pi-1)+ai ou à l'heure ce qui donne Fi-1(di-pi) (ce qui est mieux) ou en retard ce qui donne au mieux Fi-1(t-pi)+ri. Donc
Fi(t)=min(Fi-1(di-pi), Fi-1(t-pi)+ri).
Question 2 :
t ]-∞,0[[0,+∞[
F0(t)+∞ 0
Si d1<p1, F1 vaut :
t ]-∞,p1[[p1,+∞[
F1(t)+∞ r1
Si p1<d1, F1 vaut :
t]-∞,p1[[p1,d1[[d1,+∞[
F1(t)+∞a10
Question 3 : 
pour tout t dans {0,1,...,T} faire
    F[0,t]:=0
fait
pour i allant de 1 à n faire
   pour tout t dans {0,1,...,T} faire
      si t<d[i] alors
         F[i,t]:=F[i-1,t-p[i]]+a[i]
      sinon si t=d[i] alors
         F[i,t]:=F[i-1,t-p[i]]
      sinon 
         F[i,t]:=min(F[i-1,d[i]-p[i]],F[i-1,t-p[i]]+r[i])
      finsi
   fait
fait
t:=T
pour i allant de n à 1 en décroissant faire
   si t≥d[i] et F[i,t]=F[i-1,d[i]-p[i]] alors
      f[i]:=d[i]
   sinon
      f[i]:=t
   finsi
   t:=f[i]-p[i]
fait
Dans l'algorithme précédent on utilise la convention que F[i,t]=+∞ si t<0. En fait le tableau F contient des ∞ pour i<∑j=1ip[i], c'est-à-dire quand l'intervalle de temps [0,t] n'est pas assez long pour contenir toutes les tâches. Le temps de calcul de cet algorithme est Θ((T+1)(n+1)) il n'est donc pas polynômial en la taille des données. Mais on peut remarquer que la fonction Fi est constante sur des intervalles de la forme [xi,j,xi,j+1[ .Il suffit donc de garder les limites de ces intervalles et la valeur yi,j de la fonction sur chacun de ces intervalles.
On peut remarquer que l'ensemble Li des limites des intervalles où la fonction Fi est constante, se déduit de Li-1 en additionnant pi à chacun de ses éléments, et en insérant l'élément di.
Puisque L0={0} a un seul élément, on en déduit que Li a i+1 éléments. On en tire tire donc un algorithme en Θ(n2) 
L0:={(0,0)}
pour i allant de 1 à n faire
   Li:={}
   pour chaque (x,y)∈Li-1 faire
      si x+pi<di alors ajouter (x+pi,y+ai) à Li finsi
      si x+pi>di alors ajouter (x+pi,y+ri) à Li finsi
   fait
   chercher le plus grand x≤di tel que (x-pi,y)∈Li-1
   ajouter (di,y) dans Li s'il existe
   // Il reste à s'assurer que Fi est décroissante :
   tant qu'il existe (x,y) et (x',y') dans Li tels que x<x' et y≤y' faire
      enlever (x',y') de Li
   fait
fait   
chercher le plus grand t≤T tel que (t,y)∈Ln
S'il n'y en a pas c'est que T est trop petit. On n'a pas le temps de faire les n tâches.
y est la pénalité totale minimale.
pour i allant de n à 1 en décroissant faire
   fi:=t
   chercher le plus grand (x,y)∈Li-1 tel que x≤t-pi
   t:=x
fait
L'algorithme précédent est bien en O(n2) si on garde les éléments (x,y) de Li sous la forme d'une liste triée par x croissants (et donc y décroissants).
On peut transcrire tout cela en C : 
#include<stdio.h>
int resoutn2(int n,int d[n],int p[n],int a[n],int r[n],int T,int f[n])
{ struct{int x,y;} L[n+1][n+3], *u,*v;
  int i;
  u=L[0], u->x=u->y=0,  u[1].x=-1; // L0={(0,0)}  -1 indique la fin
  for(i=0;i<n;++i)
  { u=L[i], v=L[i+1];
    while(u->x>=0 && u->x+p[i]<=d[i]) v->x=u->x+p[i], v++->y=u++->y+a[i]; // en avance
    if(u>L[i])
    { if(v->x==d[i]) --v;
      v->x=d[i], v++->y=u[-1].y; // à l'heure
    }
    for(;u->x>=0;u++) v->x=u->x+p[i], v->y=u->y+r[i], v+=v==L[i+1] || v->y<v[-1].y; // en retard
    v->x=-1; // fin de la liste
  }
  for(u=L[n];u->x>=0 && u->x<=T;++u) ;
  if(u==L[n]) return -1; // T est trop petit pour faire toutes les tâches
  int res=u[-1].y;
  for(i=n;i-->0;)
  { v=--u;
    f[i]=v->x;
    for(u=L[i];u->x>=0 && u->x+p[i]<=v->x;++u) ;
  }
  return res;
}
int resoutnT(int n,int d[n],int p[n],int a[n],int r[n],int T,int f[n])
{ int F[n+1][T+1], t, i;
  for(t=0;t<=T;++t) F[0][t]=0;
  for(i=0;i< n;++i)
  { for(t=0;t<=T;++t) F[i+1][t]=t<p[i] || F[i][t-p[i]]<0 ? -1 : F[i][t-p[i]]+(t<d[i]?a:r)[i];
    if(d[i]<0 || d[i]>T || F[i+1][d[i]]<0) continue;
    int Fid=F[i][d[i]-p[i]];
    for(t=d[i];t<=T && F[i+1][t]>Fid;t++) F[i+1][t]=Fid;
  }
  t=T;
  for(i=n;i--;) f[i]=d[i]>=0 && d[i]<=T && F[i+1][t]==F[i+1][d[i]] ? d[i] : t, t=f[i]-p[i];
  return F[n][T];
}
void afft(int n,int *t) {for(;n;n--) printf("%6d",*t++); printf("\n"); }
int main()
{ int d[]={10, 5,20,23,40,30,35,45,60,53}, n=10, T=100, f[n], s[n],
      p[]={ 9, 7,10, 5, 1,12, 4, 5, 8, 6},
      a[]={ 1, 2, 1, 3, 2, 1, 3, 2, 2, 1},
      r[]={ 2, 3, 2, 1, 2, 3, 2, 1, 2, 3}, i, j;
  printf("d"), afft(n,d);
  printf("p"), afft(n,p);
  printf("a"), afft(n,a);
  printf("r"), afft(n,r);
  for(j=2;j--;)
  { printf("T=%d  %d\n",T,(j?resoutn2:resoutnT)(n,d,p,a,r,T,f));
    printf("f"), afft(n,f);
    for(i=0;i<n;++i) s[i]=f[i]<d[i]?a[i]:f[i]>d[i]?r[i]:0;
    printf("s"), afft(n,s);
  }
  return 0;
}
Le programme précédent écrit : 
d    10     5    20    23    40    30    35    45    60    53
p     9     7    10     5     1    12     4     5     8     6
a     1     2     1     3     2     1     3     2     2     1
r     2     3     2     1     2     3     2     1     2     3
T=100  17
f    10    17    27    32    40    52    56    61    69    75
s     0     3     2     1     0     3     2     1     2     3
T=100  17
f    10    24    34    39    40    77    81    86    94   100
s     0     3     2     1     0     3     2     1     2     3
Les deux procédures ne donnent pas la même solution optimale. Elles ont les mêmes pénalités, mais la procédure en O(n2) exécute les tâches le plus tôt possible, alors que la procédure en O(nT) les exécute le plus tard possible.
suivant précédent sommaire

vendredi 25 février 2005 :

programmation dynamique : mutation de l'ADN

On veut compter le nombre minimal de transformations à faire à une suite de nucléotides donnée pour arriver à une autre suite de nucléotides donnée. Les transformations autorisées sont la suppression ou l'insertion d'un nucléotide et le remplacement d'un nucléotide par un autre.
Si on note F[i][j] le nombre minimal de transformations qui permettent de passer des i premiers nucléotides de la première suite aux j premiers nucléotides de la deuxième suite on a :
F[0][j]=j et F[i][0]=i et F[i][j]=F[i-1][j-1] si ai=bj et sinon F[i][j]=1+min(F[i-1][j-1],F[i][j-1],F[i-1][j]).
En fait il est plus simple de démontrer que l'on a
F[i][j]=min((ai≠bj)+F[i-1][j-1] , 1+F[i][j-1] , 1+F[i-1][j]). Mais les deux formules donnent le même résultat car quand les deux suites se terminent par le même nucléotide, on peut toujours les apparier en restant optimal.
Cela donne le programme #include<stdio.h> #include<string.h> int mini(int a,int b) {return a>b?b:a;} int cmpADN(char *a,char *b,char *aa,char *bb) { int m=strlen(a), n=strlen(b), i, j, F[m+1][n+1]; for(i=0;i&lt;=m;++i) F[i][0]=i; for(j=0;j&lt;=n;++j) F[0][j]=j; for(i=0;i&lt;m;++i) for(j=0;j&lt;n;++j) F[i+1][j+1]=a[i]==b[j]?F[i][j]:1+mini(mini(F[i][j],F[i][j+1]),F[i+1][j]); // F[i+1][j+1]=mini((a[i]!=b[j])+F[i][j],1+mini(F[i][j],F[i][j+1])); aa[m]=bb[n]=0; for(i=m,j=n;i||j;) if(i && F[i][j]==1+F[i-1][j]) aa[--i]=' '; else if(j && F[i][j]==1+F[i][j-1]) bb[--j]=' '; else aa[--i]=b[--j], bb[j]=a[i]; return F[m][n]; } int main() { char *a="AGGCTAAACGTA", *b="GATTTAGCAGCCGT", aa[1+strlen(a)], bb[1+strlen(b)]; printf("Il y a %d mutations.\n",cmpADN(a,b,aa,bb)); printf("%s %s\n%s %s\n",a,b,aa,bb); return 0; } qui écrit 
Il y a 9 mutations.
AGGCTAAACGTA  GATTTAGCAGCCGT
 GATTTAACGT   GGCTAA  A C GT

séparation et évaluation

On considère une étape d'une méthode arborescente pour un problème de minimisation. A ce stade, l'arborescence possède 9 noeuds, qui ont été créés au fil du temps dans l'ordre S1, S2, ..., S9. Pour chaque noeud on indique son père, son évaluaton par défaut et son évaluation par excès, cette dernière étant fournie par un algorithme qui construit une solution appartenant au noeud. La valeur de la fonction objectif pour cette solution est l'évaluation par excès.
A chaque fois qu'une solution est construite, la meilleure solution est mise à jour si nécessaire.
noeud S1 S2 S3 S4 S5 S6 S7 S8 S9
père S1 S1 S1 S4 S4 S4 S5 S5
défaut220220320230230235230260250
excès350350350300300235240
1) Dessinez les étapes de la méthode arborescente jusqu'à cet état, en expliquant les différentes décisions de troncature, de mise à jour et de séparation qui ont pu être effectuées. Expliquez pourquoi à votre avis les noeuds S8 et S9 n'ont pas d'évaluation par excès.
2) Indiquer le prochain noeud à séparer selon la stratégie de parcours adoptée (largeur, profondeur ou meilleur d'abord).
1) Au départ on a S1 dont la valeur du minimum est comprise entre 220 et 350. La meilleure solution rencontrée est 350.
On sépare S1 en trois parties S2, S3 et S4 que l'on évalue. La valeur du minimum de S2 est comprise entre 220 et 350. La valeur du minimum de S3 est comprise entre 320 et 350. La valeur du minimum de S4 est comprise entre 230 et 300. La meilleure solution rencontrée est 300. On peut supprimer S3 puisque 320>300. Il reste donc S2 et S4 à étudier. On choisit S4.
On sépare S4 en trois parties S5, S6 et S7 que l'on évalue. La valeur du minimum de S5 est comprise entre 230 et 300. La valeur du minimum de S6 est 235. La valeur du minimum de S7 est comprise entre 230 et 240. La meilleure solution rencontrée est 235. On peut supprimer S6 puisqu'on sait que son minimum est 235 et on a mis de côté cette solution. Il reste donc S2, S5 et S7 à étudier. On choisit S7.
On sépare S7 en deux parties S8 et S9 que l'on évalue. La valeur du minimum de S8 est supérieure à 260 qui est plus grand que 235. On peut donc supprimer ce noeud. La valeur du minimum de S9 est supérieure à 250 qui est plus grand que 235. On peut donc supprimer ce noeud. Il reste donc S2 et S5 à étudier.
2) Si on choisit le plus profond des noeuds restants, ce sera S5. Si on choisit le moins profond ou le meilleur des noeuds restants, ce sera S2.
suivant précédent sommaire

vendredi 11 mars 2005 : séparation et évaluation

Ordonnancement sur une machine

Dans la suite de l'exercice, on s'intéresse à la définition d'une méthode arborescente pour résoudre le problème d'ordonnancement suivant :
On a n tâches. Chaque tâche i possède deux paramètres : sa durée pi, sa date d'échéance di. Ces tâches doivent être effectuées par une machine, sans temps d'arrêt. Etant donné un ordonnancement, si l'on note Ci la date de fin de la tâche i, le retard de i est noté Ti=max(Ci-di,0). On cherche un ordonnancement (c'est-à-dire une permutation σ des tâches) qui minimise la somme des retards.
Dans cet exercice on définit une méthode arborescente pour ce problème.
Un noeud S sera associé à une sous-suite de tâches JS=(i1,...,ir), et comprend l'ensemble des ordonnancements σ qui se terminent par la séquence JS : σ(n)=ir, ..., σ(n-r+1)=i1,
Notons PS=∑i∉JSpi.
1) Montrer que F(σ)=∑s=1r max(PS+∑k=1spik-dis,0) est une évaluation par défaut de la somme des retards au noeud S.
2) Indiquer un algorithme de votre choix permettant de calculer en chaque noeud une évaluation par excès.
3) Un noeud S est séparé en autant de fils qu'il y a de tâches j∉JS, correspondant à la sous-séquence j, i1, ..., ir. Appliquez la méthode arborescente à l'exemple suivant :
i 1234 5
pi4372 5
di563817
suivant précédent sommaire

mardi 15 mars 2005 : séparation et évaluation : sac à dos

exercice

Appliquez la méthode arborescente vue en cours au problème de sac à dos suivant : P=6
i 12 3456
ui5913353
pi12 4122
On précisera à chaque étape l'ordre dans lequel les noeuds sont visités, ainsi que l'objet sur lequel porte la séparation, qui doit être celui qui est éventuellement découpé dans la relaxation continue. 
#include<stdio.h>
#define n 6
int bavard=1;
typedef struct{int pris[n], defaut, exces, partiel;} noeud;
const int u[]={5,9,13,3,5,3}, psac=6,
          p[]={1,2, 4,1,2,2};
noeud meilleur;
void evaluation(noeud *a)
{ int po=0, ut=0, i;
  if(bavard) printf("evaluation de :");
  if(bavard) for(i=0;i<n;i++) if(a->pris[i]<2) printf(" %c%d","-+"[a->pris[i]],i);
  for(i=0;i<n;++i) if(a->pris[i]==1) po+=p[i], ut+=u[i];
  if(bavard) printf("  poids %d  utilite %d  ",po,ut);
  if(po>psac)                     // le sac déborde
  { if(bavard) printf("noeud vide\n");
    a->defaut=1, a->exces=0;
    return;
  }
  a->partiel=-1;
  for(i=0;i<n;i++) if(a->pris[i]<2) ; else                // objet déjà pris ou rejeté
  if(po+p[i]<=psac) po+=p[i], ut+=u[i], a->pris[i]=3; else// Il y a assez de place. On le prend.
  { a->pris[i]=2;                         // Il n'y a pas assez de place. On ne le prend pas.
    if(po<psac && a->partiel==-1) a->partiel=i, a->exces=ut+u[i]*(psac-po)/p[i]; // ou en partie
  }
  a->defaut=ut;
  if(a->partiel==-1) a->exces=ut;    // Le sac est plein, ou tous les objets sont dedans.
  if(ut>meilleur.defaut) meilleur=*a;// On a trouvé un meilleur remplissage.
  if(bavard) printf("defaut %d  exces %d  objet partiel %d\n",ut,a->exces,a->partiel);
}
int main()
{ noeud a, t[100];  // tableau des noeuds ouverts
  int nt=0, i,j;    // nt est le nombre de noeuds ouverts
  for(i=0;i<n;i++) meilleur.pris[i]=2;  // au début aucun objet n'est rejeté (0) ni pris (1)
  evaluation(&meilleur);
  if(meilleur.exces>meilleur.defaut) t[nt++]=meilleur; // il faut séparer la racine
  while(nt)                                            // tant qu'il y a des noeuds ouverts
  { for(i=j=0;i<nt;i++) if(t[i].exces>t[j].exces) j=i;
    a=t[j];                  // noeud ouvert qui a la plus grande évaluation par exces
    t[j]=t[--nt];            // on enlève t[j] du tableau t en comblant le trou avec le dernier
    if(a.exces<=meilleur.defaut) break; // On ne trouvera plus rien de mieux
    j=a.partiel;       // objet pris partiellement sur lequel on fait la séparation
    for(a.pris[j]=0;a.pris[j]<2;a.pris[j]++)// séparation en 2 parties, a.pris[a.partiel]=0 ou 1
     if(evaluation(&a), a.exces>meilleur.defaut) t[nt++]=a; // qu'on met éventuellement dans t
  }
  for(i=0;i<n;i++) meilleur.pris[i]&=1;  // 0->0 1->1 2->0 3->1
  bavard=1;
  evaluation(&meilleur);     // affichage de la meilleure solution
  return 0;
}
Le programme précédent fait l'exercice, en racontant toutes les évaluations qu'il fait (car bavard=1). Il écrit : 
evaluation de :  poids 0  utilite 0  defaut 22  exces 23  objet partiel 2
evaluation de : -2  poids 0  utilite 0  defaut 22  exces 22  objet partiel -1
evaluation de : +2  poids 4  utilite 13  defaut 21  exces 22  objet partiel 1
evaluation de : +0 +1 -2 +3 +4 -5  poids 6  utilite 22  defaut 22  exces 22  objet partiel -1
On évalue d'abord la racine, puis on la sépare en deux parties suivant qu'on prend l'objet 2 ou non. On évalue chacune de ces deux parties, et on s'arrête là, car on a trouvé un remplissage d'utilité 22 et on sait qu'on ne trouvera pas mieux.
Le programme précédent devrait évidemment commencer par trier les objets dans l'ordre des rapports utilité/poids décroissant et il devrait mettre les noeuds ouverts dans un tas, puisqu'on sépare toujours le noeud ouvert qui a la plus grande évaluation par excès.
suivant précédent sommaire

mardi 22 mars 2005 : programmation dynamique : voyageur de commerce

Un voyageur de commerce doit faire un circuit fermé passant une fois et une seule par chacune des villes 1, 2, ..., n en essayant de minimiser la longueur totale de son circuit. La distance d(i,j) de la ville i à la ville j est donnée pour tout couple de villes. On supposera que le voyageur de commerce part de la ville n et qu'il y revient après avoir visité toutes les autres villes. Si a∉I⊂{1,2,...,n-1} on note F(I,a) la longueur du plus petit chemin partant de la ville n, se terminant dans la ville a et passant par toutes les villes de I une fois est une seule. Ces nombres peuvent se calculer par récurrence en utilisant les formules :
F(∅,a)=d(n,a)
F(I,a)=minb∈IF(I-{b},b)+d(b,a)
La longueur du plus court circuit est F({1,2,...,n-1},n).
Cela donne le programme suivant : 
#include<stdio.h>
#define n 6
#define nn (1<<(n-1))
int mini(int a,int b){return a<b?a:b;}
const int maxint=~0u>>1u;
int vc(int d[n][n])
{ int F[nn][n], I, a, aa, b, bb, m;
  for(a=0;a<n;++a) F[0][a]=d[n-1][a];
  for(I=0;++I<nn;)
  for(a=0,aa=1;a<n;a++,aa*=2) if(aa&~I)
  { m=maxint;
    for(b=0,bb=1;bb<=I;b++,bb*=2) if(bb&I) m=mini(m,F[I-bb][b]+d[b][a]);
    F[I][a]=m;
    //printf("F[%d][%d]=%d ",I,a,m);
  }
  for(a=n-1,--I;I;a=b,I-=1<<a)
  { for(b=0,bb=1;;++b,bb*=2) if(I&bb && F[I][a]==F[I-bb][b]+d[b][a]) break;
    printf("d[%d][%d]=%d ",b,a,d[b][a]);
  }
  printf("d[%d][%d]=%d  %d\n",n-1,a,d[n-1][a],m);
  return m;
}
int main()
{ int d[n][n]={{},{4},{3,2},{5,7,2},{1,4,6,4},{4,2,6,7,8}}, i, j;
  for(i=n;i--;) for(j=i;j--;) d[j][i]=d[i][j];
  for(i=n;i--;) d[i][i]=0;
  vc(d);
  return 0;
}
qui écrit 
d[0][5]=4 d[4][0]=1 d[3][4]=4 d[2][3]=2 d[1][2]=2 d[5][1]=2  15
suivant précédent sommaire

vendredi 1er avril 2005 : méthode de Jackson

On a un ensemble de tâches que l'on doit exécuter l'une après l'autre, dans l'ordre que l'on veut. La tâche i ne peut commencer avant la date (de disponibilité) ri. Une fois qu'elle a commencé, elle dure un temps pi. Après ce temps on peut passer à une autre tâche, mais il faudra quand même attendre encore un temps (de latence) qi pour considérer qu'elle est vraiment finie.
On cherche dans quel ordre et à quelles dates il faut exécuter ces tâches, pour qu'elles soient toutes vraiment finies le plus tôt possible.
On fait l'évaluation et la séparation selon la méthode de Jackson.

évaluation par excès

L'évaluation par excès se fait en construisant un ordonnancement comme suit : 
t=0
tant qu'il reste des tâches à exécuter faire
  si à la date t aucune tâche restante n'est disponible alors
    avancer t à la première date de disponibilté d'une tâche restante
  fin si
  choisir la tâche i restante, disponible à la date t ayant le plus grand temps de latence
  exécuter cette tâche à la date t
  avancer t à la fin de cette tâche (t+=pi)
fait
Pour simplifier les explications suivantes, on va supposer que l'on renumérote les tâches dans l'ordre d'exécution que l'on vient de construire. (C'est ce qui est fait dans le programme suivant, puisqu'il permute les tâches dans le tableau des tâches en les mettant dans l'ordre d'exécution.) Notons di et fi les dates de début et de fin d'exécution de la tâche i. Soit k le numéro de la tâche pour lequel fi+qi est maximal. Autrement dit E=fk+qk est le temps total pris par notre ordonnancement. C'est l'évaluation par excès.

évaluation par défaut

Soit i+1, i+2, ..., k la plus longue suite possible de tâches (i est donc le plus petit possible) qui soient exécutées consécutivement sans pause et qui aient toutes des temps de latence supérieurs ou égaux à qk. L'évaluation par défaut est D=(mini<j≤krj)+pi+1+pi+2+...+pk+ (mini<j≤kqj). En fait mini<j≤kqj=qk.
Si la tâche i+1 n'est pas collée à la précédente, alors mini<j≤krj=ri+1=di+1 et l'évalutation par défaut D est égale à l'évaluation par excès E. Autrement dit l'évaluation est exacte et l'ordonnancement est optimal.
Dans le cas contraire, la tâche i qui est collée à la tâche i+1 est appelée tâche critique. Puisqu'aucune des tâches i+1 à k n'était disponible à la date di du début de la tâche i, on en déduit que mini<j≤krj>di=di+1-pi. On peut en tirer que E-D<pi.

séparation

Si dans un ordonnancement, la tâche i est effectuée entre la première et la dernière des tâches i+1 à k, alors cet ordonnancement aura un temps total supérieur à D+pi qui est strictement plus grand que E. Il ne sera donc pas optimal. Dans la recherche d'un ordonnancement optimal, on peut donc se contenter de regarder les ordonnancements dans lesquels la tâche i est faite avant toutes les tâches i+1 à k et ceux dans lesquels la tâche i est faite après toutes les tâches i+1 à k. La séparation se fait donc entre ces deux ensembles.
Pour imposer que la tâche i est faite après toutes les tâches i+1 à k, il suffit d'augmenter la date de disponibilité de i à ri:=(mini<j≤krj)+pi+1+pi+2+...+pk
Pour imposer que la tâche i est faite avant toutes les tâches i+1 à k, il suffit d'augmenter le temps de latence de i à qi:=pi+1+pi+2+...+pk+(mini<j≤kqj)

programme en C

Le programme suivant utilise l'algorithme précédent. Les notations sont légèrement différentes : ri devient av(i), pi devient pe(i), qi devient ap(i), di devient de(i), fi devient fi(i), D devient a->defaut et E devient a->exces. 
#include<stdio.h>
#define n 6
int bavard=1;
typedef struct{int avant,pendant,apres,debut,fin,numero;} tache;
typedef struct{tache ta[n]; int defaut, exces, crit, crav, crap;} noeud;
noeud meilleur=  {{{0,2,10},{1,3,14},{5,2,5},{6,4,9},{11,2,0},{12,4,4}}};
#define av(i) a->ta[i].avant
#define pe(i) a->ta[i].pendant
#define ap(i) a->ta[i].apres
#define de(i) a->ta[i].debut
#define fi(i) a->ta[i].fin
#define no(i) a->ta[i].numero+'A'
void evaluation(noeud *a)
{ int i,j,k,t;
  tache x;
  for(t=k=0;k<n;k++) // Ordonnancement des tâches ta[k] pour k=0, 1, ...  n-1. t=temps.
  { for(i=j=k;++i<n;) if(av(i)<av(j)) j=i;  // av(j)=min{av(i)|i>=k} 1ère tâche dispo.
    if(t<av(j)) t=av(j);                    // [t,av(j)] est une période d'inactivité.
    for(i=k;i<n;i++) if(av(i)<=t && ap(i)>ap(j)) j=i;//ap(j)=max{av(i)|i>=k & av(i)<=t}
    x=a->ta[k], a->ta[k]=a->ta[j], a->ta[j]=x; // On exécute la tâche j (au rang k)
    de(k)=t;                                   // à la date t.
    fi(k)=t+=pe(k);                            // Le temps s'écoule pendant la tâche.
  }
  for(k=i=0;++i<n;) if(fi(i)+ap(i)>fi(k)+ap(k)) k=i;//exces=fi(k)+ap(k)=max fi(i)+ap(i) 
  a->defaut=a->exces=fi(k)+ap(k); 
  for(i=j=k;i && fi(i-1)==de(i) && ap(--i)>=ap(k);) if(av(i)<av(j)) j=i;
  if(ap(i)<ap(k)) a->defaut+=av(j)-fi(i);//defaut=av(j)+pe(i+1)+pe(i+2)+...+pe(k)+ap(k)
  a->crit=i;
  a->crav=a->defaut-ap(k); // à mettre dans av(i) pour que i soit après i+1, ..., k
  a->crap=a->defaut-av(j); // à mettre dans ap(i) pour que i soit avant i+1, ..., k
  if(a->exces<meilleur.exces) meilleur=*a;
  if(!bavard) return;
  for(i=0;i<n;++i) printf("%c:%d+%d+%d:%d->%d ",no(i),av(i),pe(i),ap(i),de(i),fi(i));
  if(a->exces==a->defaut) printf("%d=%d\n"              ,a->exces,a->defaut);
  else                    printf("%d>%d  %c:%d+/+%d\n",a->exces,a->defaut,
    no(a->crit),a->crav,a->crap);
}
int main()
{ noeud a, b, t[100];  // tableau des noeuds ouverts
  int nt=0, i, j;      // nt est le nombre de noeuds ouverts
  for(i=n;i--;) meilleur.ta[i].numero=i;
  evaluation(&meilleur);
  if(meilleur.exces>meilleur.defaut) t[nt++]=meilleur; // il faut séparer la racine
  while(nt)                                        // tant qu'il y a des noeuds ouverts
  { for(i=j=0;i<nt;i++) if(t[i].defaut<t[j].defaut) j=i;
    a=b=t[j];        // noeud ouvert qui a la plus petite évaluation par défaut
    t[j]=t[--nt];    // on enlève t[j] du tableau t en comblant le trou avec le dernier
    if(a.defaut>=meilleur.exces) break; // On ne trouvera plus rien de mieux
    // séparation en 2 parties
    a.ta[a.crit].avant=a.crav; evaluation(&a); if(meilleur.exces>a.defaut) t[nt++]=a;
    b.ta[b.crit].apres=b.crap; evaluation(&b); if(meilleur.exces>b.defaut) t[nt++]=b;
  }
  bavard=1;
  evaluation(&meilleur);     // affichage de la meilleure solution
  return 0;
}
Ce programme écrit : 
A:0+2+10:0->2 B:1+3+14:2->5 C:5+2+5:5->7 D:6+4+9:7->11 E:11+2+0:11->13 F:12+4+4:13->17 21>20  E:16+/+8
A:0+2+10:0->2 B:1+3+14:2->5 C:5+2+5:5->7 D:6+4+9:7->11 F:12+4+4:12->16 E:16+2+0:16->18 20>19  C:10+/+13
A:0+2+10:0->2 B:1+3+14:2->5 C:5+2+5:5->7 D:6+4+9:7->11 E:11+2+8:11->13 F:12+4+4:13->17 21>20  C:12+/+14
A:0+2+10:0->2 B:1+3+14:2->5 D:6+4+9:6->10 C:10+2+5:10->12 F:12+4+4:12->16 E:16+2+0:16->18 20=20
A:0+2+10:0->2 B:1+3+14:2->5 C:5+2+13:5->7 D:6+4+9:7->11 F:12+4+4:12->16 E:16+2+0:16->18 20>19  A:6+/+18
B:1+3+14:1->4 C:5+2+13:5->7 A:6+2+10:7->9 D:6+4+9:9->13 F:12+4+4:13->17 E:16+2+0:17->19 22=22
A:0+2+18:0->2 B:1+3+14:2->5 C:5+2+13:5->7 D:6+4+9:7->11 F:12+4+4:12->16 E:16+2+0:16->18 20=20
A:0+2+10:0->2 B:1+3+14:2->5 C:5+2+5:5->7 D:6+4+9:7->11 F:12+4+4:12->16 E:16+2+0:16->18 20>19  C:10+/+13
Dessinez l'arbre correspondant.

autre exemple

Si on change les données du programme précédent en {{{0,3,10},{1,1,15},{3,1,17},{5,3,10},{5,1,2},{5,6,4}}}, il écrit : 
A:0+3+10:0->3 C:3+1+17:3->4 B:1+1+15:4->5 D:5+3+10:5->8 F:5+6+4:8->14 E:5+1+2:14->15 21=21
A:0+3+10:0->3 C:3+1+17:3->4 B:1+1+15:4->5 D:5+3+10:5->8 F:5+6+4:8->14 E:5+1+2:14->15 21=21
ce qui signifie que l'évaluation de la racine de l'arbre par la méthode de Jackson est exacte. On trouve tout de suite la solution optimale. Il n'y a pas besoin de séparation.
suivant précédent sommaire

vendredi 8 avril 2005 : contrôle

suivant précédent sommaire

vendredi 15 avril 2005 : algorithmes approchés : bin-packing

Remplir des boîtes de tailles 15, avec des objets de taille 1, 1, 1, 2, 2, 2, 4, 4, 4, 8, 8 et 8 selon les algorithmes vus en cours.

first fit

1+1+1+2+2+2+4=13
4+4=8
8
8
8

first fit, in decreasing order

8+4+2+1=15
8+4+2+1=15
8+4+2+1=15

Ce dernier algorithme est 3/2 approché

Un objet est dit petit si on peut en mettre trois comme lui dans une boîte. Sinon il est gros.
Cas où tous les objets sont gros
Une boîte ne peut pas contenir plus de deux gros objets. Supposons que les objets sont de taille e1≥e2≥e3≥e4≥... . Si par exemple le plus gros objet rentrant dans une boîte avec e1 est e8, mais que e1 est apparié avec e10 et que e8 est apparié avec e3, alors on peut remanier les boîtes e1+e10 et e3+e8, en les remplaçant par e1+e8 et e3+e10. La première boîte est un peu plus remplie, mais elle ne déborde pas. La deuxième boîte est un peu moins remplie, donc elle ne déborde pas.
Cela montre que dans un remplissage optimal on peut supposer que le plus gros objet est emballé avec le plus gros des autres qui tient avec lui dans une boite.
Le reste des boîtes forme un remplissage optimal et on peut donc lui imposer la même contrainte. Etc..
Cela montre que le remplissage obtenu par l'algorithme 
tant qu'il reste des objets à emballer faire
  On prend le plus gros des objets restants.
  On le met dans une nouvelle boîte.
  On lui rajoute le plus gros des objets restants qui tient avec lui dans la boîte, s'il y en a.
  On ferme la boîte.
fait
est optimal quand tous les objets sont gros. Or c'est justement le remplissage que donne la méthode "first fit, decreasing order".
Cas général où il y a des petits objets
Notre méthode commence par placer les gros objets dans des boîtes, de manière optimale si on oublie les petits objets. Puis on range les petits objets dans les espaces libres à coté des gros, ou dans de nouvelles boîtes si les autres sont bien remplies.
Si toutes les boîtes contiennent au moins un gros objet, alors le remplissage est optimal, puisqu'on ne peut de toute façon pas utiliser moins de boîtes pour ranger seulement les gros objets.
Si la dernière boîte remplie ne contient que des petits objets, alors aucun de ces petits objets ne rentrerait dans une des autres boîtes, qui sont donc toutes remplies plus qu'aux deux tiers. D'autre part la somme des contenus des deux dernières boîtes ne tient pas dans une seule boîte. Appelons n le nombre de boîtes utilisées et r1, r2, ..., rn les taux de remplissage des boîtes. On a r1>2/3, r2>2/3, ... rn-2>2/3, rn-1+rn>1. La somme des taux de remplissage est égale à la somme des tailles de tous les objets divisée par la contenance d'une boîte. C'est donc un minorant du nombre de boites de tout remplissage, et donc en particulier du nombre de boîtes n* du remplissage optimal. En additionnant les n-1 inégalités précédentes on obtient donc :
n*≥∑i=1nri>(n-2)(2/3)+1=(2n-1)/3
En multipliant par 3, on obtient 3n*>2n-1
Puisque les deux membres sont entiers, cela peut se réécrire 3n*≥2n ou encore n≤(3/2)n*.
On a donc bien montré que la méthode est 3/2 approchée.
Les calculs précédents supposent évidemment que n>1. Mais si n vaut 1, alors tous les objets tiennent dans une boîte et le remplissage est optimal.
suivant précédent sommaire

vendredi 22 avril 2005 :

suivant précédent sommaire

vendredi 13 mai 2005 :

suivant précédent sommaire

vendredi 20 mai 2005 :

précédent sommaire

vendredi 27 mai 2005 : sac à dos NP-complet

problème du sac à dos

On veut ranger dans un sac à dos de capacité P donnée des objets pris parmi une liste donnée. L'objet numéro i a un poids pi et une utilité ui données. La somme des poids des objets mis dans le sac à dos ne doit pas dépasser la capacité du sac, et la somme de leur utilité doit être la plus grande possible.
données :
P, n, p=(p1,p2,...,pn), u=(u1,u2,...,un).
résultat :
Sac(P,n,p,u) = max{∑i∈Jui | J⊂{1,2,...,n} et ∑i∈Jpi≤P}

problème de reconnaissance associé au problème du sac à dos

On a les même données que pour le problème du sac à dos, avec en plus une utilité minimale U. Le but maintenant n'est plus de remplir le sac à dos en maximisant l'utilité de son contenu, mais simplement de savoir si, oui ou non, il existe un remplissage du sac dont l'utilité totale est au moins égale à U.
données :
U, P, n, p=(p1,p2,...,pn), u=(u1,u2,...,un).
résultat :
Sacr(U,P,n,p,u) = ( ∃? J⊂{1,2,...,n}, ∑i∈Jui≥U et ∑i∈Jpi≤P )

relation entre les deux problèmes

Ces deux problèmes se ressemblent beaucoup. Si on a un algorithme efficace pour en résoudre un, on peut l'utiliser pour construire un algorithme efficace pour résoudre l'autre :
Si on a une procédure efficace pour calculer Sac(P,n,p,u) on peut l'utiliser dans 
fonction Sacr(U,P,n,p,u) : booleen
  return Sac(P,n,p,u)≤U
fin fonction
Cette procédure appelle une fois la procédure Sac.
Si on a une procédure efficace pour calculer Sacr(U,P,n,p,u) on peut l'utiliser dans 
fonction Sac(P,n,p,u) : entier
  a:=0
  b:=u1+u2+...+un
  tant que a≠b faire
    m:=⌊(a+b)/2⌋
    si Sacr(m+1,P,n,p,u) alors b:=m
                         sinon a:=m+1
  fait  
  return a
fin fonction
Cette procédure appelle Sacr un nombre de fois à peu près égal à log2(u1+u2+...+un) qui est un nombre plus petit que la taille des données du problème (qui est égale au nombre total de chiffres utilisés pour écrire les données).
Ainsi si on sait résoudre un des deux problèmes en un temps polynomial en la taille des données, on saura aussi le faire pour l'autre problème.
Le problème du sac à dos n'est pas NP, mais son problème de reconnaissance associé, l'est. En effet étant donnés U, P, n, p, u il est facile de vérifier qu'il existe un J tel que ∑i∈Jui≥U et ∑i∈Jpi≤P si on vous donne le J. Il n'y a que 2n additions et 2 comparaisons à faire.

problème 3-sat

Pour montrer que le problème de reconnaissance associé au problème du sac à dos est NP-complet, il faut d'abord démontrer qu'il est NP, ce que l'on vient de faire, et ensuite démontrer qu'il est plus difficile qu'un problème NP-complet connu, comme par exemple le problème 3-sat, de satisfiabilité des conjonctions de disjonctions de 3 littéraux. Un littéral est une variable booléenne (qui vaut donc vrai ou faux) ou sa négation. Disjonction veut dire "ou" logique. Conjonction veut dire "et" logique. Un prédicat, c'est-à-dire une expression logique, est satisfait s'il vaut vrai. Il est satisfiable si on peut le rendre vrai en donnant les bonnes valeurs aux variables booléennes dont il dépend. Par exemple :
R=(a∨b∨non c)∧(a∨non b∨d)∧(non a∨b∨c)∧(a∨b∨non d)∧(b∨c∨non d)
est satisfiable puisqu'il est satisfait par a=b=vrai.

3-sat est plus difficile que le sac à dos

Cela signifie que l'on peut coder une conjonction de disjonctions de 3 littéraux en une suite d'objets à mettre dans un sac à dos. On va le faire pour le prédicat R de l'exemple précédent. Pour simplifier, on supposera que U=P et que ∀i pi=ui. Le problème est donc de savoir s'il est possible de remplir le sac à dos à ras bord, avec une partie des objets dont on dispose. Il y a d'abord 8 objets (2 par variable) de poids :
a = 100000+1+10+1000
a' = 100000+100
b = 200000+1+100+1000+10000
b' = 200000+10
c = 400000+100+10000
c' = 400000+1
d = 800000+10
d' = 800000+1000+10000
puis puis 10 objets (2 par conjonction de 3 littéraux) de poids : (1, 1, 10, 10, 100, 100, 1000, 1000, 10000, 10000). La capacité du sac est 1533333. Les façons de remplir le sac à ras bord correspondent aux assignations des variables qui satisfont le prédicat R. On peut définir les variables xa, xb, xc et xd qui valent 1 si l'objet correspondant est dans le sac et 0 sinon. On peut aussi définir les variables ya, yb, yc et yd qui valent 1 ou 0, et qui valent 1 pour indiquer la présence dans le sac d'un des objets a', b', c' et d'. Enfin on peut définir les variables z1, z10, z100, z1000 et z10000, valant 0, 1 ou 2, qui comptent les objets de taille 1, 10, 100, 1000 et 10000 mis dans le sac.
"Le sac est plein" se traduit par
101011xa+211101xb+410100xc+800010xd+ 100100ya+200010yb+400001yc+811000yd+ z1+10z10+100z100+1000z1000+10000z10000 =1533333
Modulo 10 cela donne
xa+xb+yc+z1=3 (mod 10)
Puisque le membre gauche est compris entre 0 et 1+1+1+2=5, il vaut donc 3.
xa+xb+yc+z1=3
En soustrayant cela à l'équation de départ et en divisant par 10, on obtient
10101xa+21110xb+41010xc+80001xd+ 10010ya+20001yb+40000yc+81100yd+ z10+10z100+100z100+1000z10000 =153333
En recommençant cette opération modulo 10 on en déduit que
xa+xd+yb+z10=3
et
1010xa+2111xb+4101xc+8000xd+ 1001ya+2000yb+4000yc+8110yd+ z100+10z100+100z10000 =15333
On recommence ainsi plusieurs fois, ce qui nous donne
xb+xc+ya+z100=3
xa+xb+yd+z1000=3
xb+xc+yd+z10000=3
et
xa+2xb+4xc+8xd+ ya+2yb+4yc+8yd=15
En recommençant 3 fois la même opération modulo 2 (au lieu de modulo 10), on obtient
xa+ya=1
xb+yb=1
xc+yc=1
xd+yd=1
On voit donc que "le sac est plein" est équivalent au système :
xa+xb+yc+z1=3
xa+xd+yb+z10=3
xb+xc+ya+z100=3
xa+xb+yd+z1000=3
xb+xc+yd+z10000=3
xa+ya=1
xb+yb=1
xc+yc=1
xd+yd=1
La variable z1 n'intervient que dans une seule équation qui peut se réécrire
z1=3-xa-xb-yc
Le membre droit de cette équation vaut 0, 1, 2 ou 3 qui sont les trois valeurs possibles de z1 auxquelles on a ajouté 3. On peut donc éliminer cette équation du système à condition d'imposer que son membre doit ne vaut pas 3. Autrement dit on remplace cette équation par
xa+xb+yc>0
On peut de même élimininer les variables z10, z100, z1000 et z10000 du système qui devient :
xa+xb+yc>0
xa+xd+yb>0
xb+xc+ya>0
xa+xb+yd>0
xb+xc+yd>0
xa+ya=1
xb+yb=1
xc+yc=1
xd+yd=1
L'équation xa+ya=1 a deux solutions xa=1, ya=0 et xa=0, ya=1. Si on code a vrai par xa=1, ya=0 et a faux par xa=0, ya=1, et de même pour b, c et d. les cinq premières équations du système deviennent
a∨b∨non c
a∨d∨non b
b∨c∨non a
a∨b∨non d
b∨c∨non d
C'est le prédicat R. Donc tout remplissage du sac à dos correspond à une assignation des variables de R qui satisfait R.
De même pour un prédicat R' quelconque qui est une conjonction de disjonctions de 3 littéraux, on peut facilement construire une taille de sac à dos et une liste de taille d'objets, tels que R' est satisfiable si et seulement si on peut remplir le sac avec une partie des objets. Cela montre que le problème de reconnaissance associé au problème du sac à dos est plus difficile que le problème 3-sat, puisqu'il permet de le coder. Il est donc NP-complet.