simplex.c File Reference

Detailed Description

Implementation of the functions operating on box TSimplex that are independent of the simplex backend.

See Also

TSimplex, simplex.h, simplex_clp.c, simplex_glpk.c, simplex_lpsolve.c.

Definition in file simplex.c.

Functions
void	SimplexExpandBounds (unsigned int eq_type, Tinterval *b)
	Expands an interval according to the equation type. More...
void	SetSimplexBounds (Tbox *b, TSimplex *lp)
	Sets the columns bounds for the simplex. More...
boolean	SimplexAddNewConstraint (double epsilon, unsigned int safeSimplex, TLinearConstraint *lc, unsigned int eq_type, Tinterval *is, TSimplex *s)
	Adds a row (i.e., a constraint) to the simplex. More...
double	SimplexGetOptimalValue (unsigned int safeSimplex, double m, Tbox *x, TSimplex *s)
	Returns the optimal value determined by the simplex corrected to compensate for possible rounding effects. More...
unsigned int	ReduceRange (double epsilon, unsigned int safeSimplex, unsigned int nv, Tbox *b, TSimplex *lp)
	Reduces a variable range using the simplex. More...

Function Documentation

void SimplexExpandBounds	(	unsigned int	eq_type,
		Tinterval *	b
	)

Expands an interval according to the equation type.

• For EQU equations nothing is done.
• For LEQ equations the lower limit is set to infinity.
• For GEQ equations the upper limit is set to infinity.

This is an auxiliary function used when defining the bounds for a given simplex constraint. The implementation of this function is common to all simplex engines. The definition of the constant INF is the one that differs between simplex engines.

Parameters

eq_type	EQU, LEQ, GEQ. Used to set the right bounds for the interval.
b	The interval to expand.

Definition at line 19 of file simplex.c.

References GEQ, INF, LEQ, LowerLimit(), NewInterval(), and UpperLimit().

Referenced by CropEquation(), SetEquationInfo(), and SimplexAddNewConstraint().

void SetSimplexBounds	(	Tbox *	b,
		TSimplex *	lp
	)

Uses the ranges in a box to set the valid ranges for the primary variables of the simplex (i.e., the ranges for the column variables).

Parameters

b	The box from where to get the ranges.
lp	The simplex to set up.

Definition at line 40 of file simplex.c.

References GetBoxIntervals(), GetBoxNIntervals(), INF, IntervalSize(), PrintInterval(), and SimplexSetColBounds().

Referenced by ReduceRange().

boolean SimplexAddNewConstraint	(	double	epsilon,
		unsigned int	safeSimplex,
		TLinearConstraint *	lc,
		unsigned int	eq_type,
		Tinterval *	is,
		TSimplex *	s
	)

Adds a row (i.e., a constraint) after pre-processing it:

• The linear constraint is simplified removing terms with tiny constants (i.e., with a value below epsilon).
• If the linear constraint only involves one equation it is not added to the tableau but it is directly used to reduce the range for the variable.
• Finally, linear constraints not removed in the previous steps are added to the simplex.

Parameters

epsilon	Used to remove tiny elements in the input linear constraint.
safeSimplex	The degree of numerical stability as indicated by the user in the SAFE SIMPLEX parameter.
lc	The linear constraint to add to the simplex.
eq_type	EQU, LEQ, GEQ. Used to set the right bounds for the new simplex row.
is	Ranges for the variables in the problem.
s	The simplex structure.

Returns

TRUE if the constraint could be added without any problem.

Definition at line 67 of file simplex.c.

References BoundedLinearConstraint(), CleanLinearConstraint(), CopyLinearConstraint(), DeleteLinearConstraint(), EQU, GEQ, GetLinearConstraintError(), GetLinearConstraintErrorSize(), GetNumTermsInLinearConstraint(), IntervalCenter(), IntervalSize(), LEQ, NewInterval(), PrintLinearConstraint(), randomDouble(), SetLinearConstraintError(), SimplexAddNewConstraintRaw(), SimplexExpandBounds(), SimplifyLinearConstraint(), TRUE, and ZERO.

Referenced by AddEquation2Simplex(), and LinearizeGeneralEquationInt().

double SimplexGetOptimalValue	(	unsigned int	safeSimplex,
		double	m,
		Tbox *	b,
		TSimplex *	s
	)

Returns the optimal value determined by the simplex corrected to compensate for possible rounding effects.

The procedure implemented in this function is described in

• Arnold neumaier and Oleg Shcherbina, Safe bounds in linear and mixed-integer linear programming Mathematical Programming, Volume 99, Number 2, pp. 283-296, 2004.

Parameters

safeSimplex	0 not to apply the numerical correction for the optimal value.
m	A lower bound for the optimal value. The returned value can not be below this threshold.
b	A box with the bounds for the problem variables.
s	The simplex structure.

Returns

The (possibly) corrected optimal value.

Definition at line 215 of file simplex.c.

References DeleteLinearConstraint(), GetBoxInterval(), GetLinearConstraintCoefficient(), GetLinearConstraintVariable(), GetNumTermsInLinearConstraint(), INF, IntervalAdd(), IntervalProduct(), LowerLimit(), NEW, NewInterval(), ROUNDDOWN, ROUNDNEAR, ROUNDUP, SimplexGetColConstraint(), SimplexGetOptimalValueRaw(), SimplexGetOptimizationFunction(), SimplexGetRowBounds(), SimplexGetRowDual(), SimplexNColumns(), SimplexNRows(), and UpperLimit().

Referenced by ReduceRange().

unsigned int ReduceRange	(	double	epsilon,
		unsigned int	safeSimplex,
		unsigned int	nv,
		Tbox *	b,
		TSimplex *	lp
	)

Reduces a variable range using the given simplex. The reduction basically consists in minimizing and maximizing with an objective function that only takes into account the selected variable.
The simplex algorithm is quite sensible numerically and for some inputs it can produce numerical errors. The frequency of these errors depend on the simplex implementation you use.
Since this operation takes into account all constraints simultaneously, it gives global consistancy.

Parameters

epsilon	Numerical tolerance used to remove tiny elements in the input linear constraint.
safeSimplex	If >1 the simplex process is reseted before the range reduction. If >2 we also resed the simplex process in between the minimization/maximization. All this is done only for simplex engines other that CLP since in CLP the reset has no effect. Finally, with a value >0, we apply the numerical processes to ensure that the optimal value for the simplex are safe (see SimplexGetOptimalValue).
nv	The variable whose range we want to reduce.
b	The box with the ranges for all variables.
lp	The simplex with the constraints to take into account.

Returns

The status of the box after the reduction (EMPTY_BOX, REDUCED_BOX, ERROR_IN_PROCESS)

Definition at line 329 of file simplex.c.

References AddTerm2LinearConstraint(), CopyInterval(), DeleteLinearConstraint(), EMPTY_BOX, EmptyInterval(), Error(), ERROR_IN_PROCESS, FALSE, GetBoxInterval(), INF, InitLinearConstraint(), IntervalSize(), LowerLimit(), PrintInterval(), REDUCED_BOX, ResetLinearConstraint(), ResetSimplex(), SetSimplexBounds(), SimplexGetOptimalValue(), SimplexGetOptimalValueRaw(), SimplexSetOptimizationFunction(), SimplexSolve(), TRUE, UNBOUNDED_BOX, UpdateLowerLimit(), UpdateUpperLimit(), and UpperLimit().

Referenced by ReduceBox().