LpSolverBase Class Reference
[General Optimization Tools]

#include <lemon/lp_base.h>

Inherited by LpCplex, LpGlpk, and LpSkeleton.

Inheritance diagram for LpSolverBase:

Inheritance graph
[legend]
List of all members.

Detailed Description

Todo:
Much more docs


Public Types

typedef double Value
 The floating point type used by the solver.
enum  SolveExitStatus { SOLVED = 0, UNSOLVED = 1 }
 Possible outcomes of an LP solving procedure. More...
enum  SolutionStatus {
  UNDEFINED = 0, INFEASIBLE = 1, FEASIBLE = 2, OPTIMAL = 3,
  INFINITE = 4
}
  More...
enum  ProblemTypes {
  PRIMAL_DUAL_FEASIBLE = 0, PRIMAL_FEASIBLE_DUAL_INFEASIBLE = 1, PRIMAL_INFEASIBLE_DUAL_FEASIBLE = 2, PRIMAL_DUAL_INFEASIBLE = 3,
  UNKNOWN = 4
}
 The type of the investigated LP problem More...

Public Member Functions

 LpSolverBase ()
 
virtual ~LpSolverBase ()
 
LpSolverBasenewLp ()
 Creates a new LP problem.
LpSolverBasecopyLp ()
 Makes a copy of the LP problem.
Build up and modify the LP
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 a variables) at once.
void col (Col c, const DualExpr &e)
 Set a column (i.e a dual constraint) of the LP.
Col addCol (const DualExpr &e, Value obj=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 a 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.
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 eraseCol (Col c)
 Erase a coloumn (i.e a variable) from the LP.
void eraseRow (Row r)
 Erase a row (i.e a constraint) from the LP.
std::string ColName (Col c)
 Get the name of a column.
void ColName (Col c, const std::string &name)
 Set the name of a column.
void Coeff (Row r, Col c, Value val)
 Set 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).
template<class T>
void colLowerBound (T &t, Value value)
 Set the lower bound of several columns (i.e a variables) at once.
void colUpperBound (Col c, Value value)
 Set the upper bound of a column (i.e a variable).
template<class T>
void colUpperBound (T &t, Value value)
 Set the lower bound of several columns (i.e a 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 a variables) at once.
void rowBounds (Row c, Value lower, Value upper)
 Set the lower and the upper bounds of a row (i.e a constraint).
void objCoeff (Col c, Value v)
 Set an element of the objective function.
void setObj (Expr e)
 Set the objective function.
void max ()
 Maximize.
void min ()
 Minimize.
Solve the LP
SolveExitStatus solve ()
Obtain the solution
SolutionStatus primalStatus ()
 The status of the primal problem (the original LP problem).
SolutionStatus dualStatus ()
 The status of the dual (of the original LP) problem.
ProblemTypes problemType ()
 The type of the original LP problem.
Value primal (Col c)
 
Value dual (Row r)
 
bool isBasicCol (Col c)
 
Value primalValue ()
 

Static Public Attributes

static const Value INF = std::numeric_limits<Value>::infinity()
 The infinity constant.
static const Value NaN = std::numeric_limits<Value>::quiet_NaN()
 The not a number constant.

Protected Member Functions

virtual LpSolverBase_copyLp ()
virtual ProblemTypes _getProblemType ()=0

Classes

class  Col
 Refer to a column of the LP. More...
class  Constr
 Linear constraint. More...
class  DualExpr
 Linear expression of rows. More...
class  Expr
 Linear expression of variables and a constant component. More...
class  Row
 Refer to a row of the LP. More...


Member Enumeration Documentation

enum SolveExitStatus
 

Enumerator:
SOLVED  This means that the problem has been successfully solved: either an optimal solution has been found or infeasibility/unboundedness has been proved.
UNSOLVED  Any other case (including the case when some user specified limit has been exceeded).

enum SolutionStatus
 

Enumerator:
UNDEFINED  Feasible solution has'n been found (but may exist).

Todo:
NOTFOUND might be a better name.
INFEASIBLE  The problem has no feasible solution.
FEASIBLE  Feasible solution found.
OPTIMAL  Optimal solution exists and found.
INFINITE  The cost function is unbounded.

Todo:
Give a feasible solution and an infinite ray (and the corresponding bases)

enum ProblemTypes
 

Enumerator:
PRIMAL_DUAL_FEASIBLE  Primal-dual feasible.
PRIMAL_FEASIBLE_DUAL_INFEASIBLE  Primal feasible dual infeasible.
PRIMAL_INFEASIBLE_DUAL_FEASIBLE  Primal infeasible dual feasible.
PRIMAL_DUAL_INFEASIBLE  Primal-dual infeasible.
UNKNOWN  Could not determine so far.


Member Function Documentation

virtual LpSolverBase& _copyLp  )  [inline, protected, virtual]
 

Todo:
This should be implemented here, too, when we have problem retrieving routines. It can be overriden.

Reimplemented in LpGlpk, and LpSkeleton.

virtual ProblemTypes _getProblemType  )  [protected, pure virtual]
 

Todo:
This could be implemented here, too, using _getPrimalStatus() and _getDualStatus()

Implemented in LpSkeleton.

int addColSet T &  t  )  [inline]
 

This magic function takes a container as its argument and fills its elements with new columns (i.e. variables)

Parameters:
t can be
  • a standard STL compatible iterable container with Col as its values_type like
           std::vector<LpSolverBase::Col>
           std::list<LpSolverBase::Col>
    
  • a standard STL compatible iterable container with Col as its mapped_type like
           std::map<AnyType,LpSolverBase::Col>
    
  • an iterable lemon write map like
           ListGraph::NodeMap<LpSolverBase::Col>
           ListGraph::EdgeMap<LpSolverBase::Col>
    
Returns:
The number of the created column.

void col Col  c,
const DualExpr e
[inline]
 

Parameters:
c is the column to be modified
e is a dual linear expression (see DualExpr) a better one.

Col addCol const DualExpr e,
Value  obj = 0
[inline]
 

Parameters:
e is a dual linear expression (see DualExpr)
obj is the corresponding component of the objective function. It is 0 by default.
Returns:
The created column.

Row addRow  )  [inline]
 

This function adds a new empty row (i.e a new constraint) to the LP.

Returns:
The created row

int addRowSet T &  t  )  [inline]
 

This magic function takes a container as its argument and fills its elements with new row (i.e. variables)

Parameters:
t can be
  • a standard STL compatible iterable container with Row as its values_type like
           std::vector<LpSolverBase::Row>
           std::list<LpSolverBase::Row>
    
  • a standard STL compatible iterable container with Row as its mapped_type like
           std::map<AnyType,LpSolverBase::Row>
    
  • an iterable lemon write map like
           ListGraph::NodeMap<LpSolverBase::Row>
           ListGraph::EdgeMap<LpSolverBase::Row>
    
Returns:
The number of rows created.

void row Row  r,
Value  l,
const Expr e,
Value  u
[inline]
 

Parameters:
r is the row to be modified
l is lower bound (-INF means no bound)
e is a linear expression (see Expr)
u is the upper bound (INF means no bound)
Bug:
This is a temportary function. The interface will change to a better one.
Todo:
Option to control whether a constraint with a single variable is added or not.
Bug:
EPSILON would be necessary here!!!

void row Row  r,
const Constr c
[inline]
 

Parameters:
r is the row to be modified
c is a linear expression (see Constr)

Row addRow Value  l,
const Expr e,
Value  u
[inline]
 

Parameters:
l is the lower bound (-INF means no bound)
e is a linear expression (see Expr)
u is the upper bound (INF means no bound)
Returns:
The created row.
Bug:
This is a temportary function. The interface will change to a better one.

Row addRow const Constr c  )  [inline]
 

Parameters:
c is a linear expression (see Constr)
Returns:
The created row.

void eraseCol Col  c  )  [inline]
 

Parameters:
c is the coloumn to be deleted
Todo:
Please check this

void eraseRow Row  r  )  [inline]
 

Parameters:
r is the row to be deleted
Todo:
Please check this

std::string ColName Col  c  )  [inline]
 

Parameters:
c is the coresponding coloumn
Returns:
The name of the colunm

void ColName Col  c,
const std::string &  name
[inline]
 

Parameters:
c is the coresponding coloumn
name The name to be given

void Coeff Row  r,
Col  c,
Value  val
[inline]
 

Parameters:
r is the row of the element to be modified
c is the coloumn of the element to be modified
val is the new value of the coefficient

void colLowerBound Col  c,
Value  value
[inline]
 

The lower bound of a variable (column) has to be given by an extended number of type Value, i.e. a finite number of type Value or -INF.

void colLowerBound T &  t,
Value  value
[inline]
 

This magic function takes a container as its argument and applies the function on all of its elements. The lower bound of a variable (column) has to be given by an extended number of type Value, i.e. a finite number of type Value or -INF.

void colUpperBound Col  c,
Value  value
[inline]
 

The upper bound of a variable (column) has to be given by an extended number of type Value, i.e. a finite number of type Value or INF.

void colUpperBound T &  t,
Value  value
[inline]
 

This magic function takes a container as its argument and applies the function on all of its elements. The upper bound of a variable (column) has to be given by an extended number of type Value, i.e. a finite number of type Value or INF.

void colBounds Col  c,
Value  lower,
Value  upper
[inline]
 

The lower and the upper bounds of a variable (column) have to be given by an extended number of type Value, i.e. a finite number of type Value, -INF or INF.

void colBounds T &  t,
Value  lower,
Value  upper
[inline]
 

This magic function takes a container as its argument and applies the function on all of its elements. The lower and the upper bounds of a variable (column) have to be given by an extended number of type Value, i.e. a finite number of type Value, -INF or INF.

void rowBounds Row  c,
Value  lower,
Value  upper
[inline]
 

The lower and the upper bounds of a constraint (row) have to be given by an extended number of type Value, i.e. a finite number of type Value, -INF or INF.

void setObj Expr  e  )  [inline]
 

Parameters:
e is a linear expression of type Expr.
Bug:
Is should be called obj()

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.
Todo:
Which method is used to solve the problem

Value primalValue  )  [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.


The documentation for this class was generated from the following files:
Generated on Fri Feb 3 18:42:06 2006 for LEMON by  doxygen 1.4.6