PIPS
|
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "linear_assert.h"
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"
#include "sc-private.h"
Go to the source code of this file.
Macros | |
#define | SWITCH_HEURISTIC_FLAG sc_switch_heuristic_flag |
#define | LINEAR_SIMPLEX_PROJECT_EQ_METHOD 11 |
#define | LINEAR_SIMPLEX_NO_PROJECT_EQ_METHOD 12 |
#define | FM_METHOD 13 |
#define | JANUS_METHOD 14 |
#define | ALL_METHOD 15 |
#define | HEURISTIC1 1 /**Keep the old heuristic of FC */ |
We can add other heuristic if we need in an easy way. More... | |
#define | HEURISTIC2 2 /**Replace Simplex by Janus in heuristic 1 */ |
#define | HEURISTIC3 3 /**Only for experiment. Test successtively 3 methods to see the coherence */ |
#define | HEURISTIC4 4 /**The best?: (Linear Simplex vs Janus) try to use the method that succeeded recently. If failed than turn to another. Rely on the fact that the sc are similar. [optional?] : If the 2 methods fail, then call FM. This can solve many sc, in fact. */ |
Functions | |
char * | default_variable_to_string (Variable) |
bool | sc_rational_feasibility_ofl_ctrl (Psysteme sc, int ofl_ctrl, bool ofl_res) |
bool | sc_integer_feasibility_ofl_ctrl (Psysteme sc, int ofl_ctrl, bool ofl_res) |
void | decision_data (Pcontrainte c, int volatile *pc, int volatile *pv, Value *magnitude, int weight) |
just a test to improve the Simplex/FM decision. More... | |
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. More... | |
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. More... | |
static bool | internal_sc_feasibility (Psysteme sc, int heuristic, bool int_p, int ofl_ctrl) |
means LINEAR_SIMPLEX :-) More... | |
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 More... | |
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 lineaires, par projections successives du systeme selon les differentes variables du systeme More... | |
bool | sc_fourier_motzkin_feasibility_ofl_ctrl_timeout_ctrl (Psysteme sc, bool int_p, int ofl_ctrl) |
bool | sc_simplexe_feasibility_ofl_ctrl_timeout_ctrl (Psysteme sc, bool project_eq_p, bool int_p, int ofl_ctrl) |
bool | sc_janus_feasibility_ofl_ctrl_timeout_ctrl (Psysteme sc, bool ofl_ctrl) |
static Psysteme | simplify_big_coeff (Psysteme sc) |
bool | efficient_sc_check_inequality_feasibility (Pvecteur v, Psysteme prec) |
Variables | |
static int | feasibility_sc_counter = 0 |
bool | FM_timeout = false |
bool | J_timeout = false |
bool | S_timeout = false |
static int | method_used = 0 |
#define ALL_METHOD 15 |
Definition at line 352 of file sc_feasibility.c.
#define FM_METHOD 13 |
Definition at line 350 of file sc_feasibility.c.
#define HEURISTIC1 1 /**Keep the old heuristic of FC */ |
We can add other heuristic if we need in an easy way.
Note: FM is not good for big sc, but good enough for small sc. Simplex build a tableau, so it's not good for small sc
Definition at line 359 of file sc_feasibility.c.
#define HEURISTIC2 2 /**Replace Simplex by Janus in heuristic 1 */ |
Definition at line 360 of file sc_feasibility.c.
#define HEURISTIC3 3 /**Only for experiment. Test successtively 3 methods to see the coherence */ |
Definition at line 361 of file sc_feasibility.c.
#define HEURISTIC4 4 /**The best?: (Linear Simplex vs Janus) try to use the method that succeeded recently. If failed than turn to another. Rely on the fact that the sc are similar. [optional?] : If the 2 methods fail, then call FM. This can solve many sc, in fact. */ |
Definition at line 362 of file sc_feasibility.c.
#define JANUS_METHOD 14 |
Definition at line 351 of file sc_feasibility.c.
#define LINEAR_SIMPLEX_NO_PROJECT_EQ_METHOD 12 |
Definition at line 349 of file sc_feasibility.c.
#define LINEAR_SIMPLEX_PROJECT_EQ_METHOD 11 |
Definition at line 348 of file sc_feasibility.c.
#define SWITCH_HEURISTIC_FLAG sc_switch_heuristic_flag |
Definition at line 87 of file sc_feasibility.c.
chose the next variable in base b for projection in system s.
tries to avoid Fourier potential explosions when combining inequalities.
(c) FC 21 July 1995
find the lowest coeff
shouldn't find empty equalities ??
assert(minvar!=TCST);
only inequalities, reduce the explosion
initialize t
t[x][0 (resp. 1)] = number of negative (resp. positive) coeff
t[x][0] = number of combinations, i.e. new created constraints.
Definition at line 188 of file sc_feasibility.c.
References assert, contrainte_vecteur, default_variable_to_string(), fprintf(), free(), malloc(), sc_fprint(), Scontrainte::succ, Svecteur::succ, TCST, val_of, value_abs, value_lt, value_notzero_p, value_one_p, value_posz_p, VALUE_ZERO, value_zero_p, var_of, vect_fprint(), and vect_size().
Referenced by sc_fm_project_variables().
void decision_data | ( | Pcontrainte | c, |
int volatile * | pc, | ||
int volatile * | pv, | ||
Value * | magnitude, | ||
int | weight | ||
) |
just a test to improve the Simplex/FM decision.
c is a list of constraints, equalities or inequalities pc is the number of constraints in the list pv is the number of non-zero coefficients in the system magnitude is the biggest coefficent in the system pc, pv and magnitude MUST be initialized. They are multiplied by weight.
Modif: Become public, used by filters
Definition at line 156 of file sc_feasibility.c.
References Scontrainte::succ, Svecteur::succ, TCST, val_of, value_abs, value_assign, value_gt, var_of, and Scontrainte::vecteur.
Referenced by internal_sc_feasibility().
char* default_variable_to_string | ( | Variable | v | ) |
Definition at line 245 of file sc_debug.c.
References assert, var_name_stack, and var_name_stack_index.
Referenced by chose_variable_to_project_for_feasability(), hyperplane(), new_system_with_only_live_variable(), sc_default_dump(), sc_default_dump_to_files(), sc_fm_project_variables(), and sc_fourier_motzkin_feasibility_ofl_ctrl().
Definition at line 1033 of file sc_feasibility.c.
References assert, contrainte_make(), linear_number_of_exception_thrown, make_base_from_vect(), OFL_CTRL, sc_check_inequality_redundancy(), sc_constraint_add(), sc_dup(), sc_integer_feasibility_ofl_ctrl(), sc_restricted_to_variables_transitive_closure(), sc_rm(), and simplify_big_coeff().
Referenced by expression_equal_in_context_p().
means LINEAR_SIMPLEX :-)
Automatic variables read in a CATCH block need to be declared volatile as specified by the documentation
We can put the size filters here! filtering timeout is integrated in the methods themself size filtering: dimension,number_constraints, density, magnitude
HEURISTIC1 if nb_ineg >= 10 and nb_eg < 6 then use LSimplex (replace n eg by 2n ineg) if nb_ineg >= 10 and nb_eg >= 6 then project eg and use LSimplex if nb_ineg < 10 then use FM
ifscdebug(5) {fprintf(stderr,"nb_exceptions af %d\n",linear_number_of_exception_thrown);}
INEAR_SIMPLEX
ok = sc_fourier_motzkin_feasibility_ofl_ctrl_timeout_ctrl(sc,int_p,ofl_ctrl);
anus
M
f TRY
se heuristic1
f switch heuristic
fprintf(stderr, "in=%d eq=%d method=%d magnitude=", n_cont_in, n_cont_eq, method);print_Value(magnitude);
ien faire
f switch method
Definition at line 366 of file sc_feasibility.c.
References ALL_METHOD, assert, CATCH, decision_data(), Ssysteme::dimension, feasibility_sc_counter, FM_METHOD, fprintf(), HEURISTIC1, HEURISTIC2, HEURISTIC3, HEURISTIC4, JANUS_METHOD, linear_number_of_exception_thrown, LINEAR_SIMPLEX_NO_PROJECT_EQ_METHOD, LINEAR_SIMPLEX_PROJECT_EQ_METHOD, linear_use_gmp(), method_used, ok, overflow_error, sc_default_dump(), sc_default_dump_to_files(), sc_fourier_motzkin_feasibility_ofl_ctrl_timeout_ctrl(), sc_gcd_normalize(), sc_janus_feasibility_ofl_ctrl_timeout_ctrl(), sc_simplexe_feasibility_ofl_ctrl_timeout_ctrl(), TRY, UNCATCH, value_assign, value_gt, value_notzero_p, and VALUE_ZERO.
Referenced by sc_feasibility_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
In case an exception, due to an overflow or to an error such as zero divide or a GCD with 0, occurs, return ofl_res. So, an error may lead to a feasible or a non feasible system.
Automatic variables read in a CATCH block need to be declared volatile as specified by the documentation
this should be treated somewhere else -> faster
his should be treated somewhere else -> faster
What we need to do here: choose a method or a heuristic predifined by a variable of environment and catch an overflow exception if it happens DN240203
By default, heuristic flag is 0
Definition at line 630 of file sc_feasibility.c.
References assert, CATCH, Ssysteme::dimension, fprintf(), FWD_OFL_CTRL, internal_sc_feasibility(), linear_number_of_exception_thrown, OFL_CTRL, ok, overflow_error, sc_default_dump(), sc_empty_p(), sc_fix(), sc_rn_p(), SWITCH_HEURISTIC_FLAG, and UNCATCH.
Referenced by sc_integer_feasibility_ofl_ctrl(), sc_rational_feasibility_ofl_ctrl(), and test_system().
|
static |
project in s1 (which is modified) using equalities or both equalities and inequalities.
if use_eq_only
Definition at line 296 of file sc_feasibility.c.
References base_copy(), base_rm, chose_variable_to_project_for_feasability(), default_variable_to_string(), fprintf(), sc_empty_p(), sc_fprint(), sc_normalize(), and vect_erase_var().
Referenced by sc_fourier_motzkin_feasibility_ofl_ctrl(), and sc_simplexe_feasibility_ofl_ctrl_timeout_ctrl().
bool sc_fourier_motzkin_faisabilite_ofl(Psysteme s): test de faisabilite d'un systeme de contraintes lineaires, par projections successives du systeme selon les differentes variables du systeme
resultat retourne par la fonction :
bool : true si le systeme est faisable false sinon
Les parametres de la fonction :
Psysteme s : systeme lineaire
Le controle de l'overflow est effectue et traite par le retour du contexte correspondant au dernier CATCH(overflow_error) effectue.
Back to the version modifying the sc. Calls of this function should store the sc first or pls call sc_fourier_motzkin_ofl_ctrl_timeout_ctrl DN210203
maybe timeout_error or overflow_error
ethrow whatever the exception is
default is feasible
a small basis if possible... (FC).
hould remove the copy of the sc.
sc_kill_db_eg a de'sallouer s a` la detection de sa non-faisabilite
Definition at line 714 of file sc_feasibility.c.
References any_exception_error, base_rm, CATCH, default_variable_to_string(), fprintf(), FWD_OFL_CTRL, RETHROW, sc_creer_base(), sc_empty_p(), sc_fm_project_variables(), sc_fprint(), sc_gcd_normalize(), sc_rm(), sc_safe_elim_db_constraints(), and UNCATCH.
Referenced by sc_fourier_motzkin_feasibility_ofl_ctrl_timeout_ctrl().
Automatic variables read in a CATCH block need to be declared volatile as specified by the documentation
there r 2 exceptions here!
if (w) sc_rm(w); sc_fourier_motzkin_feasibility_ctrl_ofl has freed the memory. base
Definition at line 764 of file sc_feasibility.c.
References any_exception_error, CATCH, Ssysteme::dimension, feasibility_sc_counter, FM_timeout, fprintf(), FWD_OFL_CTRL, linear_number_of_exception_thrown, ok, overflow_error, sc_copy(), sc_default_dump_to_files(), sc_fourier_motzkin_feasibility_ofl_ctrl(), sc_rm(), THROW, TRY, and UNCATCH.
Referenced by internal_sc_feasibility().
Definition at line 111 of file sc_feasibility.c.
References sc_feasibility_ofl_ctrl().
Referenced by convex_cells_intersection_p(), dependence_cone_positive(), efficient_sc_check_inequality_feasibility(), interlaced_basic_workchunk_regions_p(), region_intersection(), sc_triang_elim_redund(), and sc_triang_elim_redund_n_first().
Automatic variables read in a CATCH block need to be declared volatile as specified by the documentation
N: We should be sure that the sc is not null in the sc_feasibility_ofl_ctrl, but for direct calls of Janus ...
sc_empty_p is filtered, (sc_fix is called), so there's no other reason for janus to fail ... maybe a sc_not_easy_to_see_empty
TODO aware of vectors of one element: 0 <= 1. treating it here is better than in Janus
here r 2 exceptions here!
c_janus_feasibility returns type int, not boolean
result found
result not found
default is feasible
Definition at line 911 of file sc_feasibility.c.
References any_exception_error, CATCH, Ssysteme::dimension, feasibility_sc_counter, fprintf(), FWD_OFL_CTRL, J_timeout, linear_number_of_exception_thrown, ok, overflow_error, sc_copy(), sc_default_dump_to_files(), sc_fix(), sc_janus_feasibility(), sc_rm(), THROW, TRY, and UNCATCH.
Referenced by internal_sc_feasibility().
Definition at line 102 of file sc_feasibility.c.
References sc_feasibility_ofl_ctrl().
Referenced by __attribute__(), analyze_quast(), build_integer_sc_nredund(), build_sc_nredund_1pass_ofl_ctrl(), build_third_comb(), dataflows_on_reference(), dj_feasibility_ofl_ctrl(), dj_intersection_ofl_ctrl(), find_implicit_equation(), ineq_redund_with_sc_p(), loop_executed_approximation(), my_sc_faisabilite(), sc_elim_redund(), sc_elim_redund_with_first_ofl_ctrl(), sc_inequations_elim_redund(), sc_rational_feasibility(), top_down_abc_dimension(), and vvs_faisabilite().
bool sc_simplexe_feasibility_ofl_ctrl_timeout_ctrl | ( | Psysteme | sc, |
bool | project_eq_p, | ||
bool | int_p, | ||
int | ofl_ctrl | ||
) |
Automatic variables read in a CATCH block need to be declared volatile as specified by the documentation
here r 2 exceptions here!
default is feasible
Definition at line 837 of file sc_feasibility.c.
References any_exception_error, CATCH, Ssysteme::dimension, feasibility_sc_counter, fprintf(), FWD_OFL_CTRL, linear_number_of_exception_thrown, ok, overflow_error, S_timeout, sc_copy(), sc_default_dump_to_files(), sc_fm_project_variables(), sc_rm(), sc_simplex_feasibility_ofl_ctrl(), THROW, TRY, and UNCATCH.
Referenced by internal_sc_feasibility().
Definition at line 1012 of file sc_feasibility.c.
References eq_set_vect_nul(), Ssysteme::inegalites, int_to_value, sc_rm_empty_constraints(), Scontrainte::succ, TCST, Svecteur::val, value_abs, value_gt, Scontrainte::vecteur, and VECTEUR_NUL.
Referenced by efficient_sc_check_inequality_feasibility().
|
static |
Definition at line 89 of file sc_feasibility.c.
Referenced by internal_sc_feasibility(), sc_fourier_motzkin_feasibility_ofl_ctrl_timeout_ctrl(), sc_janus_feasibility_ofl_ctrl_timeout_ctrl(), and sc_simplexe_feasibility_ofl_ctrl_timeout_ctrl().
Definition at line 91 of file sc_feasibility.c.
Referenced by sc_fourier_motzkin_feasibility_ofl_ctrl_timeout_ctrl().
Definition at line 92 of file sc_feasibility.c.
Referenced by sc_janus_feasibility_ofl_ctrl_timeout_ctrl().
|
static |
Definition at line 364 of file sc_feasibility.c.
Referenced by internal_sc_feasibility().
Definition at line 93 of file sc_feasibility.c.
Referenced by sc_simplexe_feasibility_ofl_ctrl_timeout_ctrl().