(*

  WANG Frédéric
  Groupe 4.2

*)

(****************************************************************)
(********** Première partie : mise sous forme standard **********)
(****************************************************************)

(********** Définition des structures de données **********)

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

type expression = litteral list;;

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

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

(********** Question 1 **********)

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

   test:

     let expr = generer_expression 4;;
     string_of_expression expr;;
     string_of_expression (change_signe expr);;

     val expr : litteral list =
       [Constante 10; Variable (-17, "X2"); Variable (28, "X1"); Constante (-34)]
     - : string = "10 - 17*X2 + 28*X1 - 34"
     - : string = "-10 + 17*X2 - 28*X1 + 34"
*)
let change_signe expr =
  List.map (function Constante n -> Constante (-n) | Variable (coeff, nom) -> Variable (-coeff, nom)) expr;;

(********** Question 2 **********)

(* 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.

   test:
     let litt = generer_litteral ();;
     let expr = generer_expression 5;;
     string_of_litteral true litt;;
     string_of_expression expr;;
     string_of_expression (ajouter_litteral litt expr);;

     val litt : litteral = Variable (45, "X2")
     val expr : litteral list =
       [Constante (-33); Constante (-13); Variable (-36, "X0"); Constante 6;
        Constante 15]
     - : string = "45*X2"
     - : string = "-33 - 13 - 36*X0 + 6 + 15"
     - : string = "-33 - 13 - 36*X0 + 6 + 15 + 45*X2"
*)
let rec ajouter_litteral litt expr = match (litt, expr) with

  | _, [] -> [litt]

  | (Constante n, (Constante m)::q) -> (Constante (n + m))::q
  | (Constante n, _) -> (Constante n)::expr

  | (Variable (n, x), (Variable (m, y))::q) ->
      if x = y then
        (Variable (n + m, x))::q
      else if x > y then
        (Variable (m, y))::(ajouter_litteral litt q)
      else (Variable (n, x))::expr

  | (_, t::q) -> t::(ajouter_litteral litt q);;

(* 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.
   test:
     let expr = generer_expression 10;;
     string_of_expression expr;;
     string_of_expression (forme_standard_expression expr);;

     val expr : litteral list =
       [Constante (-30); Variable (40, "X2"); Constante 16; Constante 22;
        Constante 12; Variable (42, "X1"); Constante 10; Variable (-17, "X2");
        Variable (28, "X1"); Constante (-34)]
     - : string = "-30 + 40*X2 + 16 + 22 + 12 + 42*X1 + 10 - 17*X2 + 28*X1 - 34"
     - : string = "-4 + 70*X1 + 23*X2"
*)
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 []);;

(********** Question 3 **********)

(* 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.

   test:
     let e1, e2 = (generer_expression 3), (generer_expression 6) in 
       (
       print_string "\n";
       print_string ((string_of_expression e1)^"\n");
       print_string ((string_of_expression e2)^"\n\n");
       let f1, f2 = (envoyer_a_gauche e1 e2) in
         (
         print_string ((string_of_expression f1)^"\n");
         print_string ((string_of_expression f2)^"\n");
         )
       );;

     -36 + 18 + 21*X2
     -46 - 35 - 12 + 4 + 18*X0 + 19*X1

     -19*X1 - 18*X0 - 36 + 18 + 21*X2
     -46 - 35 - 12 + 4
     - : unit = ()
*)
let rec envoyer_a_gauche e1 f1 = match f1 with
    [] -> (e1, f1)
  | (Constante n)::q -> let (e2, f2) = envoyer_a_gauche e1 q in e2, (Constante n)::f2
  | (Variable (n, x))::q -> envoyer_a_gauche ((Variable (-n, x))::e1) q;;

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

   test (n_coeff = 2):
     let e = generer_expression 10 in
       print_string ("\n"^(string_of_expression e)^"\n"^(string_of_expression (supprimer_variables_nulles e))^"\n");;
  
     0*X3 + 1 + 0*X1 + 0*X2 - X2 + X1 + 0 - X0 + 0 + 0
     1 - X2 + X1 + 0 - X0 + 0 + 0
     - : unit = ()
*)
let supprimer_variables_nulles expr =
  List.filter (function Variable (0, _) -> false | _ -> true) expr;;

(* 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é

   test:
     let ctr = generer_contrainte() in
       print_string ("\n"^(string_of_contrainte ctr)^"\n"^(string_of_contrainte (forme_standard_contrainte ctr))^"\n");;

     -46 + 21*X2 - 8 + 7 + 42*X1 >= 15*X2 + 6 + 34*X2 + 31 - 1
     47 - 42*X1 + 28*X2 <= -36
     - : unit = ()
*)
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);;

(*     let ctr = generer_contrainte() in
       print_string ("\n"^(string_of_contrainte ctr)^"\n"^(string_of_contrainte (forme_standard_contrainte ctr))^"\n");;*)

(* 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.

   test:
     
     let prog = (generer_programme 5) in
       (
       print_newline();
       afficher_programme prog;
       print_newline();
       afficher_programme (forme_standard_programme prog);
       );;
            
     { Min   45*X0 - 48*X1 - 31*X2
     { s.c.
     {       -6*X2 - 5 + 48 - 39 + 46 = 23*X2 - 30 - 24*X2 - 44*X1 + 48
     {       -45 - 5*X1 - 33 + 41*X2 + 46*X1 = 47 - 30*X1 + 43 - 13*X2 - 29*X0
     {       38 + 47*X2 + 43 - 34*X1 - 30*X0 = 36*X1 - 23 - 38*X1 - 20*X0 - 33*X1
     {       32 - 12*X0 + 2*X1 + 3*X0 - 31 = 41 - 19 + 11 + 46 + 4
     {       34 + 18*X2 + 27 + 46 + 5*X0 >= -30*X1 + 29 - 10*X0 - 26 + 36*X0

     { Min   45*X0 - 48*X1 - 31*X2
     { s.c.
     {       50 + 44*X1 - 5*X2 = 18
     {       -78 + 29*X0 + 71*X1 + 54*X2 = 90
     {       81 - 10*X0 + X1 + 47*X2 = -23
     {       1 - 9*X0 + 2*X1 = 83
     {       -107 + 21*X0 - 30*X1 - 18*X2 <= -3
     - : unit = ()
*)
let forme_standard_programme p =
    {
    fonction_a_minimiser = forme_standard_expression p.fonction_a_minimiser;
    contraintes = List.map forme_standard_contrainte p.contraintes;
    };;

(****************************************************************)
(***** Deuxième partie : résolution des programmes linéaire  ****)
(****************************************************************)

(********** Question 4a **********)

type environnement = (string * int) list;;
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
   test: 
     associer [("a", 9); ("b", 6); ("abc", 77); ("cc", 3)] "abc";;
     - : int = 77
     associer [("a", 9); ("b", 6); ("abc", 77); ("cc", 3)] "c";;
     Exception: ValeurIndefinie.
*)
let rec associer env cle = match env with
    [] -> raise ValeurIndefinie
  | (a, b)::q -> if a = cle then b else associer q cle;;

(* 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
   test:
     evaluer_litteral [] (Constante 44);;
     - : int = 44
     evaluer_litteral [] (Variable (44, "x"));;
     Exception: ValeurIndefinie.
     evaluer_litteral [("x", 2)] (Variable (44, "x"));;
     - : int = 88
*)
let evaluer_litteral env = function
    Constante n -> n
  | Variable (coeff, nom) -> coeff*(associer env nom);;

(* 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 
   test:     
     let env = generer_environnement false;;
     let expr = generer_expression 5 in
       (
       print_string ("\n"^(string_of_expression expr)^"\n");
       print_int (evaluer_expression env expr);
       print_newline()
       );;

     val env : (string * int) list =
       [("X3", -5); ("X2", 16); ("X1", -11); ("X0", -2)]
          
     -34*X1 - 30*X1 + 36*X1 - 2*X2 + 39*X3
     81
     - : unit = ()
*)
let evaluer_expression env =
  List.fold_left (function n -> function litt -> n + (evaluer_litteral env litt)) 0;;

(* 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
   test:

     let e = forme_standard_expression (generer_expression 20) in
       begin
         print_newline();
         print_string (string_of_expression e);
         print_newline();
         print_int (evaluer_borne_inferieur [("X0",1);("X1",0);("X3", 1)] e);
         print_newline();
       end;;
              
     44 - 22*X1 - 31*X2 + 10*X3 - 12*X5 + 0*X6 - 13*X7 - 76*X8 - 5*X9
     -83
     - : unit = ()

     76 + 14*X1 - 21*X2 + 21*X3 - 103*X4 + 81*X5 - 20*X6 - 8*X7
     -55
     - : unit = ()

     101 + 36*X0 + X1 + 22*X2 - 130*X3 - 47*X4 + 10*X5 - 59*X6 - 32*X7 - 11*X8 + 21*X9
     -142
     - : unit = ()
*)
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;;

(********** Question 4b **********)
(* 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."
   test:
     est_satisfiable_contrainte [] (Egal ([], [Variable (2,"x")]));;
     Exception: Failure "est_satisfiable_contrainte : la contrainte n'est pas sous forme standard."

     let ctr = forme_standard_contrainte (generer_contrainte()) and env = (generer_environnement false) in
       begin
         print_newline();
         print_string (string_of_contrainte ctr);
         print_newline();
         print_string
           (if (est_satisfiable_contrainte env ctr) then "est satisfiable dans" else "n'est pas satisfiable dans");
         env;
       end
  
     -15 - 8*X0 + 12*X1 + 18*X2 <= -52
     n'est pas satisfiable dans- : (string * int) list = [("X2", -1); ("X1", 9); ("X0", 3)]
*)
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
   test:

     let prog = (forme_standard_programme (generer_programme 2)) and env = (generer_environnement false) in
       begin
         print_newline();
         afficher_programme prog;
         print_string (if est_satisfiable_programme prog env then "est satisfiable dans" else "n'est pas satisfiable dans");
         env;
       end

     { Min   -37*X0 - 10*X1 - 3*X2
     { s.c.
     {       -8 - 21*X0 + 20*X1 + 50*X2 = 7
     {       -23 + 36*X1 + 22*X2 <= 90
     est satisfiable dans- : (string * int) list = [("X2", -5); ("X1", -3); ("X0", 17)]
            
     { Min   0*X0 - 39*X1 + 27*X2
     { s.c.
     {       -66 + 31*X0 - 24*X1 - 32*X2 <= -10
     {       38 + 3*X0 + 37*X1 + 14*X2 <= -38
     n'est pas satisfiable dans- : (string * int) list = [("X2", 5); ("X1", 1); ("X0", -4)]
*)
let est_satisfiable_programme prog env =
  List.fold_right (function x -> function y -> y && (est_satisfiable_contrainte env x)) prog.contraintes true;;

(********** Question 5 **********)
type abr = Vide | Noeud of abr * environnement * abr;;

(* 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.
   test:
     let prog = (generer_programme 2) in
       (
       print_newline();
       afficher_programme prog;
       liste_variables prog;
       );;
          
     { Min   -33*X0 + 48*X1 + 49*X2
     { s.c.
     {       24*X0 - 39*X0 - 12*X1 + 45 + 12 >= 35*X0 - 9*X1 + 40 + 0 - 36*X0
     {       -6 + 31 + 37 + 38 + 10 >= 14*X0 - 41*X2 + 10*X2 - 2*X1 + 40
     - : string list = ["X0"; "X1"; "X2"]
*)
let liste_variables prog =
   List.fold_right
     (function t -> function l -> match t with Variable (_, nom) -> nom::l | Constante _ -> l)
     prog.fonction_a_minimiser
     [];;

(* 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
   test:

     let ctr = (generer_contrainte()) and env = (generer_environnement false) in
       begin
         print_newline();
         print_string (string_of_contrainte ctr);
         print_newline();
         print_string
           (if (est_satisfaite_contrainte env ctr) then "est satisfaite dans" else "n'est pas satisfaite dans");
         env;
       end;;

     -17 + 36 - 11 + 4*X1 + 46*X2 <= -22 - 5*X2 + 4 - 46*X0 + 14
     est satisfaite dans- : (string * int) list = [("X2", -19); ("X1", 3); ("X0", -2)]

     0 - 30 + 0 + 47*X1 - 37*X1 <= -33*X2 + 36*X0 + 26 + 13 + 20*X2
     n'est pas satisfaite dans- : (string * int) list = [("X2", 9); ("X1", -5); ("X0", -6)]
*)
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);;

(* 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;;

(* 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é)
   test:
     let p = forme_standard_programme (generer_programme 5);;
     afficher_programme p;;
     recherche_1 p;;

     val p : programme =
       {fonction_a_minimiser =
         [Variable (-46, "X0"); Variable (-14, "X1"); Variable (13, "X2")];
        contraintes =
         [Inferieur
           ([Constante 3; Variable (-8, "X0"); Variable (-12, "X1");
             Variable (27, "X2")],
           [Constante (-16)])]}
     afficher_programme p;;
     { Min   -46*X0 - 14*X1 + 13*X2
     { s.c.
     {       3 - 8*X0 - 12*X1 + 27*X2 <= -16
     - : unit = ()
     recherche_1 p;;
     - : environnement list * int * abr =
     ([[("X2", 0); ("X1", 1); ("X0", 1)]], 4,
      Noeud (Vide, [],
       Noeud (Vide, [("X0", 1)],
        Noeud (Noeud (Vide, [("X2", 0); ("X1", 1); ("X0", 1)], Vide),
         [("X1", 1); ("X0", 1)], Vide))))
*)

let recherche_1 prog =

  let rec recherche env variables_libres solutions nombre_noeuds =
    match variables_libres with
      (* Toutes les variables sont liées, vérifie s'il s'agit d'une solution *)
        [] -> if toutes_satisfaites env prog.contraintes then
                env::solutions, nombre_noeuds + 1, Noeud(Vide, env, Vide)
              else
                solutions, nombre_noeuds, Vide

      (* Il reste des variables libres... *)
      | nom::q ->
              
        if not (est_satisfiable_programme prog env) then
          (* Toutes les contraintes ne sont pas satisfiables : ne développe pas le noeud *)
          solutions, nombre_noeuds, Vide
        else
          (* Développe le noeud en appliquant l'algorithme sur les fils gauche et droit *)
          let solutions2, nombre_noeuds2, fils_gauche = recherche ((nom, 0)::env) q solutions nombre_noeuds in
          let solutions3, nombre_noeuds3, fils_droit =  recherche ((nom, 1)::env) q solutions2 nombre_noeuds2 in
            solutions3, nombre_noeuds3 + 1, Noeud(fils_gauche, env, fils_droit)

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

(* 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;;

(* Interface recherche_2
   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

   test:
     val p : programme =
       {fonction_a_minimiser =
         [Variable (48, "X0"); Variable (-40, "X1"); Variable (-45, "X2")];
        contraintes =
         [Inferieur ([Constante (-9); Variable (-8, "X0"); Variable (-72, "X2")],
           [Constante 7])]}
     afficher_programme p;;
     recherche_2 p;;

     { Min   48*X0 - 40*X1 - 45*X2
     { s.c.
     {       -9 - 8*X0 - 72*X2 <= 7
     - : unit = ()

     - : resultat * int * abr =
     (Solution ([("X2", 1); ("X1", 1); ("X0", 0)], -85), 7,
      Noeud
       (Noeud
         (Noeud (Noeud (Vide, [("X2", 0); ("X1", 0); ("X0", 0)], Vide),
      [("X1", 0); ("X0", 0)],
           Noeud (Vide, [("X2", 1); ("X1", 0); ("X0", 0)], Vide)),
         [("X0", 0)],
         Noeud (Vide, [("X1", 1); ("X0", 0)],
          Noeud (Vide, [("X2", 1); ("X1", 1); ("X0", 0)], Vide))),
       [], Vide))
*)
let recherche_2 prog =

  let rec recherche env variables_libres solution nombre_noeuds =
    match variables_libres with
      (* Toutes les variables sont liées, vérifie s'il s'agit d'une solution *)
        [] -> let v = evaluer_expression env prog.fonction_a_minimiser in
           (match solution with

             | Rien ->
                 if toutes_satisfaites env prog.contraintes then
                   Solution(env, v), (nombre_noeuds + 1), Noeud(Vide, env, Vide)
                 else
                   Rien, nombre_noeuds, Vide

             | Solution(s_optimale, v_optimale) ->
                 if v < v_optimale && toutes_satisfaites env prog.contraintes then
                   Solution(env, v), (nombre_noeuds + 1), Noeud(Vide, env, Vide)
                 else
                   Solution(s_optimale, v_optimale), nombre_noeuds, Vide
           )
      (* Il reste des variables libres... *)
      | nom::q ->
        if (match solution with
               Rien -> false
             | Solution(_, v_optimale) -> v_optimale < (evaluer_borne_inferieur env prog.fonction_a_minimiser) 
          ) || not (est_satisfiable_programme prog env) then
          (* Ne développe pas le noeud *)
          solution, nombre_noeuds, Vide
        else
          let solution2, nombre_noeuds2, fils_gauche = recherche ((nom, 0)::env) q solution nombre_noeuds in
          let solution3, nombre_noeuds3, fils_droit = recherche ((nom, 1)::env) q solution2 nombre_noeuds2 in
          solution3, (nombre_noeuds3 + 1), Noeud(fils_gauche, env, fils_droit)

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

(* Interface recherche_3
   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
   test:
          val p : programme =
  {fonction_a_minimiser =
    [Variable (48, "X0"); Variable (-40, "X1"); Variable (-45, "X2")];
   contraintes =
    [Inferieur ([Constante (-9); Variable (-8, "X0"); Variable (-72, "X2")],
      [Constante 7])]}
     afficher_programme p;;
     recherche_3 p;;

     { Min   48*X0 - 40*X1 - 45*X2
     { s.c.
     {       -9 - 8*X0 - 72*X2 <= 7
     - : unit = ()
     - : resultat * int * abr =
     (Solution ([("X2", 1); ("X1", 1); ("X0", 0)], -85), 4,
      Noeud
       (Noeud (Vide, [("X0", 0)],
         Noeud (Vide, [("X1", 1); ("X0", 0)],
          Noeud (Vide, [("X2", 1); ("X1", 1); ("X0", 0)], Vide))),
       [], Vide))
*)

let recherche_3 prog =

  let rec recherche env variables_libres solution nombre_noeuds =
    match variables_libres with
      (* Toutes les variables sont liées, vérifie s'il s'agit d'une solution *)
        [] -> let v = evaluer_expression env prog.fonction_a_minimiser in
           (match solution with

             | Rien ->
                 if toutes_satisfaites env prog.contraintes then
                   Solution(env, v), (nombre_noeuds + 1), Noeud(Vide, env, Vide)
                 else
                   Rien, nombre_noeuds, Vide

             | Solution(s_optimale, v_optimale) ->
                 if v < v_optimale && toutes_satisfaites env prog.contraintes then
                   Solution(env, v), (nombre_noeuds + 1), Noeud(Vide, env, Vide)
                 else
                   Solution(s_optimale, v_optimale), nombre_noeuds, Vide
           )
      (* Il reste des variables libres... *)
      | nom::q ->
          let env_gauche = (nom, 0)::env and env_droite = (nom, 1)::env in
          let borne_inferieur_gauche = evaluer_borne_inferieur env_gauche prog.fonction_a_minimiser
          and borne_inferieur_droite = evaluer_borne_inferieur env_droite prog.fonction_a_minimiser in

        if (match solution with
               Rien -> false
             | Solution(_, v_optimale) -> v_optimale < (min borne_inferieur_gauche  borne_inferieur_droite)
          ) || not (est_satisfiable_programme prog env) then
          (* Ne développe pas le noeud *)
          solution, nombre_noeuds, Vide
        else
          if borne_inferieur_gauche < borne_inferieur_droite then
            (* Cherche d'abord dans le fils gauche *)
            let solution2, nombre_noeuds2, fils_gauche = recherche env_gauche q solution nombre_noeuds in
            let solution3, nombre_noeuds3, fils_droit = recherche env_droite q solution2 nombre_noeuds2 in
            solution3, (nombre_noeuds3 + 1), Noeud(fils_gauche, env, fils_droit)
          else
            (* Cherche d'abord dans le fils droit *)
            let solution2, nombre_noeuds2, fils_droit = recherche env_droite q solution nombre_noeuds in
            let solution3, nombre_noeuds3, fils_gauche = recherche env_gauche q solution2 nombre_noeuds2 in
            solution3, (nombre_noeuds3 + 1), Noeud(fils_gauche, env, fils_droit)

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

(****************************************************************)
(******* Fonctions annexes : Générer variables ; Affichage ******)
(****************************************************************)

(********** Générateurs de données aléatoires, pour les tests **********)

 (*
   Paramètrages des générateurs de variables aléatoires.
   Les variables suivantes doivent rester strictement positive :
     - n_coeff : valeur absolue maximale (exclue) des coefficients.
     - n_var : nombre de variables maximal (exclu).
     - n_litt : nombres de litteraux dans les expressions des contraintes et programmes.
     - n_valeur : valeur absolue maximale (exclue) prise par les variables dans un environnement.
 *)
let n_coeff = 50 and n_var = 3 and n_litt = 5 and n_valeur = 20;;

(* Interface random_signe
   type: int -> int
   pré: n > 0
   post: un nombre aléatoire entre -(n - 1) et (n - 1).
   raises: Exception: Invalid_argument "Random.int" si n <= 0
*)
let random_signe n = (if Random.bool() then 1 else -1) * Random.int(n);;

(* Interface generer_litteral ()
   type: unit -> litteral
   arguments: aucun
   pré: n_coeff > 0
   post: Génère un litteral :
           - S'il s'agit d'une constante, sa valeur est comprise entre -(n_coeff - 1) et n_coeff - 1
           - S'il s'agit d'une variable, son coefficient est compris entre 0 et n_coeff - 1,
               et son nom est de la forme "Xi" avec i compris entre 0 er n_var - 1.
   raises: Exception: Invalid_argument "Random.int" si n_coeff <= 0
*)
let generer_litteral () = 
  let coeff =  random_signe n_coeff in
    if Random.bool() then
      Constante (coeff)
    else
      Variable (coeff,
                "X"^(string_of_int (Random.int(n_var)))
		)
   ;;

(* Interface generer_liste
   type: int -> (unit -> 'a) -> 'a list
   arguments: n, fonction_generatrice
   pré: n >= 0
   post: une liste de n éléments générés par fonction_generatrice.
*)
let rec generer_liste n fonction_generatrice = match n with
    0 -> []
  | n -> (fonction_generatrice ())::(generer_liste (n - 1) fonction_generatrice);;

(* Interface generer_expression
   type: int -> litteral list
   arguments: n
   pré: n >= 0
   post: Génère une liste de literraux, i.e. une expression *)
let generer_expression n = generer_liste n generer_litteral;;

(* Interface generer_contrainte
   type: int -> contrainte
   arguments: aucun
   post: une contrainte dont les deux expressions ont chacune n_litt litteraux.
*)
let generer_contrainte () =
  let (e1, e2) = ((generer_expression n_litt), (generer_expression n_litt)) in
  match Random.int(3) with
      0 -> Egal (e1, e2)
    | 1 -> Inferieur (e1, e2)
    | _ -> Superieur (e1, e2)
  ;;

(* Interface generer_programme
   type: int -> programme
   arguments: n
   pré: n >= 0
   post: un programme avec n contraintes.
*)
let generer_programme n =
  let rec aux i =
    if i < n_var then
      (Variable ((random_signe n_coeff), "X"^(string_of_int i)))::(aux (i + 1))
    else
      []
  in
 
   let ctr = generer_liste n generer_contrainte in
    {
    fonction_a_minimiser = aux 0;
    contraintes = ctr;
    };;

(* Interface generer_environnement
   type: bool -> (string * int) list
   arguments: bivaluees
   pré: n_valeur > 0
   post: génère un environnement pour les n_var variables
         Si bivaluees est vraies, les valeurs des variables sont réduites à 0 et 1
   raises: Exception: Invalid_argument "Random.int" si bivaluees = false et n_valeur <= 0
*)
let generer_environnement bivaluees =
  let rec aux n =
    if n >= 0 then
      (("X"^(string_of_int n)), 
        if bivaluees then (Random.int 2) else (random_signe n_valeur)
       )::(aux (n - 1))
    else
      []
  in
    aux (n_var - 1);;

(********** Conversion des données vers une chaine de caractères, pour l'affichage **********)
  
(* Interface nombre_sans_signe
   type: int -> string
   arguments: un entier n
   post: une chaine de caractère codant la valeur absolue de n
*)
let nombre_sans_signe n = string_of_int (if n < 0 then (-n) else n);;

(* Interface plus_ou_moins
   type: bool -> int -> string
   arguments: est_premier, n
   post: Retourne le signe (est_premier = true) ou le symbole d'opérateur (est_premier = false)
         qui doit être placé devant le nombre n. est_premier précise si ce nombre est en début
         d'expression.
*)
let plus_ou_moins est_premier n =
  if est_premier then
    if n < 0 then "-" else ""
  else
    if n < 0 then " - " else " + ";;

(* Interface string_of_litteral 
   type:  bool -> litteral -> string
   arguments: est_premier, litt
   post: Retourne une chaine codant un littéral. est_premier indique si ce littéral est
         placé en début d'expression.
*)
let string_of_litteral est_premier litt = match litt with
    Constante n -> (plus_ou_moins est_premier n)^(nombre_sans_signe n)
  | Variable (n, nom) -> 
      (plus_ou_moins est_premier n)^
      (if (n = -1 || n = 1) then "" else (nombre_sans_signe n)^"*")
      ^nom;;

(* Interface string_of_expression
   type: expression -> string
   arguments: expr
   post: Retourne une chaine représentant une expression.
*)
let string_of_expression (expr:expression) =
  let rec aux (est_premier, e) = match e with
      [] -> ""
    | t::q -> (string_of_litteral est_premier t)^(aux (false, q))
  in
    aux (true, expr);;

(* Interface string_of_contrainte
   type: expression -> string
   arguments: ctr
   post: une chaine représentant une contrainte.
*)
let string_of_contrainte ctr = match ctr with
    Egal (e1,e2) -> (string_of_expression e1)^" = "^(string_of_expression e2)
  | Inferieur (e1,e2) -> (string_of_expression e1)^" <= "^(string_of_expression e2)
  | Superieur (e1,e2) -> (string_of_expression e1)^" >= "^(string_of_expression e2);;

(* Interface string_of_programme
   type: programme -> string
   arguments: prog
   post: une chaine représentant un programme.
*)
let string_of_programme prog =
  let rec concatener_contraintes = function
      [] -> ""
    | t::q -> "{       "^(string_of_contrainte t)^"\n"^(concatener_contraintes q)
  in    

  "{ Min   "^(string_of_expression (prog.fonction_a_minimiser))^"\n"^
  "{ s.c.\n"^
  (concatener_contraintes prog.contraintes);;

(* Interface afficher_programme
   type: programme -> unit
   arguments: prog
   post: affiche un programme.
*)
let afficher_programme prog = print_string (string_of_programme prog);;

(* Interface afficher_arbre_binaire
   type: abr -> unit
   arguments: arbre
   post: affiche un arbre binaire.
*)
let afficher_arbre_binaire arbre =

  (* espace n retourne une chaine de n espaces (n >= 0) *)
  let rec espace =  function
      0 -> "--"
    | n -> "        "^(espace (n - 1))
  in

  (*  string_of_environnement env retourne une chaine composée de 0 et 1
      représentant env. Les fonctions de recherche retournent des variables
      classées par ordre alphabétique décroissant, mais cette fonction
      s'arrange pour afficher les valeurs dans l'ordre lexicographique. *)
  let rec string_of_environnement = function
      [] -> ""
    | (nom, v)::q -> (string_of_environnement q)^(string_of_int v)
  in

  (* string_of_arbre concatène les environnements de chaque noeud/feuille
     pour obtenir une représentation graphique de l'arbre *)
  let rec string_of_arbre decalage = function
      Vide -> "\n"
    | Noeud(g, e, d) -> 
      (string_of_arbre (decalage + 1) d)^
      (espace decalage)^"("^(string_of_environnement e)^")--<\n"^
      (string_of_arbre (decalage + 1) g)

  in print_string (string_of_arbre 0 arbre);;
    
(* Interface afficher_resultat_recherche
   type: int -> programme -> unit
   arguments: numero_algo, prog
   pré: prog est sous forme standard
   post: Affiche le résultat de la résolution de prog, selon l'algorithme de recherche numéro numero_algo.
         Si numero_algo n'est pas 1, 2, 3 alors les trois algorithmes sont appliqués.
*)
let rec afficher_resultat_recherche numero_algo prog = 

  (*  string_of_environnement env donne une représentation de env sous forme
      de chaine. Les fonctions de recherche retournent des variables
      classées par ordre alphabétique décroissant, mais cette fonction
      s'arrange pour afficher les valeurs dans l'ordre lexicographique. *)
  let rec string_of_environnement = function
    | [] -> ""
    | (nom, v)::q -> (string_of_environnement q)^(nom^" = "^(string_of_int v)^"; ")
  in

  (*  string_of_solutions concatène les chaines représentant des solutions *)
  let rec string_of_solutions = function
    | [] -> "\n"
    | e::q -> (string_of_environnement e)^"\n"^(string_of_solutions q)
  in

    match numero_algo with
      | 1 ->
        (* Question 5 : liste de solutions, nombre de noeuds développés et arbre développé *)
        let solutions, nombre_noeuds, arbre = recherche_1 prog in
          begin
            print_string "***** Algorithme 1 - Résultats *****\n\n";
            print_string ("Nombre de noeuds développés : "^(string_of_int nombre_noeuds)^"\n\n");

            print_string
              (if solutions = [] then
                "Pas de solution\n\n"
              else 
                "Liste des solutions :\n"^(string_of_solutions solutions)
              );

            print_string "Arbre développé :\n";
            afficher_arbre_binaire arbre;
            print_string "************************************\n\n";
          end        

      | 2 | 3 -> 
        (* Question 6 et 7 : une solution optimale, nombre de noeuds développés et arbre développé *)
          let solution, nombre_noeuds, arbre = (if numero_algo = 2 then recherche_2 else recherche_3) prog in
          begin
            print_string ("***** Algorithme "^(string_of_int numero_algo)^" - Résultats *****\n\n");
            print_string ("Nombre de noeuds développés : "^(string_of_int nombre_noeuds)^"\n\n");

            print_string
              (match solution with
                 | Rien -> "Pas de solution\n\n"
                 | Solution(env, _) -> "Une solution optimale :\n"^(string_of_environnement env)^"\n\n"
              );

            print_string "Arbre développé :\n";
            afficher_arbre_binaire arbre;
            print_string "************************************\n\n";
          end

        (* Affiche les résultats des algorithmes des questions 5, 6, 7 *)
      | _ -> for i = 1 to 3 do afficher_resultat_recherche i prog done;;

(****************************************************************)
(*********** 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)--<

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

    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)--<

************************************
*)
    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)--<

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