linear_constraint.c File Reference

Detailed Description

Implementaton of the function operating on TLinearConstraint.

See Also
TLinearConstraint, linear_constraint.h.

Definition in file linear_constraint.c.

Functions

void InitLinearConstraint (TLinearConstraint *lc)
 Constructor. More...
 
void ResetLinearConstraint (TLinearConstraint *lc)
 Resets a linear constraint. More...
 
void CopyLinearConstraint (TLinearConstraint *lc_dst, TLinearConstraint *lc_src)
 Copy constructor. More...
 
boolean BoundedLinearConstraint (TLinearConstraint *lc)
 Test if the constraint is bounded. More...
 
unsigned int GetNumTermsInLinearConstraint (TLinearConstraint *lc)
 Number of variables in a linear constraint. More...
 
double * GetLinearConstraintCoefficients (TLinearConstraint *lc)
 Gets the linear constraint coefficients. More...
 
double GetLinearConstraintCoefficient (unsigned int i, TLinearConstraint *lc)
 Gets the a particular linear constraint coefficient. More...
 
unsigned int * GetLinearConstraintVariables (TLinearConstraint *lc)
 Gets the linear constraint variables. More...
 
unsigned int GetLinearConstraintVariable (unsigned int i, TLinearConstraint *lc)
 Gets the a particular variable index. More...
 
void GetLinearConstraintError (Tinterval *error, TLinearConstraint *lc)
 Gets the right-hand side interval for the linear constraint. More...
 
double GetLinearConstraintErrorSize (TLinearConstraint *lc)
 Gets the size of the right-hand side interval for the linear constraint. More...
 
void SetLinearConstraintError (Tinterval *error, TLinearConstraint *lc)
 Sets a new righ-hand side error of the linear constraint. More...
 
void AddCt2LinearConstraint (double ct, TLinearConstraint *lc)
 Adds a constant term to the linear constraint. More...
 
void AddTerm2LinearConstraint (unsigned int ind, double val, TLinearConstraint *lc)
 Adds a scaled variable to the linear constraint. More...
 
double RemoveTermFromLinearConstraint (unsigned int ind, TLinearConstraint *lc)
 Removes a variable from a linear constraint. More...
 
boolean LinearConstraintIncludes (unsigned int ind, TLinearConstraint *lc)
 Checks if a variable is included in a linear constraint. More...
 
void InvertLinearConstraint (TLinearConstraint *lc)
 Changes the sign of a linear constraint. More...
 
void ScaleLinearConstraint (double a, TLinearConstraint *lc)
 Scales a linear constraint. More...
 
void AddLinearConstraints (TLinearConstraint *lc1, TLinearConstraint *lc2)
 Adds one linear constraint to another. More...
 
void CleanLinearConstraint (double epsilon, Tinterval *is, TLinearConstraint *lc)
 Removes terms in the linear constraint that give too small ranges. More...
 
boolean SimplifyLinearConstraint (boolean *full, Tinterval *is, TLinearConstraint *lc)
 Apply linear constraints to reduce the ranges of the problem variables. More...
 
unsigned int CropLinearConstraint (double epsilon, unsigned int varType, Tbox *b, Tvariables *vs, TLinearConstraint *lc)
 Reduce the ranges for. More...
 
boolean CmpLinearConstraints (double *scaleOne2Two, TLinearConstraint *lc1, TLinearConstraint *lc2)
 Compares two linear constraints. More...
 
double EvaluateLinearConstraint (double *varValues, TLinearConstraint *lc)
 Evaluates a linear combination for a given point. More...
 
void EvaluateLinearConstraintInt (Tinterval *varValues, Tinterval *i_out, TLinearConstraint *lc)
 Interval evaluation of a linear constraint. More...
 
void PrintLinearConstraint (FILE *f, boolean eq, char **varName, TLinearConstraint *lc)
 Prints a linear constraint. More...
 
void SaveLinearConstraint (FILE *f, TLinearConstraint *lc)
 Saves the linear constraint into a file. More...
 
void LoadLinearConstraint (FILE *f, TLinearConstraint *lc)
 Constructor. Loads the linear constraint from a file. More...
 
void DeleteLinearConstraint (TLinearConstraint *lc)
 Destructor. More...
 

Function Documentation

void ResetLinearConstraint ( TLinearConstraint lc)

Deletes the information stored in a linear constrain, but does not frees the memory. It is more efficient to use ResetLinearConstraint instead of DeleteLinearConstraint plus InitLinearConstraint again.

Parameters
lcThe linear constraint to be reseted.

Definition at line 25 of file linear_constraint.c.

References TLinearConstraint::error, TLinearConstraint::n, and NewInterval().

Referenced by InitLinearConstraint(), and ReduceRange().

void CopyLinearConstraint ( TLinearConstraint lc_dst,
TLinearConstraint lc_src 
)

Creates a new linear constraint from another one.

Parameters
lc_dstThe linear constraint to initialize.
lc_srcThe linear constraint from where to copy.

Definition at line 31 of file linear_constraint.c.

References CopyInterval(), TLinearConstraint::error, TLinearConstraint::ind, TLinearConstraint::max, TLinearConstraint::n, NEW, and TLinearConstraint::val.

Referenced by CleanLinearConstraint(), CopyEquationInfo(), CopyMapping(), CSRemoveLCVars(), GetOriginalVarRelation(), ScaleLinearConstraint(), SetOriginalVarRelation(), and SimplexAddNewConstraint().

boolean BoundedLinearConstraint ( TLinearConstraint lc)

Test if the linear constraint actually constraint anything. This happens when the error of the linear constraint is not [-INF,+INF]. Unbounded constraints typically appear in equations including tangents o secants.

Only ounded linear constraints are added to the simplex.

Parameters
lcThe linear constraint to check.
Returns
TRUE if the error of the linear constrint is not [-INF,INF].

Definition at line 44 of file linear_constraint.c.

References TLinearConstraint::error, INF, LowerLimit(), and UpperLimit().

Referenced by SimplexAddNewConstraint().

unsigned int GetNumTermsInLinearConstraint ( TLinearConstraint lc)

Returns the number of variables involved in a linear constraint.

Parameters
lcThe linear constraint.
Returns
The number of variables involved in a linear constraint.

Definition at line 49 of file linear_constraint.c.

References TLinearConstraint::n.

Referenced by AddSimplifiedJacobianEquations(), CSRemoveLCVars(), EquationFromLinearConstraint(), EquationFromLinearConstraintProduct(), ReplaceVariableInEquation(), ReplaceVariableInEquations(), SimplexAddNewConstraint(), SimplexAddNewConstraintRaw(), SimplexGetOptimalValue(), SimplexSetOptimizationFunction(), and SimplifyCuikSystem().

double* GetLinearConstraintCoefficients ( TLinearConstraint lc)

Returns the coefficients (i.e., the scale factors) in a linear constraint.

Parameters
lcThe linear constraint.
Returns
A pointer to an array of doubles with the variable scale factors.

Definition at line 54 of file linear_constraint.c.

References TLinearConstraint::val.

Referenced by SimplexAddNewConstraintRaw(), and SimplexSetOptimizationFunction().

double GetLinearConstraintCoefficient ( unsigned int  i,
TLinearConstraint lc 
)

Returns the coefficient (i.e., the scale factor) for a particular variable in a linear constraint. Note that the index of the variable refers to its position in the linear constraint and it is not the global identifier of the variable.
If the linear constraint has less than i variables this function triggers an error.

Parameters
iThe index of the variable in the linear constraint.
lcThe linear constraint.
Returns
The variable scale factor.

Definition at line 59 of file linear_constraint.c.

References Error(), and TLinearConstraint::val.

Referenced by CSRemoveLCVars(), EquationFromLinearConstraint(), EquationFromLinearConstraintProduct(), ReplaceVariableInEquation(), SimplexAddNewConstraintRaw(), SimplexGetOptimalValue(), SimplexSetOptimizationFunction(), and SimplifyCuikSystem().

unsigned int* GetLinearConstraintVariables ( TLinearConstraint lc)

Returns the variables in a linear constraint.

Parameters
lcThe linear constraint.
Returns
A pointer to an array with the index of the variables involved in the linear constraint.

Definition at line 70 of file linear_constraint.c.

References TLinearConstraint::ind.

Referenced by SimplexAddNewConstraintRaw().

unsigned int GetLinearConstraintVariable ( unsigned int  i,
TLinearConstraint lc 
)

Returns the identifier of the i-th variable involved in the linear constraint.

Parameters
iThe index of the variable in the linear constraint.
lcThe linear constraint.
Returns
The global identifier of the i-th variable in the linear constraint.

Definition at line 75 of file linear_constraint.c.

References Error(), TLinearConstraint::ind, and NO_UINT.

Referenced by AddSimplifiedJacobianEquations(), CSRemoveLCVars(), EquationFromLinearConstraint(), EquationFromLinearConstraintProduct(), ReplaceVariableInEquation(), ReplaceVariableInEquations(), SimplexAddNewConstraintRaw(), SimplexGetOptimalValue(), SimplexSetOptimizationFunction(), and SimplifyCuikSystem().

void GetLinearConstraintError ( Tinterval error,
TLinearConstraint lc 
)

Returns the right-hand side interval for the linear constraint.

Parameters
errorOutput interval with the right-hand side of the linear constraint.
lcThe linear constraint.

Definition at line 86 of file linear_constraint.c.

References CopyInterval(), and TLinearConstraint::error.

Referenced by CropEquation(), CSRemoveLCVars(), EquationFromLinearConstraint(), EquationFromLinearConstraintProduct(), ReplaceVariableInEquation(), ReplaceVariableInEquations(), SimplexAddNewConstraint(), SimplexAddNewConstraintRaw(), SimplifyCuikSystem(), UpdateOriginalFromSimple(), and UpdateOriginalPointFromSimple().

double GetLinearConstraintErrorSize ( TLinearConstraint lc)

Returns the size of the right-hand side interval for the linear constraint.

Parameters
lcThe linear constraint.
Returns
The size of the error interval for the linear equation.

Definition at line 91 of file linear_constraint.c.

References TLinearConstraint::error, and IntervalSize().

Referenced by SimplexAddNewConstraint().

void SetLinearConstraintError ( Tinterval error,
TLinearConstraint lc 
)

Sets a new righ-hand side error of the linear constraint.

Parameters
errorThe new linear constraint error.
lcThe linear constraint.

Definition at line 96 of file linear_constraint.c.

References CopyInterval(), and TLinearConstraint::error.

Referenced by CropEquation(), GetFirstOrderApproximationToEquation(), SetEquationInfo(), SimplexAddNewConstraint(), SimplexGetColConstraint(), and SimplexGetRowConstraint().

void AddCt2LinearConstraint ( double  ct,
TLinearConstraint lc 
)

Shifts the righ-hand side error of the linear constraint by the given value (changing the sign to move it to the righ-hand side).

Parameters
ctThe ct to add to the linear constraint.
lcThe linear constraint.

Definition at line 101 of file linear_constraint.c.

References TLinearConstraint::error, and IntervalOffset().

Referenced by CSRemoveLCVars(), CSRemoveVarsWithCtRange(), FixVariableInEquation(), IsSimplificable(), LinearEquation2LinearConstraint(), and SimplifyCuikSystem().

void AddTerm2LinearConstraint ( unsigned int  ind,
double  val,
TLinearConstraint lc 
)

Adds a scaled variable to the linear constraint. If the varaible was already present in the constraint, we just add the scale factors.

Parameters
indGlobal identifier of the variable to add to the linear constraint.
valScale factor for the variable.
lcThe linear constraint.

Definition at line 106 of file linear_constraint.c.

References FALSE, TLinearConstraint::ind, TLinearConstraint::max, MEM_DUP, MEM_EXPAND, TLinearConstraint::n, and TLinearConstraint::val.

Referenced by AddLinearConstraints(), CleanLinearConstraint(), CSRemoveLCVars(), GetFirstOrderApproximationToEquation(), InitMapping(), IsSimplificable(), LinearEquation2LinearConstraint(), ReduceRange(), ScaleLinearConstraint(), SetEquationInfo(), SimplexGetColConstraint(), SimplexGetOptimizationFunction(), SimplexGetRowConstraint(), and SimplifyCuikSystem().

double RemoveTermFromLinearConstraint ( unsigned int  ind,
TLinearConstraint lc 
)

Removes a variable from a linear constraint.

Parameters
indIdentifier of the variable to remove from the linear constraint.
lcThe linear constraint to update.
Returns
The scale factor associated with the removed variable.

Definition at line 136 of file linear_constraint.c.

References FALSE, TLinearConstraint::ind, TLinearConstraint::n, and TLinearConstraint::val.

Referenced by CSRemoveLCVars().

boolean LinearConstraintIncludes ( unsigned int  ind,
TLinearConstraint lc 
)

Checks if a variable is included in a linear constraint.

Parameters
indIdentifier of the variable.
lcThe linear constraint to check.
Returns
The scale factor associated with the removed variable.

Definition at line 166 of file linear_constraint.c.

References FALSE, and TLinearConstraint::ind.

Referenced by CSRemoveLCVars().

void InvertLinearConstraint ( TLinearConstraint lc)

Changes the sign of a linear constraint.

Parameters
lcThe linear constraint to invert.

Definition at line 182 of file linear_constraint.c.

References TLinearConstraint::error, IntervalInvert(), TLinearConstraint::n, and TLinearConstraint::val.

Referenced by IsSimplificable().

void ScaleLinearConstraint ( double  a,
TLinearConstraint lc 
)

Scales a linear constraint.

Parameters
athe scale factor.
lcThe linear constraint to be scaled.

Definition at line 192 of file linear_constraint.c.

References AddTerm2LinearConstraint(), CopyLinearConstraint(), DeleteLinearConstraint(), TLinearConstraint::error, TLinearConstraint::ind, InitLinearConstraint(), IntervalScale(), TLinearConstraint::n, and TLinearConstraint::val.

Referenced by CSRemoveLCVars(), and IsSimplificable().

void AddLinearConstraints ( TLinearConstraint lc1,
TLinearConstraint lc 
)

Adds two a linear constraints.

Parameters
lc1The first linear constraint to add.
lcThe second linear constraint to add and the place where the output is stored.

Definition at line 209 of file linear_constraint.c.

References AddTerm2LinearConstraint(), TLinearConstraint::error, TLinearConstraint::ind, IntervalAdd(), TLinearConstraint::n, and TLinearConstraint::val.

Referenced by CSRemoveLCVars().

void CleanLinearConstraint ( double  epsilon,
Tinterval is,
TLinearConstraint lc 
)

Variables in the linear constraint with very narrow range or scaled by tiny scale factors can be removed and added to the error term. This enhances the numerical robustness of the system.

This can lead to tiny error ranges. If the

When using GLPK it is compulsatory to use

Parameters
epsilonUsed to purge variables with a tiny scale factors. This is done as a requirement of the simplex implementations that are unstables for tiny coefficients.
isRanges for all the variables in the problem.
lcThe linear constraint to clean.

Definition at line 232 of file linear_constraint.c.

References AddTerm2LinearConstraint(), CopyInterval(), CopyLinearConstraint(), DeleteLinearConstraint(), TLinearConstraint::error, TLinearConstraint::ind, InitLinearConstraint(), IntervalAdd(), IntervalScale(), IntervalSize(), TLinearConstraint::n, and TLinearConstraint::val.

Referenced by SimplexAddNewConstraint().

boolean SimplifyLinearConstraint ( boolean full,
Tinterval is,
TLinearConstraint lc 
)

Linear constraints involving only one variable can be directly used to reduce the variable range. We compute the range for the variable as

ct x = error


x = error/ct


and we intersect this with the given range for variable x.

Only linear equations with just one variable are feasible to be used to directly reduce variable ranges.

Linear constraints that can be directly applied do not need to be added to the simplex.

Parameters
fullIf the applied simplification, if any, produces a feasible system (i.e., if the intersection of the previous range for the variable and the new one is not empty).
isRanges for all the variables in the problem. If the linear constriant triggers a simplification, the range for the variable in the constraint is updated.
lcThe linear constraint.
Returns
TRUE if the constraint actually triggered a simplification (i.e., if the linear constraint involves only one variable).

Definition at line 263 of file linear_constraint.c.

References TLinearConstraint::error, FALSE, TLinearConstraint::ind, Intersection(), IntervalDivision(), IntervalProduct(), TLinearConstraint::n, NewInterval(), TRUE, TLinearConstraint::val, and ZERO.

Referenced by SimplexAddNewConstraint().

unsigned int CropLinearConstraint ( double  epsilon,
unsigned int  varType,
Tbox b,
Tvariables vs,
TLinearConstraint lc 
)

We have that a linear constraint can be manipulated as

Sum_i k_i x_i = error,
Sum_i k_i x_i - k_j x_j + k_j x_j = error,
k_j x_j= error - Sum_(i!=k) k_i x_i,
x_j = (error + Sum_(i!=k) - k_i x_i))/ k_j,

that can be evaluated using interval arithmetics.

Thus, a linear constraint can be used to compute a new range for all the variables in the constraint that can be intersected with the given range, possibly producing a range reduction.

This can be seen as a generalization of SimplifyLinearConstraint for the case where the linear constraint involves more than one variable.

Parameters
epsilonNumerical tolerance.
varTypeThe type of variables to which apply the crop. Use ANY_TYPE_VAR for the crop to affect all types of variables.
bThe box with the ranges for the varibles.
vsThe variable set on which the equations are defined. Used to get the type of variables.
lcThe linear constraint.

Definition at line 297 of file linear_constraint.c.

References CopyInterval(), EMPTY_BOX, TLinearConstraint::error, FALSE, GetBoxIntervals(), GetVariableTypeN(), TLinearConstraint::ind, INF, Intersection(), IntervalAdd(), IntervalDivision(), IntervalProduct(), IntervalSize(), TLinearConstraint::n, NewInterval(), NOT_REDUCED_BOX, PrintInterval(), PrintLinearConstraint(), REDUCED_BOX, TRUE, TLinearConstraint::val, and ZERO.

Referenced by CropEquation(), and CSRemoveLCVars().

boolean CmpLinearConstraints ( double *  scaleOne2Two,
TLinearConstraint lc1,
TLinearConstraint lc2 
)

We compare the linear constraints first checking if they involve the same sub-set of variables, and then computing the cosinus of the angle between them (i.e., between the vectors defining the hyperplane of the constraint).

The output scaleOne2Two gives the constant so that lc1*scaleOne2Two=lc2

Parameters
scaleOne2Twogives ct so that lc1*scale=lc2. Only valid if the function returns TRUE.
lc1The first linear constraint to compare.
lc2The second linear constraint to compare.
Returns
TRUE if the linear constrants are equivalent: if they invove the same set of variables and the cosinus between the vectors is close (up to ZERO) to 1 or to -1.

Definition at line 456 of file linear_constraint.c.

References FALSE, TLinearConstraint::ind, TLinearConstraint::n, TRUE, TLinearConstraint::val, and ZERO.

double EvaluateLinearConstraint ( double *  varValues,
TLinearConstraint lc 
)

Evaluates a linear combination for a given point

NOTE: The right-hand side of the linear constraint (represented as a error interval) is not taken into account in the evaluation.

Parameters
varValuesValues defining the point where to evaluate the equation. The array must include values for all the variables in the system (from where the function selects the values for the variables included in the equation).
lcThe linear constraint to evaluate.
Returns
The value of the linear constraint.

Definition at line 519 of file linear_constraint.c.

References TLinearConstraint::ind, TLinearConstraint::n, and TLinearConstraint::val.

Referenced by UpdateOriginalPointFromSimple().

void EvaluateLinearConstraintInt ( Tinterval varValues,
Tinterval i_out,
TLinearConstraint lc 
)

Evaluates a linear constaint for a given ranges of the variables using interval arithmetics.
NOTE: The right-hand side value of the linear constraint is not used in the evaluation.

Parameters
varValuesIntervals for the variables in the system of equations. This function only uses the ranges for the variables in the equation.
i_outThe result of the evalution.
lcThe equation.

Definition at line 531 of file linear_constraint.c.

References TLinearConstraint::ind, IntervalAdd(), IntervalProduct(), TLinearConstraint::n, NewInterval(), TLinearConstraint::val, and ZERO.

Referenced by UpdateOriginalFromSimple().

void PrintLinearConstraint ( FILE *  f,
boolean  eq,
char **  varName,
TLinearConstraint lc 
)

Writes a linear constraint into a given stream, that can be stdout.

Parameters
fThe stream where to write the constraint.
eqTRUE if the linear constraint has to be printed in the form of an equation or FALSE to print it as a simple sum of scaled variables.
varNameThe name of the variables. If this parameter is NULL the printed names for the variables are v_X with X the index of the variable.
lcThe linear constraint.

Definition at line 548 of file linear_constraint.c.

References TLinearConstraint::error, TLinearConstraint::ind, IntervalCenter(), IntervalInvert(), IntervalSize(), TLinearConstraint::n, PrintInterval(), TLinearConstraint::val, and ZERO.

Referenced by CropLinearConstraint(), CSRemoveLCVars(), PrintMapping(), SimplexAddNewConstraint(), and SimplexAddNewConstraintRaw().

void SaveLinearConstraint ( FILE *  f,
TLinearConstraint lc 
)

Saves the linear constraint into a file.

Parameters
fThe file where to store the linear constraint.
lcThe linear constraint to store.

Definition at line 600 of file linear_constraint.c.

References TLinearConstraint::error, TLinearConstraint::ind, LowerLimit(), TLinearConstraint::max, TLinearConstraint::n, UpperLimit(), and TLinearConstraint::val.

Referenced by SaveMapping().

void LoadLinearConstraint ( FILE *  f,
TLinearConstraint lc 
)

Defines a linear constraint from a file.

Parameters
fThe file from where to read the linear constraint.
lcThe linear constraint to define.

Definition at line 612 of file linear_constraint.c.

References TLinearConstraint::error, TLinearConstraint::ind, TLinearConstraint::max, TLinearConstraint::n, NEW, NewInterval(), and TLinearConstraint::val.

Referenced by LoadMapping().