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.


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.

eq_typeEQU, LEQ, GEQ. Used to set the right bounds for the interval.
bThe 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).

bThe box from where to get the ranges.
lpThe 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.
epsilonUsed to remove tiny elements in the input linear constraint.
safeSimplexThe degree of numerical stability as indicated by the user in the SAFE SIMPLEX parameter.
lcThe linear constraint to add to the simplex.
eq_typeEQU, LEQ, GEQ. Used to set the right bounds for the new simplex row.
isRanges for the variables in the problem.
sThe simplex structure.
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

safeSimplex0 not to apply the numerical correction for the optimal value.
mA lower bound for the optimal value. The returned value can not be below this threshold.
bA box with the bounds for the problem variables.
sThe simplex structure.
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.

epsilonNumerical tolerance used to remove tiny elements in the input linear constraint.
safeSimplexIf >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).
nvThe variable whose range we want to reduce.
bThe box with the ranges for all variables.
lpThe simplex with the constraints to take into account.
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().