PIPS
|
Go to the source code of this file.
Macros | |
#define | FT RR->ftrace |
========================================================================= More... | |
#define | TRACE RR->ntrace |
#define | A(i, j) RR->a[i][j] |
#define | D RR->d |
#define | E RR->e |
#define | M1 RR->m |
#define | M2 RR->m2 |
#define | MB RR->mb |
#define | N1 RR->n |
#define | NB RR->nb |
#define | NP RR->np |
#define | J0 RR->j0 |
#define | TESTP RR->testp |
#define | DUAL RR->meth |
#define | COPIE RR->copie |
#define | BASE RR->base |
#define | COST RR->cost |
#define | RHS RR->rhs |
#define | VRESULT RR->vresult |
#define | ITER RR->iter |
#define | ITEMAX RR->tmax |
#define | X RR->x |
#define | PI RR->pi |
#define | B RR->b |
#define | G RR->g |
#define | INF RR->inf |
#define | CONORM(A) *(RR->pconor+A) |
#define | INFCOL(A) *(RR->pinfcolonn+A) |
#define | VRNUL VREPS |
#define | VARIABLELIBRE(v) v>NP && v<=N1 |
Functions | |
static float | absf (float vf) |
static int | fraction (struct rproblem *RR, float vf) |
static int | voir4 (struct rproblem *RR, int v, int i11, int j11) |
static int | voir (struct rproblem *RR, int v) |
fin voir More... | |
int | realsimplex (Prproblem RR) |
static void | norm (struct rproblem *RR) |
cette procedure normalise la fonction cout, calcule les valeurs des seconds membres resultant d'une normalisation du tableau a, ou effectue ces deux operations More... | |
void | elimination (Prproblem RR, int j1) |
fin norm() More... | |
static void | retrait (struct rproblem *RR, int i1) |
fin elimination More... | |
static void | reduction (struct rproblem *RR) |
fin retrait More... | |
static int | validite (struct rproblem *RR) |
fin reduction() More... | |
static void | precision (struct rproblem *RR, int i, int nx) |
fin validite More... | |
static void | precisioncolonne (struct rproblem *RR, int j, int mx) |
fin precision More... | |
static int | pivotage (struct rproblem *RR, int i1, int j1) |
fin precisioncolonne More... | |
static int | simplexe (struct rproblem *RR, int i2, int bphase2, int *pj1, int *pbool1) |
fin pivotage More... | |
static int | simplexedual (struct rproblem *RR, int j2, int bphase2, int *pi1, int *pbool1) |
fin simplexe More... | |
static int | simbad (struct rproblem *RR) |
fin simplexedual More... | |
#define FT RR->ftrace |
=========================================================================
SIMPLEXE for integer variables
ALL-INTEGER METHODS
Jean Claude SOGNO
Projet CHLOE – INRIA ROCQUENCOURT
Juin 1994
========================================================================= ========================================================================= Duong NGUYEN QUE
Adaption to abstract computation: janusvalue
CRI-ENSMP
=========================================================================
|
static |
Definition at line 51 of file r1.c.
Referenced by norm(), pivotage(), precision(), precisioncolonne(), simbad(), simplexe(), and simplexedual().
Definition at line 55 of file r1.c.
References RR.
Referenced by realsimplex().
|
static |
cette procedure normalise la fonction cout, calcule les valeurs des seconds membres resultant d'une normalisation du tableau a, ou effectue ces deux operations
Definition at line 271 of file r1.c.
References A, absf(), CONORM, COST, D, M1, N1, and RHS.
Referenced by array_indices_communication(), build_sc_with_several_uniform_ref(), call_rwt(), free_guards(), get_const_off(), initialize_offsets(), loop_index_in_several_indices(), simbad(), and supported_ref_p().
fin precisioncolonne
le pivotage de la matrice a s'effectue a partir de la ligne i1 et de la colonne j1. Les numeros de la variable d'ecart (basique) de la ligne i1, et de la variable independante (hors-base) de la colonne j1, contenus respectivement dans les tableaux g et b, sont permutes. Dans le cas de l'elimination d'une egalite, l'operation equivaut a chasser de la base une variable d'ecart identiquement nulle
les quantites inferieures en valeurs absolue a la tolerance correspondante sont annulees
Definition at line 428 of file r1.c.
References A, absf(), B, CONORM, D, G, INF, INFCOL, ITEMAX, ITER, J0, M1, MB, N1, NB, precision(), precisioncolonne(), RR, TESTP, voir4(), VREPS, VRESULT, and VRINS.
Referenced by simbad(), simplexe(), and simplexedual().
fin validite
Definition at line 383 of file r1.c.
References A, absf(), B, G, INF, J0, M2, N1, and RR.
Referenced by MAX_ROOM_NEEDED(), pivotage(), simbad(), and VASNPRINTF().
pconor utilise par macro CONORM
utilise par macro INFCOL
peut-etre a modifier 0.0000001 0.0000003
lse fprintf(FT,",memes colonnes" );
f (TESTP==0) fprintf(FT,", tests precision pousses\n" ); if (TESTP==1) fprintf(FT,", tests precision moyens\n" ); if (TESTP==2) fprintf(FT,", tests precision sommaires\n" ); if (TESTP>2) fprintf(FT,",sommaire,entiers inconnus\n");
9
variables rendues toutes >=0
f (simbad(RR)) return(VRESULT);
9
printf(FT,"x[%2d] =%9.3f\n",jj,X[jj] );
if (NP!=nvp)
9
examen si variables fractionnaires utilisation marginale
if (mx==M1)
AUX
RAI
f (TRACE) fprintf(FT,"\\end{document}\n");
Definition at line 152 of file r1.c.
References A, COPIE, DUAL, fprintf(), fraction(), FT, G, ITER, M1, M2, MB, N1, NB, NP, RMAXCOLONNES, RMAXLIGNES, RR, simbad(), TESTP, TRACE, voir(), VRBUG, VRCAL, VRDEB, VREPS, VRESULT, VRFIN, VRINF, VRINS, VRVID, and X.
Referenced by localnewrsimplex(), phase1(), and phase2().
fin retrait
cette procedure groupe les vecteurs provenant de l'elimination des egalites dans les colonnes NB+1 a n
Definition at line 336 of file r1.c.
References B, E, elimination(), G, M1, N1, retrait(), RR, and VARIABLELIBRE.
Referenced by simbad().
fin simplexedual
apres modification directe de la matrice
on donne aux inequations le meme sens et on se ramene eventuellement a un probleme de minimisation
normalisation des lignes
normalisation des colonnes
include "base.c"
reprendre ................................................
include "corh.c"
calcul de la ligne de la nouvelle fonction cout a l'aide de l'inverse de la base du systeme dual. pi est utilise comme tableau auxiliaire
calcul de la colonne des nouveaux seconds membres a l'aide de l'inverse de la base (systeme primal). x est utilise comme tableau auxiliaire
reprendre ................................................
elimination des egalites
la premiere variable libre possible est choisie d'autorite,signalee par pivot
l'equation est surabondante ou incompatible
l'equation surabondante est ignoree
l'equation est changee en inequation dont la variable d'ecart provient du vecteur j1, qui entre dans la base
le systeme auquel on s'est ramene ne comporte que des inequations, dont le nombre de variables est egal a NB. dans les colonnes NB+1 a n ont ete groupes les vecteurs provenant des pivotages effectues au cours des eliminations des egalites ces vecteurs ne sont pas detruits, car ils appartiennent a l'inverse de la base, utilisee dans les tests de precision, et eventuellement dans le calcul de la colonne des nouveaux seconds membres
traitement variables libres
la variable n'intervient pas dans le domaine mais si le cout relatif n'est pas nul, il ne pourra exister de solution finie
on fait entrer dans la base la variable libre la variable d'ecart resultante sera desormais ignoree
une premiere phase est necessaire. une (seule) variable artificielle est introduite dans le systeme au moyen de la colonne 0 du tableau a
fin de la premiere phase avec obtention d'une solution realisable
une (seule) variable artificielle est ajoutee au systeme dual au moyen de la ligne mb+1 du tableau a
ligne conservee uniquement pour tests de precision
il n'existe pas de solution realisable dans le domaine dual, mais on ignore si cela correspond a un polyedre vide ou a une solution infinie pour le probleme primal
Definition at line 614 of file r1.c.
References A, absf(), B, BASE, CONORM, COST, D, DUAL, E, elimination(), fprintf(), FT, G, INF, INFCOL, ITEMAX, ITER, J0, M1, M2, MB, N1, NB, norm(), NP, phase2(), PI, pivot(), pivotage(), precision(), precisioncolonne(), reduction(), retrait(), RHS, RR, simplexe(), simplexedual(), TESTP, TRACE, validite(), VARIABLELIBRE, voir(), VRCAL, VRESULT, VRFIN, VRINF, VRNUL, VRVID, and X.
Referenced by realsimplex().
fin pivotage
Cette procedure minimise le cout defini dans la ligne i2 (s'il s'agit du cout artificiel, il est represente en valeur opposee)
en phase 1, bphase2 est faux
fin i
fin j
si la variable artificielle quitte la base, on sort de la procedure simplexe
le cout minimum est atteint
on chasse la variable artificielle de la base
en phase 1 le booleen bool1 indique si le polyedre est vide
Definition at line 492 of file r1.c.
References A, absf(), D, J0, MB, NB, pivot(), pivotage(), RR, VRESULT, and VRINF.
Referenced by simbad().
|
static |
fin simplexe
cette procedure maximise dans le systeme dual soit le cout defini par la colonne des seconds membres (lorsque j2=0), soit le cout defini par la colonne j2
f (A(0,j)<0.0001) zeta=0; provisoire
printf(FT,"zetafoir d=%6.3f a=%15.9f\\\\\n",D[i],A(0,j)) ;
fin j
fin i
nulle ou non, la variable artificielle est chassee de la base duale
Definition at line 558 of file r1.c.
References A, absf(), D, J0, MB, NB, pivot(), pivotage(), RR, VRESULT, and VRVID.
Referenced by simbad().
fin reduction()
cette procedure verifie, lorsque la base est donnee ou lorsqu'on utilise une matrice des contraintes ayant deja pivote, que le tableau g ou que les tableaux g et b fournis sont compatibles
Definition at line 349 of file r1.c.
References B, COST, G, M1, N1, RHS, VRCAL, and VRESULT.
Referenced by simbad().
9
appel avant les initialisations
f(v==30){fprintf(FT,"pppivot\(%2d,%2d\):%6.3f",i11,j11,1/ A(i11,j11));
printf(FT,"d=%6.3f a=%15.9f\\\\\n",D[i11],A(0,j11)) ;*provisoire
9
Definition at line 62 of file r1.c.
References A, B, D, E, fprintf(), FT, G, ITER, M1, M2, MB, N1, NB, NP, and TRACE.
Referenced by pivotage(), and voir().