8 #ifndef LIMBO_SOLVERS_SOLVERS_H
9 #define LIMBO_SOLVERS_SOLVERS_H
79 template <
typename T,
typename V>
81 template <
typename T,
typename I,
int StartingIndex>
265 template <
typename V>
347 template <
typename T>
596 template <
typename TermType>
597 bool operator()(TermType
const& t1, TermType
const& t2)
const
599 return t1.variable().id() < t2.variable().id();
605 template <
typename T>
606 class LinearExpression
751 m_vTerm.insert(
m_vTerm.end(), expr.terms().begin(), expr.terms().end());
822 for (
typename std::vector<term_type>::const_iterator it = expr.terms().begin(), ite = expr.terms().end(); it != ite; ++it)
823 this->
operator-=(*it);
850 for (
typename std::vector<term_type>::iterator it =
m_vTerm.begin(); it !=
m_vTerm.end(); ++it)
851 it->setCoefficient(c*it->coefficient());
870 for (
typename std::vector<term_type>::iterator it =
m_vTerm.begin(); it !=
m_vTerm.end(); ++it)
871 it->setCoefficient(it->coefficient()/c);
880 return expr.negate();
886 for (
typename std::vector<term_type>::iterator it =
m_vTerm.begin(); it !=
m_vTerm.end(); ++it)
887 it->setCoefficient(-it->coefficient());
935 typename std::vector<term_type>::iterator itw =
m_vTerm.begin();
936 typename std::vector<term_type>::iterator itr =
m_vTerm.begin();
937 typename std::vector<term_type>::iterator ite =
m_vTerm.end();
938 for (; itr != ite; ++itr)
942 if (itr->variable() == itw->variable())
943 itw->setCoefficient(itw->coefficient()+itr->coefficient());
956 if (itr->coefficient() == 0)
981 template <
typename T>
999 :
m_id (std::numeric_limits<unsigned int>::
max())
1049 #ifdef DEBUG_SOLVERS
1056 #ifdef DEBUG_SOLVERS
1066 if ((
m_sense ==
'<' && s ==
'>')
1067 || (
m_sense ==
'>' && s ==
'<'))
1076 void scale(coefficient_value_type factor)
1078 #ifdef DEBUG_SOLVERS
1159 template <
typename T,
typename V>
1199 this->base_type::operator=(rhs);
1228 bool emplaceConstraint(expression_type& expr,
char sense, coefficient_value_type rhs, std::string name =
"")
1233 std::vector<term_type>
const& vTerm = expr.
terms();
1236 if (vTerm.size() == 1)
1238 term_type
const& term = vTerm.front();
1400 for (
unsigned int i = 0; i < n; ++i)
1414 coefficient_value_type
evaluateExpression(expression_type
const& expr, std::vector<variable_value_type>
const& vVariableSol)
const
1416 coefficient_value_type result = 0;
1417 for (
typename std::vector<term_type>::const_iterator it = expr.
terms().begin(), ite = expr.
terms().end(); it != ite; ++it)
1418 result += it->coefficient()*vVariableSol.at(it->variable().id());
1425 coefficient_value_type
evaluateObjective(std::vector<variable_value_type>
const& vVariableSol)
const
1439 coefficient_value_type
evaluateConstraint(constraint_type
const& constr, std::vector<variable_value_type>
const& vVariableSol)
const
1442 if (constr.
sense() ==
'>')
1457 for (
unsigned int i = 0, ie =
m_vConstraint.size(); i < ie; ++i)
1464 void read(std::string
const& filename)
1477 variable_value_type lb = l;
1478 variable_value_type ub = r;
1481 if (l <= (
double)limbo::lowest<variable_value_type>())
1482 lb = limbo::lowest<variable_value_type>();
1485 limboAssertMsg(lb <= ub,
"failed to add bound %g <= %s <= %g", l, vname.c_str(), r);
1490 typename std::map<std::string, variable_type>::const_iterator found =
m_mName2Variable.find(vname);
1493 "failed to insert variable %s to hash table", vname.c_str());
1509 expression_type expr;
1510 for (LpParser::TermArray::const_iterator it = terms.begin(); it != terms.end(); ++it)
1513 add_variable(it->var);
1525 expression_type expr;
1526 for (LpParser::TermArray::const_iterator it = terms.begin(); it != terms.end(); ++it)
1529 add_variable(it->var);
1540 add_variable(vname);
1552 bool print(std::string
const& filename)
const
1554 std::ofstream out (filename.c_str());
1564 std::ostream&
print(std::ostream& os = std::cout)
const
1582 os <<
"\n\nSubject To\n";
1586 for (
typename std::vector<constraint_type>::const_iterator it =
constraints().begin(), ite =
constraints().end(); it != ite; ++it, ++i)
1589 os <<
"C" << i <<
": ";
1603 else if (it->lowerBound() <= limbo::lowest<variable_value_type>())
1617 if (it->numericType() ==
BINARY || it->numericType() ==
INTEGER)
1629 std::ostream&
print(std::ostream& os, term_type
const& term)
const
1638 std::ostream&
print(std::ostream& os, expression_type
const& expr)
const
1641 for (
typename std::vector<term_type>::const_iterator it = expr.
terms().begin(), ite = expr.
terms().end(); it != ite; ++it, ++i)
1655 std::ostream&
print(std::ostream& os, constraint_type
const& constr)
const
1658 if (constr.
sense() ==
'=')
1667 std::ofstream out (filename.c_str());
1680 os <<
"# Objective " << obj <<
"\n";
1714 template <
typename T,
typename I,
int StartingIndex = 1>
1734 , vRowBeginIndex(NULL)
1770 vRowBeginIndex =
new index_type [numRows+1];
1784 vRowBeginIndex = NULL;
1802 vRowBeginIndex =
new index_type [numRows+1];
1813 value_type
at(index_type i, index_type j)
const
1815 #ifdef DEBUG_SOLVERS
1819 index_type* elementColumnBegin = vColumn+vRowBeginIndex[i]-vRowBeginIndex[0];
1820 index_type* elementColumnEnd = vColumn+vRowBeginIndex[i+1]-vRowBeginIndex[0];
1822 index_type* found = std::lower_bound(elementColumnBegin, elementColumnEnd, j+s_startingIndex);
1823 if (found != elementColumnEnd && *found == j+s_startingIndex)
1825 #ifdef DEBUG_SOLVERS
1826 limboAssert(std::distance(vColumn, found)-s_startingIndex < numElements);
1828 return vElement[std::distance(vColumn, found)];
1843 vRowBeginIndex =
new index_type [numRows+1];
1847 constraint_type
const* it = vConstraint;
1848 constraint_type
const* ite = vConstraint+nr;
1851 for (; it != ite; ++it, ++i)
1853 #ifdef DEBUG_SOLVERS
1856 vRowBeginIndex[i] = vRowBeginIndex[i-1]+it->expression().terms().size();
1859 numElements = vRowBeginIndex[
numRows];
1865 for (it = vConstraint; it != ite; ++it)
1867 for (
typename std::vector<typename constraint_type::term_type>::const_iterator itt = it->expression().terms().begin(), itte = it->expression().terms().end(); itt != itte; ++itt, ++i)
1869 #ifdef DEBUG_SOLVERS
1872 vElement[i] = itt->coefficient();
1879 template <
typename T,
typename I,
int StartingIndex>
1880 typename MatrixCSR<T, I, StartingIndex>::index_type MatrixCSR<T, I, StartingIndex>::s_startingIndex = StartingIndex;
friend LinearConstraint< coefficient_value_type > operator<=(LinearExpression const &expr, coefficient_value_type rhs)
overload <=, same as <
bool operator==(Variable const &rhs) const
header to include PrintMsg.h and AssertMsg.h
index_type numColumns
number of columns, not in the CSR format
friend LinearConstraint< coefficient_value_type > operator<(Variable const &var, coefficient_value_type rhs)
overload <
bool operator()(TermType const &t1, TermType const &t2) const
coefficient_value_type evaluateConstraint(constraint_type const &constr, std::vector< variable_value_type > const &vVariableSol) const
evaluate slackness of a constraint given solutions of variables
friend LinearConstraint< coefficient_value_type > operator==(Variable const &var, coefficient_value_type rhs)
overload ==
LinearExpression & operator/=(coefficient_value_type c)
variable_value_type variableSolution(variable_type const &var) const
void swap(LinearConstraint &rhs)
swap with a constraint
LinearTerm & operator/=(coefficient_value_type coef)
Base class for lp database. Only pure virtual functions are defined. User needs to inheritate this cl...
LinearConstraint(LinearConstraint const &rhs)
copy constructor
Variable & operator=(Variable const &rhs)
assignment
LinearTerm< coefficient_value_type > term_type
term type
index_type * vRowBeginIndex
Element j of this integer array gives the index of the element in the values array that is first non-...
LinearTerm(LinearTerm const &rhs)
copy constructor
LinearExpression(LinearExpression const &rhs)
copy constructor
friend LinearExpression< coefficient_value_type > operator-(coefficient_value_type constant, Variable const &var)
Describe properties of a variable.
void copy(LinearExpression const &rhs)
copy object
void setVariable(variable_type const &var)
friend LinearConstraint< coefficient_value_type > operator==(LinearTerm const &term, coefficient_value_type rhs)
std::vector< property_type > m_vVariableProperty
variable properties
LinearTerm< coefficient_value_type > term_type
term type
coefficient_value_type evaluateObjective() const
evaluate objective
LinearTerm & operator*=(coefficient_value_type coef)
friend LinearExpression< coefficient_value_type > operator-(Variable const &var, coefficient_value_type constant)
friend LinearTerm< coefficient_value_type > operator*(coefficient_value_type coef, Variable const &var)
SolverProperty numericType() const
SolverProperty
Some enums used in solver.
LinearTerm< coefficient_value_type > term_type
term type
variable_value_type lowerBound() const
void initialize(index_type nr, index_type nc, index_type nv)
Initialize matrix.
void setExpression(expression_type const &expr)
std::string m_name
name of variable
friend LinearExpression< coefficient_value_type > operator-(LinearTerm const &term, coefficient_value_type constant)
int limboSPrint(MessageType m, char *buf, const char *format,...)
formatted print with prefix to buffer
LinearModel(LinearModel const &rhs)
copy constructor
std::ostream & print(std::ostream &os=std::cout) const
print problem in lp format
~LinearConstraint()
destructor
coefficient_value_type coefficient() const
LinearExpression & setConstant(coefficient_value_type constant)
set constant term
std::map< std::string, variable_type > m_mName2Variable
mapping from variable name to variable, only used when reading from files
void resizeConstraints(unsigned int n)
resize constraints
SolverProperty optimizeType() const
bool printSolution(std::string const &filename) const
print solutions to file
friend LinearTerm operator/(LinearTerm const &term, coefficient_value_type coef)
friend LinearConstraint< coefficient_value_type > operator<(LinearExpression const &expr, coefficient_value_type rhs)
overload <
VariableProperty(VariableProperty const &rhs)
copy constructor
Variable< coefficient_value_type > variable_type
variable type
void add_objective(bool minimize, LpParser::TermArray const &terms)
add object terms
friend LinearExpression< coefficient_value_type > operator-(coefficient_value_type constant, LinearTerm const &term)
void reset()
Destroy matrix and recycle memory.
void setNumericType(SolverProperty nt)
std::vector< Term > TermArray
array of terms
std::vector< constraint_type > & constraints()
bool addConstraint(constraint_type const &constr, std::string name="")
add a constraint
friend LinearExpression< coefficient_value_type > operator-(LinearTerm const &term, variable_type const &var)
void reserveVariables(unsigned int n)
reserve space for variables
std::string const & constraintName(constraint_type const &constr) const
bool operator!=(Variable const &rhs) const
Variable< coefficient_value_type > variable_type
variable type
SolverProperty variableNumericType(variable_type const &var)
void copy(LinearTerm const &rhs)
copy object
T coefficient_value_type
coefficient type
LinearTerm operator-() const
void reserveConstraints(unsigned int n)
reserve space for constraints
V variable_value_type
V variable.
LinearTerm & operator=(LinearTerm const &rhs)
assignment
std::vector< std::string > const & constraintNames() const
coefficient_value_type m_coef
coefficient
LinearModel & operator=(LinearModel const &rhs)
assignment
void updateUpperBound(variable_value_type ub)
LinearTerm< coefficient_value_type > operator-() const
variable_type m_var
variable
friend LinearExpression< coefficient_value_type > operator-(Variable const &var1, Variable const &var2)
T coefficient_value_type
T coefficient.
void setOptimizeType(SolverProperty optType)
void simplify()
simplify expression by merge terms of the same variables
LinearExpression & operator*=(coefficient_value_type c)
VariableProperty & operator=(VariableProperty const &rhs)
assignment
friend LinearTerm< coefficient_value_type > operator/(Variable const &var, coefficient_value_type coef)
void simplify()
simplify expression by merge terms of the same variables and remove terms with zero coefficients ...
expression_type const & objective() const
void swap(LinearExpression &rhs)
swap with an expression
LinearExpression & operator+=(LinearExpression const &expr)
variable_value_type upperBound() const
void copy(LinearModel const &rhs)
copy object
friend LinearConstraint< coefficient_value_type > operator<(LinearTerm const &term, coefficient_value_type rhs)
overload <
Describe linear constraint.
index_type * vColumn
Element i of the integer array columns is the number of the column in A that contains the i-th value ...
coefficient_value_type m_rhs
constant at the right hand side
std::vector< constraint_type > m_vConstraint
constraints
LinearExpression< coefficient_value_type > expression_type
expression type
friend LinearConstraint< coefficient_value_type > operator>=(LinearTerm const &term, coefficient_value_type rhs)
overload >=, same as >
friend LinearConstraint< coefficient_value_type > operator>(LinearExpression const &expr, coefficient_value_type rhs)
overload >
Variable(Variable const &rhs)
copy constructor
void setObjective(expression_type const &expr)
set objective
void reserve(unsigned int n)
reserve space for expression terms
SolverProperty m_numericType
numeric type, BINARY, INTEGER, CONTINUOUS
std::vector< constraint_type > const & constraints() const
bool operator==(LinearTerm const &rhs) const
unsigned int numVariables() const
void clear()
clear expression
friend LinearExpression operator-(term_type const &term, LinearExpression const &expr)
SolverProperty m_optType
optimization objective
T coefficient_value_type
coefficient type
friend LinearConstraint< coefficient_value_type > operator==(LinearExpression const &expr, coefficient_value_type rhs)
friend LinearExpression operator+(coefficient_value_type constant, LinearExpression const &expr)
LinearConstraint(expression_type expr=expression_type(), coefficient_value_type rhs=0, char s= '<')
constructor
void updateLowerBound(variable_value_type lb)
friend LinearExpression operator*(coefficient_value_type c, LinearExpression const &expr)
void setId(unsigned int id)
set variable index
LinearTerm(variable_type var=variable_type(), coefficient_value_type coef=1)
constructor
Describe linear expressions in optimization problem.
LinearConstraint & operator+=(term_type const &term)
LinearConstraint & operator-=(term_type term)
std::string const & name() const
LinearExpression & operator-=(LinearExpression const &expr)
VariableProperty(variable_value_type lb, variable_value_type ub, SolverProperty nt, std::string const &n)
constructor
bool emplaceConstraint(expression_type &expr, char sense, coefficient_value_type rhs, std::string name="")
emplace a constraint
coefficient_value_type evaluateConstraint(constraint_type const &constr) const
evaluate slackness of a constraint given solutions of variables
mathematical utilities such as abs
void setId(unsigned int i)
value_type at(index_type i, index_type j) const
get element
friend LinearExpression< coefficient_value_type > operator+(LinearTerm const &term1, LinearTerm const &term2)
friend LinearConstraint< coefficient_value_type > operator>=(Variable const &var, coefficient_value_type rhs)
overload >=
MatrixCSR & operator=(MatrixCSR const &rhs)
assignment
friend LinearTerm operator*(coefficient_value_type coef, LinearTerm const &term)
LinearConstraint< coefficient_value_type > constraint_type
constraint type
expression_type const & expression() const
variable_type variable(unsigned int id) const
Comapre term by variable.
friend LinearExpression operator*(LinearExpression const &expr, coefficient_value_type c)
void add_constraint(std::string const &cname, LpParser::TermArray const &terms, char compare, double constant)
add constraint that terms compare constant.
LinearExpression & incrementConstant(coefficient_value_type constant)
increment constant term
void copy(LinearConstraint const &rhs)
copy object
friend LinearConstraint< coefficient_value_type > operator<=(Variable const &var, coefficient_value_type rhs)
overload <=
value_type * vElement
Flatten data values. A real or complex array that contains the non-zero elements of A...
void setCoefficient(coefficient_value_type coef)
V variable_value_type
type of bounds
void setVariableLowerBound(variable_type const &var, variable_value_type lb)
set variable lower bound
std::string toString(SolverProperty sp)
Convert limbo::solvers::SolverProperty to std::string.
MatrixCSR(MatrixCSR const &rhs)
copy constructor
friend LinearTerm operator*(LinearTerm const &term, coefficient_value_type coef)
char m_sense
sign of operator, < (<=), > (>=), = (==)
coefficient_value_type m_constant
constant term for the linear expression
unsigned int m_id
variable index
std::ostream & print(std::ostream &os, expression_type const &expr) const
print expression
T coefficient_value_type
coefficient type
Variable(unsigned int id=std::numeric_limits< unsigned int >::max())
constructor
void copy(VariableProperty const &rhs)
copy object
friend LinearExpression< coefficient_value_type > operator+(variable_type const &var, LinearTerm const &term)
void setLowerBound(variable_value_type lb)
void normalize(char s)
normalize sense
void updateVariableLowerBound(variable_type const &var, variable_value_type lb)
update variable lower bound
LinearConstraint & operator-=(expression_type const &expr)
std::ostream & printSolution(std::ostream &os=std::cout) const
print solutions
~LinearExpression()
destructor
friend LinearExpression< coefficient_value_type > operator-(LinearTerm const &term1, LinearTerm const &term2)
void emplaceObjective(expression_type &expr)
set objective by swaping with the expression
friend LinearExpression operator+(LinearExpression const &expr1, LinearExpression const &expr2)
std::iterator_traits< Iterator >::value_type max(Iterator first, Iterator last)
get max of an array
void set(index_type nr, index_type nc, LinearConstraint< value_type > const *vConstraint)
Set from array of constraints.
LinearExpression< coefficient_value_type > expression_type
expression type
Variable< coefficient_value_type > variable_type
variable type
std::string variableName(variable_type const &var) const
LinearExpression(term_type const &term, coefficient_value_type constant=0)
constructor
void copy(MatrixCSR const &rhs)
copy object
friend LinearExpression< coefficient_value_type > operator+(Variable const &var1, Variable const &var2)
coefficient_value_type rightHandSide() const
LinearExpression & negate()
void setVariableNumericType(variable_type const &var, SolverProperty type)
set numeric type of variable
void evaluateConstraint() const
evaluate slackness of all constraints given solutions of variables and print to screen ...
LinearConstraint & operator=(LinearConstraint const &rhs)
assignment
VariableProperty< variable_value_type > property_type
variable property type
friend LinearExpression< coefficient_value_type > operator+(LinearTerm const &term, coefficient_value_type constant)
void scaleObjective(coefficient_value_type factor)
scale objective
std::vector< property_type > const & variableProperties() const
friend LinearExpression operator-(LinearExpression const &expr, term_type const &term)
void setName(std::string const &n)
friend LinearExpression< coefficient_value_type > operator+(Variable const &var, coefficient_value_type constant)
#define limboAssert(condition)
custom assertion without message
int limboPrint(MessageType m, const char *format,...)
formatted print with prefix
void setVariableUpperBound(variable_type const &var, variable_value_type ub)
set variable upper bound
std::vector< term_type > const & terms() const
void copy(Variable const &rhs)
copy object
Describe variables in optimization problem.
index_type numElements
number of non-zero elements
expression_type m_expr
linear expression
void setVariableName(variable_type const &var, std::string const &name)
set variable name
LinearExpression & operator-=(coefficient_value_type constant)
LinearConstraint & operator+=(expression_type const &expr)
double lowest< double >()
specialization for floating point types
coefficient_value_type evaluateExpression(expression_type const &expr, std::vector< variable_value_type > const &vVariableSol) const
evaluate expression given solutions of variables
LpParser::LpDataBase base_type
base class
friend LinearExpression operator/(LinearExpression const &expr, coefficient_value_type c)
friend LinearExpression< coefficient_value_type > operator+(LinearTerm const &term, variable_type const &var)
friend LinearExpression operator+(term_type const &term, LinearExpression const &expr)
expression_type m_objective
objective
LinearExpression & operator=(LinearExpression const &rhs)
assignment
unsigned int m_id
constraint index
std::vector< term_type > m_vTerm
linear expression with terms
std::vector< property_type > & variableProperties()
void setUpperBound(variable_value_type ub)
void read(std::string const &filename)
read lp format
LinearExpression & operator+=(term_type const &term)
coefficient_value_type evaluateObjective(std::vector< variable_value_type > const &vVariableSol) const
evaluate objective
std::vector< variable_value_type > & variableSolutions()
void set_integer(std::string const &vname, bool binary)
set integer variables
void setVariableSolution(variable_type const &var, variable_value_type v)
variable_value_type variableLowerBound(variable_type const &var)
friend LinearExpression operator-(coefficient_value_type constant, LinearExpression const &expr)
variable_type const & variable() const
variable_value_type m_lowerBound
lower bound
void emplaceExpression(expression_type &expr)
model to describe an optimization problem
LinearExpression & operator-=(term_type term)
std::vector< std::string > m_vConstraintName
constraint names
variable_value_type variableUpperBound(variable_type const &var)
T coefficient_value_type
coefficient type
friend LinearExpression operator-(LinearExpression const &expr1, LinearExpression const &expr2)
LinearExpression operator-() const
index_type numRows
number of rows, not in the CSR format
variable_type addVariable(variable_value_type lb, variable_value_type ub, SolverProperty nt, std::string name="")
add one variable
friend LinearExpression< coefficient_value_type > operator+(coefficient_value_type constant, Variable const &var)
std::vector< variable_value_type > m_vVariableSol
variable solutions, it can be either initial solution or final solution
friend LinearExpression operator-(LinearExpression const &expr, coefficient_value_type constant)
#define limboAssertMsg(condition, args...)
custom assertion with message
std::iterator_traits< Iterator >::value_type min(Iterator first, Iterator last)
get min of an array
friend LinearExpression< coefficient_value_type > operator-(variable_type const &var, LinearTerm const &term)
friend LinearExpression< coefficient_value_type > operator+(coefficient_value_type constant, LinearTerm const &term)
friend LinearConstraint< coefficient_value_type > operator>(LinearTerm const &term, coefficient_value_type rhs)
overload >
Compressed sparse row (CSR) matrix.
bool read(LpDataBase &db, const string &lpFile)
API for LpParser. Read LP file and initialize database by calling user-defined callback functions...
LinearExpression & operator+=(coefficient_value_type constant)
void scale(coefficient_value_type factor)
scale constraint by a scaling factor
friend LinearConstraint< coefficient_value_type > operator>(Variable const &var, coefficient_value_type rhs)
overload >
friend LinearConstraint< coefficient_value_type > operator<=(LinearTerm const &term, coefficient_value_type rhs)
overload <=, same as <
void updateVariableUpperBound(variable_type const &var, variable_value_type ub)
update variable upper bound
void scaleConstraint(unsigned int id, coefficient_value_type factor)
scaling a constraint
void clearConstant()
move the constant in the expression to rhs For example, x + 5 < 10 will become x < 5 ...
bool print(std::string const &filename) const
print problem in lp format to file
static index_type s_startingIndex
starting index, like zero-based indexing or one-based indexing
variable_value_type m_upperBound
upper bound
friend LinearTerm< coefficient_value_type > operator*(Variable const &var, coefficient_value_type coef)
coefficient_value_type constant() const
LinearExpression()
constructor
std::ostream & print(std::ostream &os, constraint_type const &constr) const
print constraint
Variable< coefficient_value_type > variable_type
variable type
friend LinearConstraint< coefficient_value_type > operator>=(LinearExpression const &expr, coefficient_value_type rhs)
overload >=, same as >
std::ostream & print(std::ostream &os, term_type const &term) const
print expression
void setRightHandSide(coefficient_value_type rhs)
friend LinearExpression operator+(LinearExpression const &expr, term_type const &term)
friend LinearExpression operator+(LinearExpression const &expr, coefficient_value_type constant)
void reserve(unsigned int n)
reserve space for terms
std::vector< variable_value_type > const & variableSolutions() const
std::vector< std::string > & constraintNames()