All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
List of all members | Public Types | Public Member Functions
LpSolver Class Referenceabstract

Detailed Description

This class is an abstract base class for LP solvers. This class provides a full interface for set and modify an LP problem, solve it and retrieve the solution. You can use one of the descendants as a concrete implementation, or the Lp default LP solver. However, if you would like to handle LP solvers as reference or pointer in a generic way, you can use this class directly.

#include <lemon/lp_base.h>

+ Inheritance diagram for LpSolver:

Public Types

enum  ProblemType {
  UNDEFINED = 0, INFEASIBLE = 1, FEASIBLE = 2, OPTIMAL = 3,
  UNBOUNDED = 4
}
 The problem types for primal and dual problems. More...
 
enum  VarStatus {
  BASIC, FREE, LOWER, UPPER,
  FIXED
}
 The basis status of variables. More...
 
- Public Types inherited from LpBase
enum  SolveExitStatus { SOLVED = 0, UNSOLVED = 1 }
 Possible outcomes of an LP solving procedure. More...
 
enum  Sense { MIN, MAX }
 Direction of the optimization. More...
 
enum  MessageLevel {
  MESSAGE_NOTHING, MESSAGE_ERROR, MESSAGE_WARNING, MESSAGE_NORMAL,
  MESSAGE_VERBOSE
}
 Enum for messageLevel() parameter. More...
 
typedef double Value
 The floating point type used by the solver.
 

Public Member Functions

virtual LpSolvernewSolver () const =0
 Allocate a new LP problem instance.
 
virtual LpSolvercloneSolver () const =0
 Make a copy of the LP problem.
 
Solve the LP
SolveExitStatus solve ()
 
Obtain the Solution
ProblemType primalType () const
 The type of the primal problem.
 
ProblemType dualType () const
 The type of the dual problem.
 
Value primal (Col c) const
 Return the primal value of the column.
 
Value primal (const Expr &e) const
 Return the primal value of the expression.
 
Value primalRay (Col c) const
 Returns a component of the primal ray.
 
Value dual (Row r) const
 Return the dual value of the row.
 
Value dual (const DualExpr &e) const
 Return the dual value of the dual expression.
 
Value dualRay (Row r) const
 Returns a component of the dual ray.
 
VarStatus colStatus (Col c) const
 Return the basis status of the column.
 
VarStatus rowStatus (Row r) const
 Return the basis status of the row.
 
Value primal () const
 The value of the objective function.
 
- Public Member Functions inherited from LpBase
virtual ~LpBase ()
 Virtual destructor.
 
const char * solverName () const
 Gives back the name of the solver.
 
Col addCol ()
 Add a new empty column (i.e a new variable) to the LP.
 
template<class T >
int addColSet (T &t)
 Adds several new columns (i.e variables) at once.
 
void col (Col c, const DualExpr &e)
 Set a column (i.e a dual constraint) of the LP.
 
DualExpr col (Col c) const
 Get a column (i.e a dual constraint) of the LP.
 
Col addCol (const DualExpr &e, Value o=0)
 Add a new column to the LP.
 
Row addRow ()
 Add a new empty row (i.e a new constraint) to the LP.
 
template<class T >
int addRowSet (T &t)
 Add several new rows (i.e constraints) at once.
 
void row (Row r, Value l, const Expr &e, Value u)
 Set a row (i.e a constraint) of the LP.
 
void row (Row r, const Constr &c)
 Set a row (i.e a constraint) of the LP.
 
Expr row (Row r) const
 Get a row (i.e a constraint) of the LP.
 
Row addRow (Value l, const Expr &e, Value u)
 Add a new row (i.e a new constraint) to the LP.
 
Row addRow (const Constr &c)
 Add a new row (i.e a new constraint) to the LP.
 
void erase (Col c)
 Erase a column (i.e a variable) from the LP.
 
void erase (Row r)
 Erase a row (i.e a constraint) from the LP.
 
std::string colName (Col c) const
 Get the name of a column.
 
void colName (Col c, const std::string &name)
 Set the name of a column.
 
Col colByName (const std::string &name) const
 Get the column by its name.
 
std::string rowName (Row r) const
 Get the name of a row.
 
void rowName (Row r, const std::string &name)
 Set the name of a row.
 
Row rowByName (const std::string &name) const
 Get the row by its name.
 
void coeff (Row r, Col c, Value val)
 Set an element of the coefficient matrix of the LP.
 
Value coeff (Row r, Col c) const
 Get an element of the coefficient matrix of the LP.
 
void colLowerBound (Col c, Value value)
 Set the lower bound of a column (i.e a variable)
 
Value colLowerBound (Col c) const
 Get the lower bound of a column (i.e a variable)
 
template<class T >
void colLowerBound (T &t, Value value)
 Set the lower bound of several columns (i.e variables) at once.
 
void colUpperBound (Col c, Value value)
 Set the upper bound of a column (i.e a variable)
 
Value colUpperBound (Col c) const
 Get the upper bound of a column (i.e a variable)
 
template<class T >
void colUpperBound (T &t, Value value)
 Set the upper bound of several columns (i.e variables) at once.
 
void colBounds (Col c, Value lower, Value upper)
 Set the lower and the upper bounds of a column (i.e a variable)
 
template<class T >
void colBounds (T &t, Value lower, Value upper)
 Set the lower and the upper bound of several columns (i.e variables) at once.
 
void rowLowerBound (Row r, Value value)
 Set the lower bound of a row (i.e a constraint)
 
Value rowLowerBound (Row r) const
 Get the lower bound of a row (i.e a constraint)
 
void rowUpperBound (Row r, Value value)
 Set the upper bound of a row (i.e a constraint)
 
Value rowUpperBound (Row r) const
 Get the upper bound of a row (i.e a constraint)
 
void objCoeff (Col c, Value v)
 Set an element of the objective function.
 
Value objCoeff (Col c) const
 Get an element of the objective function.
 
void obj (const Expr &e)
 Set the objective function.
 
Expr obj () const
 Get the objective function.
 
void sense (Sense sense)
 Set the direction of optimization.
 
Sense sense () const
 Query the direction of the optimization.
 
void max ()
 Set the sense to maximization.
 
void min ()
 Set the sense to maximization.
 
void clear ()
 Clears the problem.
 
void messageLevel (MessageLevel level)
 Sets the message level of the solver.
 

Additional Inherited Members

- Static Public Member Functions inherited from LpBase
static int id (const Col &col)
 Returns the ID of the column.
 
static Col colFromId (int id)
 Returns the column with the given ID.
 
static int id (const Row &row)
 Returns the ID of the row.
 
static Row rowFromId (int id)
 Returns the row with the given ID.
 
- Static Public Attributes inherited from LpBase
static const Value INF
 The infinity constant.
 
static const Value NaN
 The not a number constant.
 

Member Enumeration Documentation

Enumerator:
UNDEFINED 

= 0. Feasible solution hasn't been found (but may exist).

INFEASIBLE 

= 1. The problem has no feasible solution.

FEASIBLE 

= 2. Feasible solution found.

OPTIMAL 

= 3. Optimal solution exists and found.

UNBOUNDED 

= 4. The cost function is unbounded.

enum VarStatus
Enumerator:
BASIC 

The variable is in the basis.

FREE 

The variable is free, but not basic.

LOWER 

The variable has active lower bound.

UPPER 

The variable has active upper bound.

FIXED 

The variable is non-basic and fixed.

Member Function Documentation

SolveExitStatus solve ( )
inline

Solve the LP problem at hand

Returns
The result of the optimization procedure. Possible values and their meanings can be found in the documentation of SolveExitStatus.
Value primal ( Col  c) const
inline

Return the primal value of the column.

Precondition
The problem is solved.
Value primal ( const Expr e) const
inline

Return the primal value of the expression, i.e. the dot product of the primal solution and the expression.

Precondition
The problem is solved.
Value primalRay ( Col  c) const
inline

The primal ray is solution of the modified primal problem, where we change each finite bound to 0, and we looking for a negative objective value in case of minimization, and positive objective value for maximization. If there is such solution, that proofs the unsolvability of the dual problem, and if a feasible primal solution exists, then the unboundness of primal problem.

Precondition
The problem is solved and the dual problem is infeasible.
Note
Some solvers does not provide primal ray calculation functions.
Value dual ( Row  r) const
inline

Return the dual value of the row.

Precondition
The problem is solved.
Value dual ( const DualExpr e) const
inline

Return the dual value of the dual expression, i.e. the dot product of the dual solution and the dual expression.

Precondition
The problem is solved.
Value dualRay ( Row  r) const
inline

The dual ray is solution of the modified primal problem, where we change each finite bound to 0 (i.e. the objective function coefficients in the primal problem), and we looking for a ositive objective value. If there is such solution, that proofs the unsolvability of the primal problem, and if a feasible dual solution exists, then the unboundness of dual problem.

Precondition
The problem is solved and the primal problem is infeasible.
Note
Some solvers does not provide dual ray calculation functions.
VarStatus colStatus ( Col  c) const
inline
See Also
VarStatus
VarStatus rowStatus ( Row  r) const
inline
See Also
VarStatus
Value primal ( ) const
inline
Returns
  • INF or -INF means either infeasibility or unboundedness of the primal problem, depending on whether we minimize or maximize.
  • NaN if no primal solution is found.
  • The (finite) objective value if an optimal solution is found.