COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/lp/lp_solver_wrapper_3.h @ 1100:299d1127a846

Last change on this file since 1100:299d1127a846 was 1100:299d1127a846, checked in by Alpar Juttner, 19 years ago
  • Some things to do.
File size: 18.0 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  \todo A[x,y]-t cserel. Jobboldal, baloldal csere.
177  \todo LEKERDEZESEK!!!
178  \todo DOKSI!!!! Doxygen group!!!
179
180   */
181  template <typename _Value>
182  class LPSolverBase {
183  public:
184    /// \e
185    typedef _Value Value;
186    /// \e
187    typedef IterablePartition<int>::ClassIt RowIt;
188    /// \e
189    typedef IterablePartition<int>::ClassIt ColIt;
190  public:
191    /// \e
192    IterablePartition<int> row_iter_map;
193    /// \e
194    IterablePartition<int> col_iter_map;
195    /// \e
196    const int VALID_CLASS;
197    /// \e
198    const int INVALID_CLASS;
199  public:
200    /// \e
201    LPSolverBase() : row_iter_map(2),
202                     col_iter_map(2),
203                     VALID_CLASS(0), INVALID_CLASS(1) { }
204    /// \e
205    virtual ~LPSolverBase() { }
206
207    //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
208
209  public:
210    /// \e
211    virtual void setMinimize() = 0;
212    /// \e
213    virtual void setMaximize() = 0;
214
215    //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
216
217  protected:
218    /// \e
219    virtual int _addRow() = 0;
220    /// \e
221    virtual int _addCol() = 0;
222    /// \e
223    virtual void _setRowCoeffs(int i,
224                               std::vector<std::pair<int, double> > coeffs) = 0;
225    /// \e
226    virtual void _setColCoeffs(int i,
227                               std::vector<std::pair<int, double> > coeffs) = 0;
228    /// \e
229    virtual void _eraseCol(int i) = 0;
230    /// \e
231    virtual void _eraseRow(int i) = 0;
232  public:
233    /// \e
234    enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
235  protected:
236    /// \e
237    virtual void _setColBounds(int i, Bound bound,
238                               _Value lo, _Value up) = 0;
239    /// \e
240    virtual void _setRowBounds(int i, Bound bound,
241                               _Value lo, _Value up) = 0;
242    /// \e
243    virtual void _setObjCoef(int i, _Value obj_coef) = 0;
244    /// \e
245    virtual _Value _getObjCoef(int i) = 0;
246
247    //LOW LEVEL, SOLUTION RETRIEVING FUNCTIONS
248
249  protected:
250    virtual _Value _getPrimal(int i) = 0;
251
252    //HIGH LEVEL INTERFACE, MATRIX MANIPULATING FUNTIONS
253
254  public:
255    /// \e
256    RowIt addRow() {
257      int i=_addRow();
258      RowIt row_it;
259      row_iter_map.first(row_it, INVALID_CLASS);
260      if (row_iter_map.valid(row_it)) { //van hasznalhato hely
261        row_iter_map.set(row_it, INVALID_CLASS, VALID_CLASS);
262        row_iter_map[row_it]=i;
263      } else { //a cucc vegere kell inzertalni mert nincs szabad hely
264        row_it=row_iter_map.push_back(i, VALID_CLASS);
265      }
266      return row_it;
267    }
268    /// \e
269    ColIt addCol() {
270      int i=_addCol(); 
271      ColIt col_it;
272      col_iter_map.first(col_it, INVALID_CLASS);
273      if (col_iter_map.valid(col_it)) { //van hasznalhato hely
274        col_iter_map.set(col_it, INVALID_CLASS, VALID_CLASS);
275        col_iter_map[col_it]=i;
276      } else { //a cucc vegere kell inzertalni mert nincs szabad hely
277        col_it=col_iter_map.push_back(i, VALID_CLASS);
278      }
279      return col_it;
280    }
281    /// \e
282    template <typename Begin, typename End>
283    void setRowCoeffs(RowIt row_it, Begin begin, End end) {
284      std::vector<std::pair<int, double> > coeffs;
285      for ( ; begin!=end; ++begin) {
286        coeffs.push_back(std::
287                         make_pair(col_iter_map[begin->first], begin->second));
288      }
289      _setRowCoeffs(row_iter_map[row_it], coeffs);
290    }
291    /// \e
292    template <typename Begin, typename End>
293    void setColCoeffs(ColIt col_it, Begin begin, End end) {
294      std::vector<std::pair<int, double> > coeffs;
295      for ( ; begin!=end; ++begin) {
296        coeffs.push_back(std::
297                         make_pair(row_iter_map[begin->first], begin->second));
298      }
299      _setColCoeffs(col_iter_map[col_it], coeffs);
300    }
301    /// \e
302    void eraseCol(const ColIt& col_it) {
303      col_iter_map.set(col_it, VALID_CLASS, INVALID_CLASS);
304      int cols[2];
305      cols[1]=col_iter_map[col_it];
306      _eraseCol(cols[1]);
307      col_iter_map[col_it]=0; //glpk specifikus, de kell ez??
308      ColIt it;
309      for (col_iter_map.first(it, VALID_CLASS);
310           col_iter_map.valid(it); col_iter_map.next(it)) {
311        if (col_iter_map[it]>cols[1]) --col_iter_map[it];
312      }
313    }
314    /// \e
315    void eraseRow(const RowIt& row_it) {
316      row_iter_map.set(row_it, VALID_CLASS, INVALID_CLASS);
317      int rows[2];
318      rows[1]=row_iter_map[row_it];
319      _eraseRow(rows[1]);
320      row_iter_map[row_it]=0; //glpk specifikus, de kell ez??
321      RowIt it;
322      for (row_iter_map.first(it, VALID_CLASS);
323           row_iter_map.valid(it); row_iter_map.next(it)) {
324        if (row_iter_map[it]>rows[1]) --row_iter_map[it];
325      }
326    }
327    /// \e
328    void setColBounds(const ColIt& col_it, Bound bound,
329                      _Value lo, _Value up) {
330      _setColBounds(col_iter_map[col_it], bound, lo, up);
331    }
332    /// \e
333    void setRowBounds(const RowIt& row_it, Bound bound,
334                      _Value lo, _Value up) {
335      _setRowBounds(row_iter_map[row_it], bound, lo, up);
336    }
337    /// \e
338    void setObjCoef(const ColIt& col_it, _Value obj_coef) {
339      _setObjCoef(col_iter_map[col_it], obj_coef);
340    }
341    /// \e
342    _Value getObjCoef(const ColIt& col_it) {
343      return _getObjCoef(col_iter_map[col_it]);
344    }
345
346    //MOST HIGH LEVEL, USER FRIEND FUNCTIONS
347
348    /// \e
349    typedef Expr<ColIt, _Value> Expression;
350    /// \e
351    typedef Expr<RowIt, _Value> DualExpression;
352    /// \e
353    void setRowCoeffs(RowIt row_it, const Expression& expr) {
354      std::vector<std::pair<int, _Value> > row_coeffs;
355      for(typename Expression::Data::const_iterator i=expr.data.begin();
356          i!=expr.data.end(); ++i) {
357        row_coeffs.push_back(std::make_pair
358                             (col_iter_map[(*i).first], (*i).second));
359      }
360      _setRowCoeffs(row_iter_map[row_it], row_coeffs);
361    }
362    /// \e
363    void setColCoeffs(ColIt col_it, const DualExpression& expr) {
364      std::vector<std::pair<int, _Value> > col_coeffs;
365      for(typename DualExpression::Data::const_iterator i=expr.data.begin();
366          i!=expr.data.end(); ++i) {
367        col_coeffs.push_back(std::make_pair
368                             (row_iter_map[(*i).first], (*i).second));
369      }
370      _setColCoeffs(col_iter_map[col_it], col_coeffs);
371    }
372    /// \e
373    void setObjCoeffs(const Expression& expr) {
374      for(typename Expression::Data::const_iterator i=expr.data.begin();
375          i!=expr.data.end(); ++i) {
376        setObjCoef((*i).first, (*i).second);
377      }
378    }
379    //SOLVER FUNCTIONS
380
381    /// \e
382    virtual void solveSimplex() = 0;
383    /// \e
384    virtual void solvePrimalSimplex() = 0;
385    /// \e
386    virtual void solveDualSimplex() = 0;
387    /// \e
388
389    //HIGH LEVEL, SOLUTION RETRIEVING FUNCTIONS
390
391  public:
392    _Value getPrimal(const ColIt& col_it) {
393      return _getPrimal(col_iter_map[col_it]);
394    }
395    /// \e
396    virtual _Value getObjVal() = 0;
397
398    //OTHER FUNCTIONS
399
400    /// \e
401    virtual int rowNum() const = 0;
402    /// \e
403    virtual int colNum() const = 0;
404    /// \e
405    virtual int warmUp() = 0;
406    /// \e
407    virtual void printWarmUpStatus(int i) = 0;
408    /// \e
409    virtual int getPrimalStatus() = 0;
410    /// \e
411    virtual void printPrimalStatus(int i) = 0;
412    /// \e
413    virtual int getDualStatus() = 0;
414    /// \e
415    virtual void printDualStatus(int i) = 0;
416    /// Returns the status of the slack variable assigned to row \c row_it.
417    virtual int getRowStat(const RowIt& row_it) = 0;
418    /// \e
419    virtual void printRowStatus(int i) = 0;
420    /// Returns the status of the variable assigned to column \c col_it.
421    virtual int getColStat(const ColIt& col_it) = 0;
422    /// \e
423    virtual void printColStatus(int i) = 0;
424  };
425 
426
427  /// \brief Wrappers for LP solvers
428  ///
429  /// This class implements a lemon wrapper for glpk.
430  /// Later other LP-solvers will be wrapped into lemon.
431  /// The aim of this class is to give a general surface to different
432  /// solvers, i.e. it makes possible to write algorithms using LP's,
433  /// in which the solver can be changed to an other one easily.
434  class LPGLPK : public LPSolverBase<double> {
435  public:
436    typedef LPSolverBase<double> Parent;
437
438  public:
439    /// \e
440    LPX* lp;
441
442  public:
443    /// \e
444    LPGLPK() : Parent(),
445                        lp(lpx_create_prob()) {
446      lpx_set_int_parm(lp, LPX_K_DUAL, 1);
447    }
448    /// \e
449    ~LPGLPK() {
450      lpx_delete_prob(lp);
451    }
452
453    //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
454
455    /// \e
456    void setMinimize() {
457      lpx_set_obj_dir(lp, LPX_MIN);
458    }
459    /// \e
460    void setMaximize() {
461      lpx_set_obj_dir(lp, LPX_MAX);
462    }
463
464    //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
465
466  protected:
467    /// \e
468    int _addCol() {
469      return lpx_add_cols(lp, 1);
470    }
471    /// \e
472    int _addRow() {
473      return lpx_add_rows(lp, 1);
474    }
475    /// \e
476    virtual void _setRowCoeffs(int i,
477                               std::vector<std::pair<int, double> > coeffs) {
478      int mem_length=1+colNum();
479      int* indices = new int[mem_length];
480      double* doubles = new double[mem_length];
481      int length=0;
482      for (std::vector<std::pair<int, double> >::
483             const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
484        ++length;
485        indices[length]=it->first;
486        doubles[length]=it->second;
487//      std::cout << "  " << indices[length] << " "
488//                << doubles[length] << std::endl;
489      }
490//      std::cout << i << " " << length << std::endl;
491      lpx_set_mat_row(lp, i, length, indices, doubles);
492      delete [] indices;
493      delete [] doubles;
494    }
495    /// \e
496    virtual void _setColCoeffs(int i,
497                               std::vector<std::pair<int, double> > coeffs) {
498      int mem_length=1+rowNum();
499      int* indices = new int[mem_length];
500      double* doubles = new double[mem_length];
501      int length=0;
502      for (std::vector<std::pair<int, double> >::
503             const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
504        ++length;
505        indices[length]=it->first;
506        doubles[length]=it->second;
507      }
508      lpx_set_mat_col(lp, i, length, indices, doubles);
509      delete [] indices;
510      delete [] doubles;
511    }
512    /// \e
513    virtual void _eraseCol(int i) {
514      int cols[2];
515      cols[1]=i;
516      lpx_del_cols(lp, 1, cols);
517    }
518    virtual void _eraseRow(int i) {
519      int rows[2];
520      rows[1]=i;
521      lpx_del_rows(lp, 1, rows);
522    }
523    virtual void _setColBounds(int i, Bound bound,
524                               double lo, double up) {
525      switch (bound) {
526      case FREE:
527        lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
528        break;
529      case LOWER:
530        lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
531        break;
532      case UPPER:
533        lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
534        break;
535      case DOUBLE:
536        lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
537        break;
538      case FIXED:
539        lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
540        break;
541      }
542    }
543    virtual void _setRowBounds(int i, Bound bound,
544                               double lo, double up) {
545      switch (bound) {
546      case FREE:
547        lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
548        break;
549      case LOWER:
550        lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
551        break;
552      case UPPER:
553        lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
554        break;
555      case DOUBLE:
556        lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
557        break;
558      case FIXED:
559        lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
560        break;
561      }
562    }
563  protected:
564    /// \e
565    virtual double _getObjCoef(int i) {
566      return lpx_get_obj_coef(lp, i);
567    }
568    /// \e
569    virtual void _setObjCoef(int i, double obj_coef) {
570      lpx_set_obj_coef(lp, i, obj_coef);
571    }
572  public:
573    /// \e
574    void solveSimplex() { lpx_simplex(lp); }
575    /// \e
576    void solvePrimalSimplex() { lpx_simplex(lp); }
577    /// \e
578    void solveDualSimplex() { lpx_simplex(lp); }
579    /// \e
580  protected:
581    virtual double _getPrimal(int i) {
582      return lpx_get_col_prim(lp, i);
583    }
584  public:
585    /// \e
586    double getObjVal() { return lpx_get_obj_val(lp); }
587    /// \e
588    int rowNum() const { return lpx_get_num_rows(lp); }
589    /// \e
590    int colNum() const { return lpx_get_num_cols(lp); }
591    /// \e
592    int warmUp() { return lpx_warm_up(lp); }
593    /// \e
594    void printWarmUpStatus(int i) {
595      switch (i) {
596      case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
597      case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;   
598      case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
599      case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
600      }
601    }
602    /// \e
603    int getPrimalStatus() { return lpx_get_prim_stat(lp); }
604    /// \e
605    void printPrimalStatus(int i) {
606      switch (i) {
607      case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
608      case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;     
609      case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
610      case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
611      }
612    }
613    /// \e
614    int getDualStatus() { return lpx_get_dual_stat(lp); }
615    /// \e
616    void printDualStatus(int i) {
617      switch (i) {
618      case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
619      case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;     
620      case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
621      case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
622      }
623    }
624    /// Returns the status of the slack variable assigned to row \c row_it.
625    int getRowStat(const RowIt& row_it) {
626      return lpx_get_row_stat(lp, row_iter_map[row_it]);
627    }
628    /// \e
629    void printRowStatus(int i) {
630      switch (i) {
631      case LPX_BS: cout << "LPX_BS" << endl; break;
632      case LPX_NL: cout << "LPX_NL" << endl; break;     
633      case LPX_NU: cout << "LPX_NU" << endl; break;
634      case LPX_NF: cout << "LPX_NF" << endl; break;
635      case LPX_NS: cout << "LPX_NS" << endl; break;
636      }
637    }
638    /// Returns the status of the variable assigned to column \c col_it.
639    int getColStat(const ColIt& col_it) {
640      return lpx_get_col_stat(lp, col_iter_map[col_it]);
641    }
642    /// \e
643    void printColStatus(int i) {
644      switch (i) {
645      case LPX_BS: cout << "LPX_BS" << endl; break;
646      case LPX_NL: cout << "LPX_NL" << endl; break;     
647      case LPX_NU: cout << "LPX_NU" << endl; break;
648      case LPX_NF: cout << "LPX_NF" << endl; break;
649      case LPX_NS: cout << "LPX_NS" << endl; break;
650      }
651    }
652  };
653 
654  /// @}
655
656} //namespace lemon
657
658#endif //LEMON_LP_SOLVER_WRAPPER_H
Note: See TracBrowser for help on using the repository browser.