COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/lp/lp_solver_wrapper_3.h @ 1074:4a24a46407db

Last change on this file since 1074:4a24a46407db was 1074:4a24a46407db, checked in by marci, 20 years ago

:-}

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