linear_constraint.c File Reference

Implementaton of the function operating on TLinearConstraint. More...

#include "linear_constraint.h"
#include "defines.h"
#include "interval.h"
#include <string.h>
#include <math.h>

Go to the source code of this file.

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

Detailed Description

Implementaton of the function operating on TLinearConstraint.

See also:: TLinearConstraint, linear_constraint.h.

Definition in file linear_constraint.c.

Function Documentation

void InitLinearConstraint ( TLinearConstraint * lc )

Creates a new, empty linear constraint.

Parameters:

lc

The linear constraint to initialize.

Definition at line 17 of file linear_constraint.c.

References TLinearConstraint::ind, INIT_NUM_TERMS_LC, TLinearConstraint::max, NEW, ResetLinearConstraint(), and TLinearConstraint::val.

Referenced by CleanLinearConstraint(), CSRemoveVarsWithCtRange(), FixVariableInEquation(), GetFirstOrderApproximationToEquation(), GetOriginalVarRelation(), InitMapping(), IsSimplificable(), LinearEquation2LinearConstraint(), LoadMapping(), ReduceRange(), ScaleLinearConstraint(), SetEquationInfo(), SimplexGetColConstraint(), SimplexGetOptimizationFunction(), SimplexGetRowConstraint(), and SimplifyCuikSystem().

Here is the call graph for this function:

Here is the caller graph for this function:

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:

lc

The 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().

Here is the call graph for this function:

Here is the caller graph for this function:

void CopyLinearConstraint	(	TLinearConstraint *	lc_dst,
		TLinearConstraint *	lc_src
	)

Creates a new linear constraint from another one.

Parameters:

	lc_dst	The linear constraint to initialize.
	lc_src	The 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().

Here is the call graph for this function:

Here is the caller graph for this function:

unsigned int GetNumTermsInLinearConstraint ( TLinearConstraint * lc )

Returns the number of variables involved in a linear constraint.

Parameters:

lc

The linear constraint.

Returns:: The number of variables involved in a linear constraint.

Definition at line 44 of file linear_constraint.c.

References TLinearConstraint::n.

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

Here is the caller graph for this function:

double* GetLinearConstraintCoefficients ( TLinearConstraint * lc )

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

Parameters:

lc

The linear constraint.

Returns:: A pointer to an array of doubles with the variable scale factors.

Definition at line 49 of file linear_constraint.c.

References TLinearConstraint::val.

Referenced by SimplexAddNewConstraintRaw(), and SimplexSetOptimizationFunction().

Here is the caller graph for this function:

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:

	i	The index of the variable in the linear constraint.
	lc	The linear constraint.

Returns:: The variable scale factor.

Definition at line 54 of file linear_constraint.c.

References Error(), and TLinearConstraint::val.

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

Here is the call graph for this function:

Here is the caller graph for this function:

unsigned int* GetLinearConstraintVariables ( TLinearConstraint * lc )

Returns the variables in a linear constraint.

Parameters:

lc

The linear constraint.

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

Definition at line 65 of file linear_constraint.c.

References TLinearConstraint::ind.

Referenced by SimplexAddNewConstraintRaw().

Here is the caller graph for this function:

unsigned int GetLinearConstraintVariable	(	unsigned int	i,
		TLinearConstraint *	lc
	)

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

Parameters:

	i	The index of the variable in the linear constraint.
	lc	The linear constraint.

Returns:: The global identifier of the i-th variable in the linear constraint.

Definition at line 70 of file linear_constraint.c.

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

void GetLinearConstraintError	(	Tinterval *	error,
		TLinearConstraint *	lc
	)

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

Parameters:

	error	Output interval with the right-hand side of the linear constraint.
	lc	The linear constraint.

Definition at line 81 of file linear_constraint.c.

References CopyInterval(), and TLinearConstraint::error.

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

Here is the call graph for this function:

Here is the caller graph for this function:

void SetLinearConstraintError	(	Tinterval *	error,
		TLinearConstraint *	lc
	)

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

Parameters:

	error	The new linear constraint error.
	lc	The linear constraint.

Definition at line 86 of file linear_constraint.c.

References CopyInterval(), and TLinearConstraint::error.

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

Here is the call graph for this function:

Here is the caller graph for this function:

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:

	ct	The ct to add to the linear constraint.
	lc	The linear constraint.

Definition at line 91 of file linear_constraint.c.

References TLinearConstraint::error, and IntervalOffset().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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:

	ind	Global identifier of the variable to add to the linear constraint.
	val	Scale factor for the variable.
	lc	The linear constraint.

Definition at line 96 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().

Here is the caller graph for this function:

double RemoveTermFromLinearConstraint	(	unsigned int	ind,
		TLinearConstraint *	lc
	)

Removes a variable from a linear constraint.

Parameters:

	ind	Identifier of the variable to remove from the linear constraint.
	lc	The linear constraint to update.

Returns:: The scale factor associated with the removed variable.

Definition at line 126 of file linear_constraint.c.

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

Referenced by CSRemoveLCVars().

Here is the caller graph for this function:

boolean LinearConstraintIncludes	(	unsigned int	ind,
		TLinearConstraint *	lc
	)

Checks if a variable is included in a linear constraint.

Parameters:

	ind	Identifier of the variable.
	lc	The linear constraint to check.

Returns:: The scale factor associated with the removed variable.

Definition at line 156 of file linear_constraint.c.

References FALSE, and TLinearConstraint::ind.

Referenced by CSRemoveLCVars().

Here is the caller graph for this function:

void InvertLinearConstraint ( TLinearConstraint * lc )

Changes the sign of a linear constraint.

Parameters:

lc

The linear constraint to invert.

Definition at line 172 of file linear_constraint.c.

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

Referenced by IsSimplificable().

Here is the call graph for this function:

Here is the caller graph for this function:

void ScaleLinearConstraint	(	double	a,
		TLinearConstraint *	lc
	)

Scales a linear constraint.

Parameters:

	a	the scale factor.
	lc	The linear constraint to be scaled.

Definition at line 182 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().

Here is the call graph for this function:

Here is the caller graph for this function:

void AddLinearConstraints	(	TLinearConstraint *	lc1,
		TLinearConstraint *	lc
	)

Adds two a linear constraints.

Parameters:

	lc1	The first linear constraint to add.
	lc	The second linear constraint to add and the place where the output is stored.

Definition at line 199 of file linear_constraint.c.

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

Referenced by CSRemoveLCVars().

Here is the call graph for this function:

Here is the caller graph for this function:

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:

	epsilon	Used to purge variables with a tiny scale factors. This is done as a requirement of the simplex implementations that are unstables for tiny coefficients.
	is	Ranges for all the variables in the problem.
	lc	The linear constraint to clean.

Definition at line 222 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().

Here is the call graph for this function:

Here is the caller graph for this function:

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:

	full	If 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).
	is	Ranges for all the variables in the problem. If the linear constriant triggers a simplification, the range for the variable in the constraint is updated.
	lc	The linear constraint.

Returns:: TRUE if the constraint actually triggered a simplification (i.e., if the linear constraint involves only one variable).

Definition at line 253 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().

Here is the call graph for this function:

Here is the caller graph for this function:

unsigned int CropLinearConstraint	(	double	epsilon,
		Tbox *	b,
		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:

	epsilon	Numerical tolerance.
	b	The box with the ranges for the varibles.
	lc	The linear constraint.

Definition at line 287 of file linear_constraint.c.

References CopyInterval(), EMPTY_BOX, TLinearConstraint::error, FALSE, GetBoxIntervals(), GetBoxNIntervals(), TLinearConstraint::ind, INF, Intersection(), IntervalAdd(), IntervalDivision(), IntervalProduct(), IntervalSize(), IsInside(), LowerLimit(), TLinearConstraint::n, NewInterval(), NOT_REDUCED_BOX, REDUCED_BOX, TRUE, UpperLimit(), TLinearConstraint::val, and ZERO.

Referenced by CropEquation(), and CSRemoveLCVars().

Here is the call graph for this function:

Here is the caller graph for this function:

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:

	scaleOne2Two	gives ct so that lc1*scale=lc2. Only valid if the function returns TRUE.
	lc1	The first linear constraint to compare.
	lc2	The 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 403 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:

	varValues	Values 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).
	lc	The linear constraint to evaluate.

Returns:: The value of the linear constraint.

Definition at line 466 of file linear_constraint.c.

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

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:

	varValues	Intervals for the variables in the system of equations. This function only uses the ranges for the variables in the equation.
	i_out	The result of the evalution.
	lc	The equation.

Definition at line 478 of file linear_constraint.c.

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

Referenced by UpdateOriginalFromSimple().

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

Parameters:

	f	The stream where to write the constraint.
	eq	TRUE 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.
	varName	The 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.
	lc	The linear constraint.