PIPS
Functions
sc_janus_feasibility.c File Reference
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "linear.h"
#include "janusvalue.h"
+ Include dependency graph for sc_janus_feasibility.c:

Go to the source code of this file.

Functions

static bool sc_to_iproblem (Psysteme sc, Pinitpb I, Pproblem Z, FILE *fdebug)
 This file provides functions to convert a system of constraints into format of Janus. More...
 
bool sc_janus_feasibility (Psysteme sc)
 

Function Documentation

◆ sc_janus_feasibility()

bool sc_janus_feasibility ( Psysteme  sc)

ttention with dimension=0

N janus should not be used here.

the third parameter means test only one time only I is initialized. Z is still empty

#define VRFIN 0 solution finie

#define VRVID 1 polyedre vide

#define VRINF 2 solution infinie

#define VRINS 3 nombre de pivotages insuffisant, bouclage possible

#define VRDEB 4 debordement de tableaux

#define VRCAL 5 appel errone

#define VRBUG 6 bug

#define VROVF 7 overflow

DN: In Solaris, we can fclose(NULL), but in LINUX, we cannot.

in case of failure then return r >=3 donnot want to use exception here, nor one more parameter, while wanting to keep return bool for compatibility. To be changed.

Definition at line 228 of file sc_janus_feasibility.c.

229 {
230 
231  FILE *fopen(), *fdebug;
232  initpb I;
233  problem Z;
234 
235  bool ok = false;
236  int r = 0;
237 
238  /**************** change format into Janus, using global struct iproblem */
239  ok = sc_to_iproblem(sc,&I,&Z,fdebug); /*Attention with dimension=0*/
240 
241  /**************** BEGIN execution simplexe entier classique */
242  if (ok) r = isolve(&I,&Z,0);
243  else r = 9;/*DN janus should not be used here.*/
244 
245  /* the third parameter means test only one time
246  only I is initialized. Z is still empty */
247  /*
248  if (r==VRFIN) printf("solution finie\n") ;
249  else if (r==VRVID) printf("polyedre vide\n") ;
250  else if (r==VRINF) printf("solution infinie\n") ;
251  else if (r==VRINS) printf("nombre insuffisant\n") ;
252  else if (r==VRDEB) printf("debordement tableaux\n") ;
253  else if (r==VRCAL) printf("some wrong parameter\n") ;
254  else if (r==VRBUG) printf("bug de programmation\n") ;
255  else if (r==VROVF) printf("data overflow\n") ;
256  else if (r==VREPS) printf("pivot anormalement petit\n") ;
257  */
258  /* #define VRFIN 0 solution finie */
259  /* #define VRVID 1 polyedre vide */
260  /* #define VRINF 2 solution infinie */
261  /* #define VRINS 3 nombre de pivotages insuffisant, bouclage possible */
262  /* #define VRDEB 4 debordement de tableaux */
263  /* #define VRCAL 5 appel errone */
264  /* #define VRBUG 6 bug */
265  /* #define VROVF 7 overflow */
266 
267 
268  /***************** END execution simplexe entier classique */
269 
270  if (Z.ntrace||Z.ntrac2)
271  { fprintf(Z.ftrace,"\\end{document}\n");
272  }
273 
274  if (fdebug) fclose(fdebug);/* DN: In Solaris, we can fclose(NULL), but in LINUX, we cannot.*/
275 
276  if (r==VRFIN) {ok = true; return ok;}
277  else if ((r==VRVID)||(r==VRINF)) {ok = false;return ok;}
278  else return r; /* in case of failure then return r >=3
279  donnot want to use exception here, nor one more parameter,
280  while wanting to keep return bool for compatibility. To be changed.*/
281 }
VRVID
#define VRVID
Definition: iproblem.h:114
VRINF
#define VRINF
Definition: iproblem.h:115
VRFIN
#define VRFIN
.....................
Definition: iproblem.h:113
isolve
int isolve(Pinitpb II, Pproblem XX, int suite)
Definition: isolve.c:2458
sc_to_iproblem
static bool sc_to_iproblem(Psysteme sc, Pinitpb I, Pproblem Z, FILE *fdebug)
This file provides functions to convert a system of constraints into format of Janus.
Definition: sc_janus_feasibility.c:42
fprintf
int fprintf()
test sc_min : ce test s'appelle par : programme fichier1.data fichier2.data ...
ok
static bool ok
Definition: special_cases.c:702
problem
=========================================================================
Definition: iproblem.h:16
problem::ntrac2
int ntrac2
niveau "trace" (execution accompagnee de commentaires) 0: aucune impression >= 1: volume d'informatio...
Definition: iproblem.h:31
problem::ntrace
int ntrace
Definition: iproblem.h:27
problem::ftrace
FILE * ftrace
nombre de variables originales contraintes (rangees en tete).
Definition: iproblem.h:22

References fprintf(), problem::ftrace, isolve(), problem::ntrac2, problem::ntrace, ok, sc_to_iproblem(), VRFIN, VRINF, and VRVID.

+ Here is the call graph for this function:

◆ sc_to_iproblem()

static bool sc_to_iproblem ( Psysteme  sc,
Pinitpb  I,
Pproblem  Z,
FILE *  fdebug 
)
static

This file provides functions to convert a system of constraints into format of Janus.

c must be consistant

anus int p6,p5,p4,p3,p2,p1;

int tfois = 1; for time measurement only. other initiation removed.

prefixed parameter for Janus - to be changed in futur

no debug mode

ave to remove this debug in the futur for exact time measument

file for trace

technique for hierarchical computation - 0 if simplex

number of levels - 0 if simplex

dynamic visualization

amount of information

amount of information

amount of information

Fourier_Motzkin

ow to introduce constrained variables

riterion max iterations

Choice pivot primal

Choice of the pivot for dual simplex

ODO: If these parameters are already initialized before used in the code (which is not easy to see now), then it's not necessary to reinitialize them here. If not, then we might have a bug.

removed reading from file. replace by direct assign

we can chosse probleme janus ou simplexe entier classique or other in this section

scanf(fh,"%d",&Z->nvar); nombre total de variables

to be verified

c given is not correct (normally tested before)

Janus cannot handle this system of constraints

Janus cannot handle this system of constraints

scanf(fh,"%d",&Z->mcontr); nombre de contraintes

sc's parameters must be true

Janus cannot handle this system of constraints

scanf(fh,"%d",&Z->nvpos); nombre de variables >=0 donc: Z->nvpos<= Z->nvar

to be verified

?? can we put nvpos = 0 here

scanf(fh,"%d",&vi0); unused parameter

need exact DIMENSION, similar to sc_to_matrix

for ( i=1 ; i <= Z->mcontr ; i++) { fscanf(fh,"%d",&ventier) ; I->e[i]=ventier ; for ( j=1 ; j <= Z->nvar ; j++) { fscanf(fh,"%d",&ventier) ; I->a[i][j]=ventier ; } fscanf(fh,"%d",&ventier) ; I->d[i]=ventier ; }

TTENTION, first elements in array in struct initpb are not used.

his array is not initiated. In use : rows 1 -> Z->mcontr, columns 1-> Z->nvar

N: need to check the special inequality here: 0 < 1, mean a vector of one element.

differentiation eq and ineq, running by constraints

f egalite then 0, inegalite then -1. Put in egalites first

ncluded constant (or rhs) here, which is the last element in the vector, donot change the sign of constant DN 6/11/02. use Marcos of Value. Needed Value in struct problem.

galites coeffs, i for columns, j for rows

negalites

c_default_dump(sc); TODO: what to do with this special constraint? if 0<1 ok, if 1 < 0 then not ok, return false

Definition at line 42 of file sc_janus_feasibility.c.

43 {
44  Pcontrainte peq;
45  Pvecteur pv;
46  Value temp;
47  bool special_constraint_p = false;
48 
49  /*Janus
50  int p6,p5,p4,p3,p2,p1;*/
51  int vi0,targ,pr,nblevel,mtlevel,tas;
52  int i,j,choix,vision,methode;
53  int par1,par2,par3,par4,par5,par6,par7;
54  /* int tfois = 1; for time measurement only. other initiation removed.*/
55 
56  /* prefixed parameter for Janus - to be changed in futur */
57  tas=0; pr=0;
58  par1 = 0; par2 = 0; par3 = 0;
59  par4 = 0; /* no debug mode*/
60  par5 = 0; par6 = 1; par7 = 1;
61 
62  /*have to remove this debug in the futur for exact time measument*/
63  if (par4) {
64  fdebug=fopen("jtrace.tex","w") ; /* file for trace */
65  }else {
66  fdebug = NULL;
67  }
68  Z->ftrace=fdebug;
69 
70  /**************** BEGIN parameters into structure ************************/
71  Z->turbo=0; Z->remove=1;
72  mtlevel = par1; /* technique for hierarchical computation - 0 if simplex */
73  nblevel = par2; /* number of levels - 0 if simplex */
74  methode = par3; Z->met8 = methode/10000000;
75  methode -= 10000000*Z->met8;Z->met7 = methode/1000000;
76  methode -= 1000000*Z->met7; Z->met6 = methode/100000;
77  methode -= 100000*Z->met6; Z->met5 = methode/10000;
78  methode -= 10000*Z->met5; Z->met4 = methode/1000;
79  methode -= 1000*Z->met4; Z->met3 = methode/100;
80  methode -= 100*Z->met3; Z->met2 = methode/10;
81  methode -= 10*Z->met2; Z->meth = methode;
82  vision = par4; Z->dyn = vision/1000; /* dynamic visualization*/
83  vision -= 1000*Z->dyn; Z->ntrac3 = vision/100; /* amount of information */
84  vision -= 100*Z->ntrac3; Z->ntrac2 = vision/10; /* amount of information */
85  Z->ntrace = vision-10*Z->ntrac2; /* amount of information */
86  Z->fourier = par5; /* Fourier_Motzkin */
87  targ = par6; Z->forcer= targ/10;
88  targ -= 10*Z->forcer; Z->varc= targ; /*How to introduce constrained variables*/
89  choix = par7; Z->critermax = choix/100; /*Criterion max iterations*/
90  choix -= 100*Z->critermax; Z->choixprim = choix/10; /* Choice pivot primal */
91  Z->choixpiv = choix-10*Z->choixprim; /* Choice of the pivot for dual simplex */
92  /**************** END parameters into structure ************************/
93  /**************** BEGIN print debug into structure ************************/
94  if (Z->dyn) dynam(Z,0);
95  if (Z->ntrace||Z->ntrac2)
96  {fprintf(Z->ftrace,"\\documentstyle[fullpage,epic,eepic,fancybox]{article} \n");
97  fprintf(Z->ftrace,"\\begin{document}\n");
98  tableau_janus(I,Z);
99  }
100  /**************** END print debug into structure ************************/
101 
102 /**************** BEGIN reset some parameters in the structures ************************/
103  Z->negal=0;Z->icout=0;Z->minimum=0;Z->mx=0;Z->nx=0;Z->ic1=0;Z->tmax=0;Z->niter=0;Z->itdirect=0;Z->nredun=0;Z->numero=0;Z->numax=0; Z->lastfree=0;Z->nub= 0;Z->ntp = 0;Z->vdum = 0;Z->nturb = 0;
104 /*
105  for ( i=1;i<=MAXLIGNES+1; i++) {
106  for (j=1; j<=MAXCOLONNES+1; j++)
107  value_assign(I->a[i][j],VALUE_ZERO);
108  }
109  for ( i=1 ; i <= MAXLIGNES +1 ; i++) {
110  value_assign(I->d[i],VALUE_ZERO);
111  }
112  for ( i=1 ; i <= MAXLIGNES +1 ; i++) {
113  I->e[i]=0;
114  }
115  for ( i=1;i<=AKLIGNES; i++) {
116  for (j=1; j<=AKCOLONNES; j++)
117  value_assign(Z->ak[i][j],VALUE_ZERO);
118  }
119  for ( i=1 ; i <= AKLIGNES ; i++) {
120  value_assign(Z->dk[i],VALUE_ZERO);
121  }
122 */
123  /*TODO: If these parameters are already initialized before used in the code (which is not easy to see now),
124  then it's not necessary to reinitialize them here. If not, then we might have a bug.*/
125 
126  /**************** END reset some parameters in the structures ************************/
127 
128  /**************** BEGIN to insert DIMENSION with tests into structure *************/
129  /* removed reading from file. replace by direct assign*/
130  /* we can chosse probleme janus ou simplexe entier classique or other in this section*/
131 
132  /*fscanf(fh,"%d",&Z->nvar); nombre total de variables */
133  Z->nvar = sc->dimension; /* to be verified */
134  if (Z->nvar < 0) { /*sc given is not correct (normally tested before)*/
135  ifscdebug(5) {
136  printf("\n[sc_to_iproblem]: Janus has a number of variables < 0 ");
137  }
138  return false;/* Janus cannot handle this system of constraints*/
139  }
140  if (Z->nvar> MAXCOLONNES) {
141  ifscdebug(5) {
142  printf("\n[sc_to_iproblem]: Too many variables %3d > max=%3d\n",Z->nvar,MAXCOLONNES);
143  }
144  return false;/* Janus cannot handle this system of constraints*/
145  }
146 
147  /*fscanf(fh,"%d",&Z->mcontr); nombre de contraintes */
148  Z->mcontr = sc->nb_eq + sc->nb_ineq; /* sc's parameters must be true*/
149  if (Z->mcontr> MAXLIGNES) {
150  ifscdebug(5) {
151  printf("\n[sc_to_iproblem]: Too many constraints %3d > max = %3d \n",Z->mcontr,MAXLIGNES);
152  }
153  return false;/* Janus cannot handle this system of constraints*/
154  }
155 
156  /*fscanf(fh,"%d",&Z->nvpos); nombre de variables >=0 donc: Z->nvpos<= Z->nvar */
157  Z->nvpos = 0; /* to be verified */
158  if (Z->nvpos > Z->nvar) {
159  ifscdebug(5) {
160  printf("\n[sc_to_iproblem]: %3d variables positives, greater than %3d\n",Z->nvpos,Z->nvar);
161  }
162  return false;/* ?? can we put nvpos = 0 here */
163  }
164 
165  /*fscanf(fh,"%d",&vi0); unused parameter */
166  vi0 = 0;
167  /**************** END to insert DIMENSION into structure ********************/
168 
169  /**************** BEGIN to insert MATRIX into structure*********************/
170  /* need exact DIMENSION, similar to sc_to_matrix*/
171  /* for ( i=1 ; i <= Z->mcontr ; i++)
172  { fscanf(fh,"%d",&ventier) ; I->e[i]=ventier ;
173  for ( j=1 ; j <= Z->nvar ; j++)
174  { fscanf(fh,"%d",&ventier) ; I->a[i][j]=ventier ;
175  }
176  fscanf(fh,"%d",&ventier) ; I->d[i]=ventier ;
177  }
178  */
179  /*ATTENTION, first elements in array in struct initpb are not used. */
180  /*this array is not initiated. In use : rows 1 -> Z->mcontr, columns 1-> Z->nvar*/
181 
182  /*DN: need to check the special inequality here: 0 < 1, mean a vector of one element.*/
183 
184  for ( i=1 ; i <= Z->mcontr ; i++) /* differentiation eq and ineq, running by constraints*/
185  {
186  /*if egalite then 0, inegalite then -1. Put in egalites first*/
187  if (i<=sc->nb_eq) I->e[i]= 0;
188  else I->e[i]= -1;
189  }
190 
191  /*included constant (or rhs) here, which is the last element in the vector, donot change the sign of constant
192  DN 6/11/02. use Marcos of Value. Needed Value in struct problem.*/
193 
194  /*egalites coeffs, i for columns, j for rows*/
195  for (peq = sc->egalites, i = 1; !CONTRAINTE_UNDEFINED_P(peq); peq=peq->succ, i++)
196  {
197  for (pv=sc->base,j=1; !VECTEUR_NUL_P(pv); pv=pv->succ,j++)
198  {
199  value_assign(I->a[i][j],value_uminus(vect_coeff(vecteur_var(pv),peq->vecteur)));
200  }
201  value_assign(I->d[i],vect_coeff(TCST,peq->vecteur));
202  }
203 
204  /*inegalites*/
205  for (peq = sc->inegalites; !CONTRAINTE_UNDEFINED_P(peq); peq=peq->succ, i++)
206  {
207  value_assign(temp,VALUE_ZERO);
208  for (pv=sc->base,j=1; !VECTEUR_NUL_P(pv); pv=pv->succ,j++)
209  {
210  value_assign( I->a[i][j],value_uminus(vect_coeff(vecteur_var(pv),peq->vecteur)));
211  value_addto(temp,value_abs(I->a[i][j]));
212  }
213  if value_zero_p(temp) {
214  special_constraint_p = true;
215  }
216  value_assign(I->d[i],vect_coeff(TCST,peq->vecteur));
217  }
218  if (special_constraint_p) {
219  /*sc_default_dump(sc);
220  TODO: what to do with this special constraint? if 0<1 ok, if 1 < 0 then not ok, return false */
221  }
222 
223  /**************** END to insert MATRIX into structure *********************/
224  return true;
225 }
VALUE_ZERO
#define VALUE_ZERO
Definition: arithmetique-local.h:302
value_uminus
#define value_uminus(val)
unary operators on values
Definition: arithmetique-local.h:377
value_assign
#define value_assign(ref, val)
assigments
Definition: arithmetique-local.h:358
value_zero_p
#define value_zero_p(val)
Definition: arithmetique-local.h:388
Value
int Value
Definition: arithmetique-local.h:296
value_addto
#define value_addto(ref, val)
Definition: arithmetique-local.h:359
value_abs
#define value_abs(val)
Definition: arithmetique-local.h:379
CONTRAINTE_UNDEFINED_P
#define CONTRAINTE_UNDEFINED_P(c)
Definition: contrainte-local.h:114
MAXLIGNES
#define MAXLIGNES
Definition: iproblem.h:54
MAXCOLONNES
#define MAXCOLONNES
(-) choix du pivot (simplexe primal)
Definition: iproblem.h:53
dynam
int dynam(Pproblem XX, int nd)
=======================================================================
Definition: isolve.c:2082
tableau_janus
void tableau_janus(Pinitpb II, Pproblem XX)
Definition: isolve.c:69
printf
int printf()
Scontrainte::vecteur
Pvecteur vecteur
Definition: contrainte-local.h:89
Scontrainte::succ
struct Scontrainte * succ
Definition: contrainte-local.h:90
Ssysteme::inegalites
Pcontrainte inegalites
Definition: sc-local.h:71
Ssysteme::egalites
Pcontrainte egalites
Definition: sc-local.h:70
Ssysteme::base
Pbase base
Definition: sc-local.h:75
Ssysteme::dimension
int dimension
Definition: sc-local.h:74
Ssysteme::nb_ineq
int nb_ineq
Definition: sc-local.h:73
Ssysteme::nb_eq
int nb_eq
Definition: sc-local.h:72
Svecteur
le type des coefficients dans les vecteurs: Value est defini dans le package arithmetique
Definition: vecteur-local.h:89
Svecteur::succ
struct Svecteur * succ
Definition: vecteur-local.h:92
initpb::d
Value d[MAXLIGNES+1]
matrix coefficients
Definition: iproblem.h:124
initpb::e
int e[MAXLIGNES+1]
rhs
Definition: iproblem.h:125
initpb::a
Value a[MAXLIGNES+1][MAXCOLONNES+1]
Definition: iproblem.h:123
problem::nredun
int nredun
Definition: iproblem.h:77
problem::remove
int remove
in any case non negative variables
Definition: iproblem.h:44
problem::met8
int met8
Definition: iproblem.h:46
problem::nvpos
int nvpos
nombre de fonctions et contraintes originales
Definition: iproblem.h:20
problem::ntrac3
int ntrac3
Definition: iproblem.h:32
problem::lastfree
int lastfree
Definition: iproblem.h:79
problem::met3
int met3
Definition: iproblem.h:46
problem::niter
int niter
Definition: iproblem.h:76
problem::met4
int met4
Definition: iproblem.h:46
problem::met7
int met7
Definition: iproblem.h:46
problem::critermax
int critermax
Definition: iproblem.h:47
problem::numax
int numax
Definition: iproblem.h:78
problem::dyn
int dyn
numero "file system" pour "trace"
Definition: iproblem.h:25
problem::turbo
int turbo
Definition: iproblem.h:47
problem::mx
int mx
Definition: iproblem.h:74
problem::ntp
int ntp
Definition: iproblem.h:81
problem::minimum
int minimum
Definition: iproblem.h:73
problem::met5
int met5
Definition: iproblem.h:46
problem::tmax
int tmax
Definition: iproblem.h:75
problem::icout
int icout
Definition: iproblem.h:72
problem::meth
int meth
redundant inequalities are removed
Definition: iproblem.h:45
problem::choixprim
int choixprim
(0-1) choix du pivot (simplexe dual) 0 plus petit pivot 1 plus grand pivot
Definition: iproblem.h:51
problem::varc
int varc
(3) elimination FOURIER-MOTZKIN 0: elimination non appliquee 1: cas triviaux ( >= 2: lorsque le nombr...
Definition: iproblem.h:38
problem::nvar
int nvar
column in case of infinite vale of function
Definition: iproblem.h:18
problem::nturb
int nturb
Definition: iproblem.h:83
problem::choixpiv
int choixpiv
Definition: iproblem.h:48
problem::mcontr
int mcontr
nombre de variables originales
Definition: iproblem.h:19
problem::nx
int nx
Definition: iproblem.h:74
problem::vdum
int vdum
Definition: iproblem.h:82
problem::forcer
int forcer
(0-1) introduction variables contraintes 0 "strategie simplexe" 1 pivot unitaire sinon "strategie sim...
Definition: iproblem.h:43
problem::negal
int negal
nature contraintes 0 egalite 1 inequation <= -1 inequation >= 2 fonction a minimiser -2 fonction a ma...
Definition: iproblem.h:71
problem::itdirect
int itdirect
Definition: iproblem.h:77
problem::numero
int numero
Definition: iproblem.h:78
problem::met6
int met6
Definition: iproblem.h:46
problem::fourier
int fourier
Definition: iproblem.h:33
problem::met2
int met2
(0-1) methode finale de resolution
Definition: iproblem.h:46
problem::ic1
int ic1
Definition: iproblem.h:74
problem::nub
int nub
Definition: iproblem.h:80
TCST
#define TCST
VARIABLE REPRESENTANT LE TERME CONSTANT.
Definition: vecteur-local.h:131
vecteur_var
#define vecteur_var(v)
Definition: vecteur-local.h:126
VECTEUR_NUL_P
#define VECTEUR_NUL_P(v)
Definition: vecteur-local.h:111
vect_coeff
Value vect_coeff(Variable var, Pvecteur vect)
Variable vect_coeff(Variable var, Pvecteur vect): coefficient de coordonnee var du vecteur vect —> So...
Definition: unaires.c:228

References initpb::a, Ssysteme::base, problem::choixpiv, problem::choixprim, CONTRAINTE_UNDEFINED_P, problem::critermax, initpb::d, Ssysteme::dimension, problem::dyn, dynam(), initpb::e, Ssysteme::egalites, problem::forcer, problem::fourier, fprintf(), problem::ftrace, problem::ic1, problem::icout, Ssysteme::inegalites, problem::itdirect, problem::lastfree, MAXCOLONNES, MAXLIGNES, problem::mcontr, problem::met2, problem::met3, problem::met4, problem::met5, problem::met6, problem::met7, problem::met8, problem::meth, problem::minimum, problem::mx, Ssysteme::nb_eq, Ssysteme::nb_ineq, problem::negal, problem::niter, problem::nredun, problem::ntp, problem::ntrac2, problem::ntrac3, problem::ntrace, problem::nturb, problem::nub, problem::numax, problem::numero, problem::nvar, problem::nvpos, problem::nx, printf(), problem::remove, Scontrainte::succ, Svecteur::succ, tableau_janus(), TCST, problem::tmax, problem::turbo, value_abs, value_addto, value_assign, value_uminus, VALUE_ZERO, value_zero_p, problem::varc, problem::vdum, vect_coeff(), Scontrainte::vecteur, VECTEUR_NUL_P, and vecteur_var.

Referenced by sc_janus_feasibility().

+ Here is the call graph for this function:
+ Here is the caller graph for this function: