COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/lp/lp_solver_glpk.h @ 1260:d8491fce6751

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