COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/lp/lp_solver_wrapper_3.h @ 1099:91a8ee9d088d

Last change on this file since 1099:91a8ee9d088d was 1099:91a8ee9d088d, checked in by marci, 16 years ago

-=, - operators in expressions

File size: 17.9 KB
Line 
1// -*- c++ -*-
2#ifndef LEMON_LP_SOLVER_WRAPPER_H
3#define LEMON_LP_SOLVER_WRAPPER_H
4
5///\ingroup misc
6///\file
7///\brief Dijkstra algorithm.
8
9// #include <stdio.h>
10#include <stdlib.h>
11#include <iostream>
12#include <map>
13// #include <stdio>
14//#include <stdlib>
15extern "C" {
16#include "glpk.h"
17}
18
19#include <iostream>
20#include <vector>
21#include <string>
22#include <list>
23#include <memory>
24#include <utility>
25
26//#include <sage_graph.h>
27//#include <lemon/list_graph.h>
28//#include <lemon/graph_wrapper.h>
29#include <lemon/invalid.h>
30#include <expression.h>
31//#include <bfs_dfs.h>
32//#include <stp.h>
33//#include <lemon/max_flow.h>
34//#include <augmenting_flow.h>
35//#include <iter_map.h>
36
37using std::cout;
38using std::cin;
39using std::endl;
40
41namespace lemon {
42 
43  /// \addtogroup misc
44  /// @{
45
46  /// \brief A partitioned vector with iterable classes.
47  ///
48  /// This class implements a container in which the data is stored in an
49  /// stl vector, the range is partitioned into sets and each set is
50  /// doubly linked in a list.
51  /// That is, each class is iterable by lemon iterators, and any member of
52  /// the vector can bo moved to an other class.
53  template <typename T>
54  class IterablePartition {
55  protected:
56    struct Node {
57      T data;
58      int prev; //invalid az -1
59      int next;
60    };
61    std::vector<Node> nodes;
62    struct Tip {
63      int first;
64      int last;
65    };
66    std::vector<Tip> tips;
67  public:
68    /// The classes are indexed by integers from \c 0 to \c classNum()-1.
69    int classNum() const { return tips.size(); }
70    /// This lemon style iterator iterates through a class.
71    class ClassIt;
72    /// Constructor. The number of classes is to be given which is fixed
73    /// over the life of the container.
74    /// The partition classes are indexed from 0 to class_num-1.
75    IterablePartition(int class_num) {
76      for (int i=0; i<class_num; ++i) {
77        Tip t;
78        t.first=t.last=-1;
79        tips.push_back(t);
80      }
81    }
82  protected:
83    void befuz(ClassIt it, int class_id) {
84      if (tips[class_id].first==-1) {
85        if (tips[class_id].last==-1) {
86          nodes[it.i].prev=nodes[it.i].next=-1;
87          tips[class_id].first=tips[class_id].last=it.i;
88        }
89      } else {
90        nodes[it.i].prev=tips[class_id].last;
91        nodes[it.i].next=-1;
92        nodes[tips[class_id].last].next=it.i;
93        tips[class_id].last=it.i;
94      }
95    }
96    void kifuz(ClassIt it, int class_id) {
97      if (tips[class_id].first==it.i) {
98        if (tips[class_id].last==it.i) {
99          tips[class_id].first=tips[class_id].last=-1;
100        } else {
101          tips[class_id].first=nodes[it.i].next;
102          nodes[nodes[it.i].next].prev=-1;
103        }
104      } else {
105        if (tips[class_id].last==it.i) {
106          tips[class_id].last=nodes[it.i].prev;
107          nodes[nodes[it.i].prev].next=-1;
108        } else {
109          nodes[nodes[it.i].next].prev=nodes[it.i].prev;
110          nodes[nodes[it.i].prev].next=nodes[it.i].next;
111        }
112      }
113    }
114  public:
115    /// A new element with data \c t is pushed into the vector and into class
116    /// \c class_id.
117    ClassIt push_back(const T& t, int class_id) {
118      Node n;
119      n.data=t;
120      nodes.push_back(n);
121      int i=nodes.size()-1;
122      befuz(i, class_id);
123      return i;
124    }
125    /// A member is moved to an other class.
126    void set(ClassIt it, int old_class_id, int new_class_id) {
127      kifuz(it.i, old_class_id);
128      befuz(it.i, new_class_id);
129    }
130    /// Returns the data pointed by \c it.
131    T& operator[](ClassIt it) { return nodes[it.i].data; }
132    /// Returns the data pointed by \c it.
133    const T& operator[](ClassIt it) const { return nodes[it.i].data; }
134    ///.
135    class ClassIt {
136      friend class IterablePartition;
137    protected:
138      int i;
139    public:
140      /// Default constructor.
141      ClassIt() { }
142      /// This constructor constructs an iterator which points
143      /// to the member of th container indexed by the integer _i.
144      ClassIt(const int& _i) : i(_i) { }
145      /// Invalid constructor.
146      ClassIt(const Invalid&) : i(-1) { }
147      friend bool operator<(const ClassIt& x, const ClassIt& y);
148      friend std::ostream& operator<<(std::ostream& os,
149                                      const ClassIt& it);
150    };
151    friend bool operator<(const ClassIt& x, const ClassIt& y) {
152      return (x.i < y.i);
153    }
154    friend std::ostream& operator<<(std::ostream& os,
155                                    const ClassIt& it) {
156      os << it.i;
157      return os;
158    }
159    /// First member of class \c class_id.
160    ClassIt& first(ClassIt& it, int class_id) const {
161      it.i=tips[class_id].first;
162      return it;
163    }
164    /// Next member.
165    ClassIt& next(ClassIt& it) const {
166      it.i=nodes[it.i].next;
167      return it;
168    }
169    /// True iff the iterator is valid.
170    bool valid(const ClassIt& it) const { return it.i!=-1; }
171  };
172
173
174  /*! \e
175   */
176  template <typename _Value>
177  class LPSolverBase {
178  public:
179    /// \e
180    typedef _Value Value;
181    /// \e
182    typedef IterablePartition<int>::ClassIt RowIt;
183    /// \e
184    typedef IterablePartition<int>::ClassIt ColIt;
185  public:
186    /// \e
187    IterablePartition<int> row_iter_map;
188    /// \e
189    IterablePartition<int> col_iter_map;
190    /// \e
191    const int VALID_CLASS;
192    /// \e
193    const int INVALID_CLASS;
194  public:
195    /// \e
196    LPSolverBase() : row_iter_map(2),
197                     col_iter_map(2),
198                     VALID_CLASS(0), INVALID_CLASS(1) { }
199    /// \e
200    virtual ~LPSolverBase() { }
201
202    //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
203
204  public:
205    /// \e
206    virtual void setMinimize() = 0;
207    /// \e
208    virtual void setMaximize() = 0;
209
210    //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
211
212  protected:
213    /// \e
214    virtual int _addRow() = 0;
215    /// \e
216    virtual int _addCol() = 0;
217    /// \e
218    virtual void _setRowCoeffs(int i,
219                               std::vector<std::pair<int, double> > coeffs) = 0;
220    /// \e
221    virtual void _setColCoeffs(int i,
222                               std::vector<std::pair<int, double> > coeffs) = 0;
223    /// \e
224    virtual void _eraseCol(int i) = 0;
225    /// \e
226    virtual void _eraseRow(int i) = 0;
227  public:
228    /// \e
229    enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
230  protected:
231    /// \e
232    virtual void _setColBounds(int i, Bound bound,
233                               _Value lo, _Value up) = 0;
234    /// \e
235    virtual void _setRowBounds(int i, Bound bound,
236                               _Value lo, _Value up) = 0;
237    /// \e
238    virtual void _setObjCoef(int i, _Value obj_coef) = 0;
239    /// \e
240    virtual _Value _getObjCoef(int i) = 0;
241
242    //LOW LEVEL, SOLUTION RETRIEVING FUNCTIONS
243
244  protected:
245    virtual _Value _getPrimal(int i) = 0;
246
247    //HIGH LEVEL INTERFACE, MATRIX MANIPULATING FUNTIONS
248
249  public:
250    /// \e
251    RowIt addRow() {
252      int i=_addRow();
253      RowIt row_it;
254      row_iter_map.first(row_it, INVALID_CLASS);
255      if (row_iter_map.valid(row_it)) { //van hasznalhato hely
256        row_iter_map.set(row_it, INVALID_CLASS, VALID_CLASS);
257        row_iter_map[row_it]=i;
258      } else { //a cucc vegere kell inzertalni mert nincs szabad hely
259        row_it=row_iter_map.push_back(i, VALID_CLASS);
260      }
261      return row_it;
262    }
263    /// \e
264    ColIt addCol() {
265      int i=_addCol(); 
266      ColIt col_it;
267      col_iter_map.first(col_it, INVALID_CLASS);
268      if (col_iter_map.valid(col_it)) { //van hasznalhato hely
269        col_iter_map.set(col_it, INVALID_CLASS, VALID_CLASS);
270        col_iter_map[col_it]=i;
271      } else { //a cucc vegere kell inzertalni mert nincs szabad hely
272        col_it=col_iter_map.push_back(i, VALID_CLASS);
273      }
274      return col_it;
275    }
276    /// \e
277    template <typename Begin, typename End>
278    void setRowCoeffs(RowIt row_it, Begin begin, End end) {
279      std::vector<std::pair<int, double> > coeffs;
280      for ( ; begin!=end; ++begin) {
281        coeffs.push_back(std::
282                         make_pair(col_iter_map[begin->first], begin->second));
283      }
284      _setRowCoeffs(row_iter_map[row_it], coeffs);
285    }
286    /// \e
287    template <typename Begin, typename End>
288    void setColCoeffs(ColIt col_it, Begin begin, End end) {
289      std::vector<std::pair<int, double> > coeffs;
290      for ( ; begin!=end; ++begin) {
291        coeffs.push_back(std::
292                         make_pair(row_iter_map[begin->first], begin->second));
293      }
294      _setColCoeffs(col_iter_map[col_it], coeffs);
295    }
296    /// \e
297    void eraseCol(const ColIt& col_it) {
298      col_iter_map.set(col_it, VALID_CLASS, INVALID_CLASS);
299      int cols[2];
300      cols[1]=col_iter_map[col_it];
301      _eraseCol(cols[1]);
302      col_iter_map[col_it]=0; //glpk specifikus, de kell ez??
303      ColIt it;
304      for (col_iter_map.first(it, VALID_CLASS);
305           col_iter_map.valid(it); col_iter_map.next(it)) {
306        if (col_iter_map[it]>cols[1]) --col_iter_map[it];
307      }
308    }
309    /// \e
310    void eraseRow(const RowIt& row_it) {
311      row_iter_map.set(row_it, VALID_CLASS, INVALID_CLASS);
312      int rows[2];
313      rows[1]=row_iter_map[row_it];
314      _eraseRow(rows[1]);
315      row_iter_map[row_it]=0; //glpk specifikus, de kell ez??
316      RowIt it;
317      for (row_iter_map.first(it, VALID_CLASS);
318           row_iter_map.valid(it); row_iter_map.next(it)) {
319        if (row_iter_map[it]>rows[1]) --row_iter_map[it];
320      }
321    }
322    /// \e
323    void setColBounds(const ColIt& col_it, Bound bound,
324                      _Value lo, _Value up) {
325      _setColBounds(col_iter_map[col_it], bound, lo, up);
326    }
327    /// \e
328    void setRowBounds(const RowIt& row_it, Bound bound,
329                      _Value lo, _Value up) {
330      _setRowBounds(row_iter_map[row_it], bound, lo, up);
331    }
332    /// \e
333    void setObjCoef(const ColIt& col_it, _Value obj_coef) {
334      _setObjCoef(col_iter_map[col_it], obj_coef);
335    }
336    /// \e
337    _Value getObjCoef(const ColIt& col_it) {
338      return _getObjCoef(col_iter_map[col_it]);
339    }
340
341    //MOST HIGH LEVEL, USER FRIEND FUNCTIONS
342
343    /// \e
344    typedef Expr<ColIt, _Value> Expression;
345    /// \e
346    typedef Expr<RowIt, _Value> DualExpression;
347    /// \e
348    void setRowCoeffs(RowIt row_it, const Expression& expr) {
349      std::vector<std::pair<int, _Value> > row_coeffs;
350      for(typename Expression::Data::const_iterator i=expr.data.begin();
351          i!=expr.data.end(); ++i) {
352        row_coeffs.push_back(std::make_pair
353                             (col_iter_map[(*i).first], (*i).second));
354      }
355      _setRowCoeffs(row_iter_map[row_it], row_coeffs);
356    }
357    /// \e
358    void setColCoeffs(ColIt col_it, const DualExpression& expr) {
359      std::vector<std::pair<int, _Value> > col_coeffs;
360      for(typename DualExpression::Data::const_iterator i=expr.data.begin();
361          i!=expr.data.end(); ++i) {
362        col_coeffs.push_back(std::make_pair
363                             (row_iter_map[(*i).first], (*i).second));
364      }
365      _setColCoeffs(col_iter_map[col_it], col_coeffs);
366    }
367    /// \e
368    void setObjCoeffs(const Expression& expr) {
369      for(typename Expression::Data::const_iterator i=expr.data.begin();
370          i!=expr.data.end(); ++i) {
371        setObjCoef((*i).first, (*i).second);
372      }
373    }
374    //SOLVER FUNCTIONS
375
376    /// \e
377    virtual void solveSimplex() = 0;
378    /// \e
379    virtual void solvePrimalSimplex() = 0;
380    /// \e
381    virtual void solveDualSimplex() = 0;
382    /// \e
383
384    //HIGH LEVEL, SOLUTION RETRIEVING FUNCTIONS
385
386  public:
387    _Value getPrimal(const ColIt& col_it) {
388      return _getPrimal(col_iter_map[col_it]);
389    }
390    /// \e
391    virtual _Value getObjVal() = 0;
392
393    //OTHER FUNCTIONS
394
395    /// \e
396    virtual int rowNum() const = 0;
397    /// \e
398    virtual int colNum() const = 0;
399    /// \e
400    virtual int warmUp() = 0;
401    /// \e
402    virtual void printWarmUpStatus(int i) = 0;
403    /// \e
404    virtual int getPrimalStatus() = 0;
405    /// \e
406    virtual void printPrimalStatus(int i) = 0;
407    /// \e
408    virtual int getDualStatus() = 0;
409    /// \e
410    virtual void printDualStatus(int i) = 0;
411    /// Returns the status of the slack variable assigned to row \c row_it.
412    virtual int getRowStat(const RowIt& row_it) = 0;
413    /// \e
414    virtual void printRowStatus(int i) = 0;
415    /// Returns the status of the variable assigned to column \c col_it.
416    virtual int getColStat(const ColIt& col_it) = 0;
417    /// \e
418    virtual void printColStatus(int i) = 0;
419  };
420 
421
422  /// \brief Wrappers for LP solvers
423  ///
424  /// This class implements a lemon wrapper for glpk.
425  /// Later other LP-solvers will be wrapped into lemon.
426  /// The aim of this class is to give a general surface to different
427  /// solvers, i.e. it makes possible to write algorithms using LP's,
428  /// in which the solver can be changed to an other one easily.
429  class LPGLPK : public LPSolverBase<double> {
430  public:
431    typedef LPSolverBase<double> Parent;
432
433  public:
434    /// \e
435    LPX* lp;
436
437  public:
438    /// \e
439    LPGLPK() : Parent(),
440                        lp(lpx_create_prob()) {
441      lpx_set_int_parm(lp, LPX_K_DUAL, 1);
442    }
443    /// \e
444    ~LPGLPK() {
445      lpx_delete_prob(lp);
446    }
447
448    //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
449
450    /// \e
451    void setMinimize() {
452      lpx_set_obj_dir(lp, LPX_MIN);
453    }
454    /// \e
455    void setMaximize() {
456      lpx_set_obj_dir(lp, LPX_MAX);
457    }
458
459    //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
460
461  protected:
462    /// \e
463    int _addCol() {
464      return lpx_add_cols(lp, 1);
465    }
466    /// \e
467    int _addRow() {
468      return lpx_add_rows(lp, 1);
469    }
470    /// \e
471    virtual void _setRowCoeffs(int i,
472                               std::vector<std::pair<int, double> > coeffs) {
473      int mem_length=1+colNum();
474      int* indices = new int[mem_length];
475      double* doubles = new double[mem_length];
476      int length=0;
477      for (std::vector<std::pair<int, double> >::
478             const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
479        ++length;
480        indices[length]=it->first;
481        doubles[length]=it->second;
482//      std::cout << "  " << indices[length] << " "
483//                << doubles[length] << std::endl;
484      }
485//      std::cout << i << " " << length << std::endl;
486      lpx_set_mat_row(lp, i, length, indices, doubles);
487      delete [] indices;
488      delete [] doubles;
489    }
490    /// \e
491    virtual void _setColCoeffs(int i,
492                               std::vector<std::pair<int, double> > coeffs) {
493      int mem_length=1+rowNum();
494      int* indices = new int[mem_length];
495      double* doubles = new double[mem_length];
496      int length=0;
497      for (std::vector<std::pair<int, double> >::
498             const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
499        ++length;
500        indices[length]=it->first;
501        doubles[length]=it->second;
502      }
503      lpx_set_mat_col(lp, i, length, indices, doubles);
504      delete [] indices;
505      delete [] doubles;
506    }
507    /// \e
508    virtual void _eraseCol(int i) {
509      int cols[2];
510      cols[1]=i;
511      lpx_del_cols(lp, 1, cols);
512    }
513    virtual void _eraseRow(int i) {
514      int rows[2];
515      rows[1]=i;
516      lpx_del_rows(lp, 1, rows);
517    }
518    virtual void _setColBounds(int i, Bound bound,
519                               double lo, double up) {
520      switch (bound) {
521      case FREE:
522        lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
523        break;
524      case LOWER:
525        lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
526        break;
527      case UPPER:
528        lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
529        break;
530      case DOUBLE:
531        lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
532        break;
533      case FIXED:
534        lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
535        break;
536      }
537    }
538    virtual void _setRowBounds(int i, Bound bound,
539                               double lo, double up) {
540      switch (bound) {
541      case FREE:
542        lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
543        break;
544      case LOWER:
545        lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
546        break;
547      case UPPER:
548        lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
549        break;
550      case DOUBLE:
551        lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
552        break;
553      case FIXED:
554        lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
555        break;
556      }
557    }
558  protected:
559    /// \e
560    virtual double _getObjCoef(int i) {
561      return lpx_get_obj_coef(lp, i);
562    }
563    /// \e
564    virtual void _setObjCoef(int i, double obj_coef) {
565      lpx_set_obj_coef(lp, i, obj_coef);
566    }
567  public:
568    /// \e
569    void solveSimplex() { lpx_simplex(lp); }
570    /// \e
571    void solvePrimalSimplex() { lpx_simplex(lp); }
572    /// \e
573    void solveDualSimplex() { lpx_simplex(lp); }
574    /// \e
575  protected:
576    virtual double _getPrimal(int i) {
577      return lpx_get_col_prim(lp, i);
578    }
579  public:
580    /// \e
581    double getObjVal() { return lpx_get_obj_val(lp); }
582    /// \e
583    int rowNum() const { return lpx_get_num_rows(lp); }
584    /// \e
585    int colNum() const { return lpx_get_num_cols(lp); }
586    /// \e
587    int warmUp() { return lpx_warm_up(lp); }
588    /// \e
589    void printWarmUpStatus(int i) {
590      switch (i) {
591      case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
592      case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;   
593      case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
594      case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
595      }
596    }
597    /// \e
598    int getPrimalStatus() { return lpx_get_prim_stat(lp); }
599    /// \e
600    void printPrimalStatus(int i) {
601      switch (i) {
602      case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
603      case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;     
604      case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
605      case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
606      }
607    }
608    /// \e
609    int getDualStatus() { return lpx_get_dual_stat(lp); }
610    /// \e
611    void printDualStatus(int i) {
612      switch (i) {
613      case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
614      case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;     
615      case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
616      case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
617      }
618    }
619    /// Returns the status of the slack variable assigned to row \c row_it.
620    int getRowStat(const RowIt& row_it) {
621      return lpx_get_row_stat(lp, row_iter_map[row_it]);
622    }
623    /// \e
624    void printRowStatus(int i) {
625      switch (i) {
626      case LPX_BS: cout << "LPX_BS" << endl; break;
627      case LPX_NL: cout << "LPX_NL" << endl; break;     
628      case LPX_NU: cout << "LPX_NU" << endl; break;
629      case LPX_NF: cout << "LPX_NF" << endl; break;
630      case LPX_NS: cout << "LPX_NS" << endl; break;
631      }
632    }
633    /// Returns the status of the variable assigned to column \c col_it.
634    int getColStat(const ColIt& col_it) {
635      return lpx_get_col_stat(lp, col_iter_map[col_it]);
636    }
637    /// \e
638    void printColStatus(int i) {
639      switch (i) {
640      case LPX_BS: cout << "LPX_BS" << endl; break;
641      case LPX_NL: cout << "LPX_NL" << endl; break;     
642      case LPX_NU: cout << "LPX_NU" << endl; break;
643      case LPX_NF: cout << "LPX_NF" << endl; break;
644      case LPX_NS: cout << "LPX_NS" << endl; break;
645      }
646    }
647  };
648 
649  /// @}
650
651} //namespace lemon
652
653#endif //LEMON_LP_SOLVER_WRAPPER_H
Note: See TracBrowser for help on using the repository browser.