COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/lp_old/lp_solver_glpk.h @ 1244:43a3d06e0ee0

Last change on this file since 1244:43a3d06e0ee0 was 1244:43a3d06e0ee0, checked in by athos, 15 years ago
File size: 12.9 KB
RevLine 
[1241]1// -*- c++ -*-
2#ifndef LEMON_LP_SOLVER_GLPK_H
3#define LEMON_LP_SOLVER_GLPK_H
4
5///\ingroup misc
6///\file
7
8// #include <stdio.h>
9/* #include <stdlib.h> */
10/* #include <iostream> */
11/* #include <map> */
12/* #include <limits> */
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 <lemon/invalid.h>
27//#include <expression.h>
28#include <lp_solver_base.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  template <typename Value>
42  const Value LpSolverBase<Value>::INF=std::numeric_limits<Value>::infinity();
43
44
45  /// \brief Wrapper for GLPK solver
46  ///
47  /// This class implements a lemon wrapper for GLPK.
48  class LpGlpk : public LpSolverBase<double> {
49  public:
50    typedef LpSolverBase<double> Parent;
51
52  public:
53    /// \e
54    LPX* lp;
55
56  public:
57    /// \e
58    LpGlpk() : Parent(),
59                        lp(lpx_create_prob()) {
60      int_row_map.push_back(Row());
61      int_col_map.push_back(Col());
62      lpx_set_int_parm(lp, LPX_K_DUAL, 1);
63    }
64    /// \e
65    ~LpGlpk() {
66      lpx_delete_prob(lp);
67    }
68
69    //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
70
71    /// \e
72    void setMinimize() {
73      lpx_set_obj_dir(lp, LPX_MIN);
74    }
75    /// \e
76    void setMaximize() {
77      lpx_set_obj_dir(lp, LPX_MAX);
78    }
79
80    //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
81
82  protected:
83    /// \e
84    int _addCol() {
85      int i=lpx_add_cols(lp, 1);
86      _setColLowerBound(i, -INF);
87      _setColUpperBound(i, INF);
88      return i;
89    }
90    /// \e
91    int _addRow() {
92      int i=lpx_add_rows(lp, 1);
93      return i;
94    }
95    /// \e
96    virtual void _setRowCoeffs(int i,
97                               const std::vector<std::pair<int, double> >& coeffs) {
98      int mem_length=1+colNum();
99      int* indices = new int[mem_length];
100      double* doubles = new double[mem_length];
101      int length=0;
102      for (std::vector<std::pair<int, double> >::
103             const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
104        ++length;
105        indices[length]=it->first;
106        doubles[length]=it->second;
107      }
108      lpx_set_mat_row(lp, i, length, indices, doubles);
109      delete [] indices;
110      delete [] doubles;
111    }
112    /// \e
113    virtual void _getRowCoeffs(int i,
114                               std::vector<std::pair<int, double> >& coeffs) {
115      int mem_length=1+colNum();
116      int* indices = new int[mem_length];
117      double* doubles = new double[mem_length];
118      int length=lpx_get_mat_row(lp, i, indices, doubles);
119      for (int i=1; i<=length; ++i) {
120        coeffs.push_back(std::make_pair(indices[i], doubles[i]));
121      }
122      delete [] indices;
123      delete [] doubles;
124    }
125    /// \e
126    virtual void _setColCoeffs(int i,
127                               const std::vector<std::pair<int, double> >& coeffs) {
128      int mem_length=1+rowNum();
129      int* indices = new int[mem_length];
130      double* doubles = new double[mem_length];
131      int length=0;
132      for (std::vector<std::pair<int, double> >::
133             const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
134        ++length;
135        indices[length]=it->first;
136        doubles[length]=it->second;
137      }
138      lpx_set_mat_col(lp, i, length, indices, doubles);
139      delete [] indices;
140      delete [] doubles;
141    }
142    /// \e
143    virtual void _getColCoeffs(int i,
144                               std::vector<std::pair<int, double> >& coeffs) {
145      int mem_length=1+rowNum();
146      int* indices = new int[mem_length];
147      double* doubles = new double[mem_length];
148      int length=lpx_get_mat_col(lp, i, indices, doubles);
149      for (int i=1; i<=length; ++i) {
150        coeffs.push_back(std::make_pair(indices[i], doubles[i]));
151      }
152      delete [] indices;
153      delete [] doubles;
154    }
155    /// \e
156    virtual void _eraseCol(int i) {
157      int cols[2];
158      cols[1]=i;
159      lpx_del_cols(lp, 1, cols);
160    }
161    virtual void _eraseRow(int i) {
162      int rows[2];
163      rows[1]=i;
164      lpx_del_rows(lp, 1, rows);
165    }
166    void _setCoeff(int col, int row, double value) {
[1243]167      ///FIXME Of course this is not efficient at all, but GLPK knows not more.
168      int change_this;
169      bool get_set_row;
170      //The only thing we can do is optimize on whether working with a row
171      //or a coloumn
172      int row_num = rowNum();
173      int col_num = colNum();
174      if (col_num<row_num){
175        //There are more rows than coloumns
176        get_set_row=true;
177        int mem_length=1+row_num;
178        int* indices = new int[mem_length];
179        double* doubles = new double[mem_length];
180        int length=lpx_get_mat_col(lp, i, indices, doubles);
181      }else{
182        get_set_row=false;
183        int mem_length=1+col_num;
184        int* indices = new int[mem_length];
185        double* doubles = new double[mem_length];
186        int length=lpx_get_mat_row(lp, i, indices, doubles);
187      }
188      //Itten     
189int* indices = new int[mem_length];
190      double* doubles = new double[mem_length];
191      int length=lpx_get_mat_col(lp, i, indices, doubles);
192 
193      delete [] indices;
194      delete [] doubles;
195
[1241]196    }
197    double _getCoeff(int col, int row) {
198      /// FIXME not yet implemented
199      return 0.0;
200    }
201    virtual void _setColLowerBound(int i, double lo) {
202      if (lo==INF) {
203        //FIXME error
204      }
205      int b=lpx_get_col_type(lp, i);
206      double up=lpx_get_col_ub(lp, i); 
207      if (lo==-INF) {
208        switch (b) {
209        case LPX_FR:
210        case LPX_LO:
211          lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
212          break;
213        case LPX_UP:
214          break;
215        case LPX_DB:
216        case LPX_FX:
217          lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
218          break;
219        default: ;
220          //FIXME error
221        }
222      } else {
223        switch (b) {
224        case LPX_FR:
225        case LPX_LO:
226          lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
227          break;
228        case LPX_UP:     
229        case LPX_DB:
230        case LPX_FX:
231          if (lo==up)
232            lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
233          else
234            lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
235          break;
236        default: ;
237          //FIXME error
238        }
239      }
240    }
241    virtual double _getColLowerBound(int i) {
242      int b=lpx_get_col_type(lp, i);
243      switch (b) {
244      case LPX_FR:
245        return -INF;
246      case LPX_LO:
247        return lpx_get_col_lb(lp, i);
248      case LPX_UP:
249        return -INF;
250      case LPX_DB:
251      case LPX_FX:
252        return lpx_get_col_lb(lp, i);
253      default: ;
254        //FIXME error
255        return 0.0;
256      }
257    }
258    virtual void _setColUpperBound(int i, double up) {
259      if (up==-INF) {
260        //FIXME error
261      }
262      int b=lpx_get_col_type(lp, i);
263      double lo=lpx_get_col_lb(lp, i);
264      if (up==INF) {
265        switch (b) {
266        case LPX_FR:
267        case LPX_LO:
268          break;
269        case LPX_UP:
270          lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
271          break;
272        case LPX_DB:
273        case LPX_FX:
274          lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
275          break;
276        default: ;
277          //FIXME error
278        }
279      } else {
280        switch (b) {
281        case LPX_FR:
282          lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
283        case LPX_LO:
284          if (lo==up)
285            lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
286          else
287            lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
288          break;
289        case LPX_UP:
290          lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
291          break;
292        case LPX_DB:
293        case LPX_FX:
294          if (lo==up)
295            lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
296          else
297            lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
298          break;
299        default: ;
300          //FIXME error
301        }
302      }
303    }
304    virtual double _getColUpperBound(int i) {
305      int b=lpx_get_col_type(lp, i);
306      switch (b) {
307      case LPX_FR:
308      case LPX_LO:
309        return INF;
310      case LPX_UP:
311      case LPX_DB:
312      case LPX_FX:
313        return lpx_get_col_ub(lp, i);
314      default: ;
315        //FIXME error
316        return 0.0;
317      }
318    }
319    virtual void _setRowLowerBound(int i, double lo) {
320      if (lo==INF) {
321        //FIXME error
322      }
323      int b=lpx_get_row_type(lp, i);
324      double up=lpx_get_row_ub(lp, i); 
325      if (lo==-INF) {
326        switch (b) {
327        case LPX_FR:
328        case LPX_LO:
329          lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
330          break;
331        case LPX_UP:
332          break;
333        case LPX_DB:
334        case LPX_FX:
335          lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
336          break;
337        default: ;
338          //FIXME error
339        }
340      } else {
341        switch (b) {
342        case LPX_FR:
343        case LPX_LO:
344          lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
345          break;
346        case LPX_UP:     
347        case LPX_DB:
348        case LPX_FX:
349          if (lo==up)
350            lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
351          else
352            lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
353          break;
354        default: ;
355          //FIXME error
356        }
357      }
358    }
359    virtual double _getRowLowerBound(int i) {
360      int b=lpx_get_row_type(lp, i);
361      switch (b) {
362      case LPX_FR:
363        return -INF;
364      case LPX_LO:
365        return lpx_get_row_lb(lp, i);
366      case LPX_UP:
367        return -INF;
368      case LPX_DB:
369      case LPX_FX:
370        return lpx_get_row_lb(lp, i);
371      default: ;
372        //FIXME error
373        return 0.0;
374      }
375    }
376    virtual void _setRowUpperBound(int i, double up) {
377      if (up==-INF) {
378        //FIXME error
379      }
380      int b=lpx_get_row_type(lp, i);
381      double lo=lpx_get_row_lb(lp, i);
382      if (up==INF) {
383        switch (b) {
384        case LPX_FR:
385        case LPX_LO:
386          break;
387        case LPX_UP:
388          lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
389          break;
390        case LPX_DB:
391        case LPX_FX:
392          lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
393          break;
394        default: ;
395          //FIXME error
396        }
397      } else {
398        switch (b) {
399        case LPX_FR:
400          lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
401        case LPX_LO:
402          if (lo==up)
403            lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
404          else
405            lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
406          break;
407        case LPX_UP:
408          lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
409          break;
410        case LPX_DB:
411        case LPX_FX:
412          if (lo==up)
413            lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
414          else
415            lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
416          break;
417        default: ;
418          //FIXME error
419        }
420      }
421    }
422    virtual double _getRowUpperBound(int i) {
423      int b=lpx_get_row_type(lp, i);
424      switch (b) {
425      case LPX_FR:
426      case LPX_LO:
427        return INF;
428      case LPX_UP:
429      case LPX_DB:
430      case LPX_FX:
431        return lpx_get_row_ub(lp, i);
432      default: ;
433        //FIXME error
434        return 0.0;
435      }
436    }
437    /// \e
438    virtual double _getObjCoeff(int i) {
439      return lpx_get_obj_coef(lp, i);
440    }
441    /// \e
442    virtual void _setObjCoeff(int i, double obj_coef) {
443      lpx_set_obj_coef(lp, i, obj_coef);
444    }
445  public:
446    /// \e
447    void solveSimplex() { lpx_simplex(lp); }
448    /// \e
449    void solvePrimalSimplex() { lpx_simplex(lp); }
450    /// \e
451    void solveDualSimplex() { lpx_simplex(lp); }
452  protected:
453    virtual double _getPrimal(int i) {
454      return lpx_get_col_prim(lp, i);
455    }
456  public:
457    /// \e
458    double getObjVal() { return lpx_get_obj_val(lp); }
459    /// \e
460    int rowNum() const { return lpx_get_num_rows(lp); }
461    /// \e
462    int colNum() const { return lpx_get_num_cols(lp); }
463    /// \e
464    int warmUp() { return lpx_warm_up(lp); }
465    /// \e
466    void printWarmUpStatus(int i) {
467      switch (i) {
468      case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
469      case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;   
470      case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
471      case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
472      }
473    }
474    /// \e
475    int getPrimalStatus() { return lpx_get_prim_stat(lp); }
476    /// \e
477    void printPrimalStatus(int i) {
478      switch (i) {
479      case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
480      case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;     
481      case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
482      case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
483      }
484    }
485    /// \e
486    int getDualStatus() { return lpx_get_dual_stat(lp); }
487    /// \e
488    void printDualStatus(int i) {
489      switch (i) {
490      case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
491      case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;     
492      case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
493      case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
494      }
495    }
496    /// Returns the status of the slack variable assigned to row \c row.
497    int getRowStat(const Row& row) {
498      return lpx_get_row_stat(lp, row_iter_map[row]);
499    }
500    /// \e
501    void printRowStatus(int i) {
502      switch (i) {
503      case LPX_BS: cout << "LPX_BS" << endl; break;
504      case LPX_NL: cout << "LPX_NL" << endl; break;     
505      case LPX_NU: cout << "LPX_NU" << endl; break;
506      case LPX_NF: cout << "LPX_NF" << endl; break;
507      case LPX_NS: cout << "LPX_NS" << endl; break;
508      }
509    }
510    /// Returns the status of the variable assigned to column \c col.
511    int getColStat(const Col& col) {
512      return lpx_get_col_stat(lp, col_iter_map[col]);
513    }
514    /// \e
515    void printColStatus(int i) {
516      switch (i) {
517      case LPX_BS: cout << "LPX_BS" << endl; break;
518      case LPX_NL: cout << "LPX_NL" << endl; break;     
519      case LPX_NU: cout << "LPX_NU" << endl; break;
520      case LPX_NF: cout << "LPX_NF" << endl; break;
521      case LPX_NS: cout << "LPX_NS" << endl; break;
522      }
523    }
524
525    // MIP
526    /// \e
527    void solveBandB() { lpx_integer(lp); }
528    /// \e
529    void setLP() { lpx_set_class(lp, LPX_LP); }
530    /// \e
531    void setMIP() { lpx_set_class(lp, LPX_MIP); }
532  protected:
533    /// \e
534    void _setColCont(int i) { lpx_set_col_kind(lp, i, LPX_CV); }
535    /// \e
536    void _setColInt(int i) { lpx_set_col_kind(lp, i, LPX_IV); }
537    /// \e
538    double _getMIPPrimal(int i) { return lpx_mip_col_val(lp, i); }
539  };
540 
541  /// @}
542
543} //namespace lemon
544
545#endif //LEMON_LP_SOLVER_GLPK_H
Note: See TracBrowser for help on using the repository browser.