COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/lp/lp_solver_wrapper_3.h @ 1081:c0ad2673b11f

Last change on this file since 1081:c0ad2673b11f was 1081:c0ad2673b11f, checked in by marci, 15 years ago

more precise distinction 'tween low and high level lp interfaces

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