• Aide pour la navigation
  • Page d'accueil
  • Mise à jour
  • A faire
  • Rechercher
  • Plan du site
• Contacts
  • Connexion
  • Livre d'or
  • Forum
  • Auteurs
  • Liens
• Grandes parties
  • International (en)
  • Maths
  • Smileys
  • Programmation
  • Nos Programmes
  • Nos jeux
  • Jeux vidéo
• Informatique
  • Nos smileys
  • Développement d'un solveur de programmes linéaires
  • Comment dialoguer avec son ordinateur
  • TIPE 2006-2007
  • Nos Programmes
  • Programmation

Développement d'un solveur de programmes linéaires

1. Introduction

Notre objectif est résoudre un programme mathématique $\left(Ex\right)$ de la forme générale suivante :
$\left(Ex\right)\{\begin{array}{cc}\mathrm{Min}& \sum _{i=1}^n{c_{i}x}_i+k\\ \text{s.c.}& \\ & \underset{j=1}{\overset{m}{\bigwedge }}\left((\sum _{i=1}^n{a}_{i,j}{x}_i+k_{1,j}){ℛ}_j(\sum _{i=1}^n{b}_{i,j}{x}_i+k_{2,j})\right)\\ & {\left(x_i\right)}_{i\in [1,n]}\in {\{0;1\}}^n\end{array}$ où $a_{i,j},b_{i,j},c_i,k,k_{i,j}\in \mathbb{Z}$ et ${ℛ}_j\in \{=;\le ;\ge \}$.

Pour cela, nous devrons définir des structures de données qui décrivent la forme générale du programme $\left(Ex\right)$ de façon simple et efficace. De plus, pour rendre plus aisée la manipulation du programme et de ses composantes, nous chercherons une forme canonique.

La spécification ne précise pas la manière dont l'utilisateur doit rentrer les paramètres du programme. Par conséquent, aucun module de saisie ne sera proposé et nous supposerons dans les fonctions que les paramètres respectent les pré-conditions décrites dans les interfaces. En particulier, nous ferons l'hypothèse que les paramètres passés dans les fonctions de résolution ont été mis sous forme canonique. Ceci évite un excès de vérifications, qui entrainerait un coût supplémentaire en complexité.

L'absence d'une interface de saisie rend toutefois difficile le test des fonctions. Nous utiliserons donc à cet effet des paramètres générés aléatoirement par Caml ainsi que le jeu de test proposé avec le sujet. La combinaison de ces deux méthodes permet de balayer à la fois les cas généraux et les cas particuliers.

Les résultats retournés par les fonctions sont susceptibles d'être des types sommes. Bien que Caml dispose d'une méthode générale pour afficher ces types, nous utiliserons des fonctions convertissant les données en chaines de caractères de façon à obtenir une meilleure lisibilité.

Dans un premier temps, nous étudierons les structures de données requises pour résoudre le problème et chercherons à les mettre sous forme canonique. Nous proposerons ensuite un algorithme rudimentaire pour poser les bases. Une troisième partie reformulera le problème dans un arbre binaire de recherche et présentera un algorithme amélioré. Deux améliorations seront ajoutées dans une partie consacrée à la recherche d'une solution optimale. Enfin, dans une dernière partie, nous étudierons plus précisément la structure des programmes et leur résolution par les algorithmes précédents.

L'étude des fonctions génératrice de variables aléatoires, de conversion en chaine et d'affichage, utilisés uniquement à titre d'assistance, ne sera pas effectuée.

2. Structures de données et mise sous forme standard

2.1. Structures de données

Si nous regardons à nouveau le programme $\left(Ex\right)$, nous voyons qu'il faut disposer de variables ${x=\left(x_i\right)}_{i\in [1,n]}\in {\{0;1\}}^n$, d'une fonction à minimiser $f:x\mapsto \sum _{i=1}^n{c}_i{x}_i+k$ et d'une liste de contraintes. Les variables pouvant être extraites de l'expression de la fonction $f$, nous obtenons la structure suivante pour un programme :

type programme =
  {
  fonction_a_minimiser : expression;
  contraintes : (contrainte list);
  };;

Puisque les ${ℛ}_j$ prennent les valeurs "égal", "inférieur", "supérieur" et que les contraintes s'appliquent à un couple d'expressions, nous sommes naturellement conduit à la structure suivante :

type contrainte = Inferieur of expression*expression
                | Superieur of expression*expression
                | Egal of expression*expression;;

Enfin, il reste à décrire les expressions de la forme $\sum _{i=1}^n{a_{i}x}_i+k$ avec $\forall i\in [1,n]c_i\in \mathbb{Z}$ et $k\in \mathbb{Z}$. Puisqu'il s'agit d'une somme de plusieurs termes, nous pouvons la coder sous la forme d'une liste de "litteraux", c'est-à-dire soit une constante, soit une variable avec un coefficient. Notons au passage que pour les contraintes aient un sens, les variables des expressions doivent être prises parmi celles de la fonction à minimiser, ce que nous supposerons par la suite.

type litteral = Variable of int * string | Constante of int;;
type expression = litteral list;;

Nous remarquons toutefois que par rapport à l'écriture initiale de $\left(Ex\right)$ cette définition sous-forme de liste autorise la répétition des $x_i$ ou de constantes, alors que celles-ci rendent plus difficile la manipulation sans pour autant généraliser le problème. Nous allons donc réaliser par la suite des fonctions simplifiant ces expressions. Nous chercherons aussi si d'autres transformations pourraient être appliquées pour simplifier l'écriture de $\left(Ex\right)$. Cette forme canonique du programme sera appelée Forme standard.

2.2. Forme standard d'un programme

Le programme étant composé d'expressions et d'une liste de contraintes, pour le mettre sous forme standard, il est naturel de créer des fonctions forme_standard_expression et forme_standard_contrainte qui applique des opérations sur chacune des composantes :

(* Interface forme_standard_programme
   type: programme -> programme
   arguments: un programme p
   pré: p est bien formé : les variables des contraintes
        sont parmi celles de la fonction à minimiser.
   post: (forme_standard_programme p) est un programme sous forme standard équivalent à p.
*)
let forme_standard_programme p =
    {
    fonction_a_minimiser = forme_standard_expression p.fonction_a_minimiser;
    contraintes = List.map forme_standard_contrainte p.contraintes;
    };;

2.3. Forme standard d'une contrainte

Une contrainte est composée de deux sous-expressions. Une première idée est donc d'appliquer la fonction forme_standard_expression à chacun de ses membres. En outre, une observation plus précise des littéraux montre que la gestion des variables va être plus complexe que celles des constantes : les premières nécessitent une évaluation alors que les dernières n'utilisent que des opérations élémentaires sur les entiers. Il serait donc pratique avant de mettre sous-forme standard les expressions d'envoyer toutes les variables d'un coté via une fonction envoyer_a_gauche de sorte que seule la gestion des variables du membre gauche sera nécessaire.

(* Interface envoyer_a_gauche
   type: litteral list -> litteral list -> litteral list * litteral list
   args: les membres gauche et droit d'une contrainte
   post: le couple des deux membres après que les variables du membre
         droit sont envoyés à gauche. *)

let forme_standard_contrainte contrainte =
  let (e2, f2) = match contrainte with
    Superieur (e1, f1) | Inferieur (e1, f1) | Egal (e1, f1) -> envoyer_a_gauche e1 f1
  in
    (forme_standard_expression e2), (forme_standard_expression f2);;

Comme l'indique la spécification, les variables avec un coefficient nul sont inutiles et peuvent être supprimées via une fonction supprimer_variables_nulles. Au passage, notons que le membre droit a pu être transformé en une liste vide si la forme standard de l'expression f2 n'a pas de constante. Mais pour des raisons d'uniformité algorithmique, il est préférable de toujours conserver un singleton [Constante c].

(* Interface supprimer_variables_nulles
   type: litteral list -> litteral list
   args: une expression expr
   post: expr sans les litteraux correspondant à des variables
         à coefficient nul.
*)

La spécification mentionne aussi une simplification supplémentaire, consistant à ne conserver que des symboles d'égalité et d'infériorité pour les ${ℛ}_j$. Ceci est possible puisque qu'une contrainte de supériorité peut être transformée en une contrainte d'infériorité en prenant l'opposée de chaque membre. Ceci nécessité une fonction supplémentaire change_signe qui change le signe d'une expression.

(* Interface change_signe
   type: litteral list -> litteral list
   arguments: expr
   post: retourne l'expression opposée *)

Finalement, en reprenant les différentes étapes, il vient :

(* Interface forme_standard_contrainte
   type:  contrainte -> contrainte
   arg: contrainte
   post: la contrainte sous forme standard :
         - membre de droit de la forme [Constante c] (donc sous forme standard)
         - membre gauche sous forme standard
         - pas de variables à coefficient nul
         - seulement des contraintes d'égalité ou d'infériorité
*)
let forme_standard_contrainte contrainte =
  let (e2, f2) = match contrainte with
    Superieur (e1, f1) | Inferieur (e1, f1) | Egal (e1, f1) -> envoyer_a_gauche e1 f1
  in
    let (e3, f3) = (forme_standard_expression e2), (forme_standard_expression f2)
    in
      let (e4, f4) = (supprimer_variables_nulles e3), (if f3 = [] then [Constante 0] else f3)
      in
        match contrainte with
          | Egal _ -> Egal (e4, f4)
          | Inferieur _ -> Inferieur (e4, f4)
          | Superieur _ -> Inferieur (change_signe e4, change_signe f4);;

2.4. Forme standard d'une expression

Notre but est de transformer une expression donnée en une expression équivalente sans doublons. L'idée est de regarder un littéral et de chercher dans les autres litteraux la présence d'un littéral similaire, c'est-à-dire de même type (Constante ou Variable) et de même nom s'il s'agit d'une variable. Si nous en trouvons, nous les regroupons. Cette opération passera donc par une fonction ajouter_litteral :

(* Interface ajouter_litteral (première version)
   type: litteral -> litteral list -> litteral list
   arguments: litt, expr
   post: une expression codant "expr + litt" :
        - Si litt est une variable déjà présente dans expr, on remplace son coefficient par la somme des coefficients.
        - Si litt est une constante et expr en contient déjà une, on la remplace par la somme des constantes.
        - Sinon, on place litt à la fin de l'expression.
*)

Nous pouvons ensuite appliquer un algorithme similaire à celui du tri par insertion : appliquer récursivement ajouter_litteral à la tête et la queue d'une liste. Il est aussi possible d'utiliser une fonction terminale :

(* Interface forme_standard_expression
   type: litteral list -> litteral list 
   arguments: expr
   post: une expression équivalente à expr, avec au plus une constante et des variables deux à deux distinctes. *)
let forme_standard_expression expr =

  let rec aux (ancienne, nouvelle) = match ancienne with
    | [] -> ([], nouvelle)
    | litt::q -> aux (q, (ajouter_litteral litt nouvelle))
  in

   snd (aux (expr, []));;

Remarquons que l'utilisation d'un accumulateur présente le désavantage "d'inverser" l'expression, ce qui peut être indésirable si l'expression a été initialement triée. En réalité, ce problème peut facilement être contourné en modifiant l'interface de ajouter_litteral, de sorte que l'expression reste toujours triée (ceci est possible car l'accumulateur est initialement la liste vide, qui est triée) :

(* Interface ajouter_litteral
   type: litteral -> litteral list -> litteral list
   arguments: litt, expr
   pré: l'expression est "triée" : constante puis variable selon nom croissant.
   post: une expression "triée" codant "expr + litt" :
        - Si litt est une variable déjà présente dans expr, on remplace son coefficient par la somme des coefficients.
        - Si litt est une constante et expr en contient déjà une, on la remplace par la somme des constantes.
        - Sinon, on place litt dans l'expression.*)

Que ce soit l'interface initiale ou la nouvelle interface, si $n$ est la taille de l'expression, ajouter_litteral s'appelle récursivement $O\left(n\right)$ fois. L'interface initiale comporte un nombre fini de filtrage / comparaisons et la nouvelle interface n'en rajoute qu'un nombre fini, donc la complexité dans le pire des cas de ajouter_litteral est toujours en $O\left(n\right)$. Nous obtenons donc le bénéfice d'avoir une expression triée - qui ne contredit pas la spécification de la forme standard d'une expression - sans pour autant ajouter en complexité. En fait, les complexités en moyenne ou dans le meilleur des cas peuvent même diminuer car les appels de ajouter_litteral, en plus de s'arrêter lorsqu'un litteral similaire est trouvé, s'arrêtent lorsque les éléments de la queue sont "plus grands" que le littéral à insérer.

3. Algorithme de recherche élémentaire

A partir de maintenant, nous nous intéressons à des données mises sous forme standard. Nous cherchons à résoudre un système de la forme suivante :

$\left(Ex\right)\{\begin{array}{cc}\mathrm{Min}& \sum _{i=1}^n{c_{i}x}_i+k\\ \text{s.c.}& \\ & \underset{j=1}{\overset{m}{\bigwedge }}\left((\sum _{i=1}^n{d}_i{x}_i+k_{1,j}){ℛ}_j{k}_{2,j}\right)\\ & {\left(x_i\right)}_{i\in [1,n]}\in {\{0;1\}}^n\end{array}$avec ${ℛ}_j\in \{=;\le \}$

Un premier algorithme consiste à parcourir les $2^n$ possibilités pour les valeurs des ${\left(x_i\right)}_{i\in [1,n]}$ en fixant les valeurs des variables à 0 ou 1 et à récupérer les solutions. Il va donc falloir dans un premier temps définir la manière dont sont affectées les variables.

3.1. Environnement

Un environnement est une structure associant à chaque variable une valeur. Cela peut se faire par le biais d'une liste de couples (nom, valeur) :

type environnement = (string * int) list;;

Étant donné un nom, il faut pouvoir récupérer la valeur associée, ce qui se fera par la fonction classique associer. Celle-ci peut échouer si le nom de la variable n'existe pas dans l'environnement. Comme l'algorithme de recherche va tenter de récupérer la valeur d'une variable et lui en affecter une en cas d'échec, il est utile de définir une exception :

exception ValeurIndefinie;;

(* Interface associer
   type: ('a * 'b) list -> 'a -> 'b
   arguments: env, clé
   pré: la clé est dans l'environnement
   post: la valeur associée à la clé si elle est trouvée
   raises: ValeurIndefinie
*)

3.2. Structure de l'algorithme de recherche

Maintenant que nous disposons de la structure d'environnement, nous pouvons donner une description plus précise de l'algorithme de recherche. Celui-ci appelle une fonction récursive gérant trois paramètres : l'environnement courant, la liste des variables libres et la liste des solutions trouvées. Initialement, ces variables sont respectivement un environnement vide, la liste des variables de la fonctions à minimiser et une liste vide.

A chaque appel, on réalise l'opération suivante :

• Si la liste des variables libres est vide, il n'y a plus de variable à fixer. Nous vérifions alors que toutes les contraintes sont satisfaites et si tel est le cas, ajoutons l'environnement courant à la liste des solutions.
• Sinon, on recherche de nouvelles solutions en fixant la variable libre suivante à 0 puis à 1.

La liste des variables libres diminuant d'une unité à chaque appel récursif, la fonction termine. De plus, l'algorithme vérifie clairement tous les environnements possibles pour les variables de la fonction à minimiser.

(* Interface recherche
   type: programme -> environnement list
   arguments: prog
   pré: le programme est sous forme standard
   post: la liste des solutions
*)

let recherche_0 prog =

  let rec recherche env variables_libres solutions =
    match variables_libres with
      [] -> if toutes_satisfaites env prog.contraintes then
                env::solutions
              else
                solutions

      | nom::q ->
        let solutions2 = recherche ((nom, 0)::env) q solutions
          in             recherche ((nom, 1)::env) q solutions2

  in
    recherche [] (liste_variables prog) [];;

La fonction liste_variables récupère les variables de la fonction à minimiser. Pour des raisons de commodité, l'algorithme de recherche fixe les valeurs des variables selon l'ordre lexicographique, ce qui nécessite une condition de tri supplémentaire :

(* Interface liste_variable
   type: programme -> string list
   arguments: prog
   pré: le programme est sous forme standard (donc l'expression de la fonction à minimiser est triée)
   post: liste des variables de la fonction à minimiser du programme, selon l'ordre lexicographique.
*)

3.3. Satisfaction des contraintes

L'interface toutes_satisfaites précédemment utilisée vérifie si toutes les contraintes sont satisfaites, ce qui correspond à une structure en List.fold_left :

(* Interface toutes_satisfaites
   type: (string * int) list -> contrainte list -> bool
   arguments: env, une liste de contraintes
   pré: les variables des contraintes sont toutes liées
   post: true ssi toutes les contraintes sont satisfaites
*) 
let toutes_satisfaites env =
    List.fold_left
      (function e -> function ctr -> e && (est_satisfaite_contrainte env ctr))
      true;;

Pour l'interface est_satisfaite_contrainte, il suffit de retranscrire les conditions. Nous voyons alors apparaître le besoin d'une fonction évaluant une expression :

(* Interface est_satisfaite_contrainte
   type: (string * int) list -> contrainte -> bool
   arguments: un environnement et une contrainte
   pré: les variables de la contrainte ont une valeur dans l'environnement
   post: true ssi la contrainte est satisfaite dans l'environnement
   raises: ValeurIndefinie
*)
let est_satisfaite_contrainte env = function
    Egal(e1, e2) -> (evaluer_expression env e1) = (evaluer_expression env e2)
  | Inferieur(e1, e2) -> (evaluer_expression env e1) <= (evaluer_expression env e2)
  | Superieur(e1, e2) -> (evaluer_expression env e1) >= (evaluer_expression env e2);;

3.4. Évaluer une expression

L'évaluation d'une expression consiste à effectuer la somme de l'evaluation de chacun des littéraux de la liste, ce qui nous ramène à nouveau à un List.fold_left :

(* Interface evaluer_expression
   type: (string * int) list -> litteral list -> int
   arguments: un environnement et une expression.
   pré: L'expression ne contient pas de valeur indéfinie.
   post: l'évaluation de l'expression selon l'environnement.
   raises: ValeurIndefinie
*)

Pour la fonction evaluer_litteral, il s'agit tout simplement d'un filtrage : si c'est une constante on renvoie sa valeur, si c'est une variable sa valeur dans l'environnement courant.

(* Interface evaluer_litteral
   type: (string * int) list -> litteral -> int
   arguments: un environnement et un litteral
   pré: le litteral est une constante ou une variable avec une valeur
   post: la valeur du litteral
   raises: ValeurIndefinie
*)

3.5. Discussion sur la complexité

Quelle que soit la complexité étudiée (dans le meilleur des cas, en moyenne, dans le pire des cas) la recherche des solutions utilisera $2^{n+1}-1$ appels récursifs, si $n$ est le nombre de variables dans la fonction à minimiser, d'où une complexité exponentielle, ce qui n'est pas très interessant lorsque l'on a à travailler sur un grand nombre de paramètres. Nous allons donc essayer d'améliorer l'algorithme en diminuant le nombre d'appels récursifs.

4. Recherche des solutions dans un arbre binaire

4.1. Reformulation du problème à l'aide d'un arbre binaire

L'algorithme de recherche de solution précédent peut être vu comme un parcours dans un arbre binaire où les noeuds correspondent à des environnements. A la racine, toutes les variables sont libres et aux feuilles toutes les variables sont liées.

Cette formulation donne un meilleur aperçu de ce qui se passe et va nous permettre d'améliorer l'algorithme en ne développant pas les noeuds inutiles. En effet, il se peut qu'après avoir fixé un certain nombre de variables, les contraintes ne peuvent plus être satisfaites, quelles que soient les valeurs données aux variables libres. Dans ce cas, il n'est pas nécessaire de continuer le parcours plus en profondeur. Ci-dessous, un arbre de recherche pour deux variables x et y :

L'arbre binaire sera donc représenté par le type somme usuel, avec une variable de type environnement pour étiquette de chaque noeud.

type abr = Vide | Noeud of abr * environnement * abr;;

4.2. Structure de l'algorithme de recherche

Nous apportons quelques modifications dans l'interface. Tout d'abord, en plus de renvoyer la liste des solutions, l'algorithme retourne le nombre de noeuds développés ainsi que l'arbre développé. Bien que le premier puisse être déduite du second, nous réaliserons le calcul simultanément pour des raisons d'efficacité algorithmique.

(* Interface recherche_1
   type: programme -> environnement list * int * abr
   arguments: prog
   pré: le programme est sous forme standard
   post: (liste des solutions du programme, nombre de noeuds développés, arbre développé)

Évidemment ces nouvelles variables ont peu d'intérêt si on développe tous les noeuds comme précédemment : nous ne développerons donc le noeud que lorsque les contraintes sont satisfiables. Le corps de la fonction reste donc le même, sauf que l'on ajoute les nouvelles variables ainsi que la condition sur le développement des noeuds.

Pour construire l'arbre et compter le nombre de noeuds, il faut savoir ce qu'on appel un noeud développé. On prend la définition suivante, qui restera valable pour les autres algorithmes :

• Soit c'est une feuille que l'on mémorise (ici, une solution)
• Soit c'est un noeud interne dont on développe au moins l'un des fils (ici, tel que les contraintes sont satisfiables)

Par exemple dans l'arbre de la figure 1, Les noeuds internes "x, y", "x = 0, y" et "x = 1, y" ont des contraintes satisfiables et la feuille "x = 1, y = 1" est une solution.

4.3. Satisfiabilité d'un programme

Étant donné une contrainte la forme $\left((\sum _{i=1}^n{d}_i{x}_i+k_{1,j}){ℛ}_j{k}_{2,j}\right)$ avec ${ℛ}_j\in \{=;\le \}$ (i.e. sous forme standard), avec un certain nombre de variables liées, il est possible de savoir que la contrainte n'est pas satisfiable si en essayant toutes les valeurs des variables libres, $(\sum _{i=1}^n{d}_i{x}_i+k_{1,j})>k_{2,j}$. Nous dirons alors que la contrainte est non satisfiable dans l'environnement courant. Dans le cas contraire nous parlerons d'une contrainte satisfiable, bien que l'on ne soit pas sûr qu'il existe un environnement la satisfaisant. De la même façon, nous parlerons de programme satisfiable dans un environnement si toutes les contraintes sont satisfiables dans cet environnement. On arrive donc naturellement aux deux fonctions suivantes :

(* Interface est_satisfiable_contrainte
   type: (string * int) list -> contrainte -> bool
   arguments: un environnement env, une contrainte
   pré: la contrainte est sous forme standard
   post: true ssi la borne inférieur du membre gauche est inférieur à la constante du membre droit
   raises: Failure "est_satisfiable_contrainte : la contrainte n'est pas sous forme standard."
*)
let est_satisfiable_contrainte env = function
    Egal (expr, [Constante c]) | Inferieur (expr, [Constante c]) ->  (evaluer_borne_inferieur env expr) <= c
  | _ -> failwith "est_satisfiable_contrainte : la contrainte n'est pas sous forme standard.";;

(* Interface est_satisfiable_programme
   type: programme -> (string * int) list -> bool
   arguments: prog, env
   pré: le programme est sous forme standard
   post: true ssi toutes les contraintes sont satisfiables
   *)
let est_satisfiable_programme prog env =
  List.fold_right (function x -> function y -> y && (est_satisfiable_contrainte env x)) prog.contraintes true;;

Nous voyons apparaitre une fonction evaluer_borne_inferieur qui calcule la borne inférieure d'une expression selon l'environnement courant. Si cette borne inférieur est strictement supérieur à la constante du membre droit, alors toutes les évaluations du membre gauche selon un environnement "complété" le sont aussi, ce qui nous ramène à notre définition de non satisfiabilité.

4.4. Évaluation de la borne inférieur

Le fait que le programme soit linéaire permet de déduire que :

$inf(\sum _{i=1}^n{d}_i{x}_i+k_{1,j})=(\sum _{x_i\text{liée}}{d}_i{x}_i+k_{1,j})+\sum _{x_i\text{libre}}inf{d}_i{x}_i$

En outre, comme les $x_i$ ne prennent pour valeur que 0 et 1, il suffit de choisir la valeur selon le signe du coefficient $d_i$ de façon à minimiser le résultat :

$inf{d}_i{x}_i=\{\begin{array}{c}{d}_i\times 0=0 \mathrm{si} d_i\ge 0\\ d_i\times 1=-\mid d_i\mid \text{sinon}\end{array}$

Finalement, il devient très facile de calculer la borne inférieur d'une expression en $O\left(\text{n}\right)$ opérations ($n$ étant le nombre de littéraux), en utilisant un fold_left :

(* Interface evaluer_borne_inferieur
   type: (string * int) list -> litteral list -> int
   arguments: un environnement env, une expression expr
   pré: expr est sous forme standard
   post: la borne inférieur de l'expression en fonction de l'environnement courant
*)
let evaluer_borne_inferieur env =
  let aux litt = match litt with
      Variable(coeff,nom) ->
        (try evaluer_litteral env litt with ValeurIndefinie -> if coeff < 0 then coeff else 0)
    | _ -> evaluer_litteral env litt 

  in 
    List.fold_left (function n -> function litt -> aux litt + n) 0;;

4.5. Discussion sur la complexité

Si nous nous intéressons au nombre de noeuds développés, la complexité dans le pire des cas reste la même. Lorsqu'il y a beaucoup de contraintes et beaucoup de variables, il est plus rare d'avoir à développé tous les noeuds. Si on s'intéresse aux sous-fonctions, la fonction toutes_satisfaites a une plus grande compléxité (nombre de contraintes multiplié par longueur des expressions donc du $O\left(n^2\right)$) que evaluer_borne_inferieur. Ainsi, même si le nouvel algorithme ajoute un calcul de borne inférieur à chaque noeud, il diminue le nombre de feuilles auxquelles on doit vérifier les contraintes.

La Figure 2 montre l'arbre de recherche de l'exemple 5 du jeu de test. L'exemple ne comporte que 2 contraintes et 3 variables ce qui ne permet pas réellement de pouvoir comparer les complexités.

$\left(\mathrm{Ex}5\right)\{\begin{array}{cc}\mathrm{Min}& -x-2y-z\\ \text{s.c.}& \\ & y+z=1\\ & 2x+3y+z\le 4\\ & \left(x,y,z\right)\in {\{0;1\}}^3\end{array}$

5. Recherche d'une solution optimale

Les algorithmes précédents recherchaient toutes les solutions. Toutefois dans la pratique on s'intéresse à des problèmes d'optimisation où nous avons simplement besoin de trouver une bonne solution. Nous allons par conséquent modifier l'interface pour qu'elle ne retourne pas toutes les solutions, mais une solution optimale.

5.1. Structure de l'algorithme de recherche

Outre le nombre de noeuds développés et l'arbre développé, il faut donc une solution optimale comme résultat. Pour les résultats intermédiaires, il est aussi intéressant d'avoir la valeur optimale obtenue pour éviter d'avoir à la re-calculer à chaque fois. Notons qu'il est possible qu'aucune solution n'aie été trouvée et donc que la valeur optimale soit indéfinie. Il est donc pratique de définir le type suivant :

(* Type résultat, utilisés pour les recherche des questions 6 et 7.
  - Rien
  - Solution (solution_optimale, valeur_minimale_de_la_fonction_a_minimiser) *)
type resultat = Rien | Solution of environnement*int;;

La nouvelle interface pour l'algorithme de recherche est donc :

(* Interface recherche
   type: programme -> resultat * int * abr
   arguments: prog
   pré: le programme est sous forme standard
   post:
     Un triplet (resultat, nombre_noeuds_développés, arbre développé) où le résultat est
       - Rien si aucune solution n'est trouvée
       - Solution(une solution optimale, valeur optimale de la fonction à minimiser) sinon
*)

5.2. Amélioration des développements

Nous pouvons effecter deux améliorations au développement des noeuds. La première se fonde sur le fait que nous cherchons une solution optimale i.e. telle que la valeur de la fonction à minimiser soit minimale. Ainsi, si la borne inférieur de la fonction à minimiser dans le noeud courant est supérieur ou égale à sa valeur pour une solution déjà trouvée, il est inutile de développer le noeud. Notons que ce controle ne rajoute qu'un calcul de borne inférieur par noeud donc n'augmente pas la complexité (tout se passe comme si on ajoutait simplement une contrainte au programme).

La deuxième amélioration se base sur la remarque suivante : il est toujours préférable de commencer par les feuilles possédant de bonnes solutions, de façon à ce que la valeur optimale mémorisée soit la plus faible et donc que le maximum de noeuds soient ignorés. Dans le cas où le programme est satisfait en chaque feuille, il suffit de parcourir les noeuds pour lesquels la borne inférieur de la fonction à minimiser est minimale. Ceci n'est pas vrai dans le cas général, mais nous conserverons toutefois ce principe : on cherche les meilleures solutions là où la fonction à minimiser peut être la plus faible.

A titre de contre-exemple, soient $a,b\in \mathbb{Z}$ tels que $a<0,b>0$ et $\mid a\mid <\mid b\mid$. Considérons le programme suivant :

$\left(Ex\right)\{\begin{array}{cc}\mathrm{Min}& ax+by\\ \text{s.c.}& \\ & x=y\\ & \left(x,y\right)\in {\{0;1\}}^2\end{array}$

Les valeurs de la fonction à minimiser pour les feuilles $\left(0,0\right),\left(0,1\right),\left(1,0\right),\left(1,1\right)$ sont respectivement $0,b>0,a<0$ et $a+b>0$. La solution optimale est $\left(0,0\right)$ qui est dans la descendance gauche, mais la plus petite borne inférieure est $a<0$ qui est à droite. Le cas $a=-1$ et $b=2$ donne 4 noeuds développés pour l'algorithme avec la première amélioration seulement et 5 pour l'algorithme avec les deux améliorations (autant que l'algorithme initial).

    let exemple7 =
            {fonction_a_minimiser =
              [Variable (-1, "x"); Variable (2, "y")];
             contraintes = [Egal ([Variable (1, "x"); Variable (-1, "y")],[Constante 0]) ]
              };;

    afficher_programme exemple7;;
    afficher_resultat_recherche 0 exemple7;;
(*
{ Min   -x + 2*y
{ s.c.
{       x - y = 0
- : unit = ()

***** Algorithme 1 - Résultats *****

Nombre de noeuds développés : 5

Liste des solutions :
x = 1; y = 1; 
x = 0; y = 0; 

Arbre développé :

                --(11)--<

        --(1)--<

--()--<

        --(0)--<

                --(00)--<

************************************

***** Algorithme 2 - Résultats *****

Nombre de noeuds développés : 4

Une solution optimale :
x = 0; y = 0; 

Arbre développé :

        --(1)--<

--()--<

        --(0)--<

                --(00)--<

************************************

***** Algorithme 3 - Résultats *****

Nombre de noeuds développés : 5

Une solution optimale :
x = 0; y = 0; 

Arbre développé :

                --(11)--<

        --(1)--<

--()--<

        --(0)--<

                --(00)--<

************************************
*)

Toutefois, les exemples du jeu de test montre que le nombre de noeuds tend à diminuer avec cette deuxième amélioration :

(****************************************************************)
(*********** Résultats du jeu de tests **************************)
(****************************************************************)

    let exemple1 =
            {fonction_a_minimiser =
              [Variable (2, "x"); Variable (1, "y")];
             contraintes =
              [Inferieur ([Variable (1, "x"); Variable (1, "y")],
               [Constante (-2)])]};;
 
    afficher_programme exemple1;;
    afficher_resultat_recherche 0 exemple1;;

(*

{ Min   2*x + y
{ s.c.
{       x + y <= -2

***** Algorithme 1 - Résultats *****

Nombre de noeuds développés : 0

Pas de solution

Arbre développé :

************************************

***** Algorithme 2 - Résultats *****

Nombre de noeuds développés : 0

Pas de solution

Arbre développé :

************************************

***** Algorithme 3 - Résultats *****

Nombre de noeuds développés : 0

Pas de solution

Arbre développé :

************************************
*)

    let exemple2 =
            {fonction_a_minimiser =
              [Variable (2, "x"); Variable (-1, "y")];
             contraintes =
              [Inferieur ([Variable (1, "x"); Variable (1, "y")],
                [Constante 1])]};;

    afficher_programme exemple2;;
    afficher_resultat_recherche 0 exemple2;;

(*
{ Min   2*x - y
{ s.c.
{       x + y <= 1

***** Algorithme 1 - Résultats *****

Nombre de noeuds développés : 6

Liste des solutions :
x = 1; y = 0; 
x = 0; y = 1; 
x = 0; y = 0; 

Arbre développé :

        --(1)--<

                --(10)--<

--()--<

                --(01)--<

        --(0)--<

                --(00)--<

************************************

***** Algorithme 2 - Résultats *****

Nombre de noeuds développés : 4

Une solution optimale :
x = 0; y = 1; 

Arbre développé :

--()--<

                --(01)--<

        --(0)--<

                --(00)--<

************************************

***** Algorithme 3 - Résultats *****

Nombre de noeuds développés : 3

Une solution optimale :
x = 0; y = 1; 

Arbre développé :

--()--<

                --(01)--<

        --(0)--<

************************************
*)

    let exemple3 =
            {fonction_a_minimiser =
              [Variable (-2, "x"); Variable (-3, "y");  Variable (-1, "z")];
             contraintes = []
              };;

    afficher_programme exemple3;;
    afficher_resultat_recherche 0 exemple3;;

(*
{ Min   -2*x - 3*y - z
{ s.c.

***** Algorithme 1 - Résultats *****

Nombre de noeuds développés : 15

Liste des solutions :
x = 1; y = 1; z = 1; 
x = 1; y = 1; z = 0; 
x = 1; y = 0; z = 1; 
x = 1; y = 0; z = 0; 
x = 0; y = 1; z = 1; 
x = 0; y = 1; z = 0; 
x = 0; y = 0; z = 1; 
x = 0; y = 0; z = 0; 

Arbre développé :

                        --(111)--<

                --(11)--<

                        --(110)--<

        --(1)--<

                        --(101)--<

                --(10)--<

                        --(100)--<

--()--<

                        --(011)--<

                --(01)--<

                        --(010)--<

        --(0)--<

                        --(001)--<

                --(00)--<

                        --(000)--<

************************************

***** Algorithme 2 - Résultats *****

Nombre de noeuds développés : 12

Une solution optimale :
x = 1; y = 1; z = 1; 

Arbre développé :

                        --(111)--<

                --(11)--<

                        --(110)--<

        --(1)--<

--()--<

                        --(011)--<

                --(01)--<

                        --(010)--<

        --(0)--<

                        --(001)--<

                --(00)--<

                        --(000)--<

************************************

***** Algorithme 3 - Résultats *****

Nombre de noeuds développés : 4

Une solution optimale :
x = 1; y = 1; z = 1; 

Arbre développé :

                        --(111)--<

                --(11)--<

        --(1)--<

--()--<

************************************
*)

    let exemple4 =
            {fonction_a_minimiser =
              [Variable (-2, "x"); Variable (1, "y");  Variable (-4, "z")];
             contraintes = [Inferieur ([Variable (1, "x"); Variable (1, "y");  Variable (2, "z")],
                [Constante 2])]
              };;

    afficher_programme exemple4;;
    afficher_resultat_recherche 0 exemple4;;

(*
{ Min   -2*x + y - 4*z
{ s.c.
{       x + y + 2*z <= 2

***** Algorithme 1 - Résultats *****

Nombre de noeuds développés : 12

Liste des solutions :
x = 1; y = 1; z = 0; 
x = 1; y = 0; z = 0; 
x = 0; y = 1; z = 0; 
x = 0; y = 0; z = 1; 
x = 0; y = 0; z = 0; 

Arbre développé :

                --(11)--<

                        --(110)--<

        --(1)--<

                --(10)--<

                        --(100)--<

--()--<

                --(01)--<

                        --(010)--<

        --(0)--<

                        --(001)--<

                --(00)--<

                        --(000)--<

************************************

***** Algorithme 2 - Résultats *****

Nombre de noeuds développés : 8

Une solution optimale :
x = 0; y = 0; z = 1; 

Arbre développé :

                --(11)--<

        --(1)--<

                --(10)--<

--()--<

        --(0)--<

                        --(001)--<

                --(00)--<

                        --(000)--<

************************************

***** Algorithme 3 - Résultats *****

Nombre de noeuds développés : 8

Une solution optimale :
x = 0; y = 0; z = 1; 

Arbre développé :

                --(11)--<

        --(1)--<

                --(10)--<

                        --(100)--<

--()--<

        --(0)--<

                        --(001)--<

                --(00)--<

************************************
*)

    let exemple5 =
            {fonction_a_minimiser =
              [Variable (-1, "x"); Variable (-2, "y");  Variable (-1, "z")];
             contraintes = [Inferieur ([Variable (2, "x"); Variable (3, "y");  Variable (1, "z")],
                [Constante 4]);Egal ([Variable (1, "y"); Variable (1, "z")],[Constante 1]) ]
              };;

    afficher_programme exemple5;;
    afficher_resultat_recherche 0 exemple5;;

(*
{ Min   -x - 2*y - z
{ s.c.
{       2*x + 3*y + z <= 4
{       y + z = 1

***** Algorithme 1 - Résultats *****

Nombre de noeuds développés : 9

Liste des solutions :
x = 1; y = 0; z = 1; 
x = 0; y = 1; z = 0; 
x = 0; y = 0; z = 1; 

Arbre développé :

        --(1)--<

                        --(101)--<

                --(10)--<

--()--<

                --(01)--<

                        --(010)--<

        --(0)--<

                        --(001)--<

                --(00)--<

************************************

***** Algorithme 2 - Résultats *****

Nombre de noeuds développés : 8

Une solution optimale :
x = 0; y = 1; z = 0; 

Arbre développé :

        --(1)--<

                --(10)--<

--()--<

                --(01)--<

                        --(010)--<

        --(0)--<

                        --(001)--<

                --(00)--<

************************************

***** Algorithme 3 - Résultats *****

Nombre de noeuds développés : 6

Une solution optimale :
x = 1; y = 0; z = 1; 

Arbre développé :

        --(1)--<

                        --(101)--<

                --(10)--<

--()--<

                --(01)--<

        --(0)--<

************************************
*)

    let exemple6 = forme_standard_programme
            {fonction_a_minimiser =
              [Variable (-2, "w"); Variable (-2, "x"); Variable (-4, "y");  Variable (3, "z")];
             contraintes = [Inferieur ([Variable (1, "x"); Variable (3, "y");  Variable (-2, "z")],
                [Constante 2]); Egal([Variable (1, "x"); Variable (1, "y")],[Variable (1, "w"); Variable (1, "z")]) ]
              };;

    afficher_programme exemple6;;
    afficher_resultat_recherche 0 exemple6;;

(*
{ Min   -2*w - 2*x - 4*y + 3*z
{ s.c.
{       x + 3*y - 2*z <= 2
{       -w + x + y - z = 0

***** Algorithme 1 - Résultats *****

Nombre de noeuds développés : 19

Liste des solutions :
w = 1; x = 1; y = 1; z = 1; 
w = 1; x = 1; y = 0; z = 0; 
w = 0; x = 1; y = 0; z = 1; 
w = 0; x = 0; y = 1; z = 1; 
w = 0; x = 0; y = 0; z = 0; 

Arbre développé :

                                --(1111)--<

                        --(111)--<

                --(11)--<

                        --(110)--<

                                --(1100)--<

        --(1)--<

                        --(101)--<

                --(10)--<

                        --(100)--<

--()--<

                --(01)--<

                                --(0101)--<

                        --(010)--<

        --(0)--<

                                --(0011)--<

                        --(001)--<

                --(00)--<

                        --(000)--<

                                --(0000)--<

************************************

***** Algorithme 2 - Résultats *****

Nombre de noeuds développés : 18

Une solution optimale :
w = 1; x = 1; y = 1; z = 1; 

Arbre développé :

                                --(1111)--<

                        --(111)--<

                --(11)--<

                        --(110)--<

                                --(1100)--<

        --(1)--<

                        --(101)--<

                --(10)--<

                        --(100)--<

--()--<

                --(01)--<

                        --(010)--<

        --(0)--<

                                --(0011)--<

                        --(001)--<

                --(00)--<

                        --(000)--<

                                --(0000)--<

************************************

***** Algorithme 3 - Résultats *****

Nombre de noeuds développés : 9

Une solution optimale :
w = 1; x = 1; y = 1; z = 1; 

Arbre développé :

                                --(1111)--<

                        --(111)--<

                --(11)--<

        --(1)--<

                        --(101)--<

                --(10)--<

--()--<

                --(01)--<

        --(0)--<

************************************
*)

6. Étude de programmes et de leur résolution

6.1. Ensemble des solutions

Étant donné un programme, les solutions sont fixées par les contraintes. Il est légitime de se demander si certains ensembles d'environnements ne peuvent jamais être des ensembles de solutions, auquel cas on peut espérer améliorer l'algorithme de recherche en évitant ces ensembles. La proposition suivante montre que ce n'est pas le cas :

Proposition 6.1.1

Pour tout ensemble d'environnements $X\subseteq {\{0;1\}}^n$, il existe des contraintes telles que l'ensemble des environnements les satisfaisant soit $X$. En particulier il existe un programme dont l'ensemble des solutions est $X$.

Démonstration : Montrons un résultat plus fort par récurrence sur $n$, à savoir que l'on peut considérer uniquement des contraintes d'infériorité. Pour $n=1$, les ensembles de solutions possibles sont $\varnothing ,\left\{\left(0\right)\right\},\left\{\left(1\right)\right\},\{\left(0\right);\left(1\right)\}$ respectivement obtenus pour les ensembles de contraintes $\left\{2\le x\right\},\left\{x\le 0\right\},\left\{1\le x\right\},\varnothing$. Supposons maintenant le résultat obtenu au rang $n$. Pour $i\in \{0;1\}$, posons $X_i=\left\{\left(x_1,x_2,...,x_n\right)|\left(x_1,x_2,...,x_n,i\right)\in X\right\}$. Par hypothèse de récurrence, il existe des ensembles de contraintes d'infériorité tels que l'ensemble des $n$-uplets les satisfaisant soient exactement $X_0$ et $X_1$. De plus, on peut supposer que ces contraintes aient toutes leurs variables dans le membre gauche et une constante dans le membre droit. Enfin, on suppose que pour un ensemble de contraintes donné, il n'existe pas de contraintes distinctes avec le même membre gauche, ou sinon on les regroupe en une seule, en prenant la borne supérieure de la constante de droite.

Prenons alors l'ensemble des contraintes formé par :

• Pour toute contrainte $\sum _{i=1}^n{a}_i{x}_i\le k_0$ utilisée pour décrire $X_0$ telle qu'il n'existe pas de contrainte $\sum _{i=1}^n{a}_i{x}_i\le k_1$ utilisée pour décrire $X_1$ (i.e. avec le même membre gauche), on considère la contrainte $\sum _{i=1}^n{a}_i{x}_i\le \left(1-x_{n+1}\right)k_0+x_{n+1}sup\sum _{i=1}^n{a}_i{x}_i$. Cette borne supérieure existant car le nombre de valeurs prises est finie.
• Même expression que le premier point, mais en inversant les rôles de $X_0$ et $X_1$.
• Si on a deux contraintes $\sum _{i=1}^n{a}_i{x}_i\le k_0$ et $\sum _{i=1}^n{a}_i{x}_i\le k_1$ utilisées respectivement pour décrire $X_0$ et $X_1$, alors on considère la contrainte $\sum _{i=1}^n{a}_i{x}_i\le {\left(1-x_{n+1}\right)k}_0+x_{n+1}{k}_1$.

Un élément $\left(x_1,x_2,...,x_{n+1}\right)$ appartient à $X$ si et seulement si il satisfait une de ces conditions :

• $x_{n+1}=0$ et $\left(x_1,x_2,...,x_n\right)\in X_0$
• $x_{n+1}=1$ et $\left(x_1,x_2,...,x_n\right)\in X_1$

Cela permet de conclure car par construction :

• Les contraintes du premier point se transforme en $\sum _{i=1}^n{a}_i{x}_i\le k_0$ si $x_{n+1}=0$ et sont toujours vraies si $x_{n+1}=1$.
• Idem mutatis mutandis.
• Les contraintes du troisième point se transforme en $\sum _{i=1}^n{a}_i{x}_i\le k_0$ si $x_{n+1}=0$ et en $\sum _{i=1}^n{a}_i{x}_i\le k_1$ si $x_{n+1}=1$.

Enfin, il suffit de choisir une fonction à minimiser arbitraire pour obtenir le programme. □

Notons que cette démonstration est constructive, au sens où l'on pourrait en extraire un programme Caml retournant un ensemble de contraintes à partir d'un ensemble de solutions.

6.2. Valeurs de la fonction à minimiser

La fonction à minimiser est définie sur ${\{0;1\}}^n$. A nouveau, on peut se demander si il est possible de fixer la fonction à minimiser de façon à pouvoir choisir ses $2^n$ valeurs. Cette fois ci la réponse est négative, puisque l'on obtiendrait un système d'équation linéaires à $n$ inconnues (les coefficients de la fonction à minimiser) avec $2^n>\mathrm{n}$ équations.

En fait, ce ne sont pas tant les valeurs de la fonctions à minimiser qui importe pour savoir combien de noeuds seront développés mais plutôt l'ordre dans lesquel elles sont rangées. On peut alors se demander si il est possible de fixer cet ordre de façon arbitraire.s

Si $f:x\mapsto \sum _{i=1}^n{a}_i{x}_i+k$ est la fonction à minimiser, alors pour tout $i$ :

• Si $a_i\ge 0$ alors pour tout $x_1,x_2...x_{i-1},x_{i+1},...x_n$ on a $f\left(x_1,x_2...x_{i-1},0,x_{i+1},...x_n\right)\le f\left(x_1,x_2...x_{i-1},1,x_{i+1},...x_n\right)$ et l'inégalité inverse si $a_i\le 0$.
• Réciproquement, si on une inégalité du type précédent sur les images de $f$ alors le signe de $a_i$ est fixée.

Autrement dit, pour un ordre donné sur les images de la fonction à minimiser, les signes de ses coefficients sont fixés. Réciproquement, si les signes de ses coefficients sont fixés, l'ordre des images est partiellement déterminé. Les valeurs absolues des coefficients complètent cet ordre.

En dernière remarque, on peut aussi translater les valeurs de la fonction à minimiser à sa guise en modifiant sa constante. Ceci ne change pas les contraintes donc pas non plus les solutions du programme, ni la façon dont les algorithmes le résolve. En particulier, on peut prendre la constante de la fonction à minimiser nulle.

6.3. Construction de programme particulier

Nous allons maintenant rechercher si pour un nombre de variables arbitraire, on peut trouver des programmes tels que la résolution par les algorithmes de recherche se produisent dans le meilleur/pire des cas.

Tout d'abord pour le premier algorithme qui ne vérifient que la satisfiabilité des contraintes en chaque noeud, il suffit de considérer des programmes données par la proposition, tels que aucun environnement ne soit solution ou au contraire le soit tous. Le premier cas reste valable pour les algorithmes améliorés.

Interessons-nous au cas où il y a au moins une solution. Le meilleur des cas correspond à celui où la première feuille trouvée est la solution optimale. Il suffit de considérer le programme suivant :

$\left(Ex\right)\{\begin{array}{cc}\mathrm{Min}& \sum _{i=1}^n{x}_i\\ \text{s.c.}& \\ & \sum _{i=1}^n{x}_i=0\\ & {\left(x_i\right)}_{i\in [1,n]}\in {\{0;1\}}^n\end{array}$

Sur les noeuds de la branche gauche, seules les contraintes du fils gauche sont satisfiables. Les trois algorithmes vont suivre cette branche et terminer à la feuille gauche qui est la solution optimale. La complexité est alors polynomiale car l'accès à la feuille optimale se fait en $O\left(n\right)$ noeuds, et le calcul des bornes inférieurs en chacun de ces noeuds a la même complexité.

Dans le pire des cas, le programme vérifie tous les noeuds, il faut donc au moins que les conditions soient toutes satisfiables. Dans ce cas, on sait que le troisième algorithme est meilleur. Prenons pour unique contrainte $-\sum _{i=1}^n{x}_i=0$ ou $\sum _{i=1}^n{x}_i=n$ qui fournira comme solution la feuille tout à gauche ou tout à droite. Ensuite, on prend pour fonction à minimiser $-\sum _{i=1}^n{2}^i{x}_i$, de sorte que ses valeurs sont décroissantes lorsque on lit les feuilles de gauche à droite. Si on choisi la solution à droite le troisième algorithme ira directement chercher la solution optimale alors que le second parcourira tous les noeuds. Le troisième algorithme parcourt tous les noeuds si on place la solution à gauche.

    let exemple8 =
            {fonction_a_minimiser =
              [Variable (-1, "x"); Variable (-2, "y");  Variable (-4, "z")];
             contraintes = [Egal ([Variable (1, "x"); Variable (1, "y"); Variable(1, "z")],[Constante 3]) ]
              };;

    afficher_programme exemple8;;
    afficher_resultat_recherche 0 exemple8;;

(*
{ Min   -x - 2*y - 4*z
{ s.c.
{       x + y + z = 3

***** Algorithme 1 - Résultats *****

Nombre de noeuds développés : 8

Liste des solutions :
x = 1; y = 1; z = 1; 

Arbre développé :

                        --(111)--<

                --(11)--<

        --(1)--<

                --(10)--<

--()--<

                --(01)--<

        --(0)--<

                --(00)--<

************************************

***** Algorithme 2 - Résultats *****

Nombre de noeuds développés : 8

Une solution optimale :
x = 1; y = 1; z = 1; 

Arbre développé :

                        --(111)--<

                --(11)--<

        --(1)--<

                --(10)--<

--()--<

                --(01)--<

        --(0)--<

                --(00)--<

************************************

***** Algorithme 3 - Résultats *****

Nombre de noeuds développés : 4

Une solution optimale :
x = 1; y = 1; z = 1; 

Arbre développé :

                        --(111)--<

                --(11)--<

        --(1)--<

--()--<

************************************
*)
    let exemple9 =
            {fonction_a_minimiser =
              [Variable (-1, "x"); Variable (-2, "y");  Variable (-4, "z")];
             contraintes = [Egal ([Variable (-1, "x"); Variable (-1, "y"); Variable(-1, "z")],[Constante 0]) ]
              };;

    afficher_programme exemple9;;
    afficher_resultat_recherche 0 exemple9;;

(*
{ Min   -x - 2*y - 4*z
{ s.c.
{       -x - y - z = 0

***** Algorithme 1 - Résultats *****

Nombre de noeuds développés : 8

Liste des solutions :
x = 0; y = 0; z = 0; 

Arbre développé :

                --(11)--<

        --(1)--<

                --(10)--<

--()--<

                --(01)--<

        --(0)--<

                --(00)--<

                        --(000)--<

************************************

***** Algorithme 2 - Résultats *****

Nombre de noeuds développés : 8

Une solution optimale :
x = 0; y = 0; z = 0; 

Arbre développé :

                --(11)--<

        --(1)--<

                --(10)--<

--()--<

                --(01)--<

        --(0)--<

                --(00)--<

                        --(000)--<

************************************

***** Algorithme 3 - Résultats *****

Nombre de noeuds développés : 8

Une solution optimale :
x = 0; y = 0; z = 0; 

Arbre développé :

                --(11)--<

        --(1)--<

                --(10)--<

--()--<

                --(01)--<

        --(0)--<

                --(00)--<

                        --(000)--<

************************************
*)

7. Conclusion

Nous avons étudié la résolution de programme linéaire avec des conditions particulières. Dans un premier temps, nous avons mis le problème sous forme canonique de façon à ce qu'il soit plus facile à résoudre. Une première approche naïve a permis de poser les bases de la résolution de l'algorithme mais sa complexité exponentielle était peu satisfaisante.

Pour améliorer l'algorithme, nous avons envisagé le problème du point de vue du parcours dans un arbre. Une première amélioration vérifiant la satisfabilité des contraintes en chaque noeud a permis de réduire le nombre de noeuds développés.

Nous nous sommes ensuite penchés sur la recherche d'une solution optimale. Deux améliorations ont alors pu être appliquées, en regardant la borne inférieur de la fonction à minimiser. La première consiste à la comparer avec sa valeur en une solution connue, la seconde à rechercher en priorité dans les noeuds où cette borne est minimale. Ces nouveaux algorithmes diminuaient à nouveau le nombre de noeuds développés.

Nous avons étudiés la structure des programmes linéaires. Nous avons vu que tout ensemble d'environnement pouvait être l'ensemble des solutions d'un programme. Par contre, les valeurs de la fonction à minimiser ne peuvent être quelquonques, en particulier, leur ordre est en partie déterminé par le signe de ses coefficients, ce qui avais été mis a profit auparavant pour le calcul de borne inférieur.

Finalement, nous avons recherché des programmes provoquant le meilleur/pire des cas. Nous avons vu que tous les algorithmes sont au mieux en complexité polynomiale et au pire exponentielle. Le dernier algorithme semble meilleur car dans le cas où il y a beaucoup de noeuds satisfiables, il cherche les meilleurs solutions en priorité et développe donc moins de noeuds. Toutefois, seule une étude de la complexité en moyenne permettrait de conclure.

8. Annexe

Le code source Caml est disponible en annexe.

Cette page est conforme aux normes du W3C - Auteur : Frédéric WANG - Dernière mise à jour : dimanche 9 décembre 2007