Make the constructors of ColIt public.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_LP_BASE_H
20 #define LEMON_LP_BASE_H
27 #include<lemon/bits/utility.h>
28 #include<lemon/error.h>
29 #include<lemon/bits/invalid.h>
32 ///\brief The interface of the LP solver interface.
33 ///\ingroup gen_opt_group
36 ///Internal data structure to convert floating id's to fix one's
38 ///\todo This might be implemented to be also usable in other places.
45 std::vector<int> index;
46 std::vector<int> cross;
47 _FixId() : _first_index(-1), first_free(-1) {};
48 ///Convert a floating id to a fix one
50 ///\param n is a floating id
51 ///\return the corresponding fix id
52 int fixId(int n) const {return cross[n];}
53 ///Convert a fix id to a floating one
55 ///\param n is a fix id
56 ///\return the corresponding floating id
57 int floatingId(int n) const { return index[n];}
58 ///Add a new floating id.
60 ///\param n is a floating id
61 ///\return the fix id of the new value
62 ///\todo Multiple additions should also be handled.
65 if(cross.empty()) _first_index=n;
66 if(n>=int(cross.size())) {
69 cross[n]=index.size();
74 int next=index[first_free];
81 ///\todo Create an own exception type.
82 throw LogicError(); //floatingId-s must form a continuous range;
87 ///\param n is a fix id
94 for(int i=fl+1;i<int(cross.size());++i) {
100 ///An upper bound on the largest fix id.
102 ///\todo Do we need this?
104 std::size_t maxFixId() { return cross.size()-1; }
106 ///Returns the first (smallest) inserted index
108 ///Returns the first (smallest) inserted index
109 ///or -1 if no index has been inserted before.
110 int firstIndex() {return _first_index;}
113 ///Common base class for LP solvers
115 ///\todo Much more docs
116 ///\ingroup gen_opt_group
125 ///Possible outcomes of an LP solving procedure
126 enum SolveExitStatus {
127 ///This means that the problem has been successfully solved: either
128 ///an optimal solution has been found or infeasibility/unboundedness
131 ///Any other case (including the case when some user specified limit has been exceeded)
136 enum SolutionStatus {
137 ///Feasible solution hasn't been found (but may exist).
139 ///\todo NOTFOUND might be a better name.
142 ///The problem has no feasible solution
144 ///Feasible solution found
146 ///Optimal solution exists and found
148 ///The cost function is unbounded
150 ///\todo Give a feasible solution and an infinite ray (and the
151 ///corresponding bases)
155 ///\e The type of the investigated LP problem
157 ///Primal-dual feasible
158 PRIMAL_DUAL_FEASIBLE = 0,
159 ///Primal feasible dual infeasible
160 PRIMAL_FEASIBLE_DUAL_INFEASIBLE = 1,
161 ///Primal infeasible dual feasible
162 PRIMAL_INFEASIBLE_DUAL_FEASIBLE = 2,
163 ///Primal-dual infeasible
164 PRIMAL_DUAL_INFEASIBLE = 3,
165 ///Could not determine so far
169 ///The floating point type used by the solver
170 typedef double Value;
171 ///The infinity constant
172 static const Value INF;
173 ///The not a number constant
174 static const Value NaN;
176 static inline bool isNaN(const Value& v) { return v!=v; }
182 ///Refer to a column of the LP.
184 ///This type is used to refer to a column of the LP.
186 ///Its value remains valid and correct even after the addition or erase of
189 ///\todo Document what can one do with a Col (INVALID, comparing,
190 ///it is similar to Node/Edge)
194 friend class LpSolverBase;
195 friend class MipSolverBase;
197 typedef Value ExprValue;
198 typedef True LpSolverCol;
200 Col(const Invalid&) : id(-1) {}
201 bool operator< (Col c) const {return id< c.id;}
202 bool operator> (Col c) const {return id> c.id;}
203 bool operator==(Col c) const {return id==c.id;}
204 bool operator!=(Col c) const {return id!=c.id;}
207 class ColIt : public Col {
211 ColIt(LpSolverBase &lp) : _lp(&lp)
213 id = _lp->cols.cross.empty()?-1:
214 _lp->cols.fixId(_lp->cols.firstIndex());
216 ColIt(const Invalid&) : Col(INVALID) {}
219 int fid = _lp->cols.floatingId(id)+1;
220 id = unsigned(fid)<_lp->cols.cross.size() ? _lp->cols.fixId(fid) : -1;
225 ///Refer to a row of the LP.
227 ///This type is used to refer to a row of the LP.
229 ///Its value remains valid and correct even after the addition or erase of
232 ///\todo Document what can one do with a Row (INVALID, comparing,
233 ///it is similar to Node/Edge)
237 friend class LpSolverBase;
239 typedef Value ExprValue;
240 typedef True LpSolverRow;
242 Row(const Invalid&) : id(-1) {}
244 bool operator< (Row c) const {return id< c.id;}
245 bool operator> (Row c) const {return id> c.id;}
246 bool operator==(Row c) const {return id==c.id;}
247 bool operator!=(Row c) const {return id!=c.id;}
250 ///Linear expression of variables and a constant component
252 ///This data structure strores a linear expression of the variables
253 ///(\ref Col "Col"s) and also has a constant component.
255 ///There are several ways to access and modify the contents of this
257 ///- Its it fully compatible with \c std::map<Col,double>, so for expamle
258 ///if \c e is an Expr and \c v and \c w are of type \ref Col, then you can
259 ///read and modify the coefficients like
266 ///or you can also iterate through its elements.
269 ///for(LpSolverBase::Expr::iterator i=e.begin();i!=e.end();++i)
272 ///(This code computes the sum of all coefficients).
273 ///- Numbers (<tt>double</tt>'s)
274 ///and variables (\ref Col "Col"s) directly convert to an
275 ///\ref Expr and the usual linear operations are defined, so
278 ///2*v-3.12*(v-w/2)+2
279 ///v*2.1+(3*v+(v*12+w+6)*3)/2
281 ///are valid \ref Expr "Expr"essions.
282 ///The usual assignment operations are also defined.
285 ///e+=2*v-3.12*(v-w/2)+2;
289 ///- The constant member can be set and read by \ref constComp()
292 ///double c=e.constComp();
295 ///\note \ref clear() not only sets all coefficients to 0 but also
296 ///clears the constant components.
300 class Expr : public std::map<Col,Value>
303 typedef LpSolverBase::Col Key;
304 typedef LpSolverBase::Value Value;
307 typedef std::map<Col,Value> Base;
311 typedef True IsLinExpression;
313 Expr() : Base(), const_comp(0) { }
315 Expr(const Key &v) : const_comp(0) {
316 Base::insert(std::make_pair(v, 1));
319 Expr(const Value &v) : const_comp(v) {}
321 void set(const Key &v,const Value &c) {
322 Base::insert(std::make_pair(v, c));
325 Value &constComp() { return const_comp; }
327 const Value &constComp() const { return const_comp; }
329 ///Removes the components with zero coefficient.
331 for (Base::iterator i=Base::begin(); i!=Base::end();) {
334 if ((*i).second==0) Base::erase(i);
339 ///Removes the coefficients closer to zero than \c tolerance.
340 void simplify(double &tolerance) {
341 for (Base::iterator i=Base::begin(); i!=Base::end();) {
344 if (std::fabs((*i).second)<tolerance) Base::erase(i);
349 ///Sets all coefficients and the constant component to 0.
356 Expr &operator+=(const Expr &e) {
357 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
358 (*this)[j->first]+=j->second;
359 const_comp+=e.const_comp;
363 Expr &operator-=(const Expr &e) {
364 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
365 (*this)[j->first]-=j->second;
366 const_comp-=e.const_comp;
370 Expr &operator*=(const Value &c) {
371 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
377 Expr &operator/=(const Value &c) {
378 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
387 ///This data stucture represents a linear constraint in the LP.
388 ///Basically it is a linear expression with a lower or an upper bound
389 ///(or both). These parts of the constraint can be obtained by the member
390 ///functions \ref expr(), \ref lowerBound() and \ref upperBound(),
392 ///There are two ways to construct a constraint.
393 ///- You can set the linear expression and the bounds directly
394 /// by the functions above.
395 ///- The operators <tt>\<=</tt>, <tt>==</tt> and <tt>\>=</tt>
396 /// are defined between expressions, or even between constraints whenever
397 /// it makes sense. Therefore if \c e and \c f are linear expressions and
398 /// \c s and \c t are numbers, then the followings are valid expressions
399 /// and thus they can be used directly e.g. in \ref addRow() whenever
408 ///\warning The validity of a constraint is checked only at run time, so
409 ///e.g. \ref addRow(<tt>x[1]\<=x[2]<=5</tt>) will compile, but will throw a
410 ///\ref LogicError exception.
414 typedef LpSolverBase::Expr Expr;
415 typedef Expr::Key Key;
416 typedef Expr::Value Value;
418 // static const Value INF;
419 // static const Value NaN;
426 Constr() : _expr(), _lb(NaN), _ub(NaN) {}
428 Constr(Value lb,const Expr &e,Value ub) :
429 _expr(e), _lb(lb), _ub(ub) {}
431 Constr(const Expr &e,Value ub) :
432 _expr(e), _lb(NaN), _ub(ub) {}
434 Constr(Value lb,const Expr &e) :
435 _expr(e), _lb(lb), _ub(NaN) {}
437 Constr(const Expr &e) :
438 _expr(e), _lb(NaN), _ub(NaN) {}
446 ///Reference to the linear expression
447 Expr &expr() { return _expr; }
448 ///Cont reference to the linear expression
449 const Expr &expr() const { return _expr; }
450 ///Reference to the lower bound.
453 ///- \ref INF "INF": the constraint is lower unbounded.
454 ///- \ref NaN "NaN": lower bound has not been set.
455 ///- finite number: the lower bound
456 Value &lowerBound() { return _lb; }
457 ///The const version of \ref lowerBound()
458 const Value &lowerBound() const { return _lb; }
459 ///Reference to the upper bound.
462 ///- \ref INF "INF": the constraint is upper unbounded.
463 ///- \ref NaN "NaN": upper bound has not been set.
464 ///- finite number: the upper bound
465 Value &upperBound() { return _ub; }
466 ///The const version of \ref upperBound()
467 const Value &upperBound() const { return _ub; }
468 ///Is the constraint lower bounded?
469 bool lowerBounded() const {
473 ///Is the constraint upper bounded?
474 bool upperBounded() const {
480 ///Linear expression of rows
482 ///This data structure represents a column of the matrix,
483 ///thas is it strores a linear expression of the dual variables
484 ///(\ref Row "Row"s).
486 ///There are several ways to access and modify the contents of this
488 ///- Its it fully compatible with \c std::map<Row,double>, so for expamle
489 ///if \c e is an DualExpr and \c v
490 ///and \c w are of type \ref Row, then you can
491 ///read and modify the coefficients like
498 ///or you can also iterate through its elements.
501 ///for(LpSolverBase::DualExpr::iterator i=e.begin();i!=e.end();++i)
504 ///(This code computes the sum of all coefficients).
505 ///- Numbers (<tt>double</tt>'s)
506 ///and variables (\ref Row "Row"s) directly convert to an
507 ///\ref DualExpr and the usual linear operations are defined, so
511 ///v*2.1+(3*v+(v*12+w)*3)/2
513 ///are valid \ref DualExpr "DualExpr"essions.
514 ///The usual assignment operations are also defined.
517 ///e+=2*v-3.12*(v-w/2);
524 class DualExpr : public std::map<Row,Value>
527 typedef LpSolverBase::Row Key;
528 typedef LpSolverBase::Value Value;
531 typedef std::map<Row,Value> Base;
534 typedef True IsLinExpression;
536 DualExpr() : Base() { }
538 DualExpr(const Key &v) {
539 Base::insert(std::make_pair(v, 1));
542 void set(const Key &v,const Value &c) {
543 Base::insert(std::make_pair(v, c));
546 ///Removes the components with zero coefficient.
548 for (Base::iterator i=Base::begin(); i!=Base::end();) {
551 if ((*i).second==0) Base::erase(i);
556 ///Removes the coefficients closer to zero than \c tolerance.
557 void simplify(double &tolerance) {
558 for (Base::iterator i=Base::begin(); i!=Base::end();) {
561 if (std::fabs((*i).second)<tolerance) Base::erase(i);
567 ///Sets all coefficients to 0.
573 DualExpr &operator+=(const DualExpr &e) {
574 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
575 (*this)[j->first]+=j->second;
579 DualExpr &operator-=(const DualExpr &e) {
580 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
581 (*this)[j->first]-=j->second;
585 DualExpr &operator*=(const Value &c) {
586 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
591 DualExpr &operator/=(const Value &c) {
592 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
601 //Abstract virtual functions
602 virtual LpSolverBase &_newLp() = 0;
603 virtual LpSolverBase &_copyLp(){
604 ///\todo This should be implemented here, too, when we have problem retrieving routines. It can be overriden.
607 LpSolverBase & newlp(_newLp());
609 //return *(LpSolverBase*)0;
612 virtual int _addCol() = 0;
613 virtual int _addRow() = 0;
614 virtual void _eraseCol(int col) = 0;
615 virtual void _eraseRow(int row) = 0;
616 virtual void _getColName(int col, std::string & name) = 0;
617 virtual void _setColName(int col, const std::string & name) = 0;
618 virtual void _setRowCoeffs(int i,
621 Value const * values ) = 0;
622 virtual void _setColCoeffs(int i,
625 Value const * values ) = 0;
626 virtual void _setCoeff(int row, int col, Value value) = 0;
627 virtual void _setColLowerBound(int i, Value value) = 0;
628 virtual void _setColUpperBound(int i, Value value) = 0;
629 // virtual void _setRowLowerBound(int i, Value value) = 0;
630 // virtual void _setRowUpperBound(int i, Value value) = 0;
631 virtual void _setRowBounds(int i, Value lower, Value upper) = 0;
632 virtual void _setObjCoeff(int i, Value obj_coef) = 0;
633 virtual void _clearObj()=0;
634 // virtual void _setObj(int length,
635 // int const * indices,
636 // Value const * values ) = 0;
637 virtual SolveExitStatus _solve() = 0;
638 virtual Value _getPrimal(int i) = 0;
639 virtual Value _getDual(int i) = 0;
640 virtual Value _getPrimalValue() = 0;
641 virtual bool _isBasicCol(int i) = 0;
642 virtual SolutionStatus _getPrimalStatus() = 0;
643 virtual SolutionStatus _getDualStatus() = 0;
644 ///\todo This could be implemented here, too, using _getPrimalStatus() and
646 virtual ProblemTypes _getProblemType() = 0;
648 virtual void _setMax() = 0;
649 virtual void _setMin() = 0;
651 //Own protected stuff
653 //Constant component of the objective function
654 Value obj_const_comp;
662 LpSolverBase() : obj_const_comp(0) {}
665 virtual ~LpSolverBase() {}
667 ///Creates a new LP problem
668 LpSolverBase &newLp() {return _newLp();}
669 ///Makes a copy of the LP problem
670 LpSolverBase ©Lp() {return _copyLp();}
672 ///\name Build up and modify the LP
676 ///Add a new empty column (i.e a new variable) to the LP
677 Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
679 ///\brief Adds several new columns
680 ///(i.e a variables) at once
682 ///This magic function takes a container as its argument
683 ///and fills its elements
684 ///with new columns (i.e. variables)
686 ///- a standard STL compatible iterable container with
687 ///\ref Col as its \c values_type
690 ///std::vector<LpSolverBase::Col>
691 ///std::list<LpSolverBase::Col>
693 ///- a standard STL compatible iterable container with
694 ///\ref Col as its \c mapped_type
697 ///std::map<AnyType,LpSolverBase::Col>
699 ///- an iterable lemon \ref concepts::WriteMap "write map" like
701 ///ListGraph::NodeMap<LpSolverBase::Col>
702 ///ListGraph::EdgeMap<LpSolverBase::Col>
704 ///\return The number of the created column.
707 int addColSet(T &t) { return 0;}
710 typename enable_if<typename T::value_type::LpSolverCol,int>::type
711 addColSet(T &t,dummy<0> = 0) {
713 for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
717 typename enable_if<typename T::value_type::second_type::LpSolverCol,
719 addColSet(T &t,dummy<1> = 1) {
721 for(typename T::iterator i=t.begin();i!=t.end();++i) {
728 typename enable_if<typename T::MapIt::Value::LpSolverCol,
730 addColSet(T &t,dummy<2> = 2) {
732 for(typename T::MapIt i(t); i!=INVALID; ++i)
741 ///Set a column (i.e a dual constraint) of the LP
743 ///\param c is the column to be modified
744 ///\param e is a dual linear expression (see \ref DualExpr)
746 void col(Col c,const DualExpr &e) {
747 std::vector<int> indices;
748 std::vector<Value> values;
749 indices.push_back(0);
751 for(DualExpr::const_iterator i=e.begin(); i!=e.end(); ++i)
753 indices.push_back(rows.floatingId((*i).first.id));
754 values.push_back((*i).second);
756 _setColCoeffs(cols.floatingId(c.id),indices.size()-1,
757 &indices[0],&values[0]);
760 ///Add a new column to the LP
762 ///\param e is a dual linear expression (see \ref DualExpr)
763 ///\param obj is the corresponding component of the objective
764 ///function. It is 0 by default.
765 ///\return The created column.
766 Col addCol(const DualExpr &e, Value obj=0) {
773 ///Add a new empty row (i.e a new constraint) to the LP
775 ///This function adds a new empty row (i.e a new constraint) to the LP.
776 ///\return The created row
777 Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
779 ///\brief Add several new rows
780 ///(i.e a constraints) at once
782 ///This magic function takes a container as its argument
783 ///and fills its elements
784 ///with new row (i.e. variables)
786 ///- a standard STL compatible iterable container with
787 ///\ref Row as its \c values_type
790 ///std::vector<LpSolverBase::Row>
791 ///std::list<LpSolverBase::Row>
793 ///- a standard STL compatible iterable container with
794 ///\ref Row as its \c mapped_type
797 ///std::map<AnyType,LpSolverBase::Row>
799 ///- an iterable lemon \ref concepts::WriteMap "write map" like
801 ///ListGraph::NodeMap<LpSolverBase::Row>
802 ///ListGraph::EdgeMap<LpSolverBase::Row>
804 ///\return The number of rows created.
807 int addRowSet(T &t) { return 0;}
810 typename enable_if<typename T::value_type::LpSolverRow,int>::type
811 addRowSet(T &t,dummy<0> = 0) {
813 for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addRow();s++;}
817 typename enable_if<typename T::value_type::second_type::LpSolverRow,
819 addRowSet(T &t,dummy<1> = 1) {
821 for(typename T::iterator i=t.begin();i!=t.end();++i) {
828 typename enable_if<typename T::MapIt::Value::LpSolverRow,
830 addRowSet(T &t,dummy<2> = 2) {
832 for(typename T::MapIt i(t); i!=INVALID; ++i)
841 ///Set a row (i.e a constraint) of the LP
843 ///\param r is the row to be modified
844 ///\param l is lower bound (-\ref INF means no bound)
845 ///\param e is a linear expression (see \ref Expr)
846 ///\param u is the upper bound (\ref INF means no bound)
847 ///\bug This is a temportary function. The interface will change to
849 ///\todo Option to control whether a constraint with a single variable is
851 void row(Row r, Value l,const Expr &e, Value u) {
852 std::vector<int> indices;
853 std::vector<Value> values;
854 indices.push_back(0);
856 for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i)
857 if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
858 indices.push_back(cols.floatingId((*i).first.id));
859 values.push_back((*i).second);
861 _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
862 &indices[0],&values[0]);
863 // _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
864 // _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
865 _setRowBounds(rows.floatingId(r.id),l-e.constComp(),u-e.constComp());
868 ///Set a row (i.e a constraint) of the LP
870 ///\param r is the row to be modified
871 ///\param c is a linear expression (see \ref Constr)
872 void row(Row r, const Constr &c) {
874 c.lowerBounded()?c.lowerBound():-INF,
876 c.upperBounded()?c.upperBound():INF);
879 ///Add a new row (i.e a new constraint) to the LP
881 ///\param l is the lower bound (-\ref INF means no bound)
882 ///\param e is a linear expression (see \ref Expr)
883 ///\param u is the upper bound (\ref INF means no bound)
884 ///\return The created row.
885 ///\bug This is a temportary function. The interface will change to
887 Row addRow(Value l,const Expr &e, Value u) {
893 ///Add a new row (i.e a new constraint) to the LP
895 ///\param c is a linear expression (see \ref Constr)
896 ///\return The created row.
897 Row addRow(const Constr &c) {
902 ///Erase a coloumn (i.e a variable) from the LP
904 ///\param c is the coloumn to be deleted
905 ///\todo Please check this
906 void eraseCol(Col c) {
907 _eraseCol(cols.floatingId(c.id));
910 ///Erase a row (i.e a constraint) from the LP
912 ///\param r is the row to be deleted
913 ///\todo Please check this
914 void eraseRow(Row r) {
915 _eraseRow(rows.floatingId(r.id));
919 /// Get the name of a column
921 ///\param c is the coresponding coloumn
922 ///\return The name of the colunm
923 std::string colName(Col c){
925 _getColName(cols.floatingId(c.id), name);
929 /// Set the name of a column
931 ///\param c is the coresponding coloumn
932 ///\param name The name to be given
933 void colName(Col c, const std::string & name){
934 _setColName(cols.floatingId(c.id), name);
937 /// Set an element of the coefficient matrix of the LP
939 ///\param r is the row of the element to be modified
940 ///\param c is the coloumn of the element to be modified
941 ///\param val is the new value of the coefficient
943 void coeff(Row r, Col c, Value val){
944 _setCoeff(rows.floatingId(r.id),cols.floatingId(c.id), val);
947 /// Set the lower bound of a column (i.e a variable)
949 /// The lower bound of a variable (column) has to be given by an
950 /// extended number of type Value, i.e. a finite number of type
951 /// Value or -\ref INF.
952 void colLowerBound(Col c, Value value) {
953 _setColLowerBound(cols.floatingId(c.id),value);
956 ///\brief Set the lower bound of several columns
957 ///(i.e a variables) at once
959 ///This magic function takes a container as its argument
960 ///and applies the function on all of its elements.
961 /// The lower bound of a variable (column) has to be given by an
962 /// extended number of type Value, i.e. a finite number of type
963 /// Value or -\ref INF.
966 void colLowerBound(T &t, Value value) { return 0;}
969 typename enable_if<typename T::value_type::LpSolverCol,void>::type
970 colLowerBound(T &t, Value value,dummy<0> = 0) {
971 for(typename T::iterator i=t.begin();i!=t.end();++i) {
972 colLowerBound(*i, value);
976 typename enable_if<typename T::value_type::second_type::LpSolverCol,
978 colLowerBound(T &t, Value value,dummy<1> = 1) {
979 for(typename T::iterator i=t.begin();i!=t.end();++i) {
980 colLowerBound(i->second, value);
984 typename enable_if<typename T::MapIt::Value::LpSolverCol,
986 colLowerBound(T &t, Value value,dummy<2> = 2) {
987 for(typename T::MapIt i(t); i!=INVALID; ++i){
988 colLowerBound(*i, value);
993 /// Set the upper bound of a column (i.e a variable)
995 /// The upper bound of a variable (column) has to be given by an
996 /// extended number of type Value, i.e. a finite number of type
997 /// Value or \ref INF.
998 void colUpperBound(Col c, Value value) {
999 _setColUpperBound(cols.floatingId(c.id),value);
1002 ///\brief Set the lower bound of several columns
1003 ///(i.e a variables) at once
1005 ///This magic function takes a container as its argument
1006 ///and applies the function on all of its elements.
1007 /// The upper bound of a variable (column) has to be given by an
1008 /// extended number of type Value, i.e. a finite number of type
1009 /// Value or \ref INF.
1012 void colUpperBound(T &t, Value value) { return 0;}
1015 typename enable_if<typename T::value_type::LpSolverCol,void>::type
1016 colUpperBound(T &t, Value value,dummy<0> = 0) {
1017 for(typename T::iterator i=t.begin();i!=t.end();++i) {
1018 colUpperBound(*i, value);
1022 typename enable_if<typename T::value_type::second_type::LpSolverCol,
1024 colUpperBound(T &t, Value value,dummy<1> = 1) {
1025 for(typename T::iterator i=t.begin();i!=t.end();++i) {
1026 colUpperBound(i->second, value);
1030 typename enable_if<typename T::MapIt::Value::LpSolverCol,
1032 colUpperBound(T &t, Value value,dummy<2> = 2) {
1033 for(typename T::MapIt i(t); i!=INVALID; ++i){
1034 colUpperBound(*i, value);
1039 /// Set the lower and the upper bounds of a column (i.e a variable)
1041 /// The lower and the upper bounds of
1042 /// a variable (column) have to be given by an
1043 /// extended number of type Value, i.e. a finite number of type
1044 /// Value, -\ref INF or \ref INF.
1045 void colBounds(Col c, Value lower, Value upper) {
1046 _setColLowerBound(cols.floatingId(c.id),lower);
1047 _setColUpperBound(cols.floatingId(c.id),upper);
1050 ///\brief Set the lower and the upper bound of several columns
1051 ///(i.e a variables) at once
1053 ///This magic function takes a container as its argument
1054 ///and applies the function on all of its elements.
1055 /// The lower and the upper bounds of
1056 /// a variable (column) have to be given by an
1057 /// extended number of type Value, i.e. a finite number of type
1058 /// Value, -\ref INF or \ref INF.
1061 void colBounds(T &t, Value lower, Value upper) { return 0;}
1064 typename enable_if<typename T::value_type::LpSolverCol,void>::type
1065 colBounds(T &t, Value lower, Value upper,dummy<0> = 0) {
1066 for(typename T::iterator i=t.begin();i!=t.end();++i) {
1067 colBounds(*i, lower, upper);
1071 typename enable_if<typename T::value_type::second_type::LpSolverCol,
1073 colBounds(T &t, Value lower, Value upper,dummy<1> = 1) {
1074 for(typename T::iterator i=t.begin();i!=t.end();++i) {
1075 colBounds(i->second, lower, upper);
1079 typename enable_if<typename T::MapIt::Value::LpSolverCol,
1081 colBounds(T &t, Value lower, Value upper,dummy<2> = 2) {
1082 for(typename T::MapIt i(t); i!=INVALID; ++i){
1083 colBounds(*i, lower, upper);
1088 // /// Set the lower bound of a row (i.e a constraint)
1090 // /// The lower bound of a linear expression (row) has to be given by an
1091 // /// extended number of type Value, i.e. a finite number of type
1092 // /// Value or -\ref INF.
1093 // void rowLowerBound(Row r, Value value) {
1094 // _setRowLowerBound(rows.floatingId(r.id),value);
1096 // /// Set the upper bound of a row (i.e a constraint)
1098 // /// The upper bound of a linear expression (row) has to be given by an
1099 // /// extended number of type Value, i.e. a finite number of type
1100 // /// Value or \ref INF.
1101 // void rowUpperBound(Row r, Value value) {
1102 // _setRowUpperBound(rows.floatingId(r.id),value);
1105 /// Set the lower and the upper bounds of a row (i.e a constraint)
1107 /// The lower and the upper bounds of
1108 /// a constraint (row) have to be given by an
1109 /// extended number of type Value, i.e. a finite number of type
1110 /// Value, -\ref INF or \ref INF.
1111 void rowBounds(Row c, Value lower, Value upper) {
1112 _setRowBounds(rows.floatingId(c.id),lower, upper);
1113 // _setRowUpperBound(rows.floatingId(c.id),upper);
1116 ///Set an element of the objective function
1117 void objCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
1118 ///Set the objective function
1120 ///\param e is a linear expression of type \ref Expr.
1121 ///\bug Is should be called obj()
1122 void setObj(Expr e) {
1124 for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
1125 objCoeff((*i).first,(*i).second);
1126 obj_const_comp=e.constComp();
1130 void max() { _setMax(); }
1132 void min() { _setMin(); }
1138 ///\name Solve the LP
1142 ///\e Solve the LP problem at hand
1144 ///\return The result of the optimization procedure. Possible
1145 ///values and their meanings can be found in the documentation of
1146 ///\ref SolveExitStatus.
1148 ///\todo Which method is used to solve the problem
1149 SolveExitStatus solve() { return _solve(); }
1153 ///\name Obtain the solution
1157 /// The status of the primal problem (the original LP problem)
1158 SolutionStatus primalStatus() {
1159 return _getPrimalStatus();
1162 /// The status of the dual (of the original LP) problem
1163 SolutionStatus dualStatus() {
1164 return _getDualStatus();
1167 ///The type of the original LP problem
1168 ProblemTypes problemType() {
1169 return _getProblemType();
1173 Value primal(Col c) { return _getPrimal(cols.floatingId(c.id)); }
1176 Value dual(Row r) { return _getDual(rows.floatingId(r.id)); }
1179 bool isBasicCol(Col c) { return _isBasicCol(cols.floatingId(c.id)); }
1184 ///- \ref INF or -\ref INF means either infeasibility or unboundedness
1185 /// of the primal problem, depending on whether we minimize or maximize.
1186 ///- \ref NaN if no primal solution is found.
1187 ///- The (finite) objective value if an optimal solution is found.
1188 Value primalValue() { return _getPrimalValue()+obj_const_comp;}
1194 ///Common base class for MIP solvers
1195 ///\todo Much more docs
1196 ///\ingroup gen_opt_group
1197 class MipSolverBase : virtual public LpSolverBase{
1200 ///Possible variable (coloumn) types (e.g. real, integer, binary etc.)
1202 ///Continuous variable
1206 ///Unfortunately, cplex 7.5 somewhere writes something like
1207 ///#define INTEGER 'I'
1209 ///\todo No support for other types yet.
1212 ///Sets the type of the given coloumn to the given type
1214 ///Sets the type of the given coloumn to the given type.
1215 void colType(Col c, ColTypes col_type) {
1216 _colType(cols.floatingId(c.id),col_type);
1219 ///Gives back the type of the column.
1221 ///Gives back the type of the column.
1222 ColTypes colType(Col c){
1223 return _colType(cols.floatingId(c.id));
1226 ///Sets the type of the given Col to integer or remove that property.
1228 ///Sets the type of the given Col to integer or remove that property.
1229 void integer(Col c, bool enable) {
1236 ///Gives back whether the type of the column is integer or not.
1238 ///Gives back the type of the column.
1239 ///\return true if the column has integer type and false if not.
1240 bool integer(Col c){
1241 return (colType(c)==INT);
1244 /// The status of the MIP problem
1245 SolutionStatus mipStatus() {
1246 return _getMipStatus();
1251 virtual ColTypes _colType(int col) = 0;
1252 virtual void _colType(int col, ColTypes col_type) = 0;
1253 virtual SolutionStatus _getMipStatus()=0;
1257 ///\relates LpSolverBase::Expr
1259 inline LpSolverBase::Expr operator+(const LpSolverBase::Expr &a,
1260 const LpSolverBase::Expr &b)
1262 LpSolverBase::Expr tmp(a);
1268 ///\relates LpSolverBase::Expr
1270 inline LpSolverBase::Expr operator-(const LpSolverBase::Expr &a,
1271 const LpSolverBase::Expr &b)
1273 LpSolverBase::Expr tmp(a);
1279 ///\relates LpSolverBase::Expr
1281 inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
1282 const LpSolverBase::Value &b)
1284 LpSolverBase::Expr tmp(a);
1291 ///\relates LpSolverBase::Expr
1293 inline LpSolverBase::Expr operator*(const LpSolverBase::Value &a,
1294 const LpSolverBase::Expr &b)
1296 LpSolverBase::Expr tmp(b);
1302 ///\relates LpSolverBase::Expr
1304 inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
1305 const LpSolverBase::Value &b)
1307 LpSolverBase::Expr tmp(a);
1314 ///\relates LpSolverBase::Constr
1316 inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
1317 const LpSolverBase::Expr &f)
1319 return LpSolverBase::Constr(-LpSolverBase::INF,e-f,0);
1324 ///\relates LpSolverBase::Constr
1326 inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &e,
1327 const LpSolverBase::Expr &f)
1329 return LpSolverBase::Constr(e,f);
1334 ///\relates LpSolverBase::Constr
1336 inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
1337 const LpSolverBase::Value &f)
1339 return LpSolverBase::Constr(e,f);
1344 ///\relates LpSolverBase::Constr
1346 inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
1347 const LpSolverBase::Expr &f)
1349 return LpSolverBase::Constr(-LpSolverBase::INF,f-e,0);
1355 ///\relates LpSolverBase::Constr
1357 inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &e,
1358 const LpSolverBase::Expr &f)
1360 return LpSolverBase::Constr(f,e);
1366 ///\relates LpSolverBase::Constr
1368 inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
1369 const LpSolverBase::Value &f)
1371 return LpSolverBase::Constr(f,e);
1376 ///\relates LpSolverBase::Constr
1378 inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
1379 const LpSolverBase::Expr &f)
1381 return LpSolverBase::Constr(0,e-f,0);
1386 ///\relates LpSolverBase::Constr
1388 inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &n,
1389 const LpSolverBase::Constr&c)
1391 LpSolverBase::Constr tmp(c);
1392 ///\todo Create an own exception type.
1393 if(!LpSolverBase::isNaN(tmp.lowerBound())) throw LogicError();
1394 else tmp.lowerBound()=n;
1399 ///\relates LpSolverBase::Constr
1401 inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
1402 const LpSolverBase::Value &n)
1404 LpSolverBase::Constr tmp(c);
1405 ///\todo Create an own exception type.
1406 if(!LpSolverBase::isNaN(tmp.upperBound())) throw LogicError();
1407 else tmp.upperBound()=n;
1413 ///\relates LpSolverBase::Constr
1415 inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &n,
1416 const LpSolverBase::Constr&c)
1418 LpSolverBase::Constr tmp(c);
1419 ///\todo Create an own exception type.
1420 if(!LpSolverBase::isNaN(tmp.upperBound())) throw LogicError();
1421 else tmp.upperBound()=n;
1426 ///\relates LpSolverBase::Constr
1428 inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
1429 const LpSolverBase::Value &n)
1431 LpSolverBase::Constr tmp(c);
1432 ///\todo Create an own exception type.
1433 if(!LpSolverBase::isNaN(tmp.lowerBound())) throw LogicError();
1434 else tmp.lowerBound()=n;
1440 ///\relates LpSolverBase::DualExpr
1442 inline LpSolverBase::DualExpr operator+(const LpSolverBase::DualExpr &a,
1443 const LpSolverBase::DualExpr &b)
1445 LpSolverBase::DualExpr tmp(a);
1451 ///\relates LpSolverBase::DualExpr
1453 inline LpSolverBase::DualExpr operator-(const LpSolverBase::DualExpr &a,
1454 const LpSolverBase::DualExpr &b)
1456 LpSolverBase::DualExpr tmp(a);
1462 ///\relates LpSolverBase::DualExpr
1464 inline LpSolverBase::DualExpr operator*(const LpSolverBase::DualExpr &a,
1465 const LpSolverBase::Value &b)
1467 LpSolverBase::DualExpr tmp(a);
1474 ///\relates LpSolverBase::DualExpr
1476 inline LpSolverBase::DualExpr operator*(const LpSolverBase::Value &a,
1477 const LpSolverBase::DualExpr &b)
1479 LpSolverBase::DualExpr tmp(b);
1485 ///\relates LpSolverBase::DualExpr
1487 inline LpSolverBase::DualExpr operator/(const LpSolverBase::DualExpr &a,
1488 const LpSolverBase::Value &b)
1490 LpSolverBase::DualExpr tmp(a);
1498 #endif //LEMON_LP_BASE_H