COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_glpk.cc @ 2320:4e8ecce96b12

Last change on this file since 2320:4e8ecce96b12 was 2312:07e46cbb7d85, checked in by Balazs Dezso, 14 years ago

modified _setColCoeff and _setRowCoeff parameters
const simplify() for expressions

File size: 12.3 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19///\file
20///\brief Implementation of the LEMON-GLPK lp solver interface.
21
22#include <lemon/lp_glpk.h>
23//#include <iostream>
24namespace lemon {
25
26
27  LpGlpk::LpGlpk() : Parent(),
28                     lp(lpx_create_prob()) {
29    ///\todo constrol function for this:
30    lpx_set_int_parm(lp, LPX_K_DUAL, 1);
31    messageLevel(0);
32  }
33 
34  LpGlpk::~LpGlpk() {
35    lpx_delete_prob(lp);
36  }
37 
38  int LpGlpk::_addCol() {
39    int i=lpx_add_cols(lp, 1);
40    _setColLowerBound(i, -INF);
41    _setColUpperBound(i, INF);
42    return i;
43  }
44
45  ///\e
46
47
48  LpSolverBase &LpGlpk::_newLp()
49  {
50    LpGlpk* newlp=new LpGlpk();
51    return *newlp;
52  }
53 
54  ///\e
55
56  LpSolverBase &LpGlpk::_copyLp()
57  {
58    LpGlpk* newlp=new LpGlpk();
59
60    //Coefficient matrix, row bounds
61    lpx_add_rows(newlp->lp, lpx_get_num_rows(lp));
62    lpx_add_cols(newlp->lp, lpx_get_num_cols(lp));
63    int len;
64    int ind[1+lpx_get_num_cols(lp)];
65    Value val[1+lpx_get_num_cols(lp)];
66    for (int i=1;i<=lpx_get_num_rows(lp);++i){
67      len=lpx_get_mat_row(lp,i,ind,val);
68      lpx_set_mat_row(newlp->lp, i,len,ind,val);
69      lpx_set_row_bnds(newlp->lp,i,lpx_get_row_type(lp,i),
70                       lpx_get_row_lb(lp,i),lpx_get_row_ub(lp,i));
71    }
72
73    //Objective function, coloumn bounds
74    lpx_set_obj_dir(newlp->lp, lpx_get_obj_dir(lp));
75    //Objectif function's constant term treated separately
76    lpx_set_obj_coef(newlp->lp,0,lpx_get_obj_coef(lp,0));
77    for (int i=1;i<=lpx_get_num_cols(lp);++i){
78      lpx_set_obj_coef(newlp->lp,i,lpx_get_obj_coef(lp,i));
79      lpx_set_col_bnds(newlp->lp,i,lpx_get_col_type(lp,i),
80                       lpx_get_col_lb(lp,i),lpx_get_col_ub(lp,i));
81     
82     
83    }
84
85    return *newlp;
86  }
87
88  int LpGlpk::_addRow() {
89    int i=lpx_add_rows(lp, 1);
90    return i;
91  }
92
93 
94  void LpGlpk::_eraseCol(int i) {
95    int cols[2];
96    cols[1]=i;
97    lpx_del_cols(lp, 1, cols);
98  }
99 
100  void LpGlpk::_eraseRow(int i) {
101    int rows[2];
102    rows[1]=i;
103    lpx_del_rows(lp, 1, rows);
104  }
105
106  void LpGlpk::_getColName(int col, std::string & name)
107  {
108   
109    char *n = lpx_get_col_name(lp,col);
110    name = n?n:"";
111  }
112 
113 
114  void LpGlpk::_setColName(int col, const std::string & name)
115  {
116    lpx_set_col_name(lp,col,const_cast<char*>(name.c_str()));
117  }
118 
119  void LpGlpk::_setRowCoeffs(int i, LpRowIterator b, LpRowIterator e)
120  {
121    std::vector<int> indices;
122    std::vector<Value> values;
123
124    indices.push_back(0);
125    values.push_back(0);
126
127    for(LpRowIterator it=b; it!=e; ++it) {
128      indices.push_back(it->first);
129      values.push_back(it->second);
130    }
131
132    lpx_set_mat_row(lp, i, values.size() - 1, &indices[0], &values[0]);
133  }
134 
135  void LpGlpk::_setColCoeffs(int i, LpColIterator b, LpColIterator e) {
136
137    std::vector<int> indices;
138    std::vector<Value> values;
139
140    indices.push_back(0);
141    values.push_back(0);
142
143    for(LpColIterator it=b; it!=e; ++it) {
144      indices.push_back(it->first);
145      values.push_back(it->second);
146    }
147   
148    lpx_set_mat_col(lp, i, values.size() - 1, &indices[0], &values[0]);
149  }
150
151
152  void LpGlpk::_setCoeff(int row, int col, Value value)
153  {
154
155    if (lpx_get_num_cols(lp) < lpx_get_num_rows(lp)) {
156
157      int length=lpx_get_mat_row(lp, row, 0, 0);
158     
159      std::vector<int> indices(length + 2);
160      std::vector<Value> values(length + 2);
161     
162      lpx_get_mat_row(lp, row, &indices[0], &values[0]);
163     
164      //The following code does not suppose that the elements of the
165      //array indices are sorted
166      bool found=false;
167      for (int i = 1; i <= length; ++i) {
168        if (indices[i]==col){
169          found=true;
170          values[i]=value;
171          break;
172        }
173      }
174      if (!found){
175        ++length;
176        indices[length]=col;
177        values[length]=value;
178      }
179   
180      lpx_set_mat_row(lp, row, length, &indices[0], &values[0]);
181
182    } else {
183
184      int length=lpx_get_mat_col(lp, col, 0, 0);
185     
186      std::vector<int> indices(length + 2);
187      std::vector<Value> values(length + 2);
188     
189      lpx_get_mat_col(lp, col, &indices[0], &values[0]);
190     
191      //The following code does not suppose that the elements of the
192      //array indices are sorted
193      bool found=false;
194      for (int i = 1; i <= length; ++i) {
195        if (indices[i]==col){
196          found=true;
197          values[i]=value;
198          break;
199        }
200      }
201      if (!found){
202        ++length;
203        indices[length]=row;
204        values[length]=value;
205      }
206   
207      lpx_set_mat_col(lp, col, length, &indices[0], &values[0]);
208    }
209  }
210
211  void LpGlpk::_setColLowerBound(int i, Value lo)
212  {
213    if (lo==INF) {
214      //FIXME error
215    }
216    int b=lpx_get_col_type(lp, i);
217    double up=lpx_get_col_ub(lp, i);   
218    if (lo==-INF) {
219      switch (b) {
220      case LPX_FR:
221      case LPX_LO:
222        lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
223        break;
224      case LPX_UP:
225        break;
226      case LPX_DB:
227      case LPX_FX:
228        lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
229        break;
230      default: ;
231        //FIXME error
232      }
233    } else {
234      switch (b) {
235      case LPX_FR:
236      case LPX_LO:
237        lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
238        break;
239      case LPX_UP:       
240      case LPX_DB:
241      case LPX_FX:
242        if (lo==up)
243          lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
244        else
245          lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
246        break;
247      default: ;
248        //FIXME error
249      }
250    }
251
252  }
253 
254  void LpGlpk::_setColUpperBound(int i, Value up)
255  {
256    if (up==-INF) {
257      //FIXME error
258    }
259    int b=lpx_get_col_type(lp, i);
260    double lo=lpx_get_col_lb(lp, i);
261    if (up==INF) {
262      switch (b) {
263      case LPX_FR:
264      case LPX_LO:
265        break;
266      case LPX_UP:
267        lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
268        break;
269      case LPX_DB:
270      case LPX_FX:
271        lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
272        break;
273      default: ;
274        //FIXME error
275      }
276    } else {
277      switch (b) {
278      case LPX_FR:
279        lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
280        break;
281      case LPX_UP:
282        lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
283        break;
284      case LPX_LO:
285      case LPX_DB:
286      case LPX_FX:
287        if (lo==up)
288          lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
289        else
290          lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
291        break;
292      default: ;
293        //FIXME error
294      }
295    }
296  }
297 
298//   void LpGlpk::_setRowLowerBound(int i, Value lo)
299//   {
300//     if (lo==INF) {
301//       //FIXME error
302//     }
303//     int b=lpx_get_row_type(lp, i);
304//     double up=lpx_get_row_ub(lp, i);
305//     if (lo==-INF) {
306//       switch (b) {
307//       case LPX_FR:
308//       case LPX_LO:
309//      lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
310//      break;
311//       case LPX_UP:
312//      break;
313//       case LPX_DB:
314//       case LPX_FX:
315//      lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
316//      break;
317//       default: ;
318//      //FIXME error
319//       }
320//     } else {
321//       switch (b) {
322//       case LPX_FR:
323//       case LPX_LO:
324//      lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
325//      break;
326//       case LPX_UP:     
327//       case LPX_DB:
328//       case LPX_FX:
329//      if (lo==up)
330//        lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
331//      else
332//        lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
333//      break;
334//       default: ;
335//      //FIXME error
336//       }
337//     }
338//   }
339 
340//   void LpGlpk::_setRowUpperBound(int i, Value up)
341//   {
342//     if (up==-INF) {
343//       //FIXME error
344//     }
345//     int b=lpx_get_row_type(lp, i);
346//     double lo=lpx_get_row_lb(lp, i);
347//     if (up==INF) {
348//       switch (b) {
349//       case LPX_FR:
350//       case LPX_LO:
351//      break;
352//       case LPX_UP:
353//      lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
354//      break;
355//       case LPX_DB:
356//       case LPX_FX:
357//      lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
358//      break;
359//       default: ;
360//      //FIXME error
361//       }
362//     } else {
363//       switch (b) {
364//       case LPX_FR:
365//      lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
366//      break;
367//       case LPX_UP:
368//      lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
369//      break;
370//       case LPX_LO:
371//       case LPX_DB:
372//       case LPX_FX:
373//      if (lo==up)
374//        lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
375//      else
376//        lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
377//      break;
378//       default: ;
379//      //FIXME error
380//       }
381//     }
382//   }
383
384  void LpGlpk::_setRowBounds(int i, Value lb, Value ub)
385  {
386    //Bad parameter
387    if (lb==INF || ub==-INF) {
388      //FIXME error
389    }
390
391    if (lb == -INF){
392      if (ub == INF){
393        lpx_set_row_bnds(lp, i, LPX_FR, lb, ub);
394      }
395      else{
396        lpx_set_row_bnds(lp, i, LPX_UP, lb, ub);
397      }
398    }
399    else{
400      if (ub==INF){
401        lpx_set_row_bnds(lp, i, LPX_LO, lb, ub);
402
403      }
404      else{
405        if (lb == ub){
406          lpx_set_row_bnds(lp, i, LPX_FX, lb, ub);
407        }
408        else{
409          lpx_set_row_bnds(lp, i, LPX_DB, lb, ub);
410        }
411      }
412    }
413
414  }
415 
416  void LpGlpk::_setObjCoeff(int i, Value obj_coef)
417  {
418    //i=0 means the constant term (shift)
419    lpx_set_obj_coef(lp, i, obj_coef);
420  }
421
422  void LpGlpk::_clearObj()
423  {
424    for (int i=0;i<=lpx_get_num_cols(lp);++i){
425      lpx_set_obj_coef(lp, i, 0);
426    }
427  }
428//   void LpGlpk::_setObj(int length,
429//                     int  const * indices,
430//                     Value  const * values )
431//   {
432//     Value new_values[1+lpx_num_cols()];
433//     for (i=0;i<=lpx_num_cols();++i){
434//       new_values[i]=0;
435//     }
436//     for (i=1;i<=length;++i){
437//       new_values[indices[i]]=values[i];
438//     }
439   
440//     for (i=0;i<=lpx_num_cols();++i){
441//       lpx_set_obj_coef(lp, i, new_values[i]);
442//     }
443//   }
444
445  LpGlpk::SolveExitStatus LpGlpk::_solve()
446  {
447    int i =  lpx_simplex(lp);
448    switch (i) {
449    case LPX_E_OK:
450      return SOLVED;
451    default:
452      return UNSOLVED;
453    }
454  }
455
456  LpGlpk::Value LpGlpk::_getPrimal(int i)
457  {
458    return lpx_get_col_prim(lp,i);
459  }
460
461  LpGlpk::Value LpGlpk::_getDual(int i)
462  {
463    return lpx_get_row_dual(lp,i);
464  }
465 
466  LpGlpk::Value LpGlpk::_getPrimalValue()
467  {
468    return lpx_get_obj_val(lp);
469  }
470  bool LpGlpk::_isBasicCol(int i) {
471    return (lpx_get_col_stat(lp, i)==LPX_BS);
472  }
473 
474 
475  LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()
476  {
477    int stat=  lpx_get_status(lp);
478    switch (stat) {
479    case LPX_UNDEF://Undefined (no solve has been run yet)
480      return UNDEFINED;
481    case LPX_NOFEAS://There is no feasible solution (primal, I guess)
482    case LPX_INFEAS://Infeasible
483      return INFEASIBLE;
484    case LPX_UNBND://Unbounded
485      return INFINITE;
486    case LPX_FEAS://Feasible
487      return FEASIBLE;
488    case LPX_OPT://Feasible
489      return OPTIMAL;
490    default:
491      return UNDEFINED; //to avoid gcc warning
492      //FIXME error
493    }
494  }
495
496  LpGlpk::SolutionStatus LpGlpk::_getDualStatus()
497  {
498//     std::cout<<"Itt megy: "<<lpx_get_dual_stat(lp)<<std::endl;
499//     std::cout<<"Itt a primal: "<<lpx_get_prim_stat(lp)<<std::endl;
500
501    switch (lpx_get_dual_stat(lp)) {
502    case LPX_D_UNDEF://Undefined (no solve has been run yet)
503      return UNDEFINED;
504    case LPX_D_NOFEAS://There is no dual feasible solution
505//    case LPX_D_INFEAS://Infeasible
506      return INFEASIBLE;
507    case LPX_D_FEAS://Feasible   
508      switch (lpx_get_status(lp)) {
509      case LPX_NOFEAS:
510        return INFINITE;
511      case LPX_OPT:
512        return OPTIMAL;
513      default:
514        return FEASIBLE;
515      }
516    default:
517      return UNDEFINED; //to avoid gcc warning
518      //FIXME error
519    }
520  }
521
522  LpGlpk::ProblemTypes LpGlpk::_getProblemType()
523  {
524      //int stat=  lpx_get_status(lp);
525    int statp=  lpx_get_prim_stat(lp);
526    int statd=  lpx_get_dual_stat(lp);
527    if (statp==LPX_P_FEAS && statd==LPX_D_FEAS)
528        return PRIMAL_DUAL_FEASIBLE;
529    if (statp==LPX_P_FEAS && statd==LPX_D_NOFEAS)
530        return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
531    if (statp==LPX_P_NOFEAS && statd==LPX_D_FEAS)
532        return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
533    if (statp==LPX_P_NOFEAS && statd==LPX_D_NOFEAS)
534        return PRIMAL_DUAL_INFEASIBLE;
535    //In all other cases
536    return UNKNOWN;
537  }
538
539  void LpGlpk::_setMax()
540  {
541    lpx_set_obj_dir(lp, LPX_MAX);
542  }
543
544  void LpGlpk::_setMin()
545  {
546    lpx_set_obj_dir(lp, LPX_MIN);
547  }
548
549 
550  void LpGlpk::messageLevel(int m)
551  {
552    lpx_set_int_parm(lp, LPX_K_MSGLEV, m);
553  }
554
555  void LpGlpk::presolver(bool b)
556  {
557    lpx_set_int_parm(lp, LPX_K_PRESOL, b);
558  }
559
560 
561} //END OF NAMESPACE LEMON
Note: See TracBrowser for help on using the repository browser.