Demo about descriptor map.
2 * lemon/lp_base.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 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>
29 //#include"lin_expr.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.
41 std::vector<int> index;
42 std::vector<int> cross;
45 _FixId() : first_free(-1) {};
46 ///Convert a floating id to a fix one
48 ///\param n is a floating id
49 ///\return the corresponding fix id
50 int fixId(int n) const {return cross[n];}
51 ///Convert a fix id to a floating one
53 ///\param n is a fix id
54 ///\return the corresponding floating id
55 int floatingId(int n) const { return index[n];}
56 ///Add a new floating id.
58 ///\param n is a floating id
59 ///\return the fix id of the new value
60 ///\todo Multiple additions should also be handled.
63 if(n>=int(cross.size())) {
66 cross[n]=index.size();
71 int next=index[first_free];
77 ///\todo Create an own exception type.
78 else throw LogicError(); //floatingId-s must form a continuous range;
82 ///\param n is a fix id
89 for(int i=fl+1;i<int(cross.size());++i) {
95 ///An upper bound on the largest fix id.
97 ///\todo Do we need this?
99 std::size_t maxFixId() { return cross.size()-1; }
103 ///Common base class for LP solvers
105 ///\todo Much more docs
106 ///\ingroup gen_opt_group
111 ///Possible outcomes of an LP solving procedure
112 enum SolveExitStatus {
113 ///This means that the problem has been successfully solved: either
114 ///an optimal solution has been found or infeasibility/unboundedness
117 ///Any other case (including the case when some user specified limit has been exceeded)
122 enum SolutionStatus {
123 ///Feasible solution has'n been found (but may exist).
125 ///\todo NOTFOUND might be a better name.
128 ///The problem has no feasible solution
130 ///Feasible solution found
132 ///Optimal solution exists and found
134 ///The cost function is unbounded
136 ///\todo Give a feasible solution and an infinite ray (and the
137 ///corresponding bases)
141 ///\e The type of the investigated LP problem
143 ///Primal-dual feasible
144 PRIMAL_DUAL_FEASIBLE = 0,
145 ///Primal feasible dual infeasible
146 PRIMAL_FEASIBLE_DUAL_INFEASIBLE = 1,
147 ///Primal infeasible dual feasible
148 PRIMAL_INFEASIBLE_DUAL_FEASIBLE = 2,
149 ///Primal-dual infeasible
150 PRIMAL_DUAL_INFEASIBLE = 3,
151 ///Could not determine so far
155 ///The floating point type used by the solver
156 typedef double Value;
157 ///The infinity constant
158 static const Value INF;
159 ///The not a number constant
160 static const Value NaN;
162 ///Refer to a column of the LP.
164 ///This type is used to refer to a column of the LP.
166 ///Its value remains valid and correct even after the addition or erase of
169 ///\todo Document what can one do with a Col (INVALID, comparing,
170 ///it is similar to Node/Edge)
174 friend class LpSolverBase;
176 typedef Value ExprValue;
177 typedef True LpSolverCol;
179 Col(const Invalid&) : id(-1) {}
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;}
209 ///Linear expression of variables and a constant component
211 ///This data structure strores a linear expression of the variables
212 ///(\ref Col "Col"s) and also has a constant component.
214 ///There are several ways to access and modify the contents of this
216 ///- Its it fully compatible with \c std::map<Col,double>, so for expamle
217 ///if \c e is an Expr and \c v and \c w are of type \ref Col, then you can
218 ///read and modify the coefficients like
225 ///or you can also iterate through its elements.
228 ///for(LpSolverBase::Expr::iterator i=e.begin();i!=e.end();++i)
231 ///(This code computes the sum of all coefficients).
232 ///- Numbers (<tt>double</tt>'s)
233 ///and variables (\ref Col "Col"s) directly convert to an
234 ///\ref Expr and the usual linear operations are defined so
237 ///2*v-3.12*(v-w/2)+2
238 ///v*2.1+(3*v+(v*12+w+6)*3)/2
240 ///are valid \ref Expr "Expr"essions.
241 ///The usual assignment operations are also defined.
244 ///e+=2*v-3.12*(v-w/2)+2;
248 ///- The constant member can be set and read by \ref constComp()
251 ///double c=e.constComp();
254 ///\note \ref clear() not only sets all coefficients to 0 but also
255 ///clears the constant components.
259 class Expr : public std::map<Col,Value>
262 typedef LpSolverBase::Col Key;
263 typedef LpSolverBase::Value Value;
266 typedef std::map<Col,Value> Base;
270 typedef True IsLinExpression;
272 Expr() : Base(), const_comp(0) { }
274 Expr(const Key &v) : const_comp(0) {
275 Base::insert(std::make_pair(v, 1));
278 Expr(const Value &v) : const_comp(v) {}
280 void set(const Key &v,const Value &c) {
281 Base::insert(std::make_pair(v, c));
284 Value &constComp() { return const_comp; }
286 const Value &constComp() const { return const_comp; }
288 ///Removes the components with zero coefficient.
290 for (Base::iterator i=Base::begin(); i!=Base::end();) {
293 if ((*i).second==0) Base::erase(i);
298 ///Sets all coefficients and the constant component to 0.
305 Expr &operator+=(const Expr &e) {
306 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
307 (*this)[j->first]+=j->second;
308 ///\todo it might be speeded up using "hints"
309 const_comp+=e.const_comp;
313 Expr &operator-=(const Expr &e) {
314 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
315 (*this)[j->first]-=j->second;
316 const_comp-=e.const_comp;
320 Expr &operator*=(const Value &c) {
321 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
327 Expr &operator/=(const Value &c) {
328 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
337 ///This data stucture represents a linear constraint in the LP.
338 ///Basically it is a linear expression with a lower or an upper bound
339 ///(or both). These parts of the constraint can be obtained by the member
340 ///functions \ref expr(), \ref lowerBound() and \ref upperBound(),
342 ///There are two ways to construct a constraint.
343 ///- You can set the linear expression and the bounds directly
344 /// by the functions above.
345 ///- The operators <tt>\<=</tt>, <tt>==</tt> and <tt>\>=</tt>
346 /// are defined between expressions, or even between constraints whenever
347 /// it makes sense. Therefore if \c e and \c f are linear expressions and
348 /// \c s and \c t are numbers, then the followings are valid expressions
349 /// and thus they can be used directly e.g. in \ref addRow() whenever
357 ///\warning The validity of a constraint is checked only at run time, so
358 ///e.g. \ref addRow(<tt>x[1]\<=x[2]<=5</tt>) will compile, but will throw a
359 ///\ref LogicError exception.
363 typedef LpSolverBase::Expr Expr;
364 typedef Expr::Key Key;
365 typedef Expr::Value Value;
367 // static const Value INF;
368 // static const Value NaN;
375 Constr() : _expr(), _lb(NaN), _ub(NaN) {}
377 Constr(Value lb,const Expr &e,Value ub) :
378 _expr(e), _lb(lb), _ub(ub) {}
380 Constr(const Expr &e,Value ub) :
381 _expr(e), _lb(NaN), _ub(ub) {}
383 Constr(Value lb,const Expr &e) :
384 _expr(e), _lb(lb), _ub(NaN) {}
386 Constr(const Expr &e) :
387 _expr(e), _lb(NaN), _ub(NaN) {}
395 ///Reference to the linear expression
396 Expr &expr() { return _expr; }
397 ///Cont reference to the linear expression
398 const Expr &expr() const { return _expr; }
399 ///Reference to the lower bound.
402 ///- \ref INF "INF": the constraint is lower unbounded.
403 ///- \ref NaN "NaN": lower bound has not been set.
404 ///- finite number: the lower bound
405 Value &lowerBound() { return _lb; }
406 ///The const version of \ref lowerBound()
407 const Value &lowerBound() const { return _lb; }
408 ///Reference to the upper bound.
411 ///- \ref INF "INF": the constraint is upper unbounded.
412 ///- \ref NaN "NaN": upper bound has not been set.
413 ///- finite number: the upper bound
414 Value &upperBound() { return _ub; }
415 ///The const version of \ref upperBound()
416 const Value &upperBound() const { return _ub; }
417 ///Is the constraint lower bounded?
418 bool lowerBounded() const {
422 ///Is the constraint upper bounded?
423 bool upperBounded() const {
429 ///Linear expression of rows
431 ///This data structure represents a column of the matrix,
432 ///thas is it strores a linear expression of the dual variables
433 ///(\ref Row "Row"s).
435 ///There are several ways to access and modify the contents of this
437 ///- Its it fully compatible with \c std::map<Row,double>, so for expamle
438 ///if \c e is an DualExpr and \c v
439 ///and \c w are of type \ref Row, then you can
440 ///read and modify the coefficients like
447 ///or you can also iterate through its elements.
450 ///for(LpSolverBase::DualExpr::iterator i=e.begin();i!=e.end();++i)
453 ///(This code computes the sum of all coefficients).
454 ///- Numbers (<tt>double</tt>'s)
455 ///and variables (\ref Row "Row"s) directly convert to an
456 ///\ref DualExpr and the usual linear operations are defined so
460 ///v*2.1+(3*v+(v*12+w)*3)/2
462 ///are valid \ref DualExpr "DualExpr"essions.
463 ///The usual assignment operations are also defined.
466 ///e+=2*v-3.12*(v-w/2);
473 class DualExpr : public std::map<Row,Value>
476 typedef LpSolverBase::Row Key;
477 typedef LpSolverBase::Value Value;
480 typedef std::map<Row,Value> Base;
483 typedef True IsLinExpression;
485 DualExpr() : Base() { }
487 DualExpr(const Key &v) {
488 Base::insert(std::make_pair(v, 1));
491 void set(const Key &v,const Value &c) {
492 Base::insert(std::make_pair(v, c));
495 ///Removes the components with zero coefficient.
497 for (Base::iterator i=Base::begin(); i!=Base::end();) {
500 if ((*i).second==0) Base::erase(i);
505 ///Sets all coefficients to 0.
511 DualExpr &operator+=(const DualExpr &e) {
512 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
513 (*this)[j->first]+=j->second;
514 ///\todo it might be speeded up using "hints"
518 DualExpr &operator-=(const DualExpr &e) {
519 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
520 (*this)[j->first]-=j->second;
524 DualExpr &operator*=(const Value &c) {
525 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
530 DualExpr &operator/=(const Value &c) {
531 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
542 //Abstract virtual functions
543 virtual LpSolverBase &_newLp() = 0;
544 virtual LpSolverBase &_copyLp(){
545 ///\todo This should be implemented here, too, when we have problem retrieving routines. It can be overriden.
548 LpSolverBase & newlp(_newLp());
550 //return *(LpSolverBase*)0;
553 virtual int _addCol() = 0;
554 virtual int _addRow() = 0;
555 virtual void _eraseCol(int col) = 0;
556 virtual void _eraseRow(int row) = 0;
557 virtual void _setRowCoeffs(int i,
560 Value const * values ) = 0;
561 virtual void _setColCoeffs(int i,
564 Value const * values ) = 0;
565 virtual void _setCoeff(int row, int col, Value value) = 0;
566 virtual void _setColLowerBound(int i, Value value) = 0;
567 virtual void _setColUpperBound(int i, Value value) = 0;
568 // virtual void _setRowLowerBound(int i, Value value) = 0;
569 // virtual void _setRowUpperBound(int i, Value value) = 0;
570 virtual void _setRowBounds(int i, Value lower, Value upper) = 0;
571 virtual void _setObjCoeff(int i, Value obj_coef) = 0;
572 virtual void _clearObj()=0;
573 // virtual void _setObj(int length,
574 // int const * indices,
575 // Value const * values ) = 0;
576 virtual SolveExitStatus _solve() = 0;
577 virtual Value _getPrimal(int i) = 0;
578 virtual Value _getPrimalValue() = 0;
579 virtual SolutionStatus _getPrimalStatus() = 0;
580 virtual SolutionStatus _getDualStatus() = 0;
581 ///\todo This could be implemented here, too, using _getPrimalStatus() and
583 virtual ProblemTypes _getProblemType() = 0;
585 virtual void _setMax() = 0;
586 virtual void _setMin() = 0;
588 //Own protected stuff
590 //Constant component of the objective function
591 Value obj_const_comp;
599 LpSolverBase() : obj_const_comp(0) {}
602 virtual ~LpSolverBase() {}
604 ///Creates a new LP problem
605 LpSolverBase &newLp() {return _newLp();}
606 ///Makes a copy of the LP problem
607 LpSolverBase ©Lp() {return _copyLp();}
609 ///\name Build up and modify of the LP
613 ///Add a new empty column (i.e a new variable) to the LP
614 Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
616 ///\brief Adds several new columns
617 ///(i.e a variables) at once
619 ///This magic function takes a container as its argument
620 ///and fills its elements
621 ///with new columns (i.e. variables)
623 ///- a standard STL compatible iterable container with
624 ///\ref Col as its \c values_type
627 ///std::vector<LpSolverBase::Col>
628 ///std::list<LpSolverBase::Col>
630 ///- a standard STL compatible iterable container with
631 ///\ref Col as its \c mapped_type
634 ///std::map<AnyType,LpSolverBase::Col>
636 ///- an iterable lemon \ref concept::WriteMap "write map" like
638 ///ListGraph::NodeMap<LpSolverBase::Col>
639 ///ListGraph::EdgeMap<LpSolverBase::Col>
641 ///\return The number of the created column.
644 int addColSet(T &t) { return 0;}
647 typename enable_if<typename T::value_type::LpSolverCol,int>::type
648 addColSet(T &t,dummy<0> = 0) {
650 for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
654 typename enable_if<typename T::value_type::second_type::LpSolverCol,
656 addColSet(T &t,dummy<1> = 1) {
658 for(typename T::iterator i=t.begin();i!=t.end();++i) {
665 typename enable_if<typename T::ValueSet::value_type::LpSolverCol,
667 addColSet(T &t,dummy<2> = 2) {
668 ///\bug <tt>return addColSet(t.valueSet());</tt> should also work.
670 for(typename T::ValueSet::iterator i=t.valueSet().begin();
671 i!=t.valueSet().end();
681 ///Set a column (i.e a dual constraint) of the LP
683 ///\param c is the column to be modified
684 ///\param e is a dual linear expression (see \ref DualExpr)
685 ///\bug This is a temporary function. The interface will change to
687 void setCol(Col c,const DualExpr &e) {
688 std::vector<int> indices;
689 std::vector<Value> values;
690 indices.push_back(0);
692 for(DualExpr::const_iterator i=e.begin(); i!=e.end(); ++i)
693 if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
694 indices.push_back(cols.floatingId((*i).first.id));
695 values.push_back((*i).second);
697 _setColCoeffs(cols.floatingId(c.id),indices.size()-1,
698 &indices[0],&values[0]);
701 ///Add a new column to the LP
703 ///\param e is a dual linear expression (see \ref DualExpr)
704 ///\param obj is the corresponding component of the objective
705 ///function. It is 0 by default.
706 ///\return The created column.
707 ///\bug This is a temportary function. The interface will change to
709 Col addCol(const DualExpr &e, Value obj=0) {
716 ///Add a new empty row (i.e a new constraint) to the LP
718 ///This function adds a new empty row (i.e a new constraint) to the LP.
719 ///\return The created row
720 Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
722 ///\brief Add several new rows
723 ///(i.e a constraints) at once
725 ///This magic function takes a container as its argument
726 ///and fills its elements
727 ///with new row (i.e. variables)
729 ///- a standard STL compatible iterable container with
730 ///\ref Row as its \c values_type
733 ///std::vector<LpSolverBase::Row>
734 ///std::list<LpSolverBase::Row>
736 ///- a standard STL compatible iterable container with
737 ///\ref Row as its \c mapped_type
740 ///std::map<AnyType,LpSolverBase::Row>
742 ///- an iterable lemon \ref concept::WriteMap "write map" like
744 ///ListGraph::NodeMap<LpSolverBase::Row>
745 ///ListGraph::EdgeMap<LpSolverBase::Row>
747 ///\return The number of rows created.
750 int addRowSet(T &t) { return 0;}
753 typename enable_if<typename T::value_type::LpSolverRow,int>::type
754 addRowSet(T &t,dummy<0> = 0) {
756 for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addRow();s++;}
760 typename enable_if<typename T::value_type::second_type::LpSolverRow,
762 addRowSet(T &t,dummy<1> = 1) {
764 for(typename T::iterator i=t.begin();i!=t.end();++i) {
771 typename enable_if<typename T::ValueSet::value_type::LpSolverRow,
773 addRowSet(T &t,dummy<2> = 2) {
774 ///\bug <tt>return addRowSet(t.valueSet());</tt> should also work.
776 for(typename T::ValueSet::iterator i=t.valueSet().begin();
777 i!=t.valueSet().end();
787 ///Set a row (i.e a constraint) of the LP
789 ///\param r is the row to be modified
790 ///\param l is lower bound (-\ref INF means no bound)
791 ///\param e is a linear expression (see \ref Expr)
792 ///\param u is the upper bound (\ref INF means no bound)
793 ///\bug This is a temportary function. The interface will change to
795 ///\todo Option to control whether a constraint with a single variable is
797 void setRow(Row r, Value l,const Expr &e, Value u) {
798 std::vector<int> indices;
799 std::vector<Value> values;
800 indices.push_back(0);
802 for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i)
803 if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
804 indices.push_back(cols.floatingId((*i).first.id));
805 values.push_back((*i).second);
807 _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
808 &indices[0],&values[0]);
809 // _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
810 // _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
811 _setRowBounds(rows.floatingId(r.id),l-e.constComp(),u-e.constComp());
814 ///Set a row (i.e a constraint) of the LP
816 ///\param r is the row to be modified
817 ///\param c is a linear expression (see \ref Constr)
818 void setRow(Row r, const Constr &c) {
820 c.lowerBounded()?c.lowerBound():-INF,
822 c.upperBounded()?c.upperBound():INF);
825 ///Add a new row (i.e a new constraint) to the LP
827 ///\param l is the lower bound (-\ref INF means no bound)
828 ///\param e is a linear expression (see \ref Expr)
829 ///\param u is the upper bound (\ref INF means no bound)
830 ///\return The created row.
831 ///\bug This is a temportary function. The interface will change to
833 Row addRow(Value l,const Expr &e, Value u) {
839 ///Add a new row (i.e a new constraint) to the LP
841 ///\param c is a linear expression (see \ref Constr)
842 ///\return The created row.
843 Row addRow(const Constr &c) {
848 ///Erase a coloumn (i.e a variable) from the LP
850 ///\param c is the coloumn to be deleted
851 ///\todo Please check this
852 void eraseCol(Col c) {
853 _eraseCol(cols.floatingId(c.id));
856 ///Erase a row (i.e a constraint) from the LP
858 ///\param r is the row to be deleted
859 ///\todo Please check this
860 void eraseRow(Row r) {
861 _eraseRow(rows.floatingId(r.id));
865 ///Set an element of the coefficient matrix of the LP
867 ///\param r is the row of the element to be modified
868 ///\param c is the coloumn of the element to be modified
869 ///\param val is the new value of the coefficient
870 void setCoeff(Row r, Col c, Value val){
871 _setCoeff(rows.floatingId(r.id),cols.floatingId(c.id), val);
874 /// Set the lower bound of a column (i.e a variable)
876 /// The upper bound of a variable (column) has to be given by an
877 /// extended number of type Value, i.e. a finite number of type
878 /// Value or -\ref INF.
879 void colLowerBound(Col c, Value value) {
880 _setColLowerBound(cols.floatingId(c.id),value);
882 /// Set the upper bound of a column (i.e a variable)
884 /// The upper bound of a variable (column) has to be given by an
885 /// extended number of type Value, i.e. a finite number of type
886 /// Value or \ref INF.
887 void colUpperBound(Col c, Value value) {
888 _setColUpperBound(cols.floatingId(c.id),value);
890 /// Set the lower and the upper bounds of a column (i.e a variable)
892 /// The lower and the upper bounds of
893 /// a variable (column) have to be given by an
894 /// extended number of type Value, i.e. a finite number of type
895 /// Value, -\ref INF or \ref INF.
896 void colBounds(Col c, Value lower, Value upper) {
897 _setColLowerBound(cols.floatingId(c.id),lower);
898 _setColUpperBound(cols.floatingId(c.id),upper);
901 // /// Set the lower bound of a row (i.e a constraint)
903 // /// The lower bound of a linear expression (row) has to be given by an
904 // /// extended number of type Value, i.e. a finite number of type
905 // /// Value or -\ref INF.
906 // void rowLowerBound(Row r, Value value) {
907 // _setRowLowerBound(rows.floatingId(r.id),value);
909 // /// Set the upper bound of a row (i.e a constraint)
911 // /// The upper bound of a linear expression (row) has to be given by an
912 // /// extended number of type Value, i.e. a finite number of type
913 // /// Value or \ref INF.
914 // void rowUpperBound(Row r, Value value) {
915 // _setRowUpperBound(rows.floatingId(r.id),value);
918 /// Set the lower and the upper bounds of a row (i.e a constraint)
920 /// The lower and the upper bounds of
921 /// a constraint (row) have to be given by an
922 /// extended number of type Value, i.e. a finite number of type
923 /// Value, -\ref INF or \ref INF.
924 void rowBounds(Row c, Value lower, Value upper) {
925 _setRowBounds(rows.floatingId(c.id),lower, upper);
926 // _setRowUpperBound(rows.floatingId(c.id),upper);
929 ///Set an element of the objective function
930 void objCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
931 ///Set the objective function
933 ///\param e is a linear expression of type \ref Expr.
934 ///\bug The previous objective function is not cleared!
935 void setObj(Expr e) {
937 for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
938 objCoeff((*i).first,(*i).second);
939 obj_const_comp=e.constComp();
943 void max() { _setMax(); }
945 void min() { _setMin(); }
951 ///\name Solve the LP
955 ///\e Solve the LP problem at hand
957 ///\return The result of the optimization procedure. Possible values and their meanings can be found in the documentation of \ref SolveExitStatus.
959 ///\todo Which method is used to solve the problem
960 SolveExitStatus solve() { return _solve(); }
964 ///\name Obtain the solution
968 /// The status of the primal problem (the original LP problem)
969 SolutionStatus primalStatus() {
970 return _getPrimalStatus();
973 /// The status of the dual (of the original LP) problem
974 SolutionStatus dualStatus() {
975 return _getDualStatus();
978 ///The type of the original LP problem
979 ProblemTypes problemType() {
980 return _getProblemType();
984 Value primal(Col c) { return _getPrimal(cols.floatingId(c.id)); }
989 ///- \ref INF or -\ref INF means either infeasibility or unboundedness
990 /// of the primal problem, depending on whether we minimize or maximize.
991 ///- \ref NaN if no primal solution is found.
992 ///- The (finite) objective value if an optimal solution is found.
993 Value primalValue() { return _getPrimalValue()+obj_const_comp;}
1000 ///\relates LpSolverBase::Expr
1002 inline LpSolverBase::Expr operator+(const LpSolverBase::Expr &a,
1003 const LpSolverBase::Expr &b)
1005 LpSolverBase::Expr tmp(a);
1006 tmp+=b; ///\todo Doesn't STL have some special 'merge' algorithm?
1011 ///\relates LpSolverBase::Expr
1013 inline LpSolverBase::Expr operator-(const LpSolverBase::Expr &a,
1014 const LpSolverBase::Expr &b)
1016 LpSolverBase::Expr tmp(a);
1017 tmp-=b; ///\todo Doesn't STL have some special 'merge' algorithm?
1022 ///\relates LpSolverBase::Expr
1024 inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
1025 const LpSolverBase::Value &b)
1027 LpSolverBase::Expr tmp(a);
1028 tmp*=b; ///\todo Doesn't STL have some special 'merge' algorithm?
1034 ///\relates LpSolverBase::Expr
1036 inline LpSolverBase::Expr operator*(const LpSolverBase::Value &a,
1037 const LpSolverBase::Expr &b)
1039 LpSolverBase::Expr tmp(b);
1040 tmp*=a; ///\todo Doesn't STL have some special 'merge' algorithm?
1045 ///\relates LpSolverBase::Expr
1047 inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
1048 const LpSolverBase::Value &b)
1050 LpSolverBase::Expr tmp(a);
1051 tmp/=b; ///\todo Doesn't STL have some special 'merge' algorithm?
1057 ///\relates LpSolverBase::Constr
1059 inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
1060 const LpSolverBase::Expr &f)
1062 return LpSolverBase::Constr(-LpSolverBase::INF,e-f,0);
1067 ///\relates LpSolverBase::Constr
1069 inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &e,
1070 const LpSolverBase::Expr &f)
1072 return LpSolverBase::Constr(e,f);
1077 ///\relates LpSolverBase::Constr
1079 inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
1080 const LpSolverBase::Value &f)
1082 return LpSolverBase::Constr(e,f);
1087 ///\relates LpSolverBase::Constr
1089 inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
1090 const LpSolverBase::Expr &f)
1092 return LpSolverBase::Constr(-LpSolverBase::INF,f-e,0);
1098 ///\relates LpSolverBase::Constr
1100 inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &e,
1101 const LpSolverBase::Expr &f)
1103 return LpSolverBase::Constr(f,e);
1109 ///\relates LpSolverBase::Constr
1111 inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
1112 const LpSolverBase::Value &f)
1114 return LpSolverBase::Constr(f,e);
1119 ///\relates LpSolverBase::Constr
1121 inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
1122 const LpSolverBase::Expr &f)
1124 return LpSolverBase::Constr(0,e-f,0);
1129 ///\relates LpSolverBase::Constr
1131 inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &n,
1132 const LpSolverBase::Constr&c)
1134 LpSolverBase::Constr tmp(c);
1135 ///\todo Create an own exception type.
1136 if(!isnan(tmp.lowerBound())) throw LogicError();
1137 else tmp.lowerBound()=n;
1142 ///\relates LpSolverBase::Constr
1144 inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
1145 const LpSolverBase::Value &n)
1147 LpSolverBase::Constr tmp(c);
1148 ///\todo Create an own exception type.
1149 if(!isnan(tmp.upperBound())) throw LogicError();
1150 else tmp.upperBound()=n;
1156 ///\relates LpSolverBase::Constr
1158 inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &n,
1159 const LpSolverBase::Constr&c)
1161 LpSolverBase::Constr tmp(c);
1162 ///\todo Create an own exception type.
1163 if(!isnan(tmp.upperBound())) throw LogicError();
1164 else tmp.upperBound()=n;
1169 ///\relates LpSolverBase::Constr
1171 inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
1172 const LpSolverBase::Value &n)
1174 LpSolverBase::Constr tmp(c);
1175 ///\todo Create an own exception type.
1176 if(!isnan(tmp.lowerBound())) throw LogicError();
1177 else tmp.lowerBound()=n;
1183 ///\relates LpSolverBase::DualExpr
1185 inline LpSolverBase::DualExpr operator+(const LpSolverBase::DualExpr &a,
1186 const LpSolverBase::DualExpr &b)
1188 LpSolverBase::DualExpr tmp(a);
1189 tmp+=b; ///\todo Doesn't STL have some special 'merge' algorithm?
1194 ///\relates LpSolverBase::DualExpr
1196 inline LpSolverBase::DualExpr operator-(const LpSolverBase::DualExpr &a,
1197 const LpSolverBase::DualExpr &b)
1199 LpSolverBase::DualExpr tmp(a);
1200 tmp-=b; ///\todo Doesn't STL have some special 'merge' algorithm?
1205 ///\relates LpSolverBase::DualExpr
1207 inline LpSolverBase::DualExpr operator*(const LpSolverBase::DualExpr &a,
1208 const LpSolverBase::Value &b)
1210 LpSolverBase::DualExpr tmp(a);
1211 tmp*=b; ///\todo Doesn't STL have some special 'merge' algorithm?
1217 ///\relates LpSolverBase::DualExpr
1219 inline LpSolverBase::DualExpr operator*(const LpSolverBase::Value &a,
1220 const LpSolverBase::DualExpr &b)
1222 LpSolverBase::DualExpr tmp(b);
1223 tmp*=a; ///\todo Doesn't STL have some special 'merge' algorithm?
1228 ///\relates LpSolverBase::DualExpr
1230 inline LpSolverBase::DualExpr operator/(const LpSolverBase::DualExpr &a,
1231 const LpSolverBase::Value &b)
1233 LpSolverBase::DualExpr tmp(a);
1234 tmp/=b; ///\todo Doesn't STL have some special 'merge' algorithm?
1241 #endif //LEMON_LP_BASE_H