PIPS
|
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <limits.h>
#include "boolean.h"
#include "arithmetique.h"
#include "linear_assert.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"
Go to the source code of this file.
Data Structures | |
struct | hashtable_t |
this is already too much... More... | |
Macros | |
#define | DEBUG(code) { } |
debug macros may be trigered with -DDEBUG{,1,2} More... | |
#define | DEBUG1(code) { } |
#define | DEBUG2(code) { } |
#define | DEBUG3(code) { } |
#define | DIMENSION sc->dimension |
#define | NUMERO hashtable[h].numero |
#define | SOLUBLE(N) soluble=N;goto FINSIMPLEX ; |
#define | CREVARVISIBLE variables[compteur-3]=compteur-2; |
#define | CREVARCACHEE |
#define | tag(x) /**printf(x); */ |
for tracing macros after expansion: More... | |
#define | G(j, a, b) |
maybe most of them should be functions? More... | |
#define | GCD(j, a, b) |
#define | GCDZZN(j, a, b) |
#define | GCD_ZERO_CTRL(j, a, b) |
#define | SIMPL(a, b) |
SIMPL normalizes rational a/b (b<>0): divides by gcd(a,b) and returns with b>0 note that there should be no arithmetic exceptions within this macro: (well, only uminus may have trouble for VALUE_MIN...) ??? a==0 ? then a = a/b = 0 and b = b/b = 1. More... | |
#define | SIMPLIFIE(f) |
SIMPLIFIE normalizes fraction f. More... | |
#define | AFF(x, y) {x.num=y.num; x.den=y.den;} /**x=y should be ok:-) */ |
#define | AFF_PX(x, y) {x->num=y.num; x->den=y.den;} |
#define | INV(x, y) {x.num=y.den; x.den=y.num;} /**x=1/y */ |
#define | INV_ZERO_CTRL(x, y) {if (value_zero_p(y.num)) {fprintf(stderr,"ERROR : inverse of fraction zero !"); x.num = VALUE_ZERO; x.den = VALUE_ONE;} else {INV(x,y)}} |
??? value_zero_p(y.num)? Then x.num != VALUE_ZERO and x.den = VALUE_ZERO, it's not good at all. More... | |
#define | METINFINI(f) {f.num=VALUE_MAX; f.den=VALUE_ONE;} |
#define | MET_ZERO(f) {f.num=VALUE_ZERO; f.den=VALUE_ONE;} |
#define | MET_UN(f) {f.num=VALUE_ONE; f.den=VALUE_ONE;} |
#define | EGAL1(x) (value_eq(x.num,x.den)) |
#define | EGAL0(x) (value_zero_p(x.num)) |
#define | NUL(x) (value_zero_p(x.num)) |
#define | NEGATIF(x) |
#define | POSITIF(x) |
#define | SUP1(x) |
#define | EGAL_MACRO(x, y, mult) |
#define | INF_MACRO(x, y, mult) ((value_pos_p(mult(x.den,y.den)) && value_lt(mult(x.num,y.den),mult(x.den,y.num))) || (value_neg_p(mult(x.den,y.den)) && value_gt(mult(x.num,y.den),mult(x.den,y.num)))) |
define INF_MACRO(x,y,mult) (value_lt(mult(x.num,y.den),mult(x.den,y.num))) DN: c'est pas assez pour la comparaison entre deux fractions, qu'est-ce qui se passe s'il y a seulement un denominateur negatif??? Ca donnera un resultat faux. More... | |
#define | DIV_MACRO(x, y, z, mult) |
computes x = simplify(y/z) More... | |
#define | MUL_MACRO(x, y, z, mult) |
computes x = simplify(y*z) More... | |
#define | SUB_MACRO(X, A, B, mult) |
computes X = simplify(A-B) More... | |
#define | FULL_PIVOT_MACRO_SIOUX(X, A, B, C, D, mult) |
computes X = A - B*C/D, trying to avoid arithmetic exceptions... More... | |
#define | FULL_PIVOT_MACRO_DIRECT(X, A, B, C, D, mult) |
computes X = A - B*C/D, but does not try to avoid arithmetic exceptions More... | |
#define | direct_p(v) (value_lt(v,MAXVAL)) |
#define | FULL_PIVOT_MACRO(X, A, B, C, D, mult) |
computes X = A - B*C/D, with a switch to use SIOUX or DIRECT thae rationale for the actual condition is quite fuzzy. More... | |
#define | PARTIAL_PIVOT_MACRO_SIOUX(X, B, C, D, mult) |
idem if A==0 More... | |
#define | PARTIAL_PIVOT_MACRO_DIRECT(X, B, C, D, mult) |
#define | PARTIAL_PIVOT_MACRO(X, B, C, D, mult) |
#define | PIVOT_MACRO(X, A, B, C, D, mult) |
Pivot : x = a - b c / d mult is used for multiplying values. More... | |
#define | value_protected_mult(v, w) value_protected_multiply(v,w,THROW(simplex_arithmetic_error)) |
multiplies two Values of no arithmetic overflow, or throw exception. More... | |
#define | MULT(RES, A, B) RES=value_mult(A,B) |
Version with and without arithmetic exceptions... More... | |
#define | MULTOFL(RES, A, B) RES=value_protected_mult(A,B) |
#define | DIV(x, y, z) DIV_MACRO(x,y,z,value_mult) |
#define | DIVOFL(x, y, z) DIV_MACRO(x,y,z,value_protected_mult) |
#define | MUL(x, y, z) MUL_MACRO(x,y,z,value_mult) |
#define | MULOFL(x, y, z) MUL_MACRO(x,y,z,value_protected_mult) |
#define | SUB(X, A, B) SUB_MACRO(X,A,B,value_mult) |
#define | SUBOFL(X, A, B) SUB_MACRO(X,A,B,value_protected_mult) |
#define | PIVOT(X, A, B, C, D) PIVOT_MACRO(X,A,B,C,D,value_mult) |
#define | PIVOTOFL(X, A, B, C, D) PIVOT_MACRO(X,A,B,C,D,value_protected_mult) |
#define | EGAL(x, y) EGAL_MACRO(x,y,value_mult) |
#define | EGALOFL(x, y) EGAL_MACRO(x,y,value_protected_mult) |
#define | INF(x, y) INF_MACRO(x,y,value_mult) |
#define | INFOFL(x, y) INF_MACRO(x,y,value_protected_mult) |
Enumerations | |
enum | { PTR_NIL = INTPTR_MIN+767 , INFINI = INTPTR_MAX-767 , MAX_VAR = 1971 , MAXVAL = 24 } |
Hmmm. More... | |
Functions | |
void | frac_init (frac *f, int n) |
void | frac_simpl (Value *a, Value *b) |
void | frac_simplifie (frac *f) |
simplifie normalizes fraction f More... | |
void | frac_div (frac *x, frac y, frac z, bool ofl_ctrl) |
void | frac_mul (frac *x, frac y, frac z, bool ofl_ctrl) |
computes x = simplify(y*z) More... | |
void | frac_sub (frac *X, frac A, frac B, bool ofl_ctrl) |
void | full_pivot_sioux (frac *X, frac A, frac B, frac C, frac D, bool ofl_ctrl) |
void | full_pivot_direct (frac *X, frac A, frac B, frac C, frac D, bool ofl_ctrl) |
computes X = A - B*C/D, but does not try to avoid arithmetic exceptions More... | |
void | full_pivot (frac *X, frac A, frac B, frac C, frac D, bool ofl_ctrl) |
void | partial_pivot_sioux (frac *X, frac B, frac C, frac D, bool ofl_ctrl) |
idem if A==0 More... | |
void | partial_pivot_direct (frac *X, frac B, frac C, frac D, bool ofl_ctrl) |
void | partial_pivot (frac *X, frac B, frac C, frac D, bool ofl_ctrl) |
void | pivot (frac *X, frac A, frac B, frac C, frac D, bool ofl_ctrl) |
static void | __attribute__ ((unused)) |
For debugging: More... | |
static void | printfrac (frac x) |
static int | hash (Variable s) |
dump_tableau More... | |
bool | sc_simplex_feasibility_ofl_ctrl_fixprec (Psysteme sc, int ofl_ctrl) |
fonction de calcul de la faisabilite' d'un systeme d'equations et d'inequations Auteur : Robert Mahl, Date : janvier 1994 More... | |
Variables | |
static int | NB_EQ = 0 |
test du simplex : Si on compile grace a` "make simp" dans le repertoire /projects/C3/Linear/Development/polyedre/Tests alors on peut tester l'execution dans le meme directory en faisant : make test_simp More... | |
static int | NB_INEQ = 0 |
static frac | frac0 ={(Value)0,(Value)1,0} |
static int | nbvariables |
Le nombre de variables visibles est : compteur-2 La i-eme variable visible a le numero : variables[i+1]=i (0 <= i < compteur-2) Le nombre de variables cachees est : nbvarables La i-eme variable cachee a le numero : variablescachees[i+1]=MAX_VAR+i-1 (0 <= i < nbvariables) More... | |
static int | variablescachees [MAX_VAR] |
static int | variables [MAX_VAR] |
Definition at line 224 of file sc_simplex_feasibility_fixprec.c.
Definition at line 225 of file sc_simplex_feasibility_fixprec.c.
#define CREVARCACHEE |
Definition at line 122 of file sc_simplex_feasibility_fixprec.c.
#define CREVARVISIBLE variables[compteur-3]=compteur-2; |
Definition at line 121 of file sc_simplex_feasibility_fixprec.c.
#define DEBUG | ( | code | ) | { } |
debug macros may be trigered with -DDEBUG{,1,2}
Definition at line 61 of file sc_simplex_feasibility_fixprec.c.
#define DEBUG1 | ( | code | ) | { } |
Definition at line 68 of file sc_simplex_feasibility_fixprec.c.
#define DEBUG2 | ( | code | ) | { } |
Definition at line 75 of file sc_simplex_feasibility_fixprec.c.
#define DEBUG3 | ( | code | ) | { } |
Definition at line 82 of file sc_simplex_feasibility_fixprec.c.
#define DIMENSION sc->dimension |
Definition at line 118 of file sc_simplex_feasibility_fixprec.c.
Definition at line 393 of file sc_simplex_feasibility_fixprec.c.
#define DIV | ( | x, | |
y, | |||
z | |||
) | DIV_MACRO(x,y,z,value_mult) |
Definition at line 491 of file sc_simplex_feasibility_fixprec.c.
#define DIV_MACRO | ( | x, | |
y, | |||
z, | |||
mult | |||
) |
computes x = simplify(y/z)
define DIV_MACRO(x,y,z,mult) \ {tag("DIV_MACRO") \ if (value_zero_p(y.num)) \ { \ MET_ZERO(x); \ } \ else \ { \ x.num=mult(y.num,z.den); \ x.den=mult(y.den,z.num); \ SIMPLIFIE(x); \ } \ } DN: This macro DIV_MACRO doesn't test if z = 0, then x = y/z means x.num = y.num*z.den and x.den = 0. We better add the test : if z = 0 then x.num = 0 and x.den = 1 We try to avoid the denominator equal to 0.
Definition at line 292 of file sc_simplex_feasibility_fixprec.c.
#define DIVOFL | ( | x, | |
y, | |||
z | |||
) | DIV_MACRO(x,y,z,value_protected_mult) |
Definition at line 492 of file sc_simplex_feasibility_fixprec.c.
#define EGAL | ( | x, | |
y | |||
) | EGAL_MACRO(x,y,value_mult) |
Definition at line 503 of file sc_simplex_feasibility_fixprec.c.
#define EGAL0 | ( | x | ) | (value_zero_p(x.num)) |
Definition at line 240 of file sc_simplex_feasibility_fixprec.c.
Definition at line 239 of file sc_simplex_feasibility_fixprec.c.
#define EGAL_MACRO | ( | x, | |
y, | |||
mult | |||
) |
Definition at line 255 of file sc_simplex_feasibility_fixprec.c.
#define EGALOFL | ( | x, | |
y | |||
) | EGAL_MACRO(x,y,value_protected_mult) |
Definition at line 504 of file sc_simplex_feasibility_fixprec.c.
computes X = A - B*C/D, with a switch to use SIOUX or DIRECT thae rationale for the actual condition is quite fuzzy.
Definition at line 398 of file sc_simplex_feasibility_fixprec.c.
computes X = A - B*C/D, but does not try to avoid arithmetic exceptions
Definition at line 377 of file sc_simplex_feasibility_fixprec.c.
computes X = A - B*C/D, trying to avoid arithmetic exceptions...
Definition at line 361 of file sc_simplex_feasibility_fixprec.c.
#define G | ( | j, | |
a, | |||
b | |||
) |
maybe most of them should be functions?
G computes j=gcd(a,b) assuming b>0 and better with a>b. there can be no artihmetic errors.
Definition at line 136 of file sc_simplex_feasibility_fixprec.c.
#define GCD | ( | j, | |
a, | |||
b | |||
) |
Definition at line 149 of file sc_simplex_feasibility_fixprec.c.
#define GCD_ZERO_CTRL | ( | j, | |
a, | |||
b | |||
) |
Definition at line 181 of file sc_simplex_feasibility_fixprec.c.
#define GCDZZN | ( | j, | |
a, | |||
b | |||
) |
Definition at line 172 of file sc_simplex_feasibility_fixprec.c.
#define INF | ( | x, | |
y | |||
) | INF_MACRO(x,y,value_mult) |
Definition at line 506 of file sc_simplex_feasibility_fixprec.c.
#define INF_MACRO | ( | x, | |
y, | |||
mult | |||
) | ((value_pos_p(mult(x.den,y.den)) && value_lt(mult(x.num,y.den),mult(x.den,y.num))) || (value_neg_p(mult(x.den,y.den)) && value_gt(mult(x.num,y.den),mult(x.den,y.num)))) |
define INF_MACRO(x,y,mult) (value_lt(mult(x.num,y.den),mult(x.den,y.num))) DN: c'est pas assez pour la comparaison entre deux fractions, qu'est-ce qui se passe s'il y a seulement un denominateur negatif??? Ca donnera un resultat faux.
a/b < c/d <=> if b*d > 0 then a*d < b*c else a*d < b*c
Definition at line 266 of file sc_simplex_feasibility_fixprec.c.
#define INFOFL | ( | x, | |
y | |||
) | INF_MACRO(x,y,value_protected_mult) |
Definition at line 507 of file sc_simplex_feasibility_fixprec.c.
Definition at line 226 of file sc_simplex_feasibility_fixprec.c.
#define INV_ZERO_CTRL | ( | x, | |
y | |||
) | {if (value_zero_p(y.num)) {fprintf(stderr,"ERROR : inverse of fraction zero !"); x.num = VALUE_ZERO; x.den = VALUE_ONE;} else {INV(x,y)}} |
??? value_zero_p(y.num)? Then x.num != VALUE_ZERO and x.den = VALUE_ZERO, it's not good at all.
(assuming y.den != VALUE_ZERO) This means : test if y = 0 then x = 0 else x = 1/y Change in line 286 : DN.
Definition at line 232 of file sc_simplex_feasibility_fixprec.c.
Definition at line 237 of file sc_simplex_feasibility_fixprec.c.
#define MET_ZERO | ( | f | ) | {f.num=VALUE_ZERO; f.den=VALUE_ONE;} |
Definition at line 236 of file sc_simplex_feasibility_fixprec.c.
Definition at line 235 of file sc_simplex_feasibility_fixprec.c.
#define MUL | ( | x, | |
y, | |||
z | |||
) | MUL_MACRO(x,y,z,value_mult) |
Definition at line 494 of file sc_simplex_feasibility_fixprec.c.
#define MUL_MACRO | ( | x, | |
y, | |||
z, | |||
mult | |||
) |
computes x = simplify(y*z)
Definition at line 317 of file sc_simplex_feasibility_fixprec.c.
#define MULOFL | ( | x, | |
y, | |||
z | |||
) | MUL_MACRO(x,y,z,value_protected_mult) |
Definition at line 495 of file sc_simplex_feasibility_fixprec.c.
#define MULT | ( | RES, | |
A, | |||
B | |||
) | RES=value_mult(A,B) |
Version with and without arithmetic exceptions...
Definition at line 488 of file sc_simplex_feasibility_fixprec.c.
#define MULTOFL | ( | RES, | |
A, | |||
B | |||
) | RES=value_protected_mult(A,B) |
Definition at line 489 of file sc_simplex_feasibility_fixprec.c.
#define NEGATIF | ( | x | ) |
Definition at line 243 of file sc_simplex_feasibility_fixprec.c.
#define NUL | ( | x | ) | (value_zero_p(x.num)) |
Definition at line 241 of file sc_simplex_feasibility_fixprec.c.
#define NUMERO hashtable[h].numero |
Definition at line 119 of file sc_simplex_feasibility_fixprec.c.
#define PIVOT | ( | X, | |
A, | |||
B, | |||
C, | |||
D | |||
) | PIVOT_MACRO(X,A,B,C,D,value_mult) |
Definition at line 500 of file sc_simplex_feasibility_fixprec.c.
Pivot : x = a - b c / d mult is used for multiplying values.
the macro has changed a lot, for indentation and so... FC. DN: Why don't we test d.num = 0 ? (meanwhile, we do test d.den = 0)
Definition at line 449 of file sc_simplex_feasibility_fixprec.c.
#define PIVOTOFL | ( | X, | |
A, | |||
B, | |||
C, | |||
D | |||
) | PIVOT_MACRO(X,A,B,C,D,value_protected_mult) |
Definition at line 501 of file sc_simplex_feasibility_fixprec.c.
#define POSITIF | ( | x | ) |
Definition at line 247 of file sc_simplex_feasibility_fixprec.c.
#define SIMPL | ( | a, | |
b | |||
) |
SIMPL normalizes rational a/b (b<>0): divides by gcd(a,b) and returns with b>0 note that there should be no arithmetic exceptions within this macro: (well, only uminus may have trouble for VALUE_MIN...) ??? a==0 ? then a = a/b = 0 and b = b/b = 1.
Definition at line 197 of file sc_simplex_feasibility_fixprec.c.
#define SIMPLIFIE | ( | f | ) |
SIMPLIFIE normalizes fraction f.
Definition at line 213 of file sc_simplex_feasibility_fixprec.c.
#define SOLUBLE | ( | N | ) | soluble=N;goto FINSIMPLEX ; |
Definition at line 120 of file sc_simplex_feasibility_fixprec.c.
Definition at line 497 of file sc_simplex_feasibility_fixprec.c.
computes X = simplify(A-B)
Definition at line 331 of file sc_simplex_feasibility_fixprec.c.
Definition at line 498 of file sc_simplex_feasibility_fixprec.c.
#define SUP1 | ( | x | ) |
Definition at line 251 of file sc_simplex_feasibility_fixprec.c.
for tracing macros after expansion:
Definition at line 127 of file sc_simplex_feasibility_fixprec.c.
#define value_protected_mult | ( | v, | |
w | |||
) | value_protected_multiply(v,w,THROW(simplex_arithmetic_error)) |
multiplies two Values of no arithmetic overflow, or throw exception.
this version is local to the simplex. note that under some defined macros value_mult can expand to value_protected_mult, which would be ok.
Definition at line 483 of file sc_simplex_feasibility_fixprec.c.
anonymous enum |
Hmmm.
To be compatible with some weird old 16-bit constants... RK
Enumerator | |
---|---|
PTR_NIL | |
INFINI | |
MAX_VAR | |
MAXVAL | nombre max de variables seuil au dela duquel on se mefie d'un overflow |
Definition at line 104 of file sc_simplex_feasibility_fixprec.c.
|
static |
For debugging:
Definition at line 812 of file sc_simplex_feasibility_fixprec.c.
References MAX_VAR, print_Value(), printf(), and VARIABLE_DEFINED_P.
Definition at line 567 of file sc_simplex_feasibility_fixprec.c.
References frac::den, fprintf(), frac_simplifie(), FWD_OFL_CTRL, MET_ZERO, frac::num, tag, value_mult, value_protected_mult, value_zero_p, and x.
Referenced by partial_pivot_sioux(), and sc_simplex_feasibility_ofl_ctrl_fixprec().
Definition at line 523 of file sc_simplex_feasibility_fixprec.c.
References f().
Referenced by sc_simplex_feasibility_ofl_ctrl_fixprec().
computes x = simplify(y*z)
Definition at line 598 of file sc_simplex_feasibility_fixprec.c.
References frac::den, frac_simplifie(), FWD_OFL_CTRL, MET_ZERO, frac::num, tag, value_mult, value_protected_mult, value_zero_p, and x.
Referenced by partial_pivot_sioux().
Definition at line 533 of file sc_simplex_feasibility_fixprec.c.
References ABS, value_division, value_neg_p, value_notmone_p, value_notone_p, value_oppose, and VALUE_TO_LONG.
Referenced by frac_simplifie(), and full_pivot_sioux().
void frac_simplifie | ( | frac * | f | ) |
simplifie normalizes fraction f
Definition at line 553 of file sc_simplex_feasibility_fixprec.c.
References f(), frac_simpl(), MET_ZERO, tag, VALUE_ONE, and value_zero_p.
Referenced by frac_div(), frac_mul(), frac_sub(), full_pivot_direct(), partial_pivot_direct(), and sc_simplex_feasibility_ofl_ctrl_fixprec().
must compute the stuff:
Definition at line 615 of file sc_simplex_feasibility_fixprec.c.
References AFF_PX, B, frac_simplifie(), FWD_OFL_CTRL, GCD_ZERO_CTRL, tag, value_division, value_eq, value_minus, value_mult, value_notone_p, value_protected_mult, value_substract, value_uminus, value_zero_p, and X.
Referenced by full_pivot_sioux().
Definition at line 710 of file sc_simplex_feasibility_fixprec.c.
References B, D, frac::den, direct_p, full_pivot_direct(), full_pivot_sioux(), tag, value_abs, and X.
Referenced by pivot().
computes X = A - B*C/D, but does not try to avoid arithmetic exceptions
Definition at line 681 of file sc_simplex_feasibility_fixprec.c.
References B, D, frac::den, frac_simplifie(), FWD_OFL_CTRL, frac::num, tag, value_mult, value_protected_mult, value_substract, and X.
Referenced by full_pivot().
u*v*w == B*C/D
u*=v
u*=w
u*=v
u*=w
Definition at line 652 of file sc_simplex_feasibility_fixprec.c.
References AFF, B, D, frac::den, frac_simpl(), frac_sub(), FWD_OFL_CTRL, INV_ZERO_CTRL, frac::num, tag, value_mult, value_protected_mult, and X.
Referenced by full_pivot().
dump_tableau
calcule le hashcode d'un pointeur sous forme d'un nombre compris entre 0 et MAX_VAR
Definition at line 867 of file sc_simplex_feasibility_fixprec.c.
References MAX_VAR.
Referenced by sc_min(), and sc_simplex_feasibility_ofl_ctrl_fixprec().
Definition at line 755 of file sc_simplex_feasibility_fixprec.c.
References B, D, frac::den, direct_p, partial_pivot_direct(), partial_pivot_sioux(), and X.
Referenced by pivot().
Definition at line 736 of file sc_simplex_feasibility_fixprec.c.
References B, D, frac::den, frac_simplifie(), FWD_OFL_CTRL, frac::num, tag, value_mult, value_oppose, value_protected_mult, and X.
Referenced by partial_pivot().
idem if A==0
u=simplify(b*c)
x=simplify(u/d)
x=-x
Definition at line 726 of file sc_simplex_feasibility_fixprec.c.
References B, D, frac_div(), frac_mul(), tag, value_oppose, and X.
Referenced by partial_pivot().
a==0?
b*c/d != 0, calculons!
a!=0
b*c/d != 0, calculons!
no den to compute
well, we must compute the full formula!
Definition at line 770 of file sc_simplex_feasibility_fixprec.c.
References AFF_PX, B, D, DEBUG3, frac::den, fprintf(), full_pivot(), FWD_OFL_CTRL, MET_ZERO, frac::num, partial_pivot(), printfrac(), value_minus, value_mult, VALUE_ONE, value_one_p, value_protected_mult, value_zero_p, and X.
Referenced by choisir_piv(), dualentier(), gauss(), iprimal(), is2(), pivoter(), sc_min(), sc_simplex_feasibility_ofl_ctrl_fixprec(), simbad(), simplexe(), and simplexedual().
|
static |
Definition at line 832 of file sc_simplex_feasibility_fixprec.c.
References print_Value(), printf(), and x.
Referenced by pivot(), sc_min(), and sc_simplex_feasibility_ofl_ctrl_fixprec().
fonction de calcul de la faisabilite' d'un systeme d'equations et d'inequations Auteur : Robert Mahl, Date : janvier 1994
Retourne : 1 si le systeme est soluble (faisable) en rationnels, 0 s'il n'y a pas de solution.
overflow control : ofl_ctrl == NO_OFL_CTRL => no overflow control ofl_ctrl == FWD_OFL_CTRL
=> overflow control is made THROW(overflow_error,5) BC, 13/12/94
All the folowing automatic variables are used when coming back from longjmp (i.e. in a CATCH block) so they need to be declared volatile as specified by the documentation
tete de liste des noms de variables
Necessaire de declarer "hashtable" static pour initialiser tout automatiquement a` 0. Necessaire de chainer les enregistrements pour reinitialiser a 0 en sortie de la procedure.
tableau des inegalite's
les colonnes 0 et 1 sont reservees au terme const:
valeur retournee par feasible
objectif de max pour simplex : somme des (b2,c2) termes constants "inferieurs"
count number of calls of this function (at the beginning)
int soluble = 1;
N.
recompute the base so as to only allocate necessary columns some bases are quite large although all variables do not appear in actual contraints. The base is used to store all variants in preconditions for instance.
Allocation a priori du tableau des egalites. "eg" : tableau a "nb_eq" lignes et "dimension"+2 colonnes.
DEBUG(fprintf(stdout, "\n\n IN sc_simplexe_feasibility_ofl_ctrl:\n"); sc_fprint(stdout, sc, default_variable_to_string);)
c_default_dump_to_file(); print to file
the input Psysteme must be consistent; this is not the best way to do this; array bound checks should be added instead in proper places; no time to do it properly for the moment. BC.
Do not allocate place for NULL constraints
ifscdebug(2) { fprintf(stderr,"[sc_simplexe_feasibility_ofl_ctrl] arithmetic error\n"); }
restore initial base
ethrow whatever the exception is
HROW(user_exception_error);
need CATCH(user_exception_error) before calling sc_simplexe_feasibility)
if don't catch exception, then default is feasible
f (ofl_ctrl == FWD_OFL_CTRL)
HROW(overflow_error);
eturn true; default is feasible
of CATCH(simplex_arithmetic_error)
egin of TRY
Allocation a priori du tableau du simplex "t" par colonnes. Soit "dimension" le nombre de variables, la taille maximum du tableau est de (1 + nb_ineq) lignes et de (2 + dimension + nb_ineq + nb_eq) colonnes On y ajoute en fait le double du nombre d'egalite's. Ce tableau sera rempli de la facon suivante :
Initialisation de l'objectif
Entree des inegalites dans la table
skip if empty
val terme const
Creation de variable d'ecart ?
Mise a jour des colonnes 0 et 1
Element de poids M en 1ere colonne
Creation d'une colonne cachee
NON IMPLEMENTE'
Elimination de Gauss-Jordan dans le tableau "eg" Chaque variable a` eliminer est marquee eg[ ].existe = 2 Si le processus d'elimination ne revele pas d'impossibilite', il est suivi du processus d'elimination dans les inegalites.
FIN DE NON IMPLEMENTE'
SOLUTION PROVISOIRE Pour chaque egalite on introduit 2 inequations complementaires
Added by bc: do nothing for nul equalities
val terme const
Creation de variable d'ecart ?
Mise a jour des colonnes 0 et 1
Element de poids M en 1ere colonne
Creation d'une colonne cachee
Added by bc: do nothing for nul equalities
val terme const
Creation de variable d'ecart ?
Mise a jour des colonnes 0 et 1
Element de poids M en 1ere colonne
Creation d'une colonne cachee
FIN DE SOLUTION PROVISOIRE
Algorithme du simplexe - methode primale simple. L'objectif est d'etudier la faisabilite' d'un systeme de contraintes sans trouver l'optimum. Les contraintes ont la forme : a x <= b et d x = e La methode de resolution procede comme suit :
1) Creer un tableau a b d e Eliminer autant de variables que posible par Gauss-Jordan
2) Travailler sur les inegalites seulement. Poser x = x' - M 1 ou` 1 est le vecteur de chiffres 1. Les inequations prennent alors la forme : a1 x <= b1 + M c1 a2 x >= b2 + M c2 avec c1 et c2 positifs On introduit les variables d'ecart y (autant que d'inequations du 2eme type) et on cherche max{1(a2 x - y) | x,y >= 0 ; a1 x <= b1 + M c1 ; a2 x - y <= b2 + M c2} On cree donc le tableau : 0 0 1 a2 1 0 0 b1 c1 a1 0 I 0 b2 c2 a2 -I 0 I
On applique ensuite l'algorithme du simplex en se souvenant que c1 et c2 sont a multiplier par un infiniment grand. Si l'optimum est egal a (1 b2 , 1 c2), il y a une solution.
Structures de donnees : on travaille sur des tableaux de fractions rationnelles.
Recherche d'un nombre negatif 1ere ligne
Terminaison
Recherche de la ligne de pivot
si ii==-1, pas encore trouve, min{1,2} non valides...
computing rapport{1,2}
first assignment is forced
POSITIF(t[jj].colonne[i]))
it may skip over
Cas d'impossibilite'
Modification des numeros des variables
Pivot autour de la ligne ii / colonne jj Dans ce qui suit, j = colonne courante, k = numero element dans la nouvelle colonne qui remplacera la colonne j, cc = element (colonne j, ligne ii)
Remplir la derniere colonne temporaire de t qui contient un 1 en position ligne ii
N
0 en colonne j ligne t[jj].colonne[i1].numero
0 en col jj, ligne t[j].colonne[i].numero
Restauration des entrees vides de la table hashee
restore initial base
Definition at line 888 of file sc_simplex_feasibility_fixprec.c.
References AFF, assert, BASE_NULLE, base_rm, CATCH, col::colonne, CREVARCACHEE, CREVARVISIBLE, DEBUG, DEBUG1, DEBUG2, frac::den, DIMENSION, EGAL, Ssysteme::egalites, EGALOFL, col::existe, f2(), fprintf(), frac0, frac_div(), frac_init(), frac_simplifie(), free(), FWD_OFL_CTRL, hashtable_t::hash, hash(), Ssysteme::inegalites, INF, INFOFL, intptr_t, linear_assert, malloc(), MAX_VAR, NB_EQ, NB_INEQ, nbvariables, NEGATIF, hashtable_t::nom, frac::num, num, frac::numero, NUMERO, hashtable_t::numero, overflow_error, pivot(), POSITIF, printf(), printfrac(), PTR_NIL, RETHROW, sc_creer_base(), sc_default_dump(), sc_weak_consistent_p(), simplex_arithmetic_error, SOLUBLE, Scontrainte::succ, hashtable_t::succ, Svecteur::succ, col::taille, timeout_error, UNCATCH, hashtable_t::val, Svecteur::val, valeur(), value_addto, VALUE_MONE, VALUE_NAN, value_neg_p, value_notzero_p, VALUE_ONE, value_oppose, value_substract, value_uminus, VALUE_ZERO, value_zero_p, Svecteur::var, VARIABLE_DEFINED_P, VARIABLE_UNDEFINED, variables, variablescachees, vect_coeff(), vect_rm(), and Scontrainte::vecteur.
Referenced by sc_simplex_feasibility_ofl_ctrl().
Definition at line 508 of file sc_simplex_feasibility_fixprec.c.
Referenced by sc_min(), and sc_simplex_feasibility_ofl_ctrl_fixprec().
|
static |
test du simplex : Si on compile grace a` "make simp" dans le repertoire /projects/C3/Linear/Development/polyedre/Tests alors on peut tester l'execution dans le meme directory en faisant : make test_simp
To replace #define NB_EQ and #define NB_INEQ - BC, 2/4/96 - NB_EQ and NB_INEQ are initialized at the beginning of the main subroutine. they represent the number of non-NULL constraints in sc. This is useful to allocate the minimum amount of memory necessary.
Definition at line 53 of file sc_simplex_feasibility_fixprec.c.
Referenced by sc_simplex_feasibility_ofl_ctrl_fixprec().
|
static |
Definition at line 54 of file sc_simplex_feasibility_fixprec.c.
Referenced by sc_simplex_feasibility_ofl_ctrl_fixprec().
|
static |
Le nombre de variables visibles est : compteur-2 La i-eme variable visible a le numero : variables[i+1]=i (0 <= i < compteur-2) Le nombre de variables cachees est : nbvarables La i-eme variable cachee a le numero : variablescachees[i+1]=MAX_VAR+i-1 (0 <= i < nbvariables)
utilise'es par dump_tableau ; a rendre local
Definition at line 830 of file sc_simplex_feasibility_fixprec.c.
Referenced by sc_simplex_feasibility_ofl_ctrl_fixprec().
Definition at line 830 of file sc_simplex_feasibility_fixprec.c.
Referenced by build_and_test_dependence_context(), gfc2pips_namespace(), gfc2pips_vars_(), sc_restricted_to_variables_transitive_closure(), and sc_simplex_feasibility_ofl_ctrl_fixprec().
Definition at line 830 of file sc_simplex_feasibility_fixprec.c.
Referenced by sc_simplex_feasibility_ofl_ctrl_fixprec().