33 #ifndef LINEAR_SC_SIMPLEX_FEASIBILITY_H
34 #define LINEAR_SC_SIMPLEX_FEASIBILITY_H
49 #ifndef LINEAR_DEBUG_SIMPLEX
50 #define DEBUG(code) {}
52 #define DEBUG(code) {code}
60 fprintf(stderr,
"[" __FILE__
"] out of memory\n");
85 #define VAR_MAXNB (1971)
90 #define var_fprint(stream, var) (fprintf(stream, "x%d", var))
95 #define var_print(var) (var_fprint(stdout, var))
120 #define VEC_NULL NULL
125 #define vec_init(vec) (vec = VEC_NULL)
150 (*last)->var = vec->
var;
157 last = &(*last)->
succ;
186 pvec = &(*pvec)->
succ;
216 pvec = &(*pvec)->
succ;
225 pvec = &(*pvec)->
succ;
238 pvec = &(*pvec)->
succ;
274 pvec = &(*pvec)->
succ;
283 pvec = &(*pvec)->
succ;
289 qval_add((*pvec)->coeff, (*pvec)->coeff, tmp);
297 pvec = &(*pvec)->
succ;
348 #define vec_print(vec) (vec_fprint(stdout, vec))
408 constr1->
rel = constr2->
rel;
415 #define constr_get_coeff(coeff, constr, var) \
416 (vec_get_coeff(coeff, (constr)->vec, var))
504 #define constr_print(constr) (constr_fprint(stdout, constr))
541 for (i = 0; i < nbconstrs; i++) {
564 #define table_get_nbvars(tbl) ((tbl)->nbvars)
569 #define table_get_nbconstrs(tbl) ((tbl)->nbconstrs)
611 sign = rsign == 0 ? 1 : lsign * rsign;
614 sign = rsign == 0 ? -lsign : (rsign == 1 ? 0 : lsign * rsign);
616 if (sign != 0 && vars_info[var] == 0) {
617 vars_info[var] = sign;
627 if (vars_info[var] < 0) {
634 for (var = tbl->
nbvars - 1; var >= 0; var--) {
635 if (vars_info[var] == 0) {
636 vars_info[var] = tbl->
nbvars;
691 fprintf(stderr,
"Initial system:\n");
696 fprintf(stderr,
"\nWith signed variables:\n");
701 fprintf(stderr,
"\nWith offset variables:\n");
706 fprintf(stderr,
"\nWith positive constants:\n");
754 fprintf(stderr,
"\nWith objective:\n");
823 qval_t pivot_ratio, ratio;
832 if (pivot_row == -1 ||
qval_cmp(ratio, pivot_ratio) < 0) {
837 else if (
qval_cmp(ratio, pivot_ratio) == 0) {
839 if (assoc < pivot_assoc) {
898 fprintf(stderr,
"After iteration %d:\n", i);
899 fprintf(stderr,
"Pivot variable: ");
901 fprintf(stderr,
"\nPivot row: %d\nTable:\n", row);
905 fprintf(stderr,
"Seems to long, exiting...\n");
935 for (i = 0; i < 40; i++) {
940 c +=
fprintf(stream,
"true\n");
944 c +=
fprintf(stream,
"(%2d: ", i);
951 for (i = 0; i < 40; i++) {
961 #define table_print(tbl) (table_fprint(stdout, tbl))
998 #define vartbl_clear(vartbl)
1007 for (i = 0; i < vartbl->
nbvars; i++) {
1008 if (vartbl->
names[i] == name) {
1024 for (; vec != NULL; vec = vec->
succ) {
1043 for (vec = constr2->
vecteur; vec != NULL; vec = vec->
succ) {
1061 for (constr = sys->
egalites; constr != NULL; constr = constr->
succ) {
1065 for (constr = sys->
inegalites; constr != NULL; constr = constr->
succ) {
1069 tbl->
nbvars = vartbl->nbvars;
1088 fprintf(stderr,
"[sc_simplexe_feasibility] "
1089 "should not (yet) be called with control %d...\n", ofl_ctrl);
qval_s qval_t[1]
Type of rational numbers.
#define qval_clear(q)
Free the space occupied by q.
#define qval_equal_i(q1, q2num, q2den)
Return non-zero if q and q2num/q2den are equal, zero if they are non-equal.
#define qval_cmp_i(q1, q2num, q2den)
Compare q1 and q2num/q2den.
#define qval_neg(q1, q2)
Set q1 to -q2.
#define qval_fprint(stream, q)
Output q on stdio stream stream.
#define qval_init(q)
Initialize q and set its value to 0/1.
#define qval_set(q1, q2)
Set the value of q1 from q2.
#define qval_div(q1, q2, q3)
Set q1 to q2/q3.
#define qval_mul(q1, q2, q3)
Set q1 to q2 times q3.
#define qval_set_i(q1, q2num, q2den)
Set the value of q to q2num/q2den.
#define qval_cmp(q1, q2)
Compare q1 and q2.
#define qval_inv(q1, q2)
Set q1 to 1/q2.
#define qval_add(q1, q2, q3)
Set q1 to q2 + q3.
@ simplex_arithmetic_error
#define value_sign(v)
trian operators on values
int fprintf()
test sc_min : ce test s'appelle par : programme fichier1.data fichier2.data ...
static bool table_get_pivot(table_p tbl, var_t *pvar, int *prow)
Get the next pivot variable and row in @tbl, and store them in pvar and prow respectively.
static void vec_set_vecteur(vartbl_t vartbl, vec_p *pvec, Pvecteur vec)
Copy vec into pvec.
static void table_init_set_systeme(table_p tbl, Psysteme sys)
Initialize tbl from sys.
struct constr_s * constr_p
#define var_fprint(stream, var)
Output var on stdio stream stream.
static void vec_append(vec_p *pvec, var_t var, qval_t coeff)
Add the element (var, coeff) to pvec.
static bool sc_get_feasibility(Psysteme sys, int ofl_ctrl)
Main Function.
static void table_init(table_p tbl, int nbconstrs)
Initialize tbl, with room for nbconstrs constraints.
static void vec_ineg(vec_p vec)
Set vec to -vec.
#define VEC_NULL
The empty vector.
static int table_get_pivotrow(table_p tbl, var_t var)
struct vartbl_s * vartbl_p
static void constr_clear(constr_p constr)
Free the space occupied by constr.
static void constr_init(constr_p constr)
Initialize constr and set it to 0 = 0.
static var_t table_get_assocvar(table_p tbl, int row)
Retrieve the variable associated with the row (i.e.
static void table_addsignvars(table_p tbl)
Ensure that all variables in tbl are non-negative.
static int NOWUNUSED table_fprint(FILE *, table_p)
Output tbl on stdio stream stream.
static void table_clear(table_p tbl)
Free the space occupied by tbl.
static void table_run_simplex(table_p tbl)
Run simplex algorithm on @tbl.
static void NOWUNUSED constr_set(constr_p constr1, constr_p constr2)
Copy constr2 into constr1.
struct constr_s constr_s
Type of linear constraint.
static void vec_iadd(vec_p *pvec, vec_p vec)
Set pvec to pvec + vec.
static void vec_get_coeff(qval_t coeff, vec_p vec, var_t var)
Get the value associated to var in vec, and store it into coeff.
static void table_set_obj(table_p tbl)
Initialize the objective function and value from constraints in tbl.
static void vec_set(vec_p *pvec, vec_p vec)
Copy vec into pvec.
static void vec_append_atfirst(vec_p *pvec, var_t var, qval_t coeff)
Add the element (var, @coeff) to pvec, in first position.
#define constr_get_coeff(coeff, constr, var)
Get the coefficient of var in constr, and store it into coeff.
static void table_canonicalize(table_p tbl)
Canonicalize tbl: ensure that all variables are non-negative, and all constraints are equalities whos...
struct vec_s vec_s
Type of vectors.
static void constr_iadd(constr_p constr1, constr_p constr2)
Set constr1 to constr1 + constr2.
#define vec_init(vec)
Set vec to be the empty vector.
static void * safe_malloc(size_t size)
static var_t table_get_pivotvar(table_p tbl)
Get the next pivot variable in @tbl.
#define vartbl_clear(vartbl)
Free the space occupied by vartbl.
table_s table_t[1]
Type of simplex tableau.
static void constr_makepos(constr_p constr)
Turn constr into an equivalent constraint whose constant term is non-negative.
static void table_addofsvars(table_p tbl)
Ensure that all constraints in tbl are equalities.
static int NOWUNUSED vec_fprint(FILE *stream, vec_p vec)
Output vec on stdio stream stream.
static void table_addobjvars(table_p tbl)
Add objective variables to each constraint of @tbl whose constant term is not zero.
#define VAR_MAXNB
Maximum number of variables.
static void constr_apply_pivot(constr_p constr, var_t pivot_var, constr_p pivot_constr)
Make pivot_var coefficient null in constr, using pivot_constr.
#define VAR_NULL
A special value used to represent the absence of variable.
static void vec_clear(vec_p *pvec)
Free the space occupied by pvec.
struct table_s table_s
Type of simplex tableau.
static void constr_imul(constr_p constr, qval_t coeff)
Set constr to coeff times constr.
constr_s constr_t[1]
Type of linear constraint.
static void table_apply_pivot(table_p tbl, var_t var, int row)
Apply pivot (var, row) in tbl.
static void vec_iaddmul(vec_p *pvec, qval_t coeff, vec_p vec)
Set pvec to pvec + coeff times vec.
static void table_makepos(table_p tbl)
Turn constraints into tbl into equivalent ones, whose constant term is non-negative.
vartbl_s vartbl_t[1]
Type of variable tables.
static void table_prepare(table_p tbl)
Canonicalize tbl, set the objective and add objective variables.
static int NOWUNUSED constr_fprint(FILE *stream, constr_p constr)
Output constr on stdio stream stream.
static bool table_get_feasibility(table_p tbl)
Determine whether the constraint system described in tbl is feasible, using simplex method.
static void constr_iaddmul(constr_p constr1, qval_t coeff, constr_p constr2)
Set constr1 to constr1 + coeff times constr2.
static var_t vartbl_find(vartbl_p vartbl, Variable name)
Get the variable index associated to name, creating a new one if necessary.
static void constr_set_contrainte(vartbl_t vartbl, constr_p constr1, Pcontrainte constr2, bool is_ineq)
Copy constr2 into constr1.
static void vartbl_init(vartbl_p vartbl)
Initialize @vartbl to an empty table.
constrrel_t
Type of linear constraint relations.
int var_t
Type of variables.
static void vec_imul(vec_p *pvec, qval_t coeff)
Set pvec to coeff times pvec.
struct Scontrainte * succ
le type des coefficients dans les vecteurs: Value est defini dans le package arithmetique
Type of linear constraint.
constrrel_t rel
equality or inequality relation
vec_p vec
coefficients of variables
int nbvars
number of variables
int nbconstrs
number of constraints
constr_t * constrs
constraints
constr_t obj
objective function and value
Variable names[VAR_MAXNB]
int nbvars
number of variables
qval_t coeff
value associated to the variable
struct vec_s * succ
rest of the vector
#define TCST
VARIABLE REPRESENTANT LE TERME CONSTANT.
void * Variable
arithmetique is a requirement for vecteur, but I do not want to inforce it in all pips files....