COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/lp_old/lp_solver_base.h @ 1244:43a3d06e0ee0

Last change on this file since 1244:43a3d06e0ee0 was 1244:43a3d06e0ee0, checked in by athos, 15 years ago
File size: 18.1 KB
Line 
1// -*- c++ -*-
2#ifndef LEMON_LP_SOLVER_BASE_H
3#define LEMON_LP_SOLVER_BASE_H
4
5///\ingroup misc
6///\file
7
8// #include <stdio.h>
9#include <stdlib.h>
10#include <iostream>
11#include <map>
12#include <limits>
13// #include <stdio>
14//#include <stdlib>
15
16#include <iostream>
17#include <vector>
18#include <string>
19#include <list>
20#include <memory>
21#include <utility>
22
23#include <lemon/invalid.h>
24#include <expression.h>
25//#include <stp.h>
26//#include <lemon/max_flow.h>
27//#include <augmenting_flow.h>
28//#include <iter_map.h>
29
30using std::cout;
31using std::cin;
32using std::endl;
33
34namespace lemon {
35 
36  /// \addtogroup misc
37  /// @{
38
39  /// \brief A partitioned vector with iterable classes.
40  ///
41  /// This class implements a container in which the data is stored in an
42  /// stl vector, the range is partitioned into sets and each set is
43  /// doubly linked in a list.
44  /// That is, each class is iterable by lemon iterators, and any member of
45  /// the vector can bo moved to an other class.
46  template <typename T>
47  class IterablePartition {
48  protected:
49    struct Node {
50      T data;
51      int prev; //invalid az -1
52      int next;
53    };
54    std::vector<Node> nodes;
55    struct Tip {
56      int first;
57      int last;
58    };
59    std::vector<Tip> tips;
60  public:
61    /// The classes are indexed by integers from \c 0 to \c classNum()-1.
62    int classNum() const { return tips.size(); }
63    /// This lemon style iterator iterates through a class.
64    class Class;
65    /// Constructor. The number of classes is to be given which is fixed
66    /// over the life of the container.
67    /// The partition classes are indexed from 0 to class_num-1.
68    IterablePartition(int class_num) {
69      for (int i=0; i<class_num; ++i) {
70        Tip t;
71        t.first=t.last=-1;
72        tips.push_back(t);
73      }
74    }
75  protected:
76    void befuz(Class it, int class_id) {
77      if (tips[class_id].first==-1) {
78        if (tips[class_id].last==-1) {
79          nodes[it.i].prev=nodes[it.i].next=-1;
80          tips[class_id].first=tips[class_id].last=it.i;
81        }
82      } else {
83        nodes[it.i].prev=tips[class_id].last;
84        nodes[it.i].next=-1;
85        nodes[tips[class_id].last].next=it.i;
86        tips[class_id].last=it.i;
87      }
88    }
89    void kifuz(Class it, int class_id) {
90      if (tips[class_id].first==it.i) {
91        if (tips[class_id].last==it.i) {
92          tips[class_id].first=tips[class_id].last=-1;
93        } else {
94          tips[class_id].first=nodes[it.i].next;
95          nodes[nodes[it.i].next].prev=-1;
96        }
97      } else {
98        if (tips[class_id].last==it.i) {
99          tips[class_id].last=nodes[it.i].prev;
100          nodes[nodes[it.i].prev].next=-1;
101        } else {
102          nodes[nodes[it.i].next].prev=nodes[it.i].prev;
103          nodes[nodes[it.i].prev].next=nodes[it.i].next;
104        }
105      }
106    }
107  public:
108    /// A new element with data \c t is pushed into the vector and into class
109    /// \c class_id.
110    Class push_back(const T& t, int class_id) {
111      Node n;
112      n.data=t;
113      nodes.push_back(n);
114      int i=nodes.size()-1;
115      befuz(i, class_id);
116      return i;
117    }
118    /// A member is moved to an other class.
119    void set(Class it, int old_class_id, int new_class_id) {
120      kifuz(it.i, old_class_id);
121      befuz(it.i, new_class_id);
122    }
123    /// Returns the data pointed by \c it.
124    T& operator[](Class it) { return nodes[it.i].data; }
125    /// Returns the data pointed by \c it.
126    const T& operator[](Class it) const { return nodes[it.i].data; }
127    ///.
128    class Class {
129      friend class IterablePartition;
130    protected:
131      int i;
132    public:
133      /// Default constructor.
134      Class() { }
135      /// This constructor constructs an iterator which points
136      /// to the member of th container indexed by the integer _i.
137      Class(const int& _i) : i(_i) { }
138      /// Invalid constructor.
139      Class(const Invalid&) : i(-1) { }
140      friend bool operator<(const Class& x, const Class& y);
141      friend std::ostream& operator<<(std::ostream& os,
142                                      const Class& it);
143      bool operator==(const Class& node) const {return i == node.i;}
144      bool operator!=(const Class& node) const {return i != node.i;}
145    };
146    friend bool operator<(const Class& x, const Class& y) {
147      return (x.i < y.i);
148    }
149    friend std::ostream& operator<<(std::ostream& os,
150                                    const Class& it) {
151      os << it.i;
152      return os;
153    }
154    /// First member of class \c class_id.
155    Class& first(Class& it, int class_id) const {
156      it.i=tips[class_id].first;
157      return it;
158    }
159    /// Next member.
160    Class& next(Class& it) const {
161      it.i=nodes[it.i].next;
162      return it;
163    }
164    /// True iff the iterator is valid.
165    bool valid(const Class& it) const { return it.i!=-1; }
166
167    class ClassIt : public Class {
168      const IterablePartition* iterable_partition;
169    public:
170      ClassIt() { }
171      ClassIt(Invalid i) : Class(i) { }
172      ClassIt(const IterablePartition& _iterable_partition,
173              const int& i) : iterable_partition(&_iterable_partition) {
174        _iterable_partition.first(*this, i);
175      }
176      ClassIt(const IterablePartition& _iterable_partition,
177              const Class& _class) :
178        Class(_class), iterable_partition(&_iterable_partition) { }
179      ClassIt& operator++() {
180        iterable_partition->next(*this);
181        return *this;
182      }
183    };
184
185  };
186
187
188  /*! \e
189    \todo kellenene uj iterable structure bele, mert ez nem az igazi
190    \todo A[x,y]-t cserel. Jobboldal, baloldal csere.
191    \todo LEKERDEZESEK!!!
192    \todo DOKSI!!!! Doxygen group!!!
193    The aim of this class is to give a general surface to different
194    solvers, i.e. it makes possible to write algorithms using LP's,
195    in which the solver can be changed to an other one easily.
196    \nosubgrouping
197  */
198  template <typename _Value>
199  class LpSolverBase {
200   
201    /*! @name Uncategorized functions and types (public members)
202    */
203    //@{
204  public:
205
206    //UNCATEGORIZED
207
208    /// \e
209    typedef IterablePartition<int> Rows;
210    /// \e
211    typedef IterablePartition<int> Cols;
212    /// \e
213    typedef _Value Value;
214    /// \e
215    typedef Rows::Class Row;
216    /// \e
217    typedef Cols::Class Col;
218  public:
219    /// \e
220    IterablePartition<int> row_iter_map;
221    /// \e
222    IterablePartition<int> col_iter_map;
223    /// \e
224    std::vector<Row> int_row_map;
225    /// \e
226    std::vector<Col> int_col_map;
227    /// \e
228    const int VALID_CLASS;
229    /// \e
230    const int INVALID_CLASS;
231    /// \e
232    static const Value INF;
233  public:
234    /// \e
235    LpSolverBase() : row_iter_map(2),
236                     col_iter_map(2),
237                     VALID_CLASS(0), INVALID_CLASS(1) { }
238    /// \e
239    virtual ~LpSolverBase() { }
240    //@}
241
242    /*! @name Medium level interface (public members)
243      These functions appear in the low level and also in the high level
244      interfaces thus these each of these functions have to be implemented
245      only once in the different interfaces.
246      This means that these functions have to be reimplemented for all of the
247      different lp solvers. These are basic functions, and have the same
248      parameter lists in the low and high level interfaces.
249    */
250    //@{
251  public:
252
253    //UNCATEGORIZED FUNCTIONS
254
255    /// \e
256    virtual void setMinimize() = 0;
257    /// \e
258    virtual void setMaximize() = 0;
259
260    //SOLVER FUNCTIONS
261
262    /// \e
263    virtual void solveSimplex() = 0;
264    /// \e
265    virtual void solvePrimalSimplex() = 0;
266    /// \e
267    virtual void solveDualSimplex() = 0;
268
269    //SOLUTION RETRIEVING
270
271    /// \e
272    virtual Value getObjVal() = 0;
273
274    //OTHER FUNCTIONS
275
276    /// \e
277    virtual int rowNum() const = 0;
278    /// \e
279    virtual int colNum() const = 0;
280    /// \e
281    virtual int warmUp() = 0;
282    /// \e
283    virtual void printWarmUpStatus(int i) = 0;
284    /// \e
285    virtual int getPrimalStatus() = 0;
286    /// \e
287    virtual void printPrimalStatus(int i) = 0;
288    /// \e
289    virtual int getDualStatus() = 0;
290    /// \e
291    virtual void printDualStatus(int i) = 0;
292    /// Returns the status of the slack variable assigned to row \c row.
293    virtual int getRowStat(const Row& row) = 0;
294    /// \e
295    virtual void printRowStatus(int i) = 0;
296    /// Returns the status of the variable assigned to column \c col.
297    virtual int getColStat(const Col& col) = 0;
298    /// \e
299    virtual void printColStatus(int i) = 0;
300
301    //@}
302
303    /*! @name Low level interface (protected members)
304      Problem manipulating functions in the low level interface
305    */
306    //@{
307  protected:
308
309    //MATRIX MANIPULATING FUNCTIONS
310
311    /// \e
312    virtual int _addCol() = 0;
313    /// \e
314    virtual int _addRow() = 0;
315    /// \e
316    virtual void _eraseCol(int i) = 0;
317    /// \e
318    virtual void _eraseRow(int i) = 0;
319    /// \e
320    virtual void _setRowCoeffs(int i,
321                               const std::vector<std::pair<int, Value> >& coeffs) = 0;
322    /// \e
323    /// This routine modifies \c coeffs only by the \c push_back method.
324    virtual void _getRowCoeffs(int i,
325                               std::vector<std::pair<int, Value> >& coeffs) = 0;
326    /// \e
327    virtual void _setColCoeffs(int i,
328                               const std::vector<std::pair<int, Value> >& coeffs) = 0;
329    /// \e
330    /// This routine modifies \c coeffs only by the \c push_back method.
331    virtual void _getColCoeffs(int i,
332                               std::vector<std::pair<int, Value> >& coeffs) = 0;
333    /// \e
334    virtual void _setCoeff(int col, int row, Value value) = 0;
335    /// \e
336    virtual Value _getCoeff(int col, int row) = 0;
337    //  public:
338    //    /// \e
339    //    enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
340  protected:
341    /// \e
342    /// The lower bound of a variable (column) have to be given by an
343    /// extended number of type Value, i.e. a finite number of type
344    /// Value or -INF.
345    virtual void _setColLowerBound(int i, Value value) = 0;
346    /// \e
347    /// The lower bound of a variable (column) is an
348    /// extended number of type Value, i.e. a finite number of type
349    /// Value or -INF.
350    virtual Value _getColLowerBound(int i) = 0;
351    /// \e
352    /// The upper bound of a variable (column) have to be given by an
353    /// extended number of type Value, i.e. a finite number of type
354    /// Value or INF.
355    virtual void _setColUpperBound(int i, Value value) = 0;
356    /// \e
357    /// The upper bound of a variable (column) is an
358    /// extended number of type Value, i.e. a finite number of type
359    /// Value or INF.
360    virtual Value _getColUpperBound(int i) = 0;
361    /// \e
362    /// The lower bound of a linear expression (row) have to be given by an
363    /// extended number of type Value, i.e. a finite number of type
364    /// Value or -INF.
365    virtual void _setRowLowerBound(int i, Value value) = 0;
366    /// \e
367    /// The lower bound of a linear expression (row) is an
368    /// extended number of type Value, i.e. a finite number of type
369    /// Value or -INF.
370    virtual Value _getRowLowerBound(int i) = 0;
371    /// \e
372    /// The upper bound of a linear expression (row) have to be given by an
373    /// extended number of type Value, i.e. a finite number of type
374    /// Value or INF.
375    virtual void _setRowUpperBound(int i, Value value) = 0;
376    /// \e
377    /// The upper bound of a linear expression (row) is an
378    /// extended number of type Value, i.e. a finite number of type
379    /// Value or INF.
380    virtual Value _getRowUpperBound(int i) = 0;
381    /// \e
382    virtual void _setObjCoeff(int i, Value obj_coef) = 0;
383    /// \e
384    virtual Value _getObjCoeff(int i) = 0;
385   
386    //SOLUTION RETRIEVING
387
388    /// \e
389    virtual Value _getPrimal(int i) = 0;
390    //@}
391   
392    /*! @name High level interface (public members)
393      Problem manipulating functions in the high level interface
394    */
395    //@{
396  public:
397
398    //MATRIX MANIPULATING FUNCTIONS
399
400    /// \e
401    Col addCol() {
402      int i=_addCol(); 
403      Col col;
404      col_iter_map.first(col, INVALID_CLASS);
405      if (col_iter_map.valid(col)) { //van hasznalhato hely
406        col_iter_map.set(col, INVALID_CLASS, VALID_CLASS);
407        col_iter_map[col]=i;
408      } else { //a cucc vegere kell inzertalni mert nincs szabad hely
409        col=col_iter_map.push_back(i, VALID_CLASS);
410      }
411      int_col_map.push_back(col);
412      return col;
413    }
414    /// \e
415    Row addRow() {
416      int i=_addRow();
417      Row row;
418      row_iter_map.first(row, INVALID_CLASS);
419      if (row_iter_map.valid(row)) { //van hasznalhato hely
420        row_iter_map.set(row, INVALID_CLASS, VALID_CLASS);
421        row_iter_map[row]=i;
422      } else { //a cucc vegere kell inzertalni mert nincs szabad hely
423        row=row_iter_map.push_back(i, VALID_CLASS);
424      }
425      int_row_map.push_back(row);
426      return row;
427    }
428    /// \e
429    void eraseCol(const Col& col) {
430      col_iter_map.set(col, VALID_CLASS, INVALID_CLASS);
431      int cols[2];
432      cols[1]=col_iter_map[col];
433      _eraseCol(cols[1]);
434      col_iter_map[col]=0; //glpk specifikus, de kell ez??
435      Col it;
436      for (col_iter_map.first(it, VALID_CLASS);
437           col_iter_map.valid(it); col_iter_map.next(it)) {
438        if (col_iter_map[it]>cols[1]) --col_iter_map[it];
439      }
440      int_col_map.erase(int_col_map.begin()+cols[1]);
441    }
442    /// \e
443    void eraseRow(const Row& row) {
444      row_iter_map.set(row, VALID_CLASS, INVALID_CLASS);
445      int rows[2];
446      rows[1]=row_iter_map[row];
447      _eraseRow(rows[1]);
448      row_iter_map[row]=0; //glpk specifikus, de kell ez??
449      Row it;
450      for (row_iter_map.first(it, VALID_CLASS);
451           row_iter_map.valid(it); row_iter_map.next(it)) {
452        if (row_iter_map[it]>rows[1]) --row_iter_map[it];
453      }
454      int_row_map.erase(int_row_map.begin()+rows[1]);
455    }
456    /// \e
457    void setCoeff(Col col, Row row, Value value) {
458      _setCoeff(col_iter_map[col], row_iter_map[row], value);
459    }
460    /// \e
461    Value getCoeff(Col col, Row row) {
462      return _getCoeff(col_iter_map[col], row_iter_map[row], value);
463    }
464    /// \e
465    void setColLowerBound(Col col, Value lo) {
466      _setColLowerBound(col_iter_map[col], lo);
467    }
468    /// \e
469    Value getColLowerBound(Col col) {
470      return _getColLowerBound(col_iter_map[col]);
471    }
472    /// \e
473    void setColUpperBound(Col col, Value up) {
474      _setColUpperBound(col_iter_map[col], up);
475    }
476    /// \e
477    Value getColUpperBound(Col col) {     
478      return _getColUpperBound(col_iter_map[col]);
479    }
480    /// \e
481    void setRowLowerBound(Row row, Value lo) {
482      _setRowLowerBound(row_iter_map[row], lo);
483    }
484    /// \e
485    Value getRowLowerBound(Row row) {
486      return _getRowLowerBound(row_iter_map[row]);
487    }
488    /// \e
489    void setRowUpperBound(Row row, Value up) {
490      _setRowUpperBound(row_iter_map[row], up);
491    }
492    /// \e
493    Value getRowUpperBound(Row row) {     
494      return _getRowUpperBound(row_iter_map[row]);
495    }
496    /// \e
497    void setObjCoeff(const Col& col, Value obj_coef) {
498      _setObjCoeff(col_iter_map[col], obj_coef);
499    }
500    /// \e
501    Value getObjCoeff(const Col& col) {
502      return _getObjCoeff(col_iter_map[col]);
503    }
504
505    //SOLUTION RETRIEVING FUNCTIONS
506
507    /// \e
508    Value getPrimal(const Col& col) {
509      return _getPrimal(col_iter_map[col]);
510    }   
511
512    //@}
513
514    /*! @name User friend interface
515      Problem manipulating functions in the user friend interface
516    */
517    //@{
518
519    //EXPRESSION TYPES
520
521    /// \e
522    typedef Expr<Col, Value> Expression;
523    /// \e
524    typedef Expr<Row, Value> DualExpression;
525    /// \e
526    typedef Constr<Col, Value> Constraint;
527
528    //MATRIX MANIPULATING FUNCTIONS
529
530    /// \e
531    void setRowCoeffs(Row row, const Expression& expr) {
532      std::vector<std::pair<int, Value> > row_coeffs;
533      for(typename Expression::Data::const_iterator i=expr.data.begin();
534          i!=expr.data.end(); ++i) {
535        row_coeffs.push_back(std::make_pair
536                             (col_iter_map[(*i).first], (*i).second));
537      }
538      _setRowCoeffs(row_iter_map[row], row_coeffs);
539    }
540    /// \e
541    void setRow(Row row, const Constraint& constr) {
542      setRowCoeffs(row, constr.expr);
543      setRowLowerBound(row, constr.lo);
544      setRowUpperBound(row, constr.up);
545    }
546    /// \e
547    Row addRow(const Constraint& constr) {
548      Row row=addRow();
549      setRowCoeffs(row, constr.expr);
550      setRowLowerBound(row, constr.lo);
551      setRowUpperBound(row, constr.up);
552      return row;
553    }
554    /// \e
555    /// This routine modifies \c expr by only adding to it.
556    void getRowCoeffs(Row row, Expression& expr) {
557      std::vector<std::pair<int, Value> > row_coeffs;
558      _getRowCoeffs(row_iter_map[row], row_coeffs);
559      for(typename std::vector<std::pair<int, Value> >::const_iterator
560            i=row_coeffs.begin(); i!=row_coeffs.end(); ++i) {
561        expr+= (*i).second*int_col_map[(*i).first];
562      }
563    }
564    /// \e
565    void setColCoeffs(Col col, const DualExpression& expr) {
566      std::vector<std::pair<int, Value> > col_coeffs;
567      for(typename DualExpression::Data::const_iterator i=expr.data.begin();
568          i!=expr.data.end(); ++i) {
569        col_coeffs.push_back(std::make_pair
570                             (row_iter_map[(*i).first], (*i).second));
571      }
572      _setColCoeffs(col_iter_map[col], col_coeffs);
573    }
574    /// \e
575    /// This routine modifies \c expr by only adding to it.
576    void getColCoeffs(Col col, DualExpression& expr) {
577      std::vector<std::pair<int, Value> > col_coeffs;
578      _getColCoeffs(col_iter_map[col], col_coeffs);
579      for(typename std::vector<std::pair<int, Value> >::const_iterator
580            i=col_coeffs.begin(); i!=col_coeffs.end(); ++i) {
581        expr+= (*i).second*int_row_map[(*i).first];
582      }
583    }
584    /// \e
585    void setObjCoeffs(const Expression& expr) {
586      // writing zero everywhere
587      for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it)
588        setObjCoeff(it, 0.0);
589      // writing the data needed
590      for(typename Expression::Data::const_iterator i=expr.data.begin();
591          i!=expr.data.end(); ++i) {
592        setObjCoeff((*i).first, (*i).second);
593      }
594    }
595    /// \e
596    /// This routine modifies \c expr by only adding to it.
597    void getObjCoeffs(Expression& expr) {
598      for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it)
599        expr+=getObjCoeff(it)*it;
600    }
601    //@}
602
603
604    /*! @name MIP functions and types (public members)
605    */
606    //@{
607  public:
608    /// \e
609    virtual void solveBandB() = 0;
610    /// \e
611    virtual void setLP() = 0;
612    /// \e
613    virtual void setMIP() = 0;
614  protected:
615   /// \e
616    virtual void _setColCont(int i) = 0;
617    /// \e
618    virtual void _setColInt(int i) = 0;
619    /// \e
620    virtual Value _getMIPPrimal(int i) = 0;
621  public:
622    /// \e
623    void setColCont(Col col) {
624      _setColCont(col_iter_map[col]);
625    }
626    /// \e
627    void setColInt(Col col) {
628      _setColInt(col_iter_map[col]);
629    }
630    /// \e
631    Value getMIPPrimal(Col col) {
632      return _getMIPPrimal(col_iter_map[col]);
633    }
634    //@}
635  };
636
637} //namespace lemon
638
639#endif //LEMON_LP_SOLVER_BASE_H
Note: See TracBrowser for help on using the repository browser.