simplex.h File Reference

Detailed Description

Definition of the TSimplex type and the associated functions. This interface is common to the different simplex engines. To add a new simplex engine you have to re-implement these functions for the new engine.
Right now we have three possible simplex backends

Clp is the preferred option.

See Also
TSimplex, simplex_clp.c, simplex_glpk.c, simplex_lpsolve.c.

Definition in file simplex.h.

Data Structures

struct  TSimplex
 A simplex tableau structure. More...
 

Macros

#define SimplexType   LPX
 The simples tableau type when using Glpk. More...
 
#define SimplexType   __attribute__ ((aligned(8))) Clp_Simplex
 The simples tableau type when using Glpk. More...
 
#define SimplexType   lprec
 The simples tableau type when using Glpk. More...
 
#define SIMPLEX_TIMEOUT   10
 Simplex timeout. More...
 

Functions

void SimplexCreate (double epsilon, unsigned int ncols, TSimplex *s)
 Constructor. More...
 
void ResetSimplex (TSimplex *s)
 Resets the simplex structure. More...
 
unsigned int SimplexNColumns (TSimplex *s)
 Gets the number of columns (i.e., variables) of the simplex structure. More...
 
unsigned int SimplexNRows (TSimplex *s)
 Gets the number of rows (i.e., constraints) of the simplex structure. More...
 
void SimplexSetColBounds (unsigned int ncol, Tinterval *i, TSimplex *s)
 Sets the bounds for a given column (i.e., variable). More...
 
void SimplexGetColBounds (unsigned int ncol, Tinterval *i, TSimplex *s)
 Gets the bounds for a given column (i.e., variable). More...
 
void SimplexGetColConstraint (unsigned int ncol, TLinearConstraint *lc, TSimplex *s)
 Gets a column from the simplex in the form of a linear constraint. More...
 
boolean SimplexColEmpty (unsigned int ncol, TSimplex *s)
 Checks if a simplex column is empty. More...
 
double SimplexGetColPrimal (unsigned int ncol, TSimplex *s)
 Gets a column primal value after solving the simplex. More...
 
double SimplexGetColDual (unsigned int ncol, TSimplex *s)
 Gets a column dual value after solving the simplex. More...
 
void SimplexSetRowBounds (unsigned int nrow, Tinterval *i, TSimplex *s)
 Sets the bounds for a given row (i.e., constraint). More...
 
void SimplexGetRowBounds (unsigned int nrow, Tinterval *i, TSimplex *s)
 Gets the bounds for a given row (i.e., constraint). More...
 
void SimplexGetRowConstraint (unsigned int nrow, TLinearConstraint *lc, TSimplex *s)
 Gets a row constraint from the simplex. More...
 
double SimplexGetRowPrimal (unsigned int nrow, TSimplex *s)
 Gets a row primal value after solving the simplex. More...
 
double SimplexGetRowDual (unsigned int nrow, TSimplex *s)
 Gets a row dual value after solving the simplex. More...
 
void SimplexAddNewConstraintRaw (TLinearConstraint *lc, TSimplex *s)
 Adds a row (i.e., a constraint) to the simplex. More...
 
void SimplexSetOptimizationFunction (TLinearConstraint *obj, TSimplex *s)
 Sets a new objective function. More...
 
void SimplexGetOptimizationFunction (TLinearConstraint *obj, TSimplex *s)
 Gets a current objective function. More...
 
double SimplexGetOptimalValueRaw (TSimplex *s)
 Gets the optimal value after optimizing the problem. More...
 
unsigned int SimplexSolve (TSimplex *s)
 Determines an optimal value. More...
 
void SimplexDelete (TSimplex *s)
 Destructor. More...
 
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 *b, 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...
 

Macro Definition Documentation

#define SimplexType   LPX

The simples tableau type when using Lp_solve.

The simples tableau type when using Clp.

Definition at line 33 of file simplex.h.

#define SimplexType   __attribute__ ((aligned(8))) Clp_Simplex

The simples tableau type when using Lp_solve.

The simples tableau type when using Clp.

Definition at line 33 of file simplex.h.

#define SimplexType   lprec

The simples tableau type when using Lp_solve.

The simples tableau type when using Clp.

Definition at line 33 of file simplex.h.

#define SIMPLEX_TIMEOUT   10

Maximum time (in seconds) we give the simplex process to return a solution when minimizing/mazimizing for a single variable.

This figure is scaled by the number of columns in the simplex.

Definition at line 63 of file simplex.h.

Referenced by SimplexCreate().

Function Documentation

void SimplexCreate ( double  epsilon,
unsigned int  ncols,
TSimplex s 
)

Creates a simplex structure with a given number of columns (i.e., variables) but with no rows (i.e., constraints).

Parameters
epsilonThreshold to decide if a value is too small to be added to the tableau. It is also used to set up internal simplex parameters.
ncolsNumber of columns for the tableau.
sThe simplex structure.

Definition at line 22 of file simplex_clp.c.

References Error(), TSimplex::fakeRows, INF, TSimplex::inf, TSimplex::lower, TSimplex::lp, NEW, TSimplex::obj, SIMPLEX_TIMEOUT, and TSimplex::upper.

Referenced by ReduceBox().

void ResetSimplex ( TSimplex s)

Removes the rows (i.e., constraints) from the simplex structure.

Parameters
sThe simplex structure.

Definition at line 96 of file simplex_clp.c.

References TSimplex::lp.

Referenced by ReduceBox(), and ReduceRange().

unsigned int SimplexNColumns ( TSimplex s)

Gets the number of columns (i.e., variables) of the simplex structure.

Parameters
sThe simplex structure.
Returns
The number of columns (i.e., variables) of the simplex structure.

Definition at line 102 of file simplex_clp.c.

References TSimplex::lp.

Referenced by SimplexGetOptimalValue(), SimplexGetOptimizationFunction(), SimplexGetRowConstraint(), and SimplexSetOptimizationFunction().

unsigned int SimplexNRows ( TSimplex s)

Gets the number of rows (i.e., constraints) of the simplex structure.

Parameters
sThe simplex structure.
Returns
The number of rows (i.e., constraints) of the simplex structure.

Definition at line 107 of file simplex_clp.c.

References TSimplex::fakeRows, and TSimplex::lp.

Referenced by ReduceBox(), SimplexAddNewConstraintRaw(), SimplexColEmpty(), SimplexDelete(), SimplexGetColConstraint(), SimplexGetColDual(), SimplexGetColPrimal(), SimplexGetOptimalValue(), SimplexGetOptimizationFunction(), and SimplexGetRowConstraint().

void SimplexSetColBounds ( unsigned int  ncol,
Tinterval i,
TSimplex s 
)

Sets the bounds for a given column (i.e., variable).

Parameters
ncolThe column whose range we have to update.
iThe new range for the column.
sThe simplex structure.

Definition at line 113 of file simplex_clp.c.

References INF, TSimplex::inf, TSimplex::lower, LowerLimit(), TSimplex::lp, TSimplex::upper, and UpperLimit().

Referenced by SetSimplexBounds().

void SimplexGetColBounds ( unsigned int  ncol,
Tinterval i,
TSimplex s 
)

Gets the bounds for a given column (i.e., variable).

Parameters
ncolThe column whose range we have to update.
iThe output range with the column bounds.
sThe simplex structure.

Definition at line 123 of file simplex_clp.c.

References INF, TSimplex::inf, TSimplex::lp, and NewInterval().

Referenced by SimplexGetColConstraint().

void SimplexGetColConstraint ( unsigned int  ncol,
TLinearConstraint lc,
TSimplex s 
)

Gets a column from the simplex in the form of a linear constraint.

Parameters
ncolThe column whose constraint we want to get.
lcThe output linear constraint.
sThe simplex structure.

Definition at line 133 of file simplex_clp.c.

References AddTerm2LinearConstraint(), InitLinearConstraint(), TSimplex::lp, NEW, SetLinearConstraintError(), SimplexGetColBounds(), and SimplexNRows().

Referenced by SimplexGetOptimalValue().

boolean SimplexColEmpty ( unsigned int  ncol,
TSimplex s 
)

Gets a column constraint from the simplex.

Parameters
ncolThe column whose constraint we want to get.
sThe simplex structure.
Returns
TRUE if the simplex column is empty.

Definition at line 159 of file simplex_clp.c.

References TSimplex::lp, NEW, and SimplexNRows().

Referenced by ReduceBox().

double SimplexGetColPrimal ( unsigned int  ncol,
TSimplex s 
)

Gets a column primal value after solving the simplex.

Parameters
ncolThe column whose primal value we need.
sThe simplex structure.
Returns
The primal value for the column.

Definition at line 168 of file simplex_clp.c.

References TSimplex::lp, and SimplexNRows().

double SimplexGetColDual ( unsigned int  ncol,
TSimplex s 
)

Gets a column dual value after solving the simplex.

Parameters
ncolThe column whose dual value we need.
sThe simplex structure.
Returns
The primal value for the column.

Definition at line 177 of file simplex_clp.c.

References TSimplex::lp, and SimplexNRows().

void SimplexSetRowBounds ( unsigned int  nrow,
Tinterval i,
TSimplex s 
)

Sets the bounds for a given row (i.e., constraint).

Parameters
nrowThe column whose range we have to update.
iThe new range for the row.
sThe simplex structure.

Definition at line 187 of file simplex_clp.c.

References Error(), INF, TSimplex::inf, IntervalSize(), LowerLimit(), TSimplex::lp, and UpperLimit().

Referenced by SimplexAddNewConstraintRaw().

void SimplexGetRowBounds ( unsigned int  nrow,
Tinterval i,
TSimplex s 
)

Gets the bounds for a given row (i.e., constraint).

Parameters
nrowThe column whose range we have to update.
iThe output range with the column bounds.
sThe simplex structure.

Definition at line 193 of file simplex_clp.c.

References TSimplex::fakeRows, INF, TSimplex::inf, TSimplex::lp, and NewInterval().

Referenced by SimplexGetOptimalValue(), and SimplexGetRowConstraint().

void SimplexGetRowConstraint ( unsigned int  nrow,
TLinearConstraint lc,
TSimplex s 
)

Gets a row constraint from the simplex.

Parameters
nrowThe row whose constraint we want to get.
lcThe output linear constraint.
sThe simplex structure.

Definition at line 203 of file simplex_clp.c.

References AddTerm2LinearConstraint(), TSimplex::fakeRows, InitLinearConstraint(), TSimplex::lp, NEW, SetLinearConstraintError(), SimplexGetRowBounds(), SimplexNColumns(), and SimplexNRows().

double SimplexGetRowPrimal ( unsigned int  nrow,
TSimplex s 
)

Gets a row primal value after solving the simplex.

Parameters
nrowThe row whose primal value we need.
sThe simplex structure.
Returns
The primal value for the row.

Definition at line 241 of file simplex_clp.c.

References TSimplex::fakeRows, and TSimplex::lp.

double SimplexGetRowDual ( unsigned int  nrow,
TSimplex s 
)

Gets a row dual value after solving the simplex.

Parameters
nrowThe row whose dual value we need.
sThe simplex structure.
Returns
The dual value for the row.

Definition at line 250 of file simplex_clp.c.

References TSimplex::fakeRows, and TSimplex::lp.

Referenced by SimplexGetOptimalValue().

void SimplexAddNewConstraintRaw ( TLinearConstraint lc,
TSimplex s 
)

Adds a row (i.e., a constraint) to the simplex. This function adds the row without any process of the constraint.

The input linear constraint must have the bound properly expanded (see SimplexExpandBounds) before using this function.

Parameters
lcThe linear constraint to add to the simplex.
sThe simplex structure.
See Also
SimplexAddNewConstraint

Definition at line 259 of file simplex_clp.c.

References Error(), GetLinearConstraintCoefficient(), GetLinearConstraintCoefficients(), GetLinearConstraintError(), GetLinearConstraintVariable(), GetLinearConstraintVariables(), GetNumTermsInLinearConstraint(), LowerLimit(), TSimplex::lp, NEW, PrintInterval(), PrintLinearConstraint(), SimplexNRows(), SimplexSetRowBounds(), TRUE, and UpperLimit().

Referenced by SimplexAddNewConstraint().

void SimplexSetOptimizationFunction ( TLinearConstraint obj,
TSimplex s 
)

Sets a new objective function. We always minimize the objective functions. To maximize just invert the linear constraint before setting it as an optimal function.

Parameters
objThe linear constraint representing the new objective function.
sThe simplex structure.
See Also
SimplexAddNewConstraint, InvertLinearConstraint.

Definition at line 286 of file simplex_clp.c.

References GetLinearConstraintCoefficient(), GetLinearConstraintCoefficients(), GetLinearConstraintVariable(), GetNumTermsInLinearConstraint(), TSimplex::lp, NEW, TSimplex::obj, and SimplexNColumns().

Referenced by ReduceRange().

void SimplexGetOptimizationFunction ( TLinearConstraint obj,
TSimplex s 
)

Gets the current objective function.

Parameters
objThe output linear constraint with the current objective function.
sThe simplex structure.

Definition at line 312 of file simplex_clp.c.

References AddTerm2LinearConstraint(), InitLinearConstraint(), TSimplex::lp, NEW, SimplexNColumns(), and SimplexNRows().

Referenced by SimplexGetOptimalValue().

double SimplexGetOptimalValueRaw ( TSimplex s)

Gets the optimal value after optimizing the problem. This function returns the value as given by the simplex engine in use. See SimplexGetOptimalValue for a procedure that adjusts this raw value to get a numerically safe optimal (i.e., it compensates for floating points rounding errors).

Parameters
sThe simplex structure.
Returns
The optimal value.
See Also
SimplexGetOptimalValue

Definition at line 327 of file simplex_clp.c.

References TSimplex::lp.

Referenced by ReduceRange(), and SimplexGetOptimalValue().

unsigned int SimplexSolve ( TSimplex s)

Determines an optimal value given a set of constraints and an objective function.

Parameters
sThe simplex structure.
Returns
The state after solving: REDUCED_BOX, EMPTY_BOX, UNBOUNDED_BOX, ERROR_IN_PROCESS.

Definition at line 332 of file simplex_clp.c.

References EMPTY_BOX, ERROR_IN_PROCESS, TSimplex::fakeRows, TSimplex::lp, REDUCED_BOX, and UNBOUNDED_BOX.

Referenced by ReduceRange().

void SimplexDelete ( TSimplex s)

Deletes the TSimplex structure and frees the allocated memory.

Parameters
sThe simplex structure.

Definition at line 367 of file simplex_clp.c.

References TSimplex::lower, TSimplex::lp, TSimplex::obj, SimplexNRows(), and TSimplex::upper.

Referenced by ReduceBox().

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

Parameters
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.
Parameters
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.
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

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