simplex.c File Reference

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

#include "simplex.h"
#include "defines.h"
#include "random.h"

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

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.

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

Here is the call graph for this function:

Here is the caller graph for this function:

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

Here is the call graph for this function:

Here is the caller graph for this function:

boolean SimplexAddNewConstraint	(	double	epsilon,
		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.
	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 CleanLinearConstraint(), CopyLinearConstraint(), DeleteLinearConstraint(), EQU, GEQ, GetLinearConstraintError(), GetNumTermsInLinearConstraint(), IntervalSize(), LEQ, PrintLinearConstraint(), randomDouble(), SetLinearConstraintError(), SimplexAddNewConstraintRaw(), SimplexExpandBounds(), SimplifyLinearConstraint(), TRUE, and ZERO.

Referenced by AddEquation2Simplex(), and LinearizeGeneralEquationInt().

Here is the call graph for this function:

Here is the caller graph for this function:

double SimplexGetOptimalValue	(	unsigned int	safe_simplex,
		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:

	safe_simplex	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 144 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().

Here is the call graph for this function:

Here is the caller graph for this function:

unsigned int ReduceRange	(	double	epsilon,
		unsigned int	safe_simplex,
		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.
	safe_simplex	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 258 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(), SetLowerLimit(), SetSimplexBounds(), SetUpperLimit(), SimplexGetOptimalValue(), SimplexGetOptimalValueRaw(), SimplexSetOptimizationFunction(), SimplexSolve(), TRUE, UNBOUNDED_BOX, and UpperLimit().

Referenced by ReduceBox().

Here is the call graph for this function:

Here is the caller graph for this function:

simplex.c File Reference

Functions

Detailed Description

Function Documentation