PIPS
|
#include <stdio.h>
#include <string.h>
#include "arithmetique.h"
#include "boolean.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"
Go to the source code of this file.
Functions | |
bool | sc_elim_simple_redund_with_eq (Psysteme ps, Pcontrainte eg) |
package sc More... | |
bool | sc_elim_simple_redund_with_ineq (Psysteme ps, Pcontrainte ineg) |
bool sc_elim_simple_redund_with_ineq(Psysteme ps, Pcontrainte ineg): elimination des contraintes redondantes de ps avec une inegalite ineg (FI: qui doit appartenir a ps; verifier qu'on ne fait pas de comparaisons inutiles; apparemment pas parce qu'on modifie froidement ineg) More... | |
int | sc_check_inequality_redundancy (Pcontrainte ineq, Psysteme ps) |
int sc_check_inequality_redundancy(Pcontrainte ineq, Psysteme ps) Check if an inequality ineq, possibly part of ps, is trivially infeasible (return 2), redundant (return 1), potentially useful (return 0) with respect to inequalities in ps. More... | |
void | sc_elim_empty_constraints (Psysteme ps, bool process_equalities) |
void sc_elim_empty_constraints(Psysteme ps, bool process_equalities): elimination des "fausses" contraintes du systeme ps, i.e. More... | |
Psysteme | sc_elim_db_constraints (Psysteme ps) |
Psysteme sc_elim_db_constraints(Psysteme ps): elimination des egalites et des inegalites identiques ou inutiles dans le systeme; plus precisemment: More... | |
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. More... | |
Psysteme | sc_elim_double_constraints (Psysteme ps) |
Psysteme sc_elim_double_constraints(Psysteme ps): elimination des egalites et des inegalites identiques ou inutiles dans le systeme apres reduction par le gcd; plus precisemment: More... | |
int sc_check_inequality_redundancy | ( | Pcontrainte | ineq, |
Psysteme | ps | ||
) |
int sc_check_inequality_redundancy(Pcontrainte ineq, Psysteme ps) Check if an inequality ineq, possibly part of ps, is trivially infeasible (return 2), redundant (return 1), potentially useful (return 0) with respect to inequalities in ps.
Neither ps nor ineq are modified. ineq may be one of ps constraints.
c is redundant with ineq
ineq is redundant with c
c and ineq define a non-empty interval
ineq and c are incompatible
Definition at line 175 of file sc_elim_simple_redund.c.
References contrainte_succ, CONTRAINTE_UNDEFINED, CONTRAINTE_UNDEFINED_P, eq_diff_const(), eq_smg(), eq_sum_const(), inequalities_opposite_p(), value_neg_p, and value_negz_p.
Referenced by efficient_sc_check_inequality_feasibility(), expression_less_than_in_context(), sc_strong_normalize_and_check_feasibility(), and top_down_abc_dimension().
Psysteme sc_elim_db_constraints(Psysteme ps): elimination des egalites et des inegalites identiques ou inutiles dans le systeme; plus precisemment:
Pour les egalites, on elimine une equation si on a un systeme d'egalites de la forme :
a1/ Ax - b == 0, ou b1/ Ax - b == 0,
Ax - b == 0, b - Ax == 0,
ou c1/ 0 == 0
Pour les inegalites, on elimine une inequation si on a un systeme d'inegalites de la forme :
a2/ Ax - b <= c, ou b2/ 0 <= const (avec const >=0) Ax - b <= c
resultat retourne par la fonction :
Psysteme : Le systeme initial est modifie (si necessaire) et renvoye Si le systeme est non faisable (0 <= const <0 ou 0 = b), il est desalloue et NULL est renvoye.
Attention, on ne teste pas les proportionalites: 2*i=2 est different de i = 1. Il faut reduire le systeme par gcd avant d'appeler cette fonction sc_elim_db_constraints()
Notes:
so called triangular version, FC 28/09/94
b = 0
0 <= b < 0
Definition at line 317 of file sc_elim_simple_redund.c.
References contrainte_equal(), egalite_equal(), eq_set_vect_nul(), sc_elim_empty_constraints(), sc_rm(), Scontrainte::succ, Svecteur::val, val_of, value_negz_p, Svecteur::var, vect_rm(), vect_size(), and Scontrainte::vecteur.
Referenced by elim_var_with_eg(), my_sc_normalize(), and sc_transform_eg_in_ineg().
Psysteme sc_elim_double_constraints(Psysteme ps): elimination des egalites et des inegalites identiques ou inutiles dans le systeme apres reduction par le gcd; plus precisemment:
Pour les egalites, on elimine une equation si on a un systeme d'egalites de la forme :
a1/ Ax - b == 0, ou b1/ Ax - b == 0,
Ax - b == 0, b - Ax == 0,
ou c1/ 0 == 0
Si on a A=0 et b!=0, on detecte une non-faisabilite.
Si on a Ax - b == 0 et Ax - b' == 0 et b!=b', on detecte une non-faisabilite.
Pour les inegalites, on elimine une inequation si on a un systeme d'inegalites de la forme :
a2/ Ax - b <= 0, ou b2/ 0 <= const (avec const >=0) Ax - b <= 0
Une inegalite peut etre redondante ou incompatible avec une egalite:
a3/ Ax - b == 0, ou b3/ b - Ax == 0, Ax - c <= 0, Ax - c <= 0 b - c <= 0 b - c <= 0
on detecte une non-faisabilite si b - c > 0.
Une paire d'inegalites est remplacee par une egalite:
a4/ Ax - b <= 0 -Ax + b <=0
donne Ax - b == 0
resultat retourne par la fonction :
Psysteme : Le systeme initial est modifie (si necessaire) et renvoye Si le systeme est non faisable (0 <= const <0 ou 0 = b), il est desalloue et NULL est renvoye.
Notes:
Normalization by gcd's
Detection of inconsistant equations: incompatible constant term
b = 0
deux equations ne differant que par leurs termes constants
Check redundancy and inconsistency between pair of inequalities
Detection of inconsistant or redundant inequalities: incompatible or useless constant term
0 <= b < 0
Equal inequalities, redundant inequalities, equality detection
opposite STRICT inequality or contrainte_equal() would have caught it
inequalities eq1 and eq2 define an equality
No need to update the basis since it used to be an inequality
These inequalities are incompatible and the system is not satisfiable
Check redundancies and inconsistencies between equalities and inequalities
0 < b <= 0
0 < b <= 0
Definition at line 529 of file sc_elim_simple_redund.c.
References contrainte_equal(), contrainte_make(), contrainte_normalize(), contrainte_vecteur, egalite_equal(), eq, eq_set_vect_nul(), eq_smg(), sc_add_egalite(), sc_elim_empty_constraints(), sc_rm(), Scontrainte::succ, sum(), TCST, Svecteur::val, val_of, value_neg_p, value_negz_p, value_pos_p, Svecteur::var, vect_add(), vect_coeff(), vect_constant_p(), vect_copy(), vect_equal_except(), vect_normalize(), vect_rm(), vect_size(), vect_substract(), Scontrainte::vecteur, VECTEUR_NUL_P, and vecteur_val.
Referenced by sc_minmax_of_variable(), sc_normalize2(), and sc_transform_ineg_in_eg().
void sc_elim_empty_constraints(Psysteme ps, bool process_equalities): elimination des "fausses" contraintes du systeme ps, i.e.
les contraintes ne comportant plus de couple (variable,valeur), i.e. les contraintes qui ont ete eliminees par la fonction 'eq_set_vect_nul', i.e. 0 = 0 ou 0 <= 0
resultat retourne par la fonction: le systeme initial ps est modifie.
parametres de la fonction: !Psysteme ps: systeme lineaire bool egalite: true s'il faut traiter la liste des egalites false s'il faut traiter la liste des inegalites
Modifications:
Definition at line 232 of file sc_elim_simple_redund.c.
References contrainte_free(), contrainte_vecteur, and Scontrainte::succ.
Referenced by my_sc_normalize(), sc_bounded_normalization(), sc_build_triang_elim_redund(), sc_elim_db_constraints(), sc_elim_double_constraints(), sc_normalize(), sc_normalize2(), sc_safe_elim_db_constraints(), sc_strong_normalize_and_check_feasibility2(), sc_triang_elim_redund(), and transform_in_ineq().
bool sc_elim_simple_redund_with_eq | ( | Psysteme | ps, |
Pcontrainte | eg | ||
) |
package sc
bool sc_elim_simple_redund_with_eq(Psysteme ps, Pcontrainte eg): elimination en place des contraintes d'un systeme ps, qui sont redondantes avec une egalite eg
resultat retourne par la fonction :
boolean: false si l'equation a permis de montrer que le systeme etait non faisable true sinon
Les parametres de la fonction :
!Psysteme ps : systeme Pcontrainte eg : equation du systeme
cas des egalites
les deux egalites sont redondantes ==> elimination de eq
cas des inegalites
Definition at line 69 of file sc_elim_simple_redund.c.
References eq, eq_diff_const(), eq_set_vect_nul(), eq_smg(), sc_rn_p(), Scontrainte::succ, value_negz_p, and Scontrainte::vecteur.
Referenced by sc_add_normalize_eq(), and sc_normalize().
bool sc_elim_simple_redund_with_ineq | ( | Psysteme | ps, |
Pcontrainte | ineg | ||
) |
bool sc_elim_simple_redund_with_ineq(Psysteme ps, Pcontrainte ineg): elimination des contraintes redondantes de ps avec une inegalite ineg (FI: qui doit appartenir a ps; verifier qu'on ne fait pas de comparaisons inutiles; apparemment pas parce qu'on modifie froidement ineg)
si deux inegalites ont le meme membre gauche (contrainte sans le
terme constant) :
==> elimination de l'inegalite ayant le terme constant le plus
grand
resultat retourne par la fonction :
boolean: false si l'inequation a permis de montrer que le systeme etait non faisable true sinon
Les parametres de la fonction :
Psysteme ps : systeme Pcontrainte ineg : inequation du systeme
cas des egalites
inegalite redondante avec l'egalite
==> elimination de inegalite
cas des inegalites
Definition at line 130 of file sc_elim_simple_redund.c.
References eq, eq_diff_const(), eq_set_vect_nul(), eq_smg(), sc_rn_p(), Scontrainte::succ, value_negz_p, VALUE_ZERO, and Scontrainte::vecteur.
Referenced by sc_add_normalize_ineq(), and sc_normalize().
The returned value must be used because they argument is freed when the system is not feasible.
FI: I added an elimination and check of the colinear constraints.
b = 0
0 <= b < 0
Use rational simplification
The constraints are opposed. Their constant terms must be compatible
The constraint system is not feasible
ps should be replaced by sc_empty
The signs of a1 and a2 are different
get rid of the first constraint
FI: it would be safer to keep *ps and to change each field
I thought there was a function to remove the useless stuff from a Psystem and to make it an empty one, but I could not find it.
Definition at line 370 of file sc_elim_simple_redund.c.
References Ssysteme::base, BASE_NULLE, BASE_UNDEFINED, contrainte_equal(), contrainte_parallele(), contrainte_vecteur, egalite_equal(), Ssysteme::egalites, eq_set_vect_nul(), Ssysteme::inegalites, k1, k2, sc_elim_empty_constraints(), sc_empty(), sc_rm(), Scontrainte::succ, TCST, Svecteur::val, val_of, value_mult, value_negz_p, value_product, Svecteur::var, vect_coeff(), vect_rm(), vect_size(), and Scontrainte::vecteur.
Referenced by sc_fourier_motzkin_feasibility_ofl_ctrl().