An icc warning resolved.
2 * src/lemon/lp_base.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, 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.
35 ///Internal data structure to convert floating id's to fix one's
37 ///\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) {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) { 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
108 enum SolveExitStatus {
116 enum SolutionStatus {
117 ///Feasible solution has'n been found (but may exist).
119 ///\todo NOTFOUND might be a better name.
122 ///The problem has no feasible solution
124 ///Feasible solution found
126 ///Optimal solution exists and found
128 ///The cost function is unbounded
130 ///\todo Give a feasible solution and an infinite ray (and the
131 ///corresponding bases)
135 ///The floating point type used by the solver
136 typedef double Value;
137 ///The infinity constant
138 static const Value INF;
139 ///The not a number constant
140 static const Value NaN;
142 ///Refer to a column of the LP.
144 ///This type is used to refer to a column of the LP.
146 ///Its value remains valid and correct even after the addition or erase of
149 ///\todo Document what can one do with a Col (INVALID, comparing,
150 ///it is similar to Node/Edge)
154 friend class LpSolverBase;
156 typedef Value ExprValue;
157 typedef True LpSolverCol;
159 Col(const Invalid&) : id(-1) {}
160 bool operator<(Col c) const {return id<c.id;}
161 bool operator==(Col c) const {return id==c.id;}
162 bool operator!=(Col c) const {return id==c.id;}
165 ///Refer to a row of the LP.
167 ///This type is used to refer to a row of the LP.
169 ///Its value remains valid and correct even after the addition or erase of
172 ///\todo Document what can one do with a Row (INVALID, comparing,
173 ///it is similar to Node/Edge)
177 friend class LpSolverBase;
179 typedef Value ExprValue;
180 typedef True LpSolverRow;
182 Row(const Invalid&) : id(-1) {}
183 typedef True LpSolverRow;
184 bool operator<(Row c) const {return id<c.id;}
185 bool operator==(Row c) const {return id==c.id;}
186 bool operator!=(Row c) const {return id==c.id;}
189 ///Linear expression of variables and a constant component
191 ///This data structure strores a linear expression of the variables
192 ///(\ref Col "Col"s) and also has a constant component.
194 ///There are several ways to access and modify the contents of this
196 ///- Its it fully compatible with \c std::map<Col,double>, so for expamle
197 ///if \c e is an Expr and \c v and \c w are of type \ref Col then you can
198 ///read and modify the coefficients like
205 ///or you can also iterate through its elements.
208 ///for(LpSolverBase::Expr::iterator i=e.begin();i!=e.end();++i)
211 ///(This code computes the sum of all coefficients).
212 ///- Numbers (<tt>double</tt>'s)
213 ///and variables (\ref Col "Col"s) directly convert to an
214 ///\ref Expr and the usual linear operations are defined so
217 ///2*v-3.12*(v-w/2)+2
218 ///v*2.1+(3*v+(v*12+w+6)*3)/2
220 ///are valid expressions. The usual assignment operations are also defined.
223 ///e+=2*v-3.12*(v-w/2)+2;
227 ///- The constant member can be set and read by \ref constComp()
230 ///double c=e.constComp();
233 ///\note that \ref clear() not only sets all coefficients to 0 but also
234 ///clears the constant components.
235 class Expr : public std::map<Col,Value>
238 typedef LpSolverBase::Col Key;
239 typedef LpSolverBase::Value Value;
242 typedef std::map<Col,Value> Base;
246 typedef True IsLinExpression;
248 Expr() : Base(), const_comp(0) { }
250 Expr(const Key &v) : const_comp(0) {
251 Base::insert(std::make_pair(v, 1));
254 Expr(const Value &v) : const_comp(v) {}
256 void set(const Key &v,const Value &c) {
257 Base::insert(std::make_pair(v, c));
260 Value &constComp() { return const_comp; }
262 const Value &constComp() const { return const_comp; }
264 ///Removes the components with zero coefficient.
266 for (Base::iterator i=Base::begin(); i!=Base::end();) {
269 if ((*i).second==0) Base::erase(i);
274 ///Sets all coefficients and the constant component to 0.
281 Expr &operator+=(const Expr &e) {
282 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
283 (*this)[j->first]+=j->second;
284 ///\todo it might be speeded up using "hints"
285 const_comp+=e.const_comp;
289 Expr &operator-=(const Expr &e) {
290 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
291 (*this)[j->first]-=j->second;
292 const_comp-=e.const_comp;
296 Expr &operator*=(const Value &c) {
297 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
303 Expr &operator/=(const Value &c) {
304 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
312 //typedef LinConstr<Expr> Constr;
316 typedef LpSolverBase::Expr Expr;
317 typedef Expr::Key Key;
318 typedef Expr::Value Value;
320 static const Value INF;
321 static const Value NaN;
322 // static const Value INF=0;
323 // static const Value NaN=1;
330 Constr() : _expr(), _lb(NaN), _ub(NaN) {}
332 Constr(Value lb,const Expr &e,Value ub) :
333 _expr(e), _lb(lb), _ub(ub) {}
335 Constr(const Expr &e,Value ub) :
336 _expr(e), _lb(NaN), _ub(ub) {}
338 Constr(Value lb,const Expr &e) :
339 _expr(e), _lb(lb), _ub(NaN) {}
341 Constr(const Expr &e) :
342 _expr(e), _lb(NaN), _ub(NaN) {}
350 Expr &expr() { return _expr; }
352 const Expr &expr() const { return _expr; }
354 Value &lowerBound() { return _lb; }
356 const Value &lowerBound() const { return _lb; }
358 Value &upperBound() { return _ub; }
360 const Value &upperBound() const { return _ub; }
362 bool lowerBounded() const {
364 return isfinite(_lb);
367 bool upperBounded() const {
369 return isfinite(_ub);
378 //Abstract virtual functions
379 virtual int _addCol() = 0;
380 virtual int _addRow() = 0;
381 virtual void _setRowCoeffs(int i,
384 Value const * values ) = 0;
385 virtual void _setColCoeffs(int i,
388 Value const * values ) = 0;
389 virtual void _setColLowerBound(int i, Value value) = 0;
390 virtual void _setColUpperBound(int i, Value value) = 0;
391 virtual void _setRowLowerBound(int i, Value value) = 0;
392 virtual void _setRowUpperBound(int i, Value value) = 0;
393 virtual void _setObjCoeff(int i, Value obj_coef) = 0;
394 virtual SolveExitStatus _solve() = 0;
395 virtual Value _getPrimal(int i) = 0;
396 virtual Value _getPrimalValue() = 0;
397 virtual SolutionStatus _getPrimalStatus() = 0;
398 virtual void _setMax() = 0;
399 virtual void _setMin() = 0;
401 //Own protected stuff
403 //Constant component of the objective function
404 Value obj_const_comp;
408 ///\bug Unimplemented
414 LpSolverBase() : obj_const_comp(0) {}
417 virtual ~LpSolverBase() {}
419 ///\name Build up and modify of the LP
423 ///Add a new empty column (i.e a new variable) to the LP
424 Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
426 ///\brief Adds several new columns
427 ///(i.e a variables) at once
429 ///This magic function takes a container as its argument
430 ///and fills its elements
431 ///with new columns (i.e. variables)
433 ///- a standard STL compatible iterable container with
434 ///\ref Col as its \c values_type
437 ///std::vector<LpSolverBase::Col>
438 ///std::list<LpSolverBase::Col>
440 ///- a standard STL compatible iterable container with
441 ///\ref Col as its \c mapped_type
444 ///std::map<AnyStatus,LpSolverBase::Col>
446 ///- an iterable lemon \ref concept::WriteMap "write map" like
448 ///ListGraph::NodeMap<LpSolverBase::Col>
449 ///ListGraph::EdgeMap<LpSolverBase::Col>
451 ///\return The number of the created column.
452 ///\bug Iterable nodemap hasn't been implemented yet.
455 int addColSet(T &t) { return 0;}
458 typename enable_if<typename T::value_type::LpSolverCol,int>::type
459 addColSet(T &t,dummy<0> = 0) {
461 for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
465 typename enable_if<typename T::value_type::second_type::LpSolverCol,
467 addColSet(T &t,dummy<1> = 1) {
469 for(typename T::iterator i=t.begin();i!=t.end();++i) {
476 typename enable_if<typename T::ValueSet::value_type::LpSolverCol,
478 addColSet(T &t,dummy<2> = 2) {
479 ///\bug <tt>return addColSet(t.valueSet());</tt> should also work.
481 for(typename T::ValueSet::iterator i=t.valueSet().begin();
482 i!=t.valueSet().end();
492 ///Add a new empty row (i.e a new constaint) to the LP
494 ///This function adds a new empty row (i.e a new constaint) to the LP.
495 ///\return The created row
496 Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
498 ///Set a row (i.e a constaint) of the LP
500 ///\param r is the row to be modified
501 ///\param l is lower bound (-\ref INF means no bound)
502 ///\param e is a linear expression (see \ref Expr)
503 ///\param u is the upper bound (\ref INF means no bound)
504 ///\bug This is a temportary function. The interface will change to
506 void setRow(Row r, Value l,const Expr &e, Value u) {
507 std::vector<int> indices;
508 std::vector<Value> values;
509 indices.push_back(0);
511 for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i)
512 if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
513 indices.push_back(cols.floatingId((*i).first.id));
514 values.push_back((*i).second);
516 _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
517 &indices[0],&values[0]);
518 _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
519 _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
522 ///Set a row (i.e a constaint) of the LP
524 ///\param r is the row to be modified
525 ///\param c is a linear expression (see \ref Constr)
526 void setRow(Row r, const Constr &c) {
528 c.lowerBounded()?c.lowerBound():-INF,
530 c.upperBounded()?c.upperBound():INF);
533 ///Add a new row (i.e a new constaint) to the LP
535 ///\param l is the lower bound (-\ref INF means no bound)
536 ///\param e is a linear expression (see \ref Expr)
537 ///\param u is the upper bound (\ref INF means no bound)
538 ///\return The created row.
539 ///\bug This is a temportary function. The interface will change to
541 Row addRow(Value l,const Expr &e, Value u) {
547 ///Add a new row (i.e a new constaint) to the LP
549 ///\param c is a linear expression (see \ref Constr)
550 ///\return The created row.
551 Row addRow(const Constr &c) {
557 /// Set the lower bound of a column (i.e a variable)
559 /// The upper bound of a variable (column) has to be given by an
560 /// extended number of type Value, i.e. a finite number of type
561 /// Value or -\ref INF.
562 void colLowerBound(Col c, Value value) {
563 _setColLowerBound(cols.floatingId(c.id),value);
565 /// Set the upper bound of a column (i.e a variable)
567 /// The upper bound of a variable (column) has to be given by an
568 /// extended number of type Value, i.e. a finite number of type
569 /// Value or \ref INF.
570 void colUpperBound(Col c, Value value) {
571 _setColUpperBound(cols.floatingId(c.id),value);
573 /// Set the lower and the upper bounds of a column (i.e a variable)
575 /// The lower and the upper bounds of
576 /// a variable (column) have to be given by an
577 /// extended number of type Value, i.e. a finite number of type
578 /// Value, -\ref INF or \ref INF.
579 void colBounds(Col c, Value lower, Value upper) {
580 _setColLowerBound(cols.floatingId(c.id),lower);
581 _setColUpperBound(cols.floatingId(c.id),upper);
584 /// Set the lower bound of a row (i.e a constraint)
586 /// The lower bound of a linear expression (row) has to be given by an
587 /// extended number of type Value, i.e. a finite number of type
588 /// Value or -\ref INF.
589 void rowLowerBound(Row r, Value value) {
590 _setRowLowerBound(rows.floatingId(r.id),value);
592 /// Set the upper bound of a row (i.e a constraint)
594 /// The upper bound of a linear expression (row) has to be given by an
595 /// extended number of type Value, i.e. a finite number of type
596 /// Value or \ref INF.
597 void rowUpperBound(Row r, Value value) {
598 _setRowUpperBound(rows.floatingId(r.id),value);
600 /// Set the lower and the upper bounds of a row (i.e a variable)
602 /// The lower and the upper bounds of
603 /// a constraint (row) have to be given by an
604 /// extended number of type Value, i.e. a finite number of type
605 /// Value, -\ref INF or \ref INF.
606 void rowBounds(Row c, Value lower, Value upper) {
607 _setRowLowerBound(rows.floatingId(c.id),lower);
608 _setRowUpperBound(rows.floatingId(c.id),upper);
611 ///Set an element of the objective function
612 void objCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
613 ///Set the objective function
615 ///\param e is a linear expression of type \ref Expr.
616 ///\bug The previous objective function is not cleared!
617 void setObj(Expr e) {
619 for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
620 objCoeff((*i).first,(*i).second);
621 obj_const_comp=e.constComp();
625 void max() { _setMax(); }
627 void min() { _setMin(); }
633 ///\name Solve the LP
638 SolveExitStatus solve() { return _solve(); }
642 ///\name Obtain the solution
647 SolutionStatus primalStatus() {
648 return _getPrimalStatus();
652 Value primal(Col c) { return _getPrimal(cols.floatingId(c.id)); }
657 ///- \ref INF or -\ref INF means either infeasibility or unboundedness
658 /// of the primal problem, depending on whether we minimize or maximize.
659 ///- \ref NAN if no primal solution is found.
660 ///- The (finite) objective value if an optimal solution is found.
661 Value primalValue() { return _getPrimalValue()+obj_const_comp;}
668 ///\relates LpSolverBase::Expr
670 inline LpSolverBase::Expr operator+(const LpSolverBase::Expr &a,
671 const LpSolverBase::Expr &b)
673 LpSolverBase::Expr tmp(a);
674 tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?
679 ///\relates LpSolverBase::Expr
681 inline LpSolverBase::Expr operator-(const LpSolverBase::Expr &a,
682 const LpSolverBase::Expr &b)
684 LpSolverBase::Expr tmp(a);
685 tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?
690 ///\relates LpSolverBase::Expr
692 inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
693 const LpSolverBase::Value &b)
695 LpSolverBase::Expr tmp(a);
696 tmp*=b; ///\todo Don't STL have some special 'merge' algorithm?
702 ///\relates LpSolverBase::Expr
704 inline LpSolverBase::Expr operator*(const LpSolverBase::Value &a,
705 const LpSolverBase::Expr &b)
707 LpSolverBase::Expr tmp(b);
708 tmp*=a; ///\todo Don't STL have some special 'merge' algorithm?
713 ///\relates LpSolverBase::Expr
715 inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
716 const LpSolverBase::Value &b)
718 LpSolverBase::Expr tmp(a);
719 tmp/=b; ///\todo Don't STL have some special 'merge' algorithm?
725 ///\relates LpSolverBase::Constr
727 inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
728 const LpSolverBase::Expr &f)
730 return LpSolverBase::Constr(-LpSolverBase::INF,e-f,0);
735 ///\relates LpSolverBase::Constr
737 inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &e,
738 const LpSolverBase::Expr &f)
740 return LpSolverBase::Constr(e,f);
745 ///\relates LpSolverBase::Constr
747 inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
748 const LpSolverBase::Value &f)
750 return LpSolverBase::Constr(e,f);
755 ///\relates LpSolverBase::Constr
757 inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
758 const LpSolverBase::Expr &f)
760 return LpSolverBase::Constr(-LpSolverBase::INF,f-e,0);
766 ///\relates LpSolverBase::Constr
768 inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &e,
769 const LpSolverBase::Expr &f)
771 return LpSolverBase::Constr(f,e);
777 ///\relates LpSolverBase::Constr
779 inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
780 const LpSolverBase::Value &f)
782 return LpSolverBase::Constr(f,e);
787 ///\relates LpSolverBase::Constr
789 inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
790 const LpSolverBase::Expr &f)
792 return LpSolverBase::Constr(0,e-f,0);
797 ///\relates LpSolverBase::Constr
799 inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &n,
800 const LpSolverBase::Constr&c)
802 LpSolverBase::Constr tmp(c);
803 ///\todo Create an own exception type.
804 if(!isnan(tmp.lowerBound())) throw LogicError();
805 else tmp.lowerBound()=n;
810 ///\relates LpSolverBase::Constr
812 inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
813 const LpSolverBase::Value &n)
815 LpSolverBase::Constr tmp(c);
816 ///\todo Create an own exception type.
817 if(!isnan(tmp.upperBound())) throw LogicError();
818 else tmp.upperBound()=n;
824 ///\relates LpSolverBase::Constr
826 inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &n,
827 const LpSolverBase::Constr&c)
829 LpSolverBase::Constr tmp(c);
830 ///\todo Create an own exception type.
831 if(!isnan(tmp.upperBound())) throw LogicError();
832 else tmp.upperBound()=n;
837 ///\relates LpSolverBase::Constr
839 inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
840 const LpSolverBase::Value &n)
842 LpSolverBase::Constr tmp(c);
843 ///\todo Create an own exception type.
844 if(!isnan(tmp.lowerBound())) throw LogicError();
845 else tmp.lowerBound()=n;
852 #endif //LEMON_LP_BASE_H