2 * lemon/lp_base.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_LP_BASE_H
18 #define LEMON_LP_BASE_H
25 #include<lemon/utility.h>
26 #include<lemon/error.h>
27 #include<lemon/invalid.h>
30 ///\brief The interface of the LP solver interface.
31 ///\ingroup gen_opt_group
34 ///Internal data structure to convert floating id's to fix one's
36 ///\todo This might be implemented to be also usable in other places.
40 std::vector<int> index;
41 std::vector<int> cross;
44 _FixId() : first_free(-1) {};
45 ///Convert a floating id to a fix one
47 ///\param n is a floating id
48 ///\return the corresponding fix id
49 int fixId(int n) const {return cross[n];}
50 ///Convert a fix id to a floating one
52 ///\param n is a fix id
53 ///\return the corresponding floating id
54 int floatingId(int n) const { return index[n];}
55 ///Add a new floating id.
57 ///\param n is a floating id
58 ///\return the fix id of the new value
59 ///\todo Multiple additions should also be handled.
62 if(n>=int(cross.size())) {
65 cross[n]=index.size();
70 int next=index[first_free];
76 ///\todo Create an own exception type.
77 else throw LogicError(); //floatingId-s must form a continuous range;
81 ///\param n is a fix id
88 for(int i=fl+1;i<int(cross.size());++i) {
94 ///An upper bound on the largest fix id.
96 ///\todo Do we need this?
98 std::size_t maxFixId() { return cross.size()-1; }
102 ///Common base class for LP solvers
104 ///\todo Much more docs
105 ///\ingroup gen_opt_group
110 ///Possible outcomes of an LP solving procedure
111 enum SolveExitStatus {
112 ///This means that the problem has been successfully solved: either
113 ///an optimal solution has been found or infeasibility/unboundedness
116 ///Any other case (including the case when some user specified limit has been exceeded)
121 enum SolutionStatus {
122 ///Feasible solution has'n been found (but may exist).
124 ///\todo NOTFOUND might be a better name.
127 ///The problem has no feasible solution
129 ///Feasible solution found
131 ///Optimal solution exists and found
133 ///The cost function is unbounded
135 ///\todo Give a feasible solution and an infinite ray (and the
136 ///corresponding bases)
140 ///\e The type of the investigated LP problem
142 ///Primal-dual feasible
143 PRIMAL_DUAL_FEASIBLE = 0,
144 ///Primal feasible dual infeasible
145 PRIMAL_FEASIBLE_DUAL_INFEASIBLE = 1,
146 ///Primal infeasible dual feasible
147 PRIMAL_INFEASIBLE_DUAL_FEASIBLE = 2,
148 ///Primal-dual infeasible
149 PRIMAL_DUAL_INFEASIBLE = 3,
150 ///Could not determine so far
154 ///The floating point type used by the solver
155 typedef double Value;
156 ///The infinity constant
157 static const Value INF;
158 ///The not a number constant
159 static const Value NaN;
161 ///Refer to a column of the LP.
163 ///This type is used to refer to a column of the LP.
165 ///Its value remains valid and correct even after the addition or erase of
168 ///\todo Document what can one do with a Col (INVALID, comparing,
169 ///it is similar to Node/Edge)
173 friend class LpSolverBase;
175 typedef Value ExprValue;
176 typedef True LpSolverCol;
178 Col(const Invalid&) : id(-1) {}
179 bool operator< (Col c) const {return id< c.id;}
180 bool operator> (Col c) const {return id> c.id;}
181 bool operator==(Col c) const {return id==c.id;}
182 bool operator!=(Col c) const {return id!=c.id;}
185 ///Refer to a row of the LP.
187 ///This type is used to refer to a row of the LP.
189 ///Its value remains valid and correct even after the addition or erase of
192 ///\todo Document what can one do with a Row (INVALID, comparing,
193 ///it is similar to Node/Edge)
197 friend class LpSolverBase;
199 typedef Value ExprValue;
200 typedef True LpSolverRow;
202 Row(const Invalid&) : id(-1) {}
204 bool operator< (Row c) const {return id< c.id;}
205 bool operator> (Row c) const {return id> c.id;}
206 bool operator==(Row c) const {return id==c.id;}
207 bool operator!=(Row c) const {return id!=c.id;}
210 ///Linear expression of variables and a constant component
212 ///This data structure strores a linear expression of the variables
213 ///(\ref Col "Col"s) and also has a constant component.
215 ///There are several ways to access and modify the contents of this
217 ///- Its it fully compatible with \c std::map<Col,double>, so for expamle
218 ///if \c e is an Expr and \c v and \c w are of type \ref Col, then you can
219 ///read and modify the coefficients like
226 ///or you can also iterate through its elements.
229 ///for(LpSolverBase::Expr::iterator i=e.begin();i!=e.end();++i)
232 ///(This code computes the sum of all coefficients).
233 ///- Numbers (<tt>double</tt>'s)
234 ///and variables (\ref Col "Col"s) directly convert to an
235 ///\ref Expr and the usual linear operations are defined so
238 ///2*v-3.12*(v-w/2)+2
239 ///v*2.1+(3*v+(v*12+w+6)*3)/2
241 ///are valid \ref Expr "Expr"essions.
242 ///The usual assignment operations are also defined.
245 ///e+=2*v-3.12*(v-w/2)+2;
249 ///- The constant member can be set and read by \ref constComp()
252 ///double c=e.constComp();
255 ///\note \ref clear() not only sets all coefficients to 0 but also
256 ///clears the constant components.
260 class Expr : public std::map<Col,Value>
263 typedef LpSolverBase::Col Key;
264 typedef LpSolverBase::Value Value;
267 typedef std::map<Col,Value> Base;
271 typedef True IsLinExpression;
273 Expr() : Base(), const_comp(0) { }
275 Expr(const Key &v) : const_comp(0) {
276 Base::insert(std::make_pair(v, 1));
279 Expr(const Value &v) : const_comp(v) {}
281 void set(const Key &v,const Value &c) {
282 Base::insert(std::make_pair(v, c));
285 Value &constComp() { return const_comp; }
287 const Value &constComp() const { return const_comp; }
289 ///Removes the components with zero coefficient.
291 for (Base::iterator i=Base::begin(); i!=Base::end();) {
294 if ((*i).second==0) Base::erase(i);
299 ///Removes the coefficients closer to zero than \c tolerance.
300 void simplify(double &tolerance) {
301 for (Base::iterator i=Base::begin(); i!=Base::end();) {
304 if (std::fabs((*i).second)<tolerance) Base::erase(i);
309 ///Sets all coefficients and the constant component to 0.
316 Expr &operator+=(const Expr &e) {
317 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
318 (*this)[j->first]+=j->second;
319 const_comp+=e.const_comp;
323 Expr &operator-=(const Expr &e) {
324 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
325 (*this)[j->first]-=j->second;
326 const_comp-=e.const_comp;
330 Expr &operator*=(const Value &c) {
331 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
337 Expr &operator/=(const Value &c) {
338 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
347 ///This data stucture represents a linear constraint in the LP.
348 ///Basically it is a linear expression with a lower or an upper bound
349 ///(or both). These parts of the constraint can be obtained by the member
350 ///functions \ref expr(), \ref lowerBound() and \ref upperBound(),
352 ///There are two ways to construct a constraint.
353 ///- You can set the linear expression and the bounds directly
354 /// by the functions above.
355 ///- The operators <tt>\<=</tt>, <tt>==</tt> and <tt>\>=</tt>
356 /// are defined between expressions, or even between constraints whenever
357 /// it makes sense. Therefore if \c e and \c f are linear expressions and
358 /// \c s and \c t are numbers, then the followings are valid expressions
359 /// and thus they can be used directly e.g. in \ref addRow() whenever
367 ///\warning The validity of a constraint is checked only at run time, so
368 ///e.g. \ref addRow(<tt>x[1]\<=x[2]<=5</tt>) will compile, but will throw a
369 ///\ref LogicError exception.
373 typedef LpSolverBase::Expr Expr;
374 typedef Expr::Key Key;
375 typedef Expr::Value Value;
377 // static const Value INF;
378 // static const Value NaN;
385 Constr() : _expr(), _lb(NaN), _ub(NaN) {}
387 Constr(Value lb,const Expr &e,Value ub) :
388 _expr(e), _lb(lb), _ub(ub) {}
390 Constr(const Expr &e,Value ub) :
391 _expr(e), _lb(NaN), _ub(ub) {}
393 Constr(Value lb,const Expr &e) :
394 _expr(e), _lb(lb), _ub(NaN) {}
396 Constr(const Expr &e) :
397 _expr(e), _lb(NaN), _ub(NaN) {}
405 ///Reference to the linear expression
406 Expr &expr() { return _expr; }
407 ///Cont reference to the linear expression
408 const Expr &expr() const { return _expr; }
409 ///Reference to the lower bound.
412 ///- \ref INF "INF": the constraint is lower unbounded.
413 ///- \ref NaN "NaN": lower bound has not been set.
414 ///- finite number: the lower bound
415 Value &lowerBound() { return _lb; }
416 ///The const version of \ref lowerBound()
417 const Value &lowerBound() const { return _lb; }
418 ///Reference to the upper bound.
421 ///- \ref INF "INF": the constraint is upper unbounded.
422 ///- \ref NaN "NaN": upper bound has not been set.
423 ///- finite number: the upper bound
424 Value &upperBound() { return _ub; }
425 ///The const version of \ref upperBound()
426 const Value &upperBound() const { return _ub; }
427 ///Is the constraint lower bounded?
428 bool lowerBounded() const {
432 ///Is the constraint upper bounded?
433 bool upperBounded() const {
439 ///Linear expression of rows
441 ///This data structure represents a column of the matrix,
442 ///thas is it strores a linear expression of the dual variables
443 ///(\ref Row "Row"s).
445 ///There are several ways to access and modify the contents of this
447 ///- Its it fully compatible with \c std::map<Row,double>, so for expamle
448 ///if \c e is an DualExpr and \c v
449 ///and \c w are of type \ref Row, then you can
450 ///read and modify the coefficients like
457 ///or you can also iterate through its elements.
460 ///for(LpSolverBase::DualExpr::iterator i=e.begin();i!=e.end();++i)
463 ///(This code computes the sum of all coefficients).
464 ///- Numbers (<tt>double</tt>'s)
465 ///and variables (\ref Row "Row"s) directly convert to an
466 ///\ref DualExpr and the usual linear operations are defined so
470 ///v*2.1+(3*v+(v*12+w)*3)/2
472 ///are valid \ref DualExpr "DualExpr"essions.
473 ///The usual assignment operations are also defined.
476 ///e+=2*v-3.12*(v-w/2);
483 class DualExpr : public std::map<Row,Value>
486 typedef LpSolverBase::Row Key;
487 typedef LpSolverBase::Value Value;
490 typedef std::map<Row,Value> Base;
493 typedef True IsLinExpression;
495 DualExpr() : Base() { }
497 DualExpr(const Key &v) {
498 Base::insert(std::make_pair(v, 1));
501 void set(const Key &v,const Value &c) {
502 Base::insert(std::make_pair(v, c));
505 ///Removes the components with zero coefficient.
507 for (Base::iterator i=Base::begin(); i!=Base::end();) {
510 if ((*i).second==0) Base::erase(i);
515 ///Removes the coefficients closer to zero than \c tolerance.
516 void simplify(double &tolerance) {
517 for (Base::iterator i=Base::begin(); i!=Base::end();) {
520 if (std::fabs((*i).second)<tolerance) Base::erase(i);
526 ///Sets all coefficients to 0.
532 DualExpr &operator+=(const DualExpr &e) {
533 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
534 (*this)[j->first]+=j->second;
538 DualExpr &operator-=(const DualExpr &e) {
539 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
540 (*this)[j->first]-=j->second;
544 DualExpr &operator*=(const Value &c) {
545 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
550 DualExpr &operator/=(const Value &c) {
551 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
562 //Abstract virtual functions
563 virtual LpSolverBase &_newLp() = 0;
564 virtual LpSolverBase &_copyLp(){
565 ///\todo This should be implemented here, too, when we have problem retrieving routines. It can be overriden.
568 LpSolverBase & newlp(_newLp());
570 //return *(LpSolverBase*)0;
573 virtual int _addCol() = 0;
574 virtual int _addRow() = 0;
575 virtual void _eraseCol(int col) = 0;
576 virtual void _eraseRow(int row) = 0;
577 virtual void _getColName(int col, std::string & name) = 0;
578 virtual void _setColName(int col, const std::string & name) = 0;
579 virtual void _setRowCoeffs(int i,
582 Value const * values ) = 0;
583 virtual void _setColCoeffs(int i,
586 Value const * values ) = 0;
587 virtual void _setCoeff(int row, int col, Value value) = 0;
588 virtual void _setColLowerBound(int i, Value value) = 0;
589 virtual void _setColUpperBound(int i, Value value) = 0;
590 // virtual void _setRowLowerBound(int i, Value value) = 0;
591 // virtual void _setRowUpperBound(int i, Value value) = 0;
592 virtual void _setRowBounds(int i, Value lower, Value upper) = 0;
593 virtual void _setObjCoeff(int i, Value obj_coef) = 0;
594 virtual void _clearObj()=0;
595 // virtual void _setObj(int length,
596 // int const * indices,
597 // Value const * values ) = 0;
598 virtual SolveExitStatus _solve() = 0;
599 virtual Value _getPrimal(int i) = 0;
600 virtual Value _getDual(int i) = 0;
601 virtual Value _getPrimalValue() = 0;
602 virtual bool _isBasicCol(int i) = 0;
603 virtual SolutionStatus _getPrimalStatus() = 0;
604 virtual SolutionStatus _getDualStatus() = 0;
605 ///\todo This could be implemented here, too, using _getPrimalStatus() and
607 virtual ProblemTypes _getProblemType() = 0;
609 virtual void _setMax() = 0;
610 virtual void _setMin() = 0;
612 //Own protected stuff
614 //Constant component of the objective function
615 Value obj_const_comp;
623 LpSolverBase() : obj_const_comp(0) {}
626 virtual ~LpSolverBase() {}
628 ///Creates a new LP problem
629 LpSolverBase &newLp() {return _newLp();}
630 ///Makes a copy of the LP problem
631 LpSolverBase ©Lp() {return _copyLp();}
633 ///\name Build up and modify the LP
637 ///Add a new empty column (i.e a new variable) to the LP
638 Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
640 ///\brief Adds several new columns
641 ///(i.e a variables) at once
643 ///This magic function takes a container as its argument
644 ///and fills its elements
645 ///with new columns (i.e. variables)
647 ///- a standard STL compatible iterable container with
648 ///\ref Col as its \c values_type
651 ///std::vector<LpSolverBase::Col>
652 ///std::list<LpSolverBase::Col>
654 ///- a standard STL compatible iterable container with
655 ///\ref Col as its \c mapped_type
658 ///std::map<AnyType,LpSolverBase::Col>
660 ///- an iterable lemon \ref concept::WriteMap "write map" like
662 ///ListGraph::NodeMap<LpSolverBase::Col>
663 ///ListGraph::EdgeMap<LpSolverBase::Col>
665 ///\return The number of the created column.
668 int addColSet(T &t) { return 0;}
671 typename enable_if<typename T::value_type::LpSolverCol,int>::type
672 addColSet(T &t,dummy<0> = 0) {
674 for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
678 typename enable_if<typename T::value_type::second_type::LpSolverCol,
680 addColSet(T &t,dummy<1> = 1) {
682 for(typename T::iterator i=t.begin();i!=t.end();++i) {
689 typename enable_if<typename T::MapIt::Value::LpSolverCol,
691 addColSet(T &t,dummy<2> = 2) {
693 for(typename T::MapIt i(t); i!=INVALID; ++i)
702 ///Set a column (i.e a dual constraint) of the LP
704 ///\param c is the column to be modified
705 ///\param e is a dual linear expression (see \ref DualExpr)
707 void col(Col c,const DualExpr &e) {
708 std::vector<int> indices;
709 std::vector<Value> values;
710 indices.push_back(0);
712 for(DualExpr::const_iterator i=e.begin(); i!=e.end(); ++i)
714 indices.push_back(rows.floatingId((*i).first.id));
715 values.push_back((*i).second);
717 _setColCoeffs(cols.floatingId(c.id),indices.size()-1,
718 &indices[0],&values[0]);
721 ///Add a new column to the LP
723 ///\param e is a dual linear expression (see \ref DualExpr)
724 ///\param obj is the corresponding component of the objective
725 ///function. It is 0 by default.
726 ///\return The created column.
727 Col addCol(const DualExpr &e, Value obj=0) {
734 ///Add a new empty row (i.e a new constraint) to the LP
736 ///This function adds a new empty row (i.e a new constraint) to the LP.
737 ///\return The created row
738 Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
740 ///\brief Add several new rows
741 ///(i.e a constraints) at once
743 ///This magic function takes a container as its argument
744 ///and fills its elements
745 ///with new row (i.e. variables)
747 ///- a standard STL compatible iterable container with
748 ///\ref Row as its \c values_type
751 ///std::vector<LpSolverBase::Row>
752 ///std::list<LpSolverBase::Row>
754 ///- a standard STL compatible iterable container with
755 ///\ref Row as its \c mapped_type
758 ///std::map<AnyType,LpSolverBase::Row>
760 ///- an iterable lemon \ref concept::WriteMap "write map" like
762 ///ListGraph::NodeMap<LpSolverBase::Row>
763 ///ListGraph::EdgeMap<LpSolverBase::Row>
765 ///\return The number of rows created.
768 int addRowSet(T &t) { return 0;}
771 typename enable_if<typename T::value_type::LpSolverRow,int>::type
772 addRowSet(T &t,dummy<0> = 0) {
774 for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addRow();s++;}
778 typename enable_if<typename T::value_type::second_type::LpSolverRow,
780 addRowSet(T &t,dummy<1> = 1) {
782 for(typename T::iterator i=t.begin();i!=t.end();++i) {
789 typename enable_if<typename T::MapIt::Value::LpSolverRow,
791 addRowSet(T &t,dummy<2> = 2) {
793 for(typename T::MapIt i(t); i!=INVALID; ++i)
802 ///Set a row (i.e a constraint) of the LP
804 ///\param r is the row to be modified
805 ///\param l is lower bound (-\ref INF means no bound)
806 ///\param e is a linear expression (see \ref Expr)
807 ///\param u is the upper bound (\ref INF means no bound)
808 ///\bug This is a temportary function. The interface will change to
810 ///\todo Option to control whether a constraint with a single variable is
812 void row(Row r, Value l,const Expr &e, Value u) {
813 std::vector<int> indices;
814 std::vector<Value> values;
815 indices.push_back(0);
817 for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i)
818 if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
819 indices.push_back(cols.floatingId((*i).first.id));
820 values.push_back((*i).second);
822 _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
823 &indices[0],&values[0]);
824 // _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
825 // _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
826 _setRowBounds(rows.floatingId(r.id),l-e.constComp(),u-e.constComp());
829 ///Set a row (i.e a constraint) of the LP
831 ///\param r is the row to be modified
832 ///\param c is a linear expression (see \ref Constr)
833 void row(Row r, const Constr &c) {
835 c.lowerBounded()?c.lowerBound():-INF,
837 c.upperBounded()?c.upperBound():INF);
840 ///Add a new row (i.e a new constraint) to the LP
842 ///\param l is the lower bound (-\ref INF means no bound)
843 ///\param e is a linear expression (see \ref Expr)
844 ///\param u is the upper bound (\ref INF means no bound)
845 ///\return The created row.
846 ///\bug This is a temportary function. The interface will change to
848 Row addRow(Value l,const Expr &e, Value u) {
854 ///Add a new row (i.e a new constraint) to the LP
856 ///\param c is a linear expression (see \ref Constr)
857 ///\return The created row.
858 Row addRow(const Constr &c) {
863 ///Erase a coloumn (i.e a variable) from the LP
865 ///\param c is the coloumn to be deleted
866 ///\todo Please check this
867 void eraseCol(Col c) {
868 _eraseCol(cols.floatingId(c.id));
871 ///Erase a row (i.e a constraint) from the LP
873 ///\param r is the row to be deleted
874 ///\todo Please check this
875 void eraseRow(Row r) {
876 _eraseRow(rows.floatingId(r.id));
880 /// Get the name of a column
882 ///\param c is the coresponding coloumn
883 ///\return The name of the colunm
884 std::string ColName(Col c){
886 _getColName(cols.floatingId(c.id), name);
890 /// Set the name of a column
892 ///\param c is the coresponding coloumn
893 ///\param name The name to be given
894 void ColName(Col c, const std::string & name){
895 _setColName(cols.floatingId(c.id), name);
898 /// Set an element of the coefficient matrix of the LP
900 ///\param r is the row of the element to be modified
901 ///\param c is the coloumn of the element to be modified
902 ///\param val is the new value of the coefficient
904 void Coeff(Row r, Col c, Value val){
905 _setCoeff(rows.floatingId(r.id),cols.floatingId(c.id), val);
908 /// Set the lower bound of a column (i.e a variable)
910 /// The lower bound of a variable (column) has to be given by an
911 /// extended number of type Value, i.e. a finite number of type
912 /// Value or -\ref INF.
913 void colLowerBound(Col c, Value value) {
914 _setColLowerBound(cols.floatingId(c.id),value);
917 ///\brief Set the lower bound of several columns
918 ///(i.e a variables) at once
920 ///This magic function takes a container as its argument
921 ///and applies the function on all of its elements.
922 /// The lower bound of a variable (column) has to be given by an
923 /// extended number of type Value, i.e. a finite number of type
924 /// Value or -\ref INF.
927 void colLowerBound(T &t, Value value) { return 0;}
930 typename enable_if<typename T::value_type::LpSolverCol,void>::type
931 colLowerBound(T &t, Value value,dummy<0> = 0) {
932 for(typename T::iterator i=t.begin();i!=t.end();++i) {
933 colLowerBound(*i, value);
937 typename enable_if<typename T::value_type::second_type::LpSolverCol,
939 colLowerBound(T &t, Value value,dummy<1> = 1) {
940 for(typename T::iterator i=t.begin();i!=t.end();++i) {
941 colLowerBound(i->second, value);
945 typename enable_if<typename T::MapIt::Value::LpSolverCol,
947 colLowerBound(T &t, Value value,dummy<2> = 2) {
948 for(typename T::MapIt i(t); i!=INVALID; ++i){
949 colLowerBound(*i, value);
954 /// Set the upper bound of a column (i.e a variable)
956 /// The upper bound of a variable (column) has to be given by an
957 /// extended number of type Value, i.e. a finite number of type
958 /// Value or \ref INF.
959 void colUpperBound(Col c, Value value) {
960 _setColUpperBound(cols.floatingId(c.id),value);
963 ///\brief Set the lower bound of several columns
964 ///(i.e a variables) at once
966 ///This magic function takes a container as its argument
967 ///and applies the function on all of its elements.
968 /// The upper bound of a variable (column) has to be given by an
969 /// extended number of type Value, i.e. a finite number of type
970 /// Value or \ref INF.
973 void colUpperBound(T &t, Value value) { return 0;}
976 typename enable_if<typename T::value_type::LpSolverCol,void>::type
977 colUpperBound(T &t, Value value,dummy<0> = 0) {
978 for(typename T::iterator i=t.begin();i!=t.end();++i) {
979 colUpperBound(*i, value);
983 typename enable_if<typename T::value_type::second_type::LpSolverCol,
985 colUpperBound(T &t, Value value,dummy<1> = 1) {
986 for(typename T::iterator i=t.begin();i!=t.end();++i) {
987 colUpperBound(i->second, value);
991 typename enable_if<typename T::MapIt::Value::LpSolverCol,
993 colUpperBound(T &t, Value value,dummy<2> = 2) {
994 for(typename T::MapIt i(t); i!=INVALID; ++i){
995 colUpperBound(*i, value);
1000 /// Set the lower and the upper bounds of a column (i.e a variable)
1002 /// The lower and the upper bounds of
1003 /// a variable (column) have to be given by an
1004 /// extended number of type Value, i.e. a finite number of type
1005 /// Value, -\ref INF or \ref INF.
1006 void colBounds(Col c, Value lower, Value upper) {
1007 _setColLowerBound(cols.floatingId(c.id),lower);
1008 _setColUpperBound(cols.floatingId(c.id),upper);
1011 ///\brief Set the lower and the upper bound of several columns
1012 ///(i.e a variables) at once
1014 ///This magic function takes a container as its argument
1015 ///and applies the function on all of its elements.
1016 /// The lower and the upper bounds of
1017 /// a variable (column) have to be given by an
1018 /// extended number of type Value, i.e. a finite number of type
1019 /// Value, -\ref INF or \ref INF.
1022 void colBounds(T &t, Value lower, Value upper) { return 0;}
1025 typename enable_if<typename T::value_type::LpSolverCol,void>::type
1026 colBounds(T &t, Value lower, Value upper,dummy<0> = 0) {
1027 for(typename T::iterator i=t.begin();i!=t.end();++i) {
1028 colBounds(*i, lower, upper);
1032 typename enable_if<typename T::value_type::second_type::LpSolverCol,
1034 colBounds(T &t, Value lower, Value upper,dummy<1> = 1) {
1035 for(typename T::iterator i=t.begin();i!=t.end();++i) {
1036 colBounds(i->second, lower, upper);
1040 typename enable_if<typename T::MapIt::Value::LpSolverCol,
1042 colBounds(T &t, Value lower, Value upper,dummy<2> = 2) {
1043 for(typename T::MapIt i(t); i!=INVALID; ++i){
1044 colBounds(*i, lower, upper);
1049 // /// Set the lower bound of a row (i.e a constraint)
1051 // /// The lower bound of a linear expression (row) has to be given by an
1052 // /// extended number of type Value, i.e. a finite number of type
1053 // /// Value or -\ref INF.
1054 // void rowLowerBound(Row r, Value value) {
1055 // _setRowLowerBound(rows.floatingId(r.id),value);
1057 // /// Set the upper bound of a row (i.e a constraint)
1059 // /// The upper bound of a linear expression (row) has to be given by an
1060 // /// extended number of type Value, i.e. a finite number of type
1061 // /// Value or \ref INF.
1062 // void rowUpperBound(Row r, Value value) {
1063 // _setRowUpperBound(rows.floatingId(r.id),value);
1066 /// Set the lower and the upper bounds of a row (i.e a constraint)
1068 /// The lower and the upper bounds of
1069 /// a constraint (row) have to be given by an
1070 /// extended number of type Value, i.e. a finite number of type
1071 /// Value, -\ref INF or \ref INF.
1072 void rowBounds(Row c, Value lower, Value upper) {
1073 _setRowBounds(rows.floatingId(c.id),lower, upper);
1074 // _setRowUpperBound(rows.floatingId(c.id),upper);
1077 ///Set an element of the objective function
1078 void objCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
1079 ///Set the objective function
1081 ///\param e is a linear expression of type \ref Expr.
1082 ///\bug Is should be called obj()
1083 void setObj(Expr e) {
1085 for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
1086 objCoeff((*i).first,(*i).second);
1087 obj_const_comp=e.constComp();
1091 void max() { _setMax(); }
1093 void min() { _setMin(); }
1099 ///\name Solve the LP
1103 ///\e Solve the LP problem at hand
1105 ///\return The result of the optimization procedure. Possible values and their meanings can be found in the documentation of \ref SolveExitStatus.
1107 ///\todo Which method is used to solve the problem
1108 SolveExitStatus solve() { return _solve(); }
1112 ///\name Obtain the solution
1116 /// The status of the primal problem (the original LP problem)
1117 SolutionStatus primalStatus() {
1118 return _getPrimalStatus();
1121 /// The status of the dual (of the original LP) problem
1122 SolutionStatus dualStatus() {
1123 return _getDualStatus();
1126 ///The type of the original LP problem
1127 ProblemTypes problemType() {
1128 return _getProblemType();
1132 Value primal(Col c) { return _getPrimal(cols.floatingId(c.id)); }
1135 Value dual(Row r) { return _getDual(rows.floatingId(r.id)); }
1138 bool isBasicCol(Col c) { return _isBasicCol(cols.floatingId(c.id)); }
1143 ///- \ref INF or -\ref INF means either infeasibility or unboundedness
1144 /// of the primal problem, depending on whether we minimize or maximize.
1145 ///- \ref NaN if no primal solution is found.
1146 ///- The (finite) objective value if an optimal solution is found.
1147 Value primalValue() { return _getPrimalValue()+obj_const_comp;}
1154 ///\relates LpSolverBase::Expr
1156 inline LpSolverBase::Expr operator+(const LpSolverBase::Expr &a,
1157 const LpSolverBase::Expr &b)
1159 LpSolverBase::Expr tmp(a);
1165 ///\relates LpSolverBase::Expr
1167 inline LpSolverBase::Expr operator-(const LpSolverBase::Expr &a,
1168 const LpSolverBase::Expr &b)
1170 LpSolverBase::Expr tmp(a);
1176 ///\relates LpSolverBase::Expr
1178 inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
1179 const LpSolverBase::Value &b)
1181 LpSolverBase::Expr tmp(a);
1188 ///\relates LpSolverBase::Expr
1190 inline LpSolverBase::Expr operator*(const LpSolverBase::Value &a,
1191 const LpSolverBase::Expr &b)
1193 LpSolverBase::Expr tmp(b);
1199 ///\relates LpSolverBase::Expr
1201 inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
1202 const LpSolverBase::Value &b)
1204 LpSolverBase::Expr tmp(a);
1211 ///\relates LpSolverBase::Constr
1213 inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
1214 const LpSolverBase::Expr &f)
1216 return LpSolverBase::Constr(-LpSolverBase::INF,e-f,0);
1221 ///\relates LpSolverBase::Constr
1223 inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &e,
1224 const LpSolverBase::Expr &f)
1226 return LpSolverBase::Constr(e,f);
1231 ///\relates LpSolverBase::Constr
1233 inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
1234 const LpSolverBase::Value &f)
1236 return LpSolverBase::Constr(e,f);
1241 ///\relates LpSolverBase::Constr
1243 inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
1244 const LpSolverBase::Expr &f)
1246 return LpSolverBase::Constr(-LpSolverBase::INF,f-e,0);
1252 ///\relates LpSolverBase::Constr
1254 inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &e,
1255 const LpSolverBase::Expr &f)
1257 return LpSolverBase::Constr(f,e);
1263 ///\relates LpSolverBase::Constr
1265 inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
1266 const LpSolverBase::Value &f)
1268 return LpSolverBase::Constr(f,e);
1273 ///\relates LpSolverBase::Constr
1275 inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
1276 const LpSolverBase::Expr &f)
1278 return LpSolverBase::Constr(0,e-f,0);
1283 ///\relates LpSolverBase::Constr
1285 inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &n,
1286 const LpSolverBase::Constr&c)
1288 LpSolverBase::Constr tmp(c);
1289 ///\todo Create an own exception type.
1290 if(!isnan(tmp.lowerBound())) throw LogicError();
1291 else tmp.lowerBound()=n;
1296 ///\relates LpSolverBase::Constr
1298 inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
1299 const LpSolverBase::Value &n)
1301 LpSolverBase::Constr tmp(c);
1302 ///\todo Create an own exception type.
1303 if(!isnan(tmp.upperBound())) throw LogicError();
1304 else tmp.upperBound()=n;
1310 ///\relates LpSolverBase::Constr
1312 inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &n,
1313 const LpSolverBase::Constr&c)
1315 LpSolverBase::Constr tmp(c);
1316 ///\todo Create an own exception type.
1317 if(!isnan(tmp.upperBound())) throw LogicError();
1318 else tmp.upperBound()=n;
1323 ///\relates LpSolverBase::Constr
1325 inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
1326 const LpSolverBase::Value &n)
1328 LpSolverBase::Constr tmp(c);
1329 ///\todo Create an own exception type.
1330 if(!isnan(tmp.lowerBound())) throw LogicError();
1331 else tmp.lowerBound()=n;
1337 ///\relates LpSolverBase::DualExpr
1339 inline LpSolverBase::DualExpr operator+(const LpSolverBase::DualExpr &a,
1340 const LpSolverBase::DualExpr &b)
1342 LpSolverBase::DualExpr tmp(a);
1348 ///\relates LpSolverBase::DualExpr
1350 inline LpSolverBase::DualExpr operator-(const LpSolverBase::DualExpr &a,
1351 const LpSolverBase::DualExpr &b)
1353 LpSolverBase::DualExpr tmp(a);
1359 ///\relates LpSolverBase::DualExpr
1361 inline LpSolverBase::DualExpr operator*(const LpSolverBase::DualExpr &a,
1362 const LpSolverBase::Value &b)
1364 LpSolverBase::DualExpr tmp(a);
1371 ///\relates LpSolverBase::DualExpr
1373 inline LpSolverBase::DualExpr operator*(const LpSolverBase::Value &a,
1374 const LpSolverBase::DualExpr &b)
1376 LpSolverBase::DualExpr tmp(b);
1382 ///\relates LpSolverBase::DualExpr
1384 inline LpSolverBase::DualExpr operator/(const LpSolverBase::DualExpr &a,
1385 const LpSolverBase::Value &b)
1387 LpSolverBase::DualExpr tmp(a);
1395 #endif //LEMON_LP_BASE_H