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 LpSolver *	newSolver () const =0
	Allocate a new LP problem instance.

virtual LpSolver *	cloneSolver () 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 ()
	Clear the problem.

void	messageLevel (MessageLevel level)
	Set the message level of the solver.

void	write (std::string file, std::string format="MPS") const
	Write the problem to a file in the given format.

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

enum ProblemType

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.

Detailed Description

Public Types

Public Member Functions

Additional Inherited Members

Member Enumeration Documentation

Member Function Documentation