52 #define MALLOC(s,t,f) malloc(s)
88 bool degenere =
false;
93 printf(
" * algorithme de GOMORY \n");
98 if (sys1!=NULL && fonct != NULL)
100 if ((
sol_entiere(sys1,*lvbase,*nb_som) ==
false) ||
105 while ((sys1 != NULL) &&
107 if (sys1 != NULL && fonct != NULL)
123 (
cout_nul(fonct,*lvbase,*nbvars,*b) ==
124 false) || degenere) {
135 if (((eq_gom =
gomory_eq(&sys1,*lvbase,*nb_som,&no_som,&var2)) != NULL) && (sys1 !=NULL)) {
145 sys = som_sys_conv(sys1);
154 if ((sys1 != NULL) && non_stop )
159 if (
dual_pivot_pas(&sys1,lvbase,*nb_som,fonct,nbvars,b) !=
false) {
163 while ((sys1 != NULL)
170 printf(
" - Gomory - on a une solution optimale \n");
184 printf (
" - Gomory - on a une solution optimale \n");
202 printf (
" - Gomory - on a une solution entiere \n");
211 sys = som_sys_conv(sys1);
220 if (
plint_degen(&sys1,fonct,nb_som,lvbase,nbvars,b) ==
false)
225 printf (
" - Gomory - on a une solution reelle \n");
226 sys = som_sys_conv(sys1);
240 printf (
" - Gomory - on a une solution \n");
245 else printf (
" - Gomory - le systeme est non realisable - fin !!\n");
252 printf (
" - Gomory - on a une solution optimale \n");
253 sys = som_sys_conv(sys1);
261 printf (
" - Gomory - pas de sol. reelle ==> pas de sol. entiere \n");
311 printf(
" ** Gomory - cas de degenerescence \n");
317 for (pv= *lvbase;pv!=NULL;pv=pv->
succ)
337 for (pv= lvhb_de_cnnul;pv!=NULL;pv=pv->
succ)
342 fonct2->
eq_sat = (
int *)
MALLOC(
sizeof(
int),INTEGER,
"plint_degen");
348 sys1 =
plint_pas(sys1,fonct2,lvbase,nb_som,nbvars,b);
353 printf (
" -- Gomory degen. - le pb. a une sol. optimale \n ");
367 eq_for_ndegen =
vect_dup(lvhb_de_cnnul);
368 for (pv = eq_for_ndegen; pv!= NULL; pv = pv->
succ)
372 eq_coupe->
vecteur = eq_for_ndegen;
373 eq_coupe->
eq_sat = (
int *)
MALLOC(
sizeof(
int),INTEGER,
"plint_degen");
384 if (var_entrant != NULL)
387 pivoter (*sys,eq_coupe,var_entrant,fonct);
394 printf (
" -- Gomory degen. - le pb. n'est pas borne \n");
446 printf(
" * algorithme des congruences decroissantes global \n");
447 printf (
" - GOMORY - le nb. de variables du systeme est %d \n",first_sys->dimension);
450 nbvars = first_sys->dimension;
454 if ((first_sys->egalites != NULL) || (first_sys->inegalites != NULL))
459 sys1 = sys_som_conv(sys2,&nb_som);
462 printf (
" - GOMORY - le nb. de contraintes est %d \n",nb_som);
470 sys1 =
plint_pas(sys1,fonct,&lvbase,&nb_som,&nbvars,&b);
476 for (sol = *sol_fin; sol != NULL; sol = sol->
succ)
484 if (sys1 == NULL && fonct != NULL) fonct->
vecteur = NULL;
486 if ((syst_res = som_sys_conv(sys1)) != NULL) {
#define value_uminus(val)
unary operators on values
#define VALUE_TO_DOUBLE(val)
#define value_zero_p(val)
#define value_div(v1, v2)
char * noms_var(entity e)
comp_expr_to_pnome.c
Variable var_pivotd(Psommet eq, Psommet fonct)
int var_pivotd(Psommet eq, Psommet fonct): recherche de la nouvelle variable pivot entrant dans la ba...
Psommet ligne_pivot(Psommet sys, int nb_som, no_som)
Psommet ligne_pivot(Psommet sys, int nb_som, int * no_som): recherche de la ligne pivot dans l'algori...
bool dual_pivot_pas(Psommet *sys, Pvecteur *lvbase, int nb_som, Psommet fonct, int *nbvars, Pbase *b)
bool dual_pivot_pas(Psommet * sys, Pvecteur * lvbase, int nb_som, Psommet fonct, int * nbvars,...
Psommet gomory_trait_eq(Psommet eq, Variable var)
Psommet gomory_trait_eq(Psommet eq, Variable var): Cette fonction utilise une contrainte du systeme e...
Psommet gomory_eq(Psommet *sys, Pvecteur lvbase, int nb_som, int *no_som, Variable *var)
Psommet gomory_eq(Psommet *sys, Pvecteur lvbase, int nb_som, int * no_som, Variable * var): Recherche...
#define MALLOC(s, t, f)
package plint
bool plint_degen(Psommet *sys, Psommet fonct, int *nb_som, Pvecteur *lvbase, int *nbvars, Pbase *b)
void plint_degen(Psommet *sys, Psommet fonct, int *nb_som, Pvecteur * lvbase, int nbvars,...
Psommet plint_pas(Psommet sys1, Psommet fonct, Pvecteur *lvbase, int *nb_som, int *nbvars, Pbase *b)
Psommet plint_pas(Psommet sys1, Psommet fonct, Pvecteur * lvbase, int * nb_som, int * nbvars,...
Psysteme plint(Psysteme first_sys, Psommet fonct, Psolution *sol_fin)
Psysteme plint(Psysteme first_sys, Psommet fonct, Psolution *sol_fin): resolution d'un systeme lineai...
void pivoter(Psommet sys, Psommet ligne, Variable var, Psommet fonct)
Psommet primal_pivot(Psommet sys, Pvecteur *lvbase, int nb_som, Psommet fonct)
Psommet primal_pivot(Psommet sys, Pvecteur * lvbase, int nb_som, Psommet fonct): algorithme primal du...
bool sol_entiere(Psommet sys, Pvecteur lvbase, int nb_som)
bool sol_entiere(Psommet sys, Pvecteur lvbase, int nb_som): Cette fonction teste si la solution est e...
bool sol_positive(Psommet sys, Pvecteur lvbase, int nb_som)
bool sol_positive(Psommet sys, Pvecteur lvbase, int nb_som): Cette fonction teste si la solution est ...
Psolution sol_finale(Psommet sys, Pvecteur lvbase, int nb_som)
Psolution sol_finale(Psommet sys, Pvecteur lvbase, int nb_som): Calcul de la solution finale du progr...
Psommet sommets_dupc(Psommet som)
Psommet sommets_dupc(Psommet som): copie d'une liste de sommets tout en respectant le meme ordre.
bool cout_nul(Psommet fonct, Pvecteur lvbase, int nbvars, Pbase b)
bool const_negative(Psommet som)
Psommet eq_in_ineq(Psommet *sys, int *nb_som, Pvecteur *lvbase)
Psommet eq_in_ineq(Psommet * sys, int * nb_som, Pvecteur * lvbase): Transformation des egalites du sy...
Psommet var_ecart_sup(Psommet sys, int nb_som, Pvecteur *lvbase, int *nbvars, Pbase *b)
Psommet var_ecart_sup(Psommet sys, int nb_som, Pvecteur * lvbase, int * nbvars, Pbase *b): ajout des ...
void lvbase_ote_no_ligne(int no_ligne, Pvecteur *lvbase)
void lvbase_ote_no_ligne(int no_ligne, Pvecteur * lvbase): Elimination de la variable de base corresp...
void lvbase_add(Variable var, int no_ligne, Pvecteur *lvbase)
void lvbase_add(Variable var, int no_ligne, Pvecteur * lvbase): ajout d'un couple (variable de base,...
void oter_lvbase(Psommet sys, Pvecteur lvbase)
void oter_lvbase(Psommet sys, Pvecteur lvbase): Elimination d'une liste de variables contenues dans u...
bool syst_smith(Psysteme ps)
bool syst_smith(Psysteme ps): Test de faisabilite d'un systeme lineaire en nombres entiers positifs p...
void sc_rm(Psysteme ps)
void sc_rm(Psysteme ps): liberation de l'espace memoire occupe par le systeme de contraintes ps;
Psysteme sc_dup(Psysteme ps)
Psysteme sc_dup(Psysteme ps): should becomes a link.
void sc_fprint(FILE *fp, Psysteme ps, get_variable_name_t nom_var)
void sc_fprint(FILE * f, Psysteme ps, char * (*nom_var)()): cette fonction imprime dans le fichier po...
Psysteme sc_normalize(Psysteme ps)
Psysteme sc_normalize(Psysteme ps): normalisation d'un systeme d'equation et d'inequations lineaires ...
struct typ_som * Psommet
structure de donnees Sommet
#define SOMMET
package sommet: structure de donnees representant les sommets d'un systeme generateur; elle contient:
void sommet_add(Psommet *ps, Psommet som, int *nb_som)
void sommet_add(Psommet *ps, Psommet som, int *nb_soms): Ajout d'un sommet a une liste de sommets Le ...
void sommets_rm(Psommet)
void sommets_rm(Psommet ps): liberation de l'espace memoire alloue a une liste de sommets
Value val
valeur de la variable
struct Ssolution * succ
pointeur vers la variable suivante
Value denominateur
denominateur de la valeur de la variable
Variable var
variable du systeme
le type des coefficients dans les vecteurs: Value est defini dans le package arithmetique
structure de donnees Sommet
#define TCST
VARIABLE REPRESENTANT LE TERME CONSTANT.
#define VECTEUR_NUL
DEFINITION DU VECTEUR NUL.
void * Variable
arithmetique is a requirement for vecteur, but I do not want to inforce it in all pips files....
#define BASE_NULLE
MACROS SUR LES BASES.
Pvecteur vect_dup(Pvecteur v_in)
Pvecteur vect_dup(Pvecteur v_in): duplication du vecteur v_in; allocation de et copie dans v_out;.
Pbase base_dup(Pbase b)
Pbase base_dup(Pbase b) Note: this function changes the value of the pointer.
Pvecteur vect_new(Variable var, Value coeff)
Pvecteur vect_new(Variable var,Value coeff): allocation d'un vecteur colineaire au vecteur de base va...
void vect_rm(Pvecteur v)
void vect_rm(Pvecteur v): desallocation des couples de v;
void vect_add_elem(Pvecteur *pvect, Variable var, Value val)
void vect_add_elem(Pvecteur * pvect, Variable var, Value val): addition d'un vecteur colineaire au ve...
Value vect_coeff(Variable var, Pvecteur vect)
Variable vect_coeff(Variable var, Pvecteur vect): coefficient de coordonnee var du vecteur vect —> So...
void vect_chg_coeff(Pvecteur *ppv, Variable var, Value val)
void vect_chg_coeff(Pvecteur *ppv, Variable var, Value val): mise de la coordonnee var du vecteur *pp...