COIN-OR::LEMON - Graph Library

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

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

RoadMap? to more general flow algs.

File size: 12.2 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  /// \brief Wrappers for LP solvers
161  ///
162  /// This class implements a lemon wrapper for glpk.
163  /// Later other LP-solvers will be wrapped into lemon.
164  /// The aim of this class is to give a general surface to different
165  /// solvers, i.e. it makes possible to write algorithms using LP's,
166  /// in which the solver can be changed to an other one easily.
167  class LPSolverWrapper {
168  public:
169
170//   class Row {
171//   protected:
172//     int i;
173//   public:
174//     Row() { }
175//     Row(const Invalid&) : i(0) { }
176//     Row(const int& _i) : i(_i) { }
177//     operator int() const { return i; }
178//   };
179//   class RowIt : public Row {
180//   public:
181//     RowIt(const Row& row) : Row(row) { }
182//   };
183
184//   class Col {
185//   protected:
186//     int i;
187//   public:
188//     Col() { }
189//     Col(const Invalid&) : i(0) { }
190//     Col(const int& _i) : i(_i) { }
191//     operator int() const { return i; }
192//   };
193//   class ColIt : public Col {
194//     ColIt(const Col& col) : Col(col) { }
195//   };
196
197  public:
198    ///.
199    LPX* lp;
200    ///.
201    typedef IterablePartition<int>::ClassIt RowIt;
202    ///.
203    IterablePartition<int> row_iter_map;
204    ///.
205    typedef IterablePartition<int>::ClassIt ColIt;
206    ///.
207    IterablePartition<int> col_iter_map;
208    //std::vector<int> row_id_to_lp_row_id;
209    //std::vector<int> col_id_to_lp_col_id;
210    ///.
211    const int VALID_ID;
212    ///.
213    const int INVALID_ID;
214
215  public:
216    ///.
217    LPSolverWrapper() : lp(lpx_create_prob()),
218                        row_iter_map(2),
219                        col_iter_map(2),
220                        //row_id_to_lp_row_id(), col_id_to_lp_col_id(),
221                        VALID_ID(0), INVALID_ID(1) {
222      lpx_set_int_parm(lp, LPX_K_DUAL, 1);
223    }
224    ///.
225    ~LPSolverWrapper() {
226      lpx_delete_prob(lp);
227    }
228    ///.
229    void setMinimize() {
230      lpx_set_obj_dir(lp, LPX_MIN);
231    }
232    ///.
233    void setMaximize() {
234      lpx_set_obj_dir(lp, LPX_MAX);
235    }
236    ///.
237    ColIt addCol() {
238      int i=lpx_add_cols(lp, 1); 
239      ColIt col_it;
240      col_iter_map.first(col_it, INVALID_ID);
241      if (col_iter_map.valid(col_it)) { //van hasznalhato hely
242        col_iter_map.set(col_it, INVALID_ID, VALID_ID);
243        col_iter_map[col_it]=i;
244        //col_id_to_lp_col_id[col_iter_map[col_it]]=i;
245      } else { //a cucc vegere kell inzertalni mert nincs szabad hely
246        //col_id_to_lp_col_id.push_back(i);
247        //int j=col_id_to_lp_col_id.size()-1;
248        col_it=col_iter_map.push_back(i, VALID_ID);
249      }
250//    edge_index_map.set(e, i);
251//    lpx_set_col_bnds(lp, i, LPX_DB, 0.0, 1.0);
252//    lpx_set_obj_coef(lp, i, cost[e]);   
253      return col_it;
254    }
255    ///.
256    RowIt addRow() {
257      int i=lpx_add_rows(lp, 1); 
258      RowIt row_it;
259      row_iter_map.first(row_it, INVALID_ID);
260      if (row_iter_map.valid(row_it)) { //van hasznalhato hely
261        row_iter_map.set(row_it, INVALID_ID, VALID_ID);
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_ID);
265      }
266      return row_it;
267    }
268    //pair<RowIt, double>-bol kell megadni egy std range-et
269    ///.
270    template <typename Begin, typename End>
271    void setColCoeffs(const ColIt& col_it,
272                      Begin begin, End end) {
273      int mem_length=1+lpx_get_num_rows(lp);
274      int* indices = new int[mem_length];
275      double* doubles = new double[mem_length];
276      int length=0;
277      for ( ; begin!=end; ++begin) {
278        ++length;
279        indices[length]=row_iter_map[begin->first];
280        doubles[length]=begin->second;
281      }
282      lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles);
283      delete [] indices;
284      delete [] doubles;
285    }
286    //pair<ColIt, double>-bol kell megadni egy std range-et
287    ///.
288    template <typename Begin, typename End>
289    void setRowCoeffs(const RowIt& row_it,
290                      Begin begin, End end) {
291      int mem_length=1+lpx_get_num_cols(lp);
292      int* indices = new int[mem_length];
293      double* doubles = new double[mem_length];
294      int length=0;
295      for ( ; begin!=end; ++begin) {
296        ++length;
297        indices[length]=col_iter_map[begin->first];
298        doubles[length]=begin->second;
299      }
300      lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles);
301      delete [] indices;
302      delete [] doubles;
303    }
304    ///.
305    void eraseCol(const ColIt& col_it) {
306      col_iter_map.set(col_it, VALID_ID, INVALID_ID);
307      int cols[2];
308      cols[1]=col_iter_map[col_it];
309      lpx_del_cols(lp, 1, cols);
310      col_iter_map[col_it]=0; //glpk specifikus
311      ColIt it;
312      for (col_iter_map.first(it, VALID_ID);
313           col_iter_map.valid(it); col_iter_map.next(it)) {
314        if (col_iter_map[it]>cols[1]) --col_iter_map[it];
315      }
316    }
317    ///.
318    void eraseRow(const RowIt& row_it) {
319      row_iter_map.set(row_it, VALID_ID, INVALID_ID);
320      int rows[2];
321      rows[1]=row_iter_map[row_it];
322      lpx_del_rows(lp, 1, rows);
323      row_iter_map[row_it]=0; //glpk specifikus
324      RowIt it;
325      for (row_iter_map.first(it, VALID_ID);
326           row_iter_map.valid(it); row_iter_map.next(it)) {
327        if (row_iter_map[it]>rows[1]) --row_iter_map[it];
328      }
329    }
330    ///.
331    void setColBounds(const ColIt& col_it, int bound_type,
332                      double lo, double up) {
333      lpx_set_col_bnds(lp, col_iter_map[col_it], bound_type, lo, up);
334    }
335    ///.
336    double getObjCoef(const ColIt& col_it) {
337      return lpx_get_obj_coef(lp, col_iter_map[col_it]);
338    }
339    ///.
340    void setRowBounds(const RowIt& row_it, int bound_type,
341                      double lo, double up) {
342      lpx_set_row_bnds(lp, row_iter_map[row_it], bound_type, lo, up);
343    }
344    ///.
345    void setObjCoef(const ColIt& col_it, double obj_coef) {
346      lpx_set_obj_coef(lp, col_iter_map[col_it], obj_coef);
347    }
348    ///.
349    void solveSimplex() { lpx_simplex(lp); }
350    ///.
351    void solvePrimalSimplex() { lpx_simplex(lp); }
352    ///.
353    void solveDualSimplex() { lpx_simplex(lp); }
354    ///.
355    double getPrimal(const ColIt& col_it) {
356      return lpx_get_col_prim(lp, col_iter_map[col_it]);
357    }
358    ///.
359    double getObjVal() { return lpx_get_obj_val(lp); }
360    ///.
361    int rowNum() const { return lpx_get_num_rows(lp); }
362    ///.
363    int colNum() const { return lpx_get_num_cols(lp); }
364    ///.
365    int warmUp() { return lpx_warm_up(lp); }
366    ///.
367    void printWarmUpStatus(int i) {
368      switch (i) {
369        case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
370        case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;
371        case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
372        case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
373      }
374    }
375    ///.
376    int getPrimalStatus() { return lpx_get_prim_stat(lp); }
377    ///.
378    void printPrimalStatus(int i) {
379      switch (i) {
380        case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
381        case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;   
382        case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
383        case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
384      }
385    }
386    ///.
387    int getDualStatus() { return lpx_get_dual_stat(lp); }
388    ///.
389    void printDualStatus(int i) {
390      switch (i) {
391        case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
392        case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;   
393        case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
394        case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
395      }
396    }
397    /// Returns the status of the slack variable assigned to row \c row_it.
398    int getRowStat(const RowIt& row_it) {
399      return lpx_get_row_stat(lp, row_iter_map[row_it]);
400    }
401    ///.
402    void printRowStatus(int i) {
403      switch (i) {
404        case LPX_BS: cout << "LPX_BS" << endl; break;
405        case LPX_NL: cout << "LPX_NL" << endl; break;   
406        case LPX_NU: cout << "LPX_NU" << endl; break;
407        case LPX_NF: cout << "LPX_NF" << endl; break;
408        case LPX_NS: cout << "LPX_NS" << endl; break;
409      }
410    }
411    /// Returns the status of the variable assigned to column \c col_it.
412    int getColStat(const ColIt& col_it) {
413      return lpx_get_col_stat(lp, col_iter_map[col_it]);
414    }
415    ///.
416    void printColStatus(int i) {
417      switch (i) {
418        case LPX_BS: cout << "LPX_BS" << endl; break;
419        case LPX_NL: cout << "LPX_NL" << endl; break;   
420        case LPX_NU: cout << "LPX_NU" << endl; break;
421        case LPX_NF: cout << "LPX_NF" << endl; break;
422        case LPX_NS: cout << "LPX_NS" << endl; break;
423      }
424    }
425  };
426 
427  /// @}
428
429} //namespace lemon
430
431#endif //LEMON_LP_SOLVER_WRAPPER_H
Note: See TracBrowser for help on using the repository browser.