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 SolutionStatus {
127 ///The floating point type used by the solver
128 typedef double Value;
129 ///The infinity constant
130 static const Value INF;
131 ///The not a number constant
132 static const Value NaN;
134 ///Refer to a column of the LP.
136 ///This type is used to refer to a column of the LP.
138 ///Its value remains valid and correct even after the addition or erase of
141 ///\todo Document what can one do with a Col (INVALID, comparing,
142 ///it is similar to Node/Edge)
146 friend class LpSolverBase;
148 typedef Value ExprValue;
149 typedef True LpSolverCol;
151 Col(const Invalid&) : id(-1) {}
152 bool operator<(Col c) const {return id<c.id;}
153 bool operator==(Col c) const {return id==c.id;}
154 bool operator!=(Col c) const {return id==c.id;}
157 ///Refer to a row of the LP.
159 ///This type is used to refer to a row of the LP.
161 ///Its value remains valid and correct even after the addition or erase of
164 ///\todo Document what can one do with a Row (INVALID, comparing,
165 ///it is similar to Node/Edge)
169 friend class LpSolverBase;
171 typedef Value ExprValue;
172 typedef True LpSolverRow;
174 Row(const Invalid&) : id(-1) {}
175 typedef True LpSolverRow;
176 bool operator<(Row c) const {return id<c.id;}
177 bool operator==(Row c) const {return id==c.id;}
178 bool operator!=(Row c) const {return id==c.id;}
181 ///Linear expression of variables and a constant component
183 ///This data structure strores a linear expression of the variables
184 ///(\ref Col "Col"s) and also has a constant component.
186 ///There are several ways to access and modify the contents of this
188 ///- Its it fully compatible with \c std::map<Col,double>, so for expamle
189 ///if \c e is an Expr and \c v and \c w are of type \ref Col then you can
190 ///read and modify the coefficients like
197 ///or you can also iterate through its elements.
200 ///for(LpSolverBase::Expr::iterator i=e.begin();i!=e.end();++i)
203 ///(This code computes the sum of all coefficients).
204 ///- Numbers (<tt>double</tt>'s)
205 ///and variables (\ref Col "Col"s) directly convert to an
206 ///\ref Expr and the usual linear operations are defined so
209 ///2*v-3.12*(v-w/2)+2
210 ///v*2.1+(3*v+(v*12+w+6)*3)/2
212 ///are valid expressions. The usual assignment operations are also defined.
215 ///e+=2*v-3.12*(v-w/2)+2;
219 ///- The constant member can be set and read by \ref constComp()
222 ///double c=e.constComp();
225 ///\note that \ref clear() not only sets all coefficients to 0 but also
226 ///clears the constant components.
227 class Expr : public std::map<Col,Value>
230 typedef LpSolverBase::Col Key;
231 typedef LpSolverBase::Value Value;
234 typedef std::map<Col,Value> Base;
238 typedef True IsLinExpression;
240 Expr() : Base(), const_comp(0) { }
242 Expr(const Key &v) : const_comp(0) {
243 Base::insert(std::make_pair(v, 1));
246 Expr(const Value &v) : const_comp(v) {}
248 void set(const Key &v,const Value &c) {
249 Base::insert(std::make_pair(v, c));
252 Value &constComp() { return const_comp; }
254 const Value &constComp() const { return const_comp; }
256 ///Removes the components with zero coefficient.
258 for (Base::iterator i=Base::begin(); i!=Base::end();) {
261 if ((*i).second==0) Base::erase(i);
266 ///Sets all coefficients and the constant component to 0.
273 Expr &operator+=(const Expr &e) {
274 for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
275 (*this)[j->first]+=j->second;
276 ///\todo it might be speeded up using "hints"
277 const_comp+=e.const_comp;
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 const_comp-=e.const_comp;
288 Expr &operator*=(const Value &c) {
289 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
295 Expr &operator/=(const Value &c) {
296 for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
304 //typedef LinConstr<Expr> Constr;
308 typedef LpSolverBase::Expr Expr;
309 typedef Expr::Key Key;
310 typedef Expr::Value Value;
312 static const Value INF;
313 static const Value NaN;
314 // static const Value INF=0;
315 // static const Value NaN=1;
322 Constr() : _expr(), _lb(NaN), _ub(NaN) {}
324 Constr(Value lb,const Expr &e,Value ub) :
325 _expr(e), _lb(lb), _ub(ub) {}
327 Constr(const Expr &e,Value ub) :
328 _expr(e), _lb(NaN), _ub(ub) {}
330 Constr(Value lb,const Expr &e) :
331 _expr(e), _lb(lb), _ub(NaN) {}
333 Constr(const Expr &e) :
334 _expr(e), _lb(NaN), _ub(NaN) {}
342 Expr &expr() { return _expr; }
344 const Expr &expr() const { return _expr; }
346 Value &lowerBound() { return _lb; }
348 const Value &lowerBound() const { return _lb; }
350 Value &upperBound() { return _ub; }
352 const Value &upperBound() const { return _ub; }
354 bool lowerBounded() const { return std::isfinite(_lb); }
356 bool upperBounded() const { return std::isfinite(_ub); }
365 virtual int _addCol() = 0;
367 virtual int _addRow() = 0;
370 /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
372 virtual void _setRowCoeffs(int i,
375 Value const * values ) = 0;
378 /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
380 virtual void _setColCoeffs(int i,
383 Value const * values ) = 0;
387 /// The lower bound of a variable (column) have to be given by an
388 /// extended number of type Value, i.e. a finite number of type
389 /// Value or -\ref INF.
390 virtual void _setColLowerBound(int i, Value value) = 0;
393 /// The upper bound of a variable (column) have to be given by an
394 /// extended number of type Value, i.e. a finite number of type
395 /// Value or \ref INF.
396 virtual void _setColUpperBound(int i, Value value) = 0;
399 /// The lower bound of a linear expression (row) have to be given by an
400 /// extended number of type Value, i.e. a finite number of type
401 /// Value or -\ref INF.
402 virtual void _setRowLowerBound(int i, Value value) = 0;
405 /// The upper bound of a linear expression (row) have to be given by an
406 /// extended number of type Value, i.e. a finite number of type
407 /// Value or \ref INF.
408 virtual void _setRowUpperBound(int i, Value value) = 0;
411 virtual void _setObjCoeff(int i, Value obj_coef) = 0;
415 ///\bug Wrong interface
417 virtual SolutionStatus _solve() = 0;
421 ///\bug Wrong interface
423 virtual Value _getPrimal(int i) = 0;
426 ///\bug unimplemented!!!!
432 virtual ~LpSolverBase() {}
434 ///\name Building up and modification of the LP
438 ///Add a new empty column (i.e a new variable) to the LP
439 Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
441 ///\brief Fill the elements of a container with newly created columns
442 ///(i.e a new variables)
444 ///This magic function takes a container as its argument
445 ///and fills its elements
446 ///with new columns (i.e. variables)
448 ///- a standard STL compatible iterable container with
449 ///\ref Col as its \c values_type
452 ///std::vector<LpSolverBase::Col>
453 ///std::list<LpSolverBase::Col>
455 ///- a standard STL compatible iterable container with
456 ///\ref Col as its \c mapped_type
459 ///std::map<AnyType,LpSolverBase::Col>
461 ///- an iterable lemon \ref concept::WriteMap "write map" like
463 ///ListGraph::NodeMap<LpSolverBase::Col>
464 ///ListGraph::EdgeMap<LpSolverBase::Col>
466 ///\return The number of the created column.
467 ///\bug Iterable nodemap hasn't been implemented yet.
470 int addColSet(T &t) { return 0;}
473 typename enable_if<typename T::value_type::LpSolverCol,int>::type
474 addColSet(T &t,dummy<0> = 0) {
476 for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
480 typename enable_if<typename T::value_type::second_type::LpSolverCol,
482 addColSet(T &t,dummy<1> = 1) {
484 for(typename T::iterator i=t.begin();i!=t.end();++i) {
491 typename enable_if<typename T::ValueSet::value_type::LpSolverCol,
493 addColSet(T &t,dummy<2> = 2) {
494 ///\bug <tt>return addColSet(t.valueSet());</tt> should also work.
496 for(typename T::ValueSet::iterator i=t.valueSet().begin();
497 i!=t.valueSet().end();
507 ///Add a new empty row (i.e a new constaint) to the LP
509 ///This function adds a new empty row (i.e a new constaint) to the LP.
510 ///\return The created row
511 Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
513 ///Set a row (i.e a constaint) of the LP
515 ///\param r is the row to be modified
516 ///\param l is lower bound (-\ref INF means no bound)
517 ///\param e is a linear expression (see \ref Expr)
518 ///\param u is the upper bound (\ref INF means no bound)
519 ///\bug This is a temportary function. The interface will change to
521 void setRow(Row r, Value l,const Expr &e, Value u) {
522 std::vector<int> indices;
523 std::vector<Value> values;
524 indices.push_back(0);
526 for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i)
527 if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
528 indices.push_back(cols.floatingId((*i).first.id));
529 values.push_back((*i).second);
531 _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
532 &indices[0],&values[0]);
533 _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
534 _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
537 ///Set a row (i.e a constaint) of the LP
539 ///\param r is the row to be modified
540 ///\param c is a linear expression (see \ref Constr)
541 void setRow(Row r, const Constr &c) {
543 c.lowerBounded()?c.lowerBound():-INF,
545 c.upperBounded()?c.upperBound():INF);
548 ///Add a new row (i.e a new constaint) to the LP
550 ///\param l is the lower bound (-\ref INF means no bound)
551 ///\param e is a linear expression (see \ref Expr)
552 ///\param u is the upper bound (\ref INF means no bound)
553 ///\return The created row.
554 ///\bug This is a temportary function. The interface will change to
556 Row addRow(Value l,const Expr &e, Value u) {
562 ///Add a new row (i.e a new constaint) to the LP
564 ///\param c is a linear expression (see \ref Constr)
565 ///\return The created row.
566 Row addRow(const Constr &c) {
572 /// Set the lower bound of a column (i.e a variable)
574 /// The upper bound of a variable (column) has to be given by an
575 /// extended number of type Value, i.e. a finite number of type
576 /// Value or -\ref INF.
577 void colLowerBound(Col c, Value value) {
578 _setColLowerBound(cols.floatingId(c.id),value);
580 /// Set the upper bound of a column (i.e a variable)
582 /// The upper bound of a variable (column) has to be given by an
583 /// extended number of type Value, i.e. a finite number of type
584 /// Value or \ref INF.
585 void colUpperBound(Col c, Value value) {
586 _setColUpperBound(cols.floatingId(c.id),value);
588 /// Set the lower and the upper bounds of a column (i.e a variable)
590 /// The lower and the upper bounds of
591 /// a variable (column) have to be given by an
592 /// extended number of type Value, i.e. a finite number of type
593 /// Value, -\ref INF or \ref INF.
594 void colBounds(Col c, Value lower, Value upper) {
595 _setColLowerBound(cols.floatingId(c.id),lower);
596 _setColUpperBound(cols.floatingId(c.id),upper);
599 /// Set the lower bound of a row (i.e a constraint)
601 /// The lower bound of a linear expression (row) has to be given by an
602 /// extended number of type Value, i.e. a finite number of type
603 /// Value or -\ref INF.
604 void rowLowerBound(Row r, Value value) {
605 _setRowLowerBound(rows.floatingId(r.id),value);
607 /// Set the upper bound of a row (i.e a constraint)
609 /// The upper bound of a linear expression (row) has to be given by an
610 /// extended number of type Value, i.e. a finite number of type
611 /// Value or \ref INF.
612 void rowUpperBound(Row r, Value value) {
613 _setRowUpperBound(rows.floatingId(r.id),value);
615 /// Set the lower and the upper bounds of a row (i.e a variable)
617 /// The lower and the upper bounds of
618 /// a constraint (row) have to be given by an
619 /// extended number of type Value, i.e. a finite number of type
620 /// Value, -\ref INF or \ref INF.
621 void rowBounds(Row c, Value lower, Value upper) {
622 _setRowLowerBound(rows.floatingId(c.id),lower);
623 _setRowUpperBound(rows.floatingId(c.id),upper);
626 ///Set an element of the objective function
627 void objCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
628 ///Set the objective function
630 ///\param e is a linear expression of type \ref Expr.
631 ///\todo What to do with the constant component?
632 void setObj(Expr e) {
634 for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
635 objCoeff((*i).first,(*i).second);
641 ///\name Solving the LP
646 SolutionStatus solve() { return _solve(); }
650 ///\name Obtaining the solution LP
655 Value primal(Col c) { return _getPrimal(cols.floatingId(c.id)); }
663 ///\relates LpSolverBase::Expr
665 inline LpSolverBase::Expr operator+(const LpSolverBase::Expr &a,
666 const LpSolverBase::Expr &b)
668 LpSolverBase::Expr tmp(a);
669 tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?
674 ///\relates LpSolverBase::Expr
676 inline LpSolverBase::Expr operator-(const LpSolverBase::Expr &a,
677 const LpSolverBase::Expr &b)
679 LpSolverBase::Expr tmp(a);
680 tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?
685 ///\relates LpSolverBase::Expr
687 inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
688 const LpSolverBase::Value &b)
690 LpSolverBase::Expr tmp(a);
691 tmp*=b; ///\todo Don't STL have some special 'merge' algorithm?
697 ///\relates LpSolverBase::Expr
699 inline LpSolverBase::Expr operator*(const LpSolverBase::Value &a,
700 const LpSolverBase::Expr &b)
702 LpSolverBase::Expr tmp(b);
703 tmp*=a; ///\todo Don't STL have some special 'merge' algorithm?
708 ///\relates LpSolverBase::Expr
710 inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
711 const LpSolverBase::Value &b)
713 LpSolverBase::Expr tmp(a);
714 tmp/=b; ///\todo Don't STL have some special 'merge' algorithm?
720 ///\relates LpSolverBase::Constr
722 inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
723 const LpSolverBase::Expr &f)
725 return LpSolverBase::Constr(-LpSolverBase::INF,e-f,0);
730 ///\relates LpSolverBase::Constr
732 inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &e,
733 const LpSolverBase::Expr &f)
735 return LpSolverBase::Constr(e,f);
740 ///\relates LpSolverBase::Constr
742 inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
743 const LpSolverBase::Value &f)
745 return LpSolverBase::Constr(e,f);
750 ///\relates LpSolverBase::Constr
752 inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
753 const LpSolverBase::Expr &f)
755 return LpSolverBase::Constr(-LpSolverBase::INF,f-e,0);
761 ///\relates LpSolverBase::Constr
763 inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &e,
764 const LpSolverBase::Expr &f)
766 return LpSolverBase::Constr(f,e);
772 ///\relates LpSolverBase::Constr
774 inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
775 const LpSolverBase::Value &f)
777 return LpSolverBase::Constr(f,e);
782 ///\relates LpSolverBase::Constr
784 inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
785 const LpSolverBase::Expr &f)
787 return LpSolverBase::Constr(0,e-f,0);
792 ///\relates LpSolverBase::Constr
794 inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &n,
795 const LpSolverBase::Constr&c)
797 LpSolverBase::Constr tmp(c);
798 ///\todo Create an own exception type.
799 if(!isnan(tmp.lowerBound())) throw LogicError();
800 else tmp.lowerBound()=n;
805 ///\relates LpSolverBase::Constr
807 inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
808 const LpSolverBase::Value &n)
810 LpSolverBase::Constr tmp(c);
811 ///\todo Create an own exception type.
812 if(!isnan(tmp.upperBound())) throw LogicError();
813 else tmp.upperBound()=n;
819 ///\relates LpSolverBase::Constr
821 inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &n,
822 const LpSolverBase::Constr&c)
824 LpSolverBase::Constr tmp(c);
825 ///\todo Create an own exception type.
826 if(!isnan(tmp.upperBound())) throw LogicError();
827 else tmp.upperBound()=n;
832 ///\relates LpSolverBase::Constr
834 inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
835 const LpSolverBase::Value &n)
837 LpSolverBase::Constr tmp(c);
838 ///\todo Create an own exception type.
839 if(!isnan(tmp.lowerBound())) throw LogicError();
840 else tmp.lowerBound()=n;
847 #endif //LEMON_LP_BASE_H