LpSolverBase Class Reference
[Lp and Mip solvers]

Detailed Description

Todo:: Much more docs

#include <lemon/lp_base.h>

Inheritance diagram for LpSolverBase:

List of all members.

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

Public Types

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

typedef double Value

The floating point type used by the solver.

Public Member Functions

LpSolverBase ()

virtual ~LpSolverBase ()

LpSolverBase * newLp ()

Creates a new LP problem.

LpSolverBase * copyLp ()

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.

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

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

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 a 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 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 getRowBounds (Row c, Value &lower, Value &upper) const

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

Value objCoeff (Col c) const

Get an element of the objective function.

void obj (Expr e)

Set the objective function.

Expr obj () const

Get the objective function.

void max ()

Maximize.

void min ()

Minimize.

bool isMax () const

Query function: is this a maximization problem?

bool isMin () const

Query function: is this a minimization problem?

Solve the LP

SolveExitStatus solve ()

Obtain the solution

SolutionStatus primalStatus () const

The status of the primal problem (the original LP problem).

SolutionStatus dualStatus () const

The status of the dual (of the original LP) problem.

ProblemTypes problemType () const

The type of the original LP problem.

Value primal (Col c) const

Value primal (const Expr &e) const

Value dual (Row r) const

Value dual (const DualExpr &e) const

bool isBasicCol (Col c) const

Value primalValue () const

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 Types

typedef MappedInputIterator< Expr > ConstRowIterator

STL compatible iterator for lp col.

typedef MappedInputIterator
< DualExpr > ConstColIterator

STL compatible iterator for lp row.

typedef MappedOutputIterator
< Expr > RowIterator

STL compatible iterator for lp col.

typedef MappedOutputIterator
< DualExpr > ColIterator

STL compatible iterator for lp row.

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 hasn't 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

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.

DualExpr col ( Col c ) const [inline]

Parameters:

r

is the column to get

Returns:: the dual expression associated to the column

Col addCol	(	const DualExpr &	e,
		Value	o = `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 temporary function. The interface will change to a better one.

Todo:: Option to control whether a constraint with a single variable is added or not.

void row	(	Row	r,
		const Constr &	c
	)			`[inline]`

Parameters:

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

Expr row ( Row r ) const [inline]

Parameters:

r

is the row to get

Returns:: the expression associated to the row

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 temporary 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 ) const [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

Col colByName ( const std::string & name ) const [inline]

Parameters:

name

The name of the column

Returns:: the proper column or INVALID

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

Value coeff	(	Row	r,
		Col	c
	)			const `[inline]`

Parameters:

	r	is the row of the element in question
	c	is the coloumn of the element in question

Returns:: the corresponding 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.

Value colLowerBound ( Col c ) const [inline]

This function returns the lower bound for column (variable) c (this might be -INF as well).

Returns:: The lower bound for coloumn c

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.

Value colUpperBound ( Col c ) const [inline]

This function returns the upper bound for column (variable) c (this might be INF as well).

Returns:: The upper bound for coloumn c

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 bound 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. There is no separate function for the lower and the upper bound because that would have been hard to implement for CPLEX.

void getRowBounds	(	Row	c,
		Value &	lower,
		Value &	upper
	)			const `[inline]`

The lower and the upper bound of a constraint (row) are extended numbers of type Value, i.e. finite numbers of type Value, -INF or INF.

Todo:: There is no separate function for the lower and the upper bound because we had problems with the implementation of the setting functions for CPLEX: check out whether this can be done for these functions.

void obj ( Expr e ) [inline]

Parameters:

e

is a linear expression of type Expr.

Expr obj ( ) const [inline]

Returns:: the objective function as a linear expression of type Expr.

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


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...
Public Types
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...
typedef double	Value
	The floating point type used by the solver.
Public Member Functions
	LpSolverBase ()

virtual	~LpSolverBase ()

LpSolverBase *	newLp ()
	Creates a new LP problem.
LpSolverBase *	copyLp ()
	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.
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 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.
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	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) 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.
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 a 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 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	getRowBounds (Row c, Value &lower, Value &upper) const
	Get 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.
Value	objCoeff (Col c) const
	Get an element of the objective function.
void	obj (Expr e)
	Set the objective function.
Expr	obj () const
	Get the objective function.
void	max ()
	Maximize.
void	min ()
	Minimize.
bool	isMax () const
	Query function: is this a maximization problem?
bool	isMin () const
	Query function: is this a minimization problem?
Solve the LP
SolveExitStatus	solve ()
Obtain the solution
SolutionStatus	primalStatus () const
	The status of the primal problem (the original LP problem).
SolutionStatus	dualStatus () const
	The status of the dual (of the original LP) problem.
ProblemTypes	problemType () const
	The type of the original LP problem.
Value	primal (Col c) const

Value	primal (const Expr &e) const

Value	dual (Row r) const

Value	dual (const DualExpr &e) const

bool	isBasicCol (Col c) const

Value	primalValue () const

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 Types
typedef MappedInputIterator< Expr >	ConstRowIterator
	STL compatible iterator for lp col.
typedef MappedInputIterator < DualExpr >	ConstColIterator
	STL compatible iterator for lp row.
typedef MappedOutputIterator < Expr >	RowIterator
	STL compatible iterator for lp col.
typedef MappedOutputIterator < DualExpr >	ColIterator
	STL compatible iterator for lp row.

LpSolverBase Class Reference [Lp and Mip solvers]

Detailed Description

Classes

Public Types

Public Member Functions

Static Public Attributes

Protected Types

Member Enumeration Documentation

Member Function Documentation

LpSolverBase Class Reference
[Lp and Mip solvers]