72 #define EXCEPTION_PRINT_LINEAR_SIMPLEX true
73 #define EXCEPTION_PRINT_FM true
74 #define EXCEPTION_PRINT_JANUS true
76 #define FILTERING_TIMEOUT_FM filtering_timeout_FM
77 #define FILTERING_TIMEOUT_LINEAR_SIMPLEX filtering_timeout_S
78 #define FILTERING_TIMEOUT_JANUS filtering_timeout_J
80 #define FILTERING_DIMENSION_FEASIBILITY filtering_dimension_feasibility
81 #define FILTERING_NUMBER_CONSTRAINTS_FEASIBILITY filtering_number_constraints_feasibility
82 #define FILTERING_DENSITY_FEASIBILITY filtering_density_feasibility
83 #define FILTERING_MAGNITUDE_FEASIBILITY (Value) filtering_magnitude_feasibility
87 #define SWITCH_HEURISTIC_FLAG sc_switch_heuristic_flag
126 filtering_catch_alarm_FM (
int sig)
132 filtering_catch_alarm_J (
int sig)
138 filtering_catch_alarm_S (
int sig)
164 for(; c!=NULL; c=c->
succ) {
168 for(; v!=NULL; v=v->
succ)
198 fprintf(stderr,
"[chose_variable_to_project_for_feasability] b/s:\n");
203 if (size==1)
return var_of(b);
224 minval = val, minvar = var;
241 two_int_infop t = (two_int_infop)
malloc(2*size*
sizeof(
int));
245 c = sc_inegalites(s);
249 for (i=0; i<size; i++) t[i][0]=0, t[i][1]=0;
263 for (i=0, tmp=b; tmp &&
var_of(tmp)!=var;
264 i++, tmp=tmp->
succ) (
void) NULL;
274 for (i=0; i<size; i++) t[i][0] *= t[i][1];
276 for (tmp=b->
succ, var=
var_of(b), min_new=t[0][0], i=1;
278 i++, tmp=tmp->
succ) {
280 min_new = t[i][0], var=
var_of(tmp);
287 fprintf(stderr,
"[chose_variable_to_project_for_feasability] "
297 (
Psysteme volatile * ps1,
bool integer_p,
bool use_eq_only,
int ofl_ctrl)
301 bool faisable =
true;
303 while (b && faisable)
315 "[sc_fm_project_variables] system before %s projection:\n",
320 sc_projection_along_variable_ofl_ctrl(ps1, var, ofl_ctrl);
325 "[sc_fm_project_variables] system after projection:\n");
337 if (SC_EMPTY_P(*ps1))
348 #define LINEAR_SIMPLEX_PROJECT_EQ_METHOD 11
349 #define LINEAR_SIMPLEX_NO_PROJECT_EQ_METHOD 12
351 #define JANUS_METHOD 14
352 #define ALL_METHOD 15
367 (
Psysteme sc,
int heuristic,
bool int_p,
int ofl_ctrl)
370 int method, n_ref_eq = 0, n_ref_in = 0;
373 int volatile n_cont_in = 0;
374 int volatile n_cont_eq = 0;
386 int dimens;
int nb_cont_eq = 0;
int nb_ref_eq = 0;
int nb_cont_in = 0;
int nb_ref_in = 0;
389 decision_data(sc_egalites(sc), &nb_cont_eq, &nb_ref_eq, &magnitude, 1);
390 decision_data(sc_inegalites(sc), &nb_cont_in, &nb_ref_in, &magnitude, 1);
392 if ((FILTERING_DIMENSION_FEASIBILITY)&&(dimens>=FILTERING_DIMENSION_FEASIBILITY)) {
393 char *directory_name =
"feasibility_dimension_filtering_SC_OUT";
396 if ((FILTERING_NUMBER_CONSTRAINTS_FEASIBILITY)&&((nb_cont_eq + nb_cont_in) >= FILTERING_NUMBER_CONSTRAINTS_FEASIBILITY)) {
397 char *directory_name =
"feasibility_number_constraints_filtering_SC_OUT";
400 if ((FILTERING_DENSITY_FEASIBILITY)&&((nb_ref_eq + nb_ref_in) >= FILTERING_DENSITY_FEASIBILITY)) {
401 char *directory_name =
"feasibility_density_filtering_SC_OUT";
404 if ((
value_notzero_p(FILTERING_MAGNITUDE_FEASIBILITY))&&(
value_gt(magnitude,FILTERING_MAGNITUDE_FEASIBILITY))) {
405 char *directory_name =
"feasibility_magnitude_filtering_SC_OUT";
416 method=0, n_cont_eq = 0, n_ref_eq = 0, n_cont_in = 0, n_ref_in = 0;
418 decision_data(sc_egalites(sc), &n_cont_eq, &n_ref_eq, &magnitude, 1);
419 decision_data(sc_inegalites(sc), &n_cont_in, &n_ref_in, &magnitude, 1);
425 if (n_cont_in >= 10) {
435 method=0, n_cont_eq = 0, n_ref_eq = 0, n_cont_in = 0, n_ref_in = 0;
437 decision_data(sc_egalites(sc), &n_cont_eq, &n_ref_eq, &magnitude, 1);
438 decision_data(sc_inegalites(sc), &n_cont_in, &n_ref_in, &magnitude, 1);
440 if (n_cont_in >= 10) {
447 method=0, n_cont_eq = 0, n_ref_eq = 0, n_cont_in = 0, n_ref_in = 0;
449 decision_data(sc_egalites(sc), &n_cont_eq, &n_ref_eq, &magnitude, 1);
450 decision_data(sc_inegalites(sc), &n_cont_in, &n_ref_in, &magnitude, 1);
457 method=0, n_cont_eq = 0, n_ref_eq = 0, n_cont_in = 0, n_ref_in = 0;
459 decision_data(sc_egalites(sc), &n_cont_eq, &n_ref_eq, &magnitude, 1);
460 decision_data(sc_inegalites(sc), &n_cont_in, &n_ref_in, &magnitude, 1);
466 if (n_cont_in >= 10) {
469 ifscdebug(5) {
fprintf(stderr,
"J failes so change to LS ...");}
475 ifscdebug(5) {
fprintf(stderr,
" ...Passed\n");}
479 ifscdebug(5) {
fprintf(stderr,
"LS failed so change to J ...");}
481 ifscdebug(5) {
fprintf(stderr,
" ...Passed\n");}
486 ifscdebug(5) {
fprintf(stderr,
"\nFM fail with small sc => bug??? ...");}
497 ifscdebug(5) {
fprintf(stderr,
" ...Passed\n");}
502 if (n_cont_in >= 10) {
515 if (n_cont_eq >= 6) {
533 method=0, n_cont_eq = 0, n_ref_eq = 0, n_cont_in = 0, n_ref_in = 0;
535 decision_data(sc_egalites(sc), &n_cont_eq, &n_ref_eq, &magnitude, 1);
536 decision_data(sc_inegalites(sc), &n_cont_in, &n_ref_in, &magnitude, 1);
538 if (n_cont_in >= 10) {
576 bool okS =
true,okJ =
true,okFM =
true;
579 fprintf(stderr,
"Janus or Simplex failed. Let's go with FM\n");
585 if (n_cont_eq >= 10) {
596 fprintf(stderr,
"\n[internal_sc_feasibility]: okS %d != okFM %d\n",okS,okFM);
600 fprintf(stderr,
"\n[internal_sc_feasibility]: okJ %d != okFM %d\n",okJ,okFM);
633 volatile int ofl_ctrl,
634 volatile bool ofl_res)
637 volatile bool catch_performed =
false;
640 int volatile heuristic = 0;
652 fprintf(stderr,
"\n sc_rn is given to sc_feasibility_ofl_ctrl : return true");
658 fprintf(stderr,
"\n sc_empty is given to sc_feasibility_ofl_ctrl : return false");
666 catch_performed =
true;
669 catch_performed =
false;
676 fprintf(stderr,
"\n[sc_feasibility_ofl_ctrl] "
677 "arithmetic error (%d) -> %s\n",
678 heuristic, ofl_res ?
"true" :
"false");
719 bool faisable =
true;
726 fprintf(stderr,
"\n[sc_fourier_motzkin_feasibility_ofl_ctrl] without OFL_CTRL => RETURN true\n");
731 if (s == NULL)
return true;
735 fprintf(stderr,
"[sc_fourier_motzkin_feasibility_ofl_ctrl] system:\n");
779 fprintf(stderr,
"sc_fourier_motzkin_feasibility_ofl_ctrl_timeout_ctrl fails");
783 if (FILTERING_TIMEOUT_FM) alarm(0);
784 if (EXCEPTION_PRINT_FM) {
785 char *directory_name =
"feasibility_FM_fail_SC_OUT";
796 fprintf(stderr,
"\n[sc_fourier_motzkin_feasibility_ofl_ctrl_timeout_ctrl] without OFL_CTRL => RETURN true\n");
805 if (FILTERING_TIMEOUT_FM) {
806 signal(SIGALRM, filtering_catch_alarm_FM);
807 alarm(FILTERING_TIMEOUT_FM);
818 if (FILTERING_TIMEOUT_FM) {
821 char *directory_name =
"feasibility_FM_timeout_filtering_SC_OUT";
853 fprintf(stderr,
"\n[sc_simplexe_feasibility_ofl_ctrl_timeout_ctrl] fails");
857 if (FILTERING_TIMEOUT_LINEAR_SIMPLEX) alarm(0);
859 if (EXCEPTION_PRINT_LINEAR_SIMPLEX) {
860 char *directory_name =
"feasibility_linear_simplex_fail_SC_OUT";
870 fprintf(stderr,
"\n[sc_simplex_feasibility_ofl_ctrl_timeout_ctrl] without OFL_CTRL => RETURN true\n");
877 if (FILTERING_TIMEOUT_LINEAR_SIMPLEX) {
878 signal(SIGALRM, filtering_catch_alarm_S);
879 alarm(FILTERING_TIMEOUT_LINEAR_SIMPLEX);
893 if (FILTERING_TIMEOUT_LINEAR_SIMPLEX) {
896 char *directory_name =
"feasibility_linear_simplex_timeout_filtering_SC_OUT";
934 fprintf(stderr,
"\n[sc_janus_feasibility_ofl_ctrl_timeout_ctrl] fails");
938 if (FILTERING_TIMEOUT_JANUS) alarm(0);
940 if (EXCEPTION_PRINT_JANUS) {
941 char *directory_name =
"feasibility_janus_fail_SC_OUT";
958 if (FILTERING_TIMEOUT_JANUS) {
959 signal(SIGALRM, filtering_catch_alarm_J);
960 alarm(FILTERING_TIMEOUT_JANUS);
968 if (FILTERING_TIMEOUT_JANUS) {
971 char *directory_name =
"feasibility_janus_timeout_filtering_SC_OUT";
986 if (
ok > 0)
return true;
991 if (
ok ==7)
fprintf(stderr,
"TRIED JANUS BUT OVERFLOW !!\n");
992 if (
ok ==6)
fprintf(stderr,
"TRIED JANUS BUT BUG OF PROGRAMMATION IN JANUS !!\n");
993 if (
ok ==5)
fprintf(stderr,
"TRIED JANUS BUT WRONG PARAMETER !!\n");
994 if (
ok ==4)
fprintf(stderr,
"TRIED JANUS BUT ARRAY OUT OF BOUNDARY !!\n");
995 if (
ok ==3)
fprintf(stderr,
"TRIED JANUS BUT NUMBER OF PIVOTAGE TOO BIG, MIGHT BOUCLE !!\n");
996 if (
ok ==8)
fprintf(stderr,
"TRIED JANUS BUT pivot anormally small !!\n");
997 if (
ok ==9)
fprintf(stderr,
"Janus is not ready for this system of constraints !!\n");
1003 fprintf(stderr,
"\n[sc_janus_feasibility_ofl_ctrl_timeout_ctrl] without OFL_CTRL => RETURN true\n");
1014 int MAXCOEFFICIENT = 1000;
1017 for (ineg = sc->
inegalites; ineg != NULL; ineg = ineg1)
1041 if (fast_check == 1 || fast_check == 2)
1042 return fast_check == 1;
@ any_exception_error
catch all
#define int_to_value(i)
end LINEAR_VALUE_IS_INT
#define value_notzero_p(val)
#define value_assign(ref, val)
assigments
#define value_zero_p(val)
#define value_posz_p(val)
int linear_number_of_exception_thrown
bool linear_use_gmp(void)
whether linear is to use gmp
Pbase make_base_from_vect(Pvecteur pv)
#define contrainte_vecteur(c)
passage au champ vecteur d'une contrainte "a la Newgen"
Pcontrainte contrainte_make(Pvecteur pv)
Pcontrainte contrainte_make(Pvecteur pv): allocation et initialisation d'une contrainte avec un vecte...
void eq_set_vect_nul(Pcontrainte)
void_eq_set_vect_nul(Pcontrainte c): transformation d'une contrainte en une contrainte triviale 0 == ...
bool sc_janus_feasibility(Psysteme sc)
Compute feasibility, using custom Janus function if set, fallback function otherwise.
void vect_fprint(FILE *f, Pvecteur v, get_variable_name_t variable_name)
void vect_fprint(FILE * f, Pvecteur v, char * (*variable_name)()): impression d'un vecteur creux v su...
int vect_size(Pvecteur v)
package vecteur - reductions
bool sc_rn_p(Psysteme sc)
bool sc_rn_p(Psysteme sc): check if the set associated to sc is the whole space, rn
void sc_creer_base(Psysteme ps)
void sc_creer_base(Psysteme ps): initialisation des parametres dimension et base d'un systeme lineair...
void sc_fix(Psysteme s)
fix system s for coherency of the base and number of things.
void sc_rm(Psysteme ps)
void sc_rm(Psysteme ps): liberation de l'espace memoire occupe par le systeme de contraintes ps;
bool sc_empty_p(Psysteme sc)
bool sc_empty_p(Psysteme sc): check if the set associated to sc is the constant sc_empty or not.
Psysteme sc_dup(Psysteme ps)
Psysteme sc_dup(Psysteme ps): should becomes a link.
Psysteme sc_copy(Psysteme ps)
Psysteme sc_copy(Psysteme ps): duplication d'un systeme (allocation et copie complete des champs sans...
void sc_rm_empty_constraints(Psysteme ps, bool process_equalities)
package sc: elimination de redondance simple
Psysteme sc_safe_elim_db_constraints(Psysteme ps)
The returned value must be used because they argument is freed when the system is not feasible.
int sc_check_inequality_redundancy(Pcontrainte ineq, Psysteme ps)
int sc_check_inequality_redundancy(Pcontrainte ineq, Psysteme ps) Check if an inequality ineq,...
bool sc_fourier_motzkin_feasibility_ofl_ctrl(Psysteme s, bool integer_p, int ofl_ctrl)
bool sc_fourier_motzkin_faisabilite_ofl(Psysteme s): test de faisabilite d'un systeme de contraintes ...
bool efficient_sc_check_inequality_feasibility(Pvecteur v, Psysteme prec)
void decision_data(Pcontrainte c, int volatile *pc, int volatile *pv, Value *magnitude, int weight)
just a test to improve the Simplex/FM decision.
bool sc_rational_feasibility_ofl_ctrl(Psysteme sc, int ofl_ctrl, bool ofl_res)
static int feasibility_sc_counter
static bool sc_fm_project_variables(Psysteme volatile *ps1, bool integer_p, bool use_eq_only, int ofl_ctrl)
project in s1 (which is modified) using equalities or both equalities and inequalities.
bool sc_integer_feasibility_ofl_ctrl(Psysteme sc, int ofl_ctrl, bool ofl_res)
static Psysteme simplify_big_coeff(Psysteme sc)
#define LINEAR_SIMPLEX_NO_PROJECT_EQ_METHOD
bool sc_fourier_motzkin_feasibility_ofl_ctrl_timeout_ctrl(Psysteme sc, bool int_p, int ofl_ctrl)
static bool internal_sc_feasibility(Psysteme sc, int heuristic, bool int_p, int ofl_ctrl)
means LINEAR_SIMPLEX :-)
bool sc_simplexe_feasibility_ofl_ctrl_timeout_ctrl(Psysteme sc, bool project_eq_p, bool int_p, int ofl_ctrl)
bool sc_feasibility_ofl_ctrl(Psysteme sc, bool integer_p, volatile int ofl_ctrl, volatile bool ofl_res)
return true is the system is feasible
char * default_variable_to_string(Variable)
#define SWITCH_HEURISTIC_FLAG
#define LINEAR_SIMPLEX_PROJECT_EQ_METHOD
bool sc_janus_feasibility_ofl_ctrl_timeout_ctrl(Psysteme sc, bool ofl_ctrl)
static Variable chose_variable_to_project_for_feasability(Psysteme s, Pbase b, bool ineq)
chose the next variable in base b for projection in system s.
#define HEURISTIC1
We can add other heuristic if we need in an easy way.
Psysteme sc_constraint_add(Psysteme sc, Pcontrainte c, bool equality)
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...
void sc_default_dump_to_files(Psysteme sc, int sc_nb, char *directory_name)
void sc_default_dump_to_files(Psysteme sc, sc_nb,directory_name):
void sc_default_dump(Psysteme sc)
void sc_default_dump(Psysteme sc): dump to stderr
int fprintf()
test sc_min : ce test s'appelle par : programme fichier1.data fichier2.data ...
Psysteme sc_restricted_to_variables_transitive_closure(Psysteme sc, Pbase variables)
for an improved dependence test (Beatrice Creusillet)
void sc_gcd_normalize(Psysteme ps)
sc_gcd_normalize(ps)
Psysteme sc_normalize(Psysteme ps)
Psysteme sc_normalize(Psysteme ps): normalisation d'un systeme d'equation et d'inequations lineaires ...
bool sc_simplex_feasibility_ofl_ctrl(Psysteme sys, int ofl_ctrl)
Main Function.
struct Scontrainte * succ
le type des coefficients dans les vecteurs: Value est defini dans le package arithmetique
#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 OFL_CTRL
I do thing that overflows are managed in a very poor manner.
Pbase base_copy(Pbase b)
Direct duplication.
void vect_erase_var(Pvecteur *ppv, Variable v)
void vect_erase_var(Pvecteur * ppv, Variable v): projection du vecteur *ppv selon la direction v (i....