LpBase
Declared in lemon/lp_base.h, in the group LP and MIP Solvers; the same class on the Doxygen site.
-
class LpBase
Common base class for LP and MIP solvers.
Usually this class is not used directly, please use one of the concrete implementations of the solver interface.
Subclassed by CplexBase, GlpkBase, LpSolver, MipSolver, SkeletonSolverBase
Build Up and Modify the LP
-
template< class T >
inline int addColSet( T & t ) Adds several new columns (i.e variables) at once.
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_typelikestd::vector< LpBase::Col > std::list< LpBase::Col >
a standard STL compatible iterable container with Col as its
mapped_typelikestd::map< AnyType , LpBase::Col >
an iterable lemon write map like
ListGraph::NodeMap< LpBase::Col > ListGraph::ArcMap< LpBase::Col >
- Returns:
The number of the created column.
-
inline void col( Col c , const DualExpr & e )
Set a column (i.e a dual constraint) of the LP.
- Parameters:
c – is the column to be modified
e – is a dual linear expression (see DualExpr) a better one.
-
inline DualExpr col( Col c ) const
Get a column (i.e a dual constraint) of the LP.
- Parameters:
c – is the column to get
- Returns:
the dual expression associated to the column
-
inline Col addCol( const DualExpr & e , Value o = 0 )
Add a new column to the LP.
- Parameters:
e – is a dual linear expression (see DualExpr)
o – is the corresponding component of the objective function. It is 0 by default.
- Returns:
The created column.
-
inline Row addRow()
Add a new empty row (i.e a new constraint) to the LP.
This function adds a new empty row (i.e a new constraint) to the LP.
- Returns:
The created row
-
template< class T >
inline int addRowSet( T & t ) Add several new rows (i.e constraints) at once.
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_typelikestd::vector< LpBase::Row > std::list< LpBase::Row >
a standard STL compatible iterable container with Row as its
mapped_typelikestd::map< AnyType , LpBase::Row >
an iterable lemon write map like
ListGraph::NodeMap< LpBase::Row > ListGraph::ArcMap< LpBase::Row >
- Returns:
The number of rows created.
-
inline void row( Row r , Value l , const Expr & e , Value u )
Set a row (i.e a constraint) of the LP.
-
inline void row( Row r , const Constr & c )
Set a row (i.e a constraint) of the LP.
- Parameters:
r – is the row to be modified
c – is a linear expression (see Constr)
-
inline Expr row( Row r ) const
Get a row (i.e a constraint) of the LP.
- Parameters:
r – is the row to get
- Returns:
the expression associated to the row
-
inline Row addRow( Value l , const Expr & e , Value u )
Add a new row (i.e a new constraint) to the LP.
-
inline Row addRow( const Constr & c )
Add a new row (i.e a new constraint) to the LP.
- Parameters:
c – is a linear expression (see Constr)
- Returns:
The created row.
-
inline void erase( Col c )
Erase a column (i.e a variable) from the LP.
- Parameters:
c – is the column to be deleted
-
inline void erase( Row r )
Erase a row (i.e a constraint) from the LP.
- Parameters:
r – is the row to be deleted
-
inline std::string colName( Col c ) const
Get the name of a column.
- Parameters:
c – is the coresponding column
- Returns:
The name of the colunm
-
inline void colName( Col c , const std::string & name )
Set the name of a column.
- Parameters:
c – is the coresponding column
name – The name to be given
-
inline Col colByName( const std::string & name ) const
Get the column by its name.
- Parameters:
name – The name of the column
- Returns:
the proper column or
INVALID
-
inline std::string rowName( Row r ) const
Get the name of a row.
- Parameters:
r – is the coresponding row
- Returns:
The name of the row
-
inline void rowName( Row r , const std::string & name )
Set the name of a row.
- Parameters:
r – is the coresponding row
name – The name to be given
-
inline Row rowByName( const std::string & name ) const
Get the row by its name.
- Parameters:
name – The name of the row
- Returns:
the proper row or
INVALID
-
inline void coeff( Row r , Col c , Value val )
Set an element of the coefficient matrix of the LP.
- Parameters:
r – is the row of the element to be modified
c – is the column of the element to be modified
val – is the new value of the coefficient
-
inline Value coeff( Row r , Col c ) const
Get an element of the coefficient matrix of the LP.
- Parameters:
r – is the row of the element
c – is the column of the element
- Returns:
the corresponding coefficient
-
inline void colLowerBound( Col c , Value value )
Set the lower bound of a column (i.e a variable).
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.
-
inline Value colLowerBound( Col c ) const
Get the lower bound of a column (i.e a variable).
This function returns the lower bound for column (variable)
c(this might be -INF as well).- Returns:
The lower bound for column
c
-
template< class T >
inline void colLowerBound( T & t , Value value ) Set the lower bound of several columns (i.e variables) at once.
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.
-
inline void colUpperBound( Col c , Value value )
Set the upper bound of a column (i.e a variable).
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.
-
inline Value colUpperBound( Col c ) const
Get the upper bound of a column (i.e a variable).
This function returns the upper bound for column (variable)
c(this might be INF as well).- Returns:
The upper bound for column
c
-
template< class T >
inline void colUpperBound( T & t , Value value ) Set the upper bound of several columns (i.e variables) at once.
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.
-
inline void colBounds( Col c , Value lower , Value upper )
Set the lower and the upper bounds of a column (i.e a variable).
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.
-
template< class T >
inline void colBounds( T & t , Value lower , Value upper ) Set the lower and the upper bound of several columns (i.e variables) at once.
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.
-
inline void rowLowerBound( Row r , Value value )
Set the lower bound of a row (i.e a constraint).
The lower bound of a constraint (row) has to be given by an extended number of type Value, i.e. a finite number of type Value or -INF.
-
inline Value rowLowerBound( Row r ) const
Get the lower bound of a row (i.e a constraint).
This function returns the lower bound for row (constraint)
c(this might be -INF as well).- Returns:
The lower bound for row
r
-
inline void rowUpperBound( Row r , Value value )
Set the upper bound of a row (i.e a constraint).
The upper bound of a constraint (row) has to be given by an extended number of type Value, i.e. a finite number of type Value or -INF.
-
inline Value rowUpperBound( Row r ) const
Get the upper bound of a row (i.e a constraint).
This function returns the upper bound for row (constraint)
c(this might be -INF as well).- Returns:
The upper bound for row
r
-
inline void obj( const Expr & e )
Set the objective function.
- Parameters:
e – is a linear expression of type Expr.
-
inline Expr obj() const
Get the objective function.
- Returns:
the objective function as a linear expression of type Expr.
-
inline void max()
Set the sense to maximization.
-
inline void min()
Set the sense to maximization.
-
inline void clear()
Clear the problem.
-
inline void messageLevel( MessageLevel level )
Set the message level of the solver.
-
inline void write( std::string file , std::string format = "MPS" ) const
Write the problem to a file in the given format.
This function writes the problem to a file in the given format. Different solver backends may support different formats. Trying to write in an unsupported format will trigger UnsupportedFormatError. For the supported formats, visit the documentation of the base class of the related backends (CplexBase, GlpkBase etc.)
- Parameters:
file – The file path
format – The output file format.
Public Types
-
enum SolveExitStatus
Possible outcomes of an LP solving procedure.
Values:
-
enumerator SOLVED
= 0. It means that the problem has been successfully solved: either an optimal solution has been found or infeasibility/unboundedness has been proved.
-
enumerator UNSOLVED
= 1. Any other case (including the case when some user specified limit has been exceeded).
-
enumerator SOLVED
-
enum Sense
Direction of the optimization.
Values:
-
enumerator MIN
Minimization.
-
enumerator MAX
Maximization.
-
enumerator MIN
-
enum MessageLevel
Enum for
messageLevel()parameter.Values:
-
enumerator MESSAGE_NOTHING
No output (default value).
-
enumerator MESSAGE_ERROR
Error messages only.
-
enumerator MESSAGE_WARNING
Warnings.
-
enumerator MESSAGE_NORMAL
Normal output.
-
enumerator MESSAGE_VERBOSE
Verbose output.
-
enumerator MESSAGE_NOTHING
-
typedef double Value
The floating point type used by the solver.
Public Functions
-
inline LemonRangeWrapper1< ColIt , LpBase > cols()
Gets the collection of the columns of the LP problem.
This function can be used for iterating on the columns of the LP problem. It returns a wrapped ColIt, which looks like an STL container (by having begin() and end()) which you can use in range-based for loops, STL algorithms, etc. For example you can write:
for( auto c : lp.cols() ) doSomething( c );
-
inline LemonRangeWrapper1< RowIt , LpBase > rows()
Gets the collection of the rows of the LP problem.
This function can be used for iterating on the rows of the LP problem. It returns a wrapped RowIt, which looks like an STL container (by having begin() and end()) which you can use in range-based for loops, STL algorithms, etc. For example you can write:
for( auto c : lp.rows() ) doSomething( c );
-
inline virtual ~LpBase()
Virtual destructor.
-
inline const char * solverName() const
Gives back the name of the solver.
Public Static Functions
Public Static Attributes
Protected Functions
-
inline virtual int _addColId( int col )
-
inline virtual int _addRowId( int row )
-
inline virtual void _eraseColId( int col )
-
inline virtual void _eraseRowId( int row )
-
virtual int _addCol() = 0
-
virtual int _addRow() = 0
-
inline virtual int _addRow( Value l , ExprIterator b , ExprIterator e , Value u )
-
virtual void _eraseCol( int col ) = 0
-
virtual void _eraseRow( int row ) = 0
-
virtual void _getColName( int col , std::string & name ) const = 0
-
virtual void _setColName( int col , const std::string & name ) = 0
-
virtual int _colByName( const std::string & name ) const = 0
-
virtual void _getRowName( int row , std::string & name ) const = 0
-
virtual void _setRowName( int row , const std::string & name ) = 0
-
virtual int _rowByName( const std::string & name ) const = 0
-
virtual void _setRowCoeffs( int i , ExprIterator b , ExprIterator e ) = 0
-
virtual void _getRowCoeffs( int i , InsertIterator b ) const = 0
-
virtual void _setColCoeffs( int i , ExprIterator b , ExprIterator e ) = 0
-
virtual void _getColCoeffs( int i , InsertIterator b ) const = 0
-
virtual void _setObjCoeffs( ExprIterator b , ExprIterator e ) = 0
-
virtual void _getObjCoeffs( InsertIterator b ) const = 0
-
virtual void _clear() = 0
-
virtual const char * _solverName() const = 0
-
virtual void _messageLevel( MessageLevel level ) = 0
-
inline LpBase()
-
inline virtual void _write( std::string , std::string format ) const
Friends
- friend class Col
- friend class ColIt
- friend class Row
- friend class RowIt
-
inline LpBase::Expr operator*( const LpBase::Expr & a , const LpBase::Value & b )
Multiply with constant.
-
inline LpBase::Expr operator*( const LpBase::Value & a , const LpBase::Expr & b )
Multiply with constant.
-
inline LpBase::Expr operator/( const LpBase::Expr & a , const LpBase::Value & b )
Divide with constant.
-
inline LpBase::Constr operator<=( const LpBase::Expr & e , const LpBase::Expr & f )
Create constraint.
-
inline LpBase::Constr operator<=( const LpBase::Value & e , const LpBase::Expr & f )
Create constraint.
-
inline LpBase::Constr operator<=( const LpBase::Expr & e , const LpBase::Value & f )
Create constraint.
-
inline LpBase::Constr operator>=( const LpBase::Expr & e , const LpBase::Expr & f )
Create constraint.
-
inline LpBase::Constr operator>=( const LpBase::Value & e , const LpBase::Expr & f )
Create constraint.
-
inline LpBase::Constr operator>=( const LpBase::Expr & e , const LpBase::Value & f )
Create constraint.
-
inline LpBase::Constr operator==( const LpBase::Expr & e , const LpBase::Value & f )
Create constraint.
-
inline LpBase::Constr operator==( const LpBase::Expr & e , const LpBase::Expr & f )
Create constraint.
-
inline LpBase::Constr operator<=( const LpBase::Value & n , const LpBase::Constr & c )
Create constraint.
-
inline LpBase::Constr operator<=( const LpBase::Constr & c , const LpBase::Value & n )
Create constraint.
-
inline LpBase::Constr operator>=( const LpBase::Value & n , const LpBase::Constr & c )
Create constraint.
-
inline LpBase::Constr operator>=( const LpBase::Constr & c , const LpBase::Value & n )
Create constraint.
-
inline LpBase::DualExpr operator+( const LpBase::DualExpr & a , const LpBase::DualExpr & b )
Addition.
-
inline LpBase::DualExpr operator-( const LpBase::DualExpr & a , const LpBase::DualExpr & b )
Substraction.
-
inline LpBase::DualExpr operator*( const LpBase::DualExpr & a , const LpBase::Value & b )
Multiply with constant.
-
class Col
Refer to a column of the LP.
This type is used to refer to a column of the LP.
Its value remains valid and correct even after the addition or erase of other columns.
Note
This class is similar to other Item types in LEMON, like Node and Arc types in digraph.
Subclassed by LpBase::ColIt
Public Functions
-
Col() = default
Default constructor.
-
inline Col( const Invalid & )
Invalid constructor & conversion.
This constructor initializes the Col to be invalid.
See also
Invalid for more details.
-
inline bool operator==( Col c ) const
Equality operator.
Two Cols are equal if and only if they point to the same LP column or both are invalid.
-
inline bool operator<( Col c ) const
Artificial ordering operator.
To allow the use of this object in std::map or similar associative container we require this.
Note
This operator only have to define some strict ordering of the items; this order has nothing to do with the iteration ordering of the items.
Protected Functions
-
inline explicit Col( int id )
Protected Attributes
-
int _id
-
Col() = default
-
class ColIt : public LpBase::Col
Iterator for iterate over the columns of an LP problem.
Its usage is quite simple, for example, you can count the number of columns in an LP
lp:int count = 0; for( LpBase::ColIt c( lp ) ; c != INVALID ; ++c ) ++count;
-
class Row
Refer to a row of the LP.
This type is used to refer to a row of the LP.
Its value remains valid and correct even after the addition or erase of other rows.
Note
This class is similar to other Item types in LEMON, like Node and Arc types in digraph.
Subclassed by LpBase::RowIt
Public Functions
-
Row() = default
Default constructor.
-
inline Row( const Invalid & )
Invalid constructor & conversion.
This constructor initializes the Row to be invalid.
See also
Invalid for more details.
-
inline bool operator==( Row r ) const
Equality operator.
Two Rows are equal if and only if they point to the same LP row or both are invalid.
-
inline bool operator<( Row r ) const
Artificial ordering operator.
To allow the use of this object in std::map or similar associative container we require this.
Note
This operator only have to define some strict ordering of the items; this order has nothing to do with the iteration ordering of the items.
Protected Functions
-
inline explicit Row( int id )
Protected Attributes
-
int _id
-
Row() = default
-
class RowIt : public LpBase::Row
Iterator for iterate over the rows of an LP problem.
Its usage is quite simple, for example, you can count the number of rows in an LP
lp:int count = 0; for( LpBase::RowIt c( lp ) ; c != INVALID ; ++c ) ++count;
-
class Expr
Linear expression of variables and a constant component.
This data structure stores a linear expression of the variables (Cols) and also has a constant component.
There are several ways to access and modify the contents of this container.
or you can also iterate through its elements.e[ v ] = 5; e[ v ] += 12; e.erase( v );
(This code computes the primal value of the expression).double s = 0; for( LpBase::Expr::ConstCoeffIt i( e ) ; i != INVALID ; ++i ) s += *i * primal( i );
Numbers (
double’s) and variables (Cols) directly convert to an Expr and the usual linear operations are defined, soare valid expressions. The usual assignment operations are also defined.v + w 2 * v - 3.12 * ( v - w / 2 ) + 2 v * 2.1 + ( 3 * v + ( v * 12 + w + 6 ) * 3 ) / 2
e = v + w; e += 2 * v - 3.12 * ( v - w / 2 ) + 2; e *= 3.4; e /= 5;
The constant member can be set and read by dereference operator (unary *)
*e = 12; double c = *e;
See also
Public Types
-
typedef True SolverExpr
Public Functions
-
inline Expr()
Default constructor.
Construct an empty expression, the coefficients and the constant component are initialized to zero.
-
inline Expr( const Col & c )
Construct an expression from a column.
Construct an expression, which has a term with
cvariable and 1.0 coefficient.
-
inline Expr( const Value & v )
Construct an expression from a constant.
Construct an expression, which’s constant component is
v.
-
inline void simplify( Value epsilon = 0.0 )
Removes the coefficients which’s absolute value does not exceed
epsilon. It also sets to zero the constant component, if it does not exceed epsilon in absolute value.
-
inline void clear()
Sets all coefficients and the constant component to 0.
-
inline LpBase::Expr operator*( const LpBase::Expr & a , const LpBase::Value & b )
Multiply with constant.
-
class CoeffIt
Iterator over the expression.
The iterator iterates over the terms of the expression.
double s = 0; for( LpBase::Expr::CoeffIt i( e ) ; i != INVALID ; ++i ) s += *i * primal( i );
-
class ConstCoeffIt
Const iterator over the expression.
The iterator iterates over the terms of the expression.
double s = 0; for( LpBase::Expr::ConstCoeffIt i( e ) ; i != INVALID ; ++i ) s += *i * primal( i );
Public Functions
-
inline ConstCoeffIt( const Expr & e )
Sets the iterator to the first term.
Sets the iterator to the first term of the expression.
-
inline ConstCoeffIt & operator++()
Next term.
Assign the iterator to the next term.
-
inline ConstCoeffIt( const Expr & e )
-
class Constr
Linear constraint.
This data stucture represents a linear constraint in the LP. Basically it is a linear expression with a lower or an upper bound (or both). These parts of the constraint can be obtained by the member functions expr(), lowerBound() and upperBound(), respectively. There are two ways to construct a constraint.
You can set the linear expression and the bounds directly by the functions above.
The operators
<=,==and>=are defined between expressions, or even between constraints whenever it makes sense. Therefore ifeandfare linear expressions andsandtare numbers, then the followings are valid expressions and thus they can be used directly e.g. in addRow() whenever it makes sense.e <= s e <= f e == f s <= e <= t e >= t
Warning
The validity of a constraint is checked only at run time, so e.g. addRow() of
(x[1]<=5)<=6, which sets the upper bound twice, will compile, but will fail an assertion, whilex[1]<=x[2]<=5is the valid constraint0< =x[2]-x[1]<=5.Public Functions
-
inline Constr()
-
inline void clear()
-
inline const Value & lowerBound() const
The const version of lowerBound().
-
inline const Value & upperBound() const
The const version of upperBound().
-
inline bool lowerBounded() const
Is the constraint lower bounded?
-
inline bool upperBounded() const
Is the constraint upper bounded?
-
inline LpBase::Constr operator<=( const LpBase::Expr & e , const LpBase::Expr & f )
Create constraint.
-
inline LpBase::Constr operator<=( const LpBase::Value & e , const LpBase::Expr & f )
Create constraint.
-
inline LpBase::Constr operator<=( const LpBase::Expr & e , const LpBase::Value & f )
Create constraint.
-
inline LpBase::Constr operator>=( const LpBase::Expr & e , const LpBase::Expr & f )
Create constraint.
-
inline LpBase::Constr operator>=( const LpBase::Value & e , const LpBase::Expr & f )
Create constraint.
-
inline LpBase::Constr operator>=( const LpBase::Expr & e , const LpBase::Value & f )
Create constraint.
-
inline LpBase::Constr operator==( const LpBase::Expr & e , const LpBase::Value & f )
Create constraint.
-
inline LpBase::Constr operator==( const LpBase::Expr & e , const LpBase::Expr & f )
Create constraint.
-
inline LpBase::Constr operator<=( const LpBase::Value & n , const LpBase::Constr & c )
Create constraint.
-
inline LpBase::Constr operator<=( const LpBase::Constr & c , const LpBase::Value & n )
Create constraint.
-
class DualExpr
Linear expression of rows.
This data structure represents a column of the matrix, thas is it strores a linear expression of the dual variables (Rows).
There are several ways to access and modify the contents of this container.
or you can also iterate through its elements.e[ v ] = 5; e[ v ] += 12; e.erase( v );
(This code computes the sum of all coefficients).double s = 0; for( LpBase::DualExpr::ConstCoeffIt i( e ) ; i != INVALID ; ++i ) s += *i;
Numbers (
double’s) and variables (Rows) directly convert to an DualExpr and the usual linear operations are defined, soare valid DualExpr dual expressions. The usual assignment operations are also defined.v + w 2 * v - 3.12 * ( v - w / 2 ) v * 2.1 + ( 3 * v + ( v * 12 + w ) * 3 ) / 2
e = v + w; e += 2 * v - 3.12 * ( v - w / 2 ); e *= 3.4; e /= 5;
See also
Public Types
-
typedef True SolverExpr
Public Functions
-
inline DualExpr()
Default constructor.
Construct an empty expression, the coefficients are initialized to zero.
-
inline DualExpr( const Row & r )
Construct an expression from a row.
Construct an expression, which has a term with
rdual variable and 1.0 coefficient.
-
inline void simplify( Value epsilon = 0.0 )
Removes the coefficients which’s absolute value does not exceed
epsilon.
-
inline void clear()
Sets all coefficients to 0.
-
inline LpBase::DualExpr operator+( const LpBase::DualExpr & a , const LpBase::DualExpr & b )
Addition.
-
inline LpBase::DualExpr operator-( const LpBase::DualExpr & a , const LpBase::DualExpr & b )
Substraction.
-
inline LpBase::DualExpr operator*( const LpBase::DualExpr & a , const LpBase::Value & b )
Multiply with constant.
-
class CoeffIt
Iterator over the expression.
The iterator iterates over the terms of the expression.
double s = 0; for( LpBase::DualExpr::CoeffIt i( e ) ; i != INVALID ; ++i ) s += *i * dual( i );
-
class ConstCoeffIt
Iterator over the expression.
The iterator iterates over the terms of the expression.
double s = 0; for( LpBase::DualExpr::ConstCoeffIt i( e ) ; i != INVALID ; ++i ) s += *i * dual( i );
Public Functions
-
inline ConstCoeffIt( const DualExpr & e )
Sets the iterator to the first term.
Sets the iterator to the first term of the expression.
-
inline ConstCoeffIt & operator++()
Next term.
Assign the iterator to the next term.
-
inline ConstCoeffIt( const DualExpr & e )
-
class InsertIterator
Public Types
-
typedef std::output_iterator_tag iterator_category
-
typedef void difference_type
-
typedef void value_type
-
typedef void reference
-
typedef void pointer
Public Functions
-
inline InsertIterator & operator=( const std::pair< int , Value > & value )
-
inline InsertIterator & operator*()
-
inline InsertIterator & operator++()
-
inline InsertIterator operator++(int)
-
typedef std::output_iterator_tag iterator_category
-
class ExprIterator
Public Types
-
typedef std::bidirectional_iterator_tag iterator_category
-
typedef std::ptrdiff_t difference_type
-
typedef value_type reference
Public Functions
- inline ExprIterator(
- const std::map< int , Value >::const_iterator & host_it,
- const _solver_bits::VarIndex & index
-
inline ExprIterator & operator++()
-
inline ExprIterator operator++(int)
-
inline ExprIterator & operator--()
-
inline ExprIterator operator--(int)
-
inline bool operator==( const ExprIterator & it ) const
-
inline bool operator!=( const ExprIterator & it ) const
-
class pointer
-
typedef std::bidirectional_iterator_tag iterator_category
-
template< class T >