COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_glpk.cc @ 2349:c945f577a66d

Last change on this file since 2349:c945f577a66d was 2349:c945f577a66d, checked in by athos, 13 years ago

Small bug corrected.

File size: 14.0 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(const LpGlpk &glp) : Parent(glp),
35                                      lp(lpx_create_prob()) {
36    ///\todo constrol function for this:
37    lpx_set_int_parm(lp, LPX_K_DUAL, 1);
38    messageLevel(0);
39    //Coefficient matrix, row bounds
40    lpx_add_rows(lp, lpx_get_num_rows(glp.lp));
41    lpx_add_cols(lp, lpx_get_num_cols(glp.lp));
42    int len;
43    int ind[1+lpx_get_num_cols(glp.lp)];
44    Value val[1+lpx_get_num_cols(glp.lp)];
45    for (int i=1;i<=lpx_get_num_rows(glp.lp);++i)
46      {
47        len=lpx_get_mat_row(glp.lp,i,ind,val);
48        lpx_set_mat_row(lp, i,len,ind,val);
49        lpx_set_row_bnds(lp,i,lpx_get_row_type(glp.lp,i),
50                         lpx_get_row_lb(glp.lp,i),lpx_get_row_ub(glp.lp,i));
51      }
52
53    //Objective function, coloumn bounds
54    lpx_set_obj_dir(lp, lpx_get_obj_dir(glp.lp));
55    //Objectif function's constant term treated separately
56    lpx_set_obj_coef(lp,0,lpx_get_obj_coef(glp.lp,0));
57    for (int i=1;i<=lpx_get_num_cols(glp.lp);++i)
58      {
59        lpx_set_obj_coef(lp,i,lpx_get_obj_coef(glp.lp,i));
60        lpx_set_col_bnds(lp,i,lpx_get_col_type(glp.lp,i),
61                         lpx_get_col_lb(glp.lp,i),lpx_get_col_ub(glp.lp,i));
62      }
63  }
64 
65  LpGlpk::~LpGlpk() {
66    lpx_delete_prob(lp);
67  }
68 
69  int LpGlpk::_addCol() {
70    int i=lpx_add_cols(lp, 1);
71    _setColLowerBound(i, -INF);
72    _setColUpperBound(i, INF);
73    return i;
74  }
75
76  ///\e
77
78
79  LpSolverBase &LpGlpk::_newLp()
80  {
81    LpGlpk* newlp=new LpGlpk;
82    return *newlp;
83  }
84 
85  ///\e
86
87  LpSolverBase &LpGlpk::_copyLp()
88  {
89    LpGlpk* newlp=new LpGlpk(*this);
90    return *newlp;
91  }
92
93  int LpGlpk::_addRow() {
94    int i=lpx_add_rows(lp, 1);
95    return i;
96  }
97
98 
99  void LpGlpk::_eraseCol(int i) {
100    int cols[2];
101    cols[1]=i;
102    lpx_del_cols(lp, 1, cols);
103  }
104 
105  void LpGlpk::_eraseRow(int i) {
106    int rows[2];
107    rows[1]=i;
108    lpx_del_rows(lp, 1, rows);
109  }
110
111  void LpGlpk::_getColName(int col, std::string & name)
112  {
113   
114    char *n = lpx_get_col_name(lp,col);
115    name = n?n:"";
116  }
117 
118 
119  void LpGlpk::_setColName(int col, const std::string & name)
120  {
121    lpx_set_col_name(lp,col,const_cast<char*>(name.c_str()));
122
123  }
124 
125  void LpGlpk::_setRowCoeffs(int i, LpRowIterator b, LpRowIterator e)
126  {
127    std::vector<int> indices;
128    std::vector<Value> values;
129
130    indices.push_back(0);
131    values.push_back(0);
132
133    for(LpRowIterator it=b; it!=e; ++it) {
134      indices.push_back(it->first);
135      values.push_back(it->second);
136    }
137
138    lpx_set_mat_row(lp, i, values.size() - 1, &indices[0], &values[0]);
139  }
140 
141  void LpGlpk::_setColCoeffs(int i, LpColIterator b, LpColIterator e) {
142
143    std::vector<int> indices;
144    std::vector<Value> values;
145
146    indices.push_back(0);
147    values.push_back(0);
148
149    for(LpColIterator it=b; it!=e; ++it) {
150      indices.push_back(it->first);
151      values.push_back(it->second);
152    }
153   
154    lpx_set_mat_col(lp, i, values.size() - 1, &indices[0], &values[0]);
155  }
156
157
158  void LpGlpk::_setCoeff(int row, int col, Value value)
159  {
160
161    if (lpx_get_num_cols(lp) < lpx_get_num_rows(lp)) {
162
163      int length=lpx_get_mat_row(lp, row, 0, 0);
164     
165      std::vector<int> indices(length + 2);
166      std::vector<Value> values(length + 2);
167     
168      lpx_get_mat_row(lp, row, &indices[0], &values[0]);
169     
170      //The following code does not suppose that the elements of the
171      //array indices are sorted
172      bool found=false;
173      for (int i = 1; i <= length; ++i) {
174        if (indices[i]==col){
175          found=true;
176          values[i]=value;
177          break;
178        }
179      }
180      if (!found){
181        ++length;
182        indices[length]=col;
183        values[length]=value;
184      }
185   
186      lpx_set_mat_row(lp, row, length, &indices[0], &values[0]);
187
188    } else {
189
190      int length=lpx_get_mat_col(lp, col, 0, 0);
191     
192      std::vector<int> indices(length + 2);
193      std::vector<Value> values(length + 2);
194     
195      lpx_get_mat_col(lp, col, &indices[0], &values[0]);
196     
197      //The following code does not suppose that the elements of the
198      //array indices are sorted
199      bool found=false;
200      for (int i = 1; i <= length; ++i) {
201        if (indices[i]==col){
202          found=true;
203          values[i]=value;
204          break;
205        }
206      }
207      if (!found){
208        ++length;
209        indices[length]=row;
210        values[length]=value;
211      }
212   
213      lpx_set_mat_col(lp, col, length, &indices[0], &values[0]);
214    }
215  }
216
217  LpGlpk::Value LpGlpk::_getCoeff(int row, int col)
218  {
219
220    int length=lpx_get_mat_row(lp, row, 0, 0);
221   
222    std::vector<int> indices(length + 2);
223    std::vector<Value> values(length + 2);
224   
225    lpx_get_mat_row(lp, row, &indices[0], &values[0]);
226   
227    //The following code does not suppose that the elements of the
228    //array indices are sorted
229    for (int i = 1; i <= length; ++i) {
230      if (indices[i]==col){
231        return values[i];
232      }
233    }
234    return 0;
235
236  }
237
238
239  void LpGlpk::_setColLowerBound(int i, Value lo)
240  {
241    if (lo==INF) {
242      //FIXME error
243    }
244    int b=lpx_get_col_type(lp, i);
245    double up=lpx_get_col_ub(lp, i);   
246    if (lo==-INF) {
247      switch (b) {
248      case LPX_FR:
249      case LPX_LO:
250        lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
251        break;
252      case LPX_UP:
253        break;
254      case LPX_DB:
255      case LPX_FX:
256        lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
257        break;
258      default: ;
259        //FIXME error
260      }
261    } else {
262      switch (b) {
263      case LPX_FR:
264      case LPX_LO:
265        lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
266        break;
267      case LPX_UP:       
268      case LPX_DB:
269      case LPX_FX:
270        if (lo==up)
271          lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
272        else
273          lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
274        break;
275      default: ;
276        //FIXME error
277      }
278    }
279
280  }
281
282  LpGlpk::Value LpGlpk::_getColLowerBound(int i)
283  {
284    int b=lpx_get_col_type(lp, i);
285      switch (b) {
286      case LPX_LO:
287      case LPX_DB:
288      case LPX_FX:
289        return lpx_get_col_lb(lp, i);   
290      default: ;
291        return -INF;
292      }
293  }
294 
295  void LpGlpk::_setColUpperBound(int i, Value up)
296  {
297    if (up==-INF) {
298      //FIXME error
299    }
300    int b=lpx_get_col_type(lp, i);
301    double lo=lpx_get_col_lb(lp, i);
302    if (up==INF) {
303      switch (b) {
304      case LPX_FR:
305      case LPX_LO:
306        break;
307      case LPX_UP:
308        lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
309        break;
310      case LPX_DB:
311      case LPX_FX:
312        lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
313        break;
314      default: ;
315        //FIXME error
316      }
317    } else {
318      switch (b) {
319      case LPX_FR:
320        lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
321        break;
322      case LPX_UP:
323        lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
324        break;
325      case LPX_LO:
326      case LPX_DB:
327      case LPX_FX:
328        if (lo==up)
329          lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
330        else
331          lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
332        break;
333      default: ;
334        //FIXME error
335      }
336    }
337  }
338
339  LpGlpk::Value LpGlpk::_getColUpperBound(int i)
340  {
341    int b=lpx_get_col_type(lp, i);
342      switch (b) {
343      case LPX_UP:
344      case LPX_DB:
345      case LPX_FX:
346        return lpx_get_col_ub(lp, i);   
347      default: ;
348        return INF;
349      }
350  }
351 
352//   void LpGlpk::_setRowLowerBound(int i, Value lo)
353//   {
354//     if (lo==INF) {
355//       //FIXME error
356//     }
357//     int b=lpx_get_row_type(lp, i);
358//     double up=lpx_get_row_ub(lp, i);
359//     if (lo==-INF) {
360//       switch (b) {
361//       case LPX_FR:
362//       case LPX_LO:
363//      lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
364//      break;
365//       case LPX_UP:
366//      break;
367//       case LPX_DB:
368//       case LPX_FX:
369//      lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
370//      break;
371//       default: ;
372//      //FIXME error
373//       }
374//     } else {
375//       switch (b) {
376//       case LPX_FR:
377//       case LPX_LO:
378//      lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
379//      break;
380//       case LPX_UP:     
381//       case LPX_DB:
382//       case LPX_FX:
383//      if (lo==up)
384//        lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
385//      else
386//        lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
387//      break;
388//       default: ;
389//      //FIXME error
390//       }
391//     }
392//   }
393 
394//   void LpGlpk::_setRowUpperBound(int i, Value up)
395//   {
396//     if (up==-INF) {
397//       //FIXME error
398//     }
399//     int b=lpx_get_row_type(lp, i);
400//     double lo=lpx_get_row_lb(lp, i);
401//     if (up==INF) {
402//       switch (b) {
403//       case LPX_FR:
404//       case LPX_LO:
405//      break;
406//       case LPX_UP:
407//      lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
408//      break;
409//       case LPX_DB:
410//       case LPX_FX:
411//      lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
412//      break;
413//       default: ;
414//      //FIXME error
415//       }
416//     } else {
417//       switch (b) {
418//       case LPX_FR:
419//      lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
420//      break;
421//       case LPX_UP:
422//      lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
423//      break;
424//       case LPX_LO:
425//       case LPX_DB:
426//       case LPX_FX:
427//      if (lo==up)
428//        lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
429//      else
430//        lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
431//      break;
432//       default: ;
433//      //FIXME error
434//       }
435//     }
436//   }
437
438  void LpGlpk::_setRowBounds(int i, Value lb, Value ub)
439  {
440    //Bad parameter
441    if (lb==INF || ub==-INF) {
442      //FIXME error
443    }
444
445    if (lb == -INF){
446      if (ub == INF){
447        lpx_set_row_bnds(lp, i, LPX_FR, lb, ub);
448      }
449      else{
450        lpx_set_row_bnds(lp, i, LPX_UP, lb, ub);
451      }
452    }
453    else{
454      if (ub==INF){
455        lpx_set_row_bnds(lp, i, LPX_LO, lb, ub);
456
457      }
458      else{
459        if (lb == ub){
460          lpx_set_row_bnds(lp, i, LPX_FX, lb, ub);
461        }
462        else{
463          lpx_set_row_bnds(lp, i, LPX_DB, lb, ub);
464        }
465      }
466    }
467
468  }
469
470  void LpGlpk::_getRowBounds(int i, Value &lb, Value &ub)
471  {
472
473    int b=lpx_get_row_type(lp, i);
474    switch (b) {
475    case LPX_FR:
476    case LPX_UP:
477      lb = -INF;
478        break;
479    default:
480      lb=lpx_get_row_lb(lp, i);
481    }
482
483    switch (b) {
484    case LPX_FR:
485    case LPX_LO:
486      ub = INF;
487        break;
488    default:
489      ub=lpx_get_row_ub(lp, i);
490    }
491   
492  }
493 
494  void LpGlpk::_setObjCoeff(int i, Value obj_coef)
495  {
496    //i=0 means the constant term (shift)
497    lpx_set_obj_coef(lp, i, obj_coef);
498  }
499
500  LpGlpk::Value LpGlpk::_getObjCoeff(int i){
501    //i=0 means the constant term (shift)
502    return lpx_get_obj_coef(lp, i);
503  }
504
505  void LpGlpk::_clearObj()
506  {
507    for (int i=0;i<=lpx_get_num_cols(lp);++i){
508      lpx_set_obj_coef(lp, i, 0);
509    }
510  }
511//   void LpGlpk::_setObj(int length,
512//                     int  const * indices,
513//                     Value  const * values )
514//   {
515//     Value new_values[1+lpx_num_cols()];
516//     for (i=0;i<=lpx_num_cols();++i){
517//       new_values[i]=0;
518//     }
519//     for (i=1;i<=length;++i){
520//       new_values[indices[i]]=values[i];
521//     }
522   
523//     for (i=0;i<=lpx_num_cols();++i){
524//       lpx_set_obj_coef(lp, i, new_values[i]);
525//     }
526//   }
527
528  LpGlpk::SolveExitStatus LpGlpk::_solve()
529  {
530    // A way to check the problem to be solved
531    //lpx_write_cpxlp(lp,"naittvan.cpx");   
532
533    int i =  lpx_simplex(lp);
534    switch (i) {
535    case LPX_E_OK:
536      return SOLVED;
537    default:
538      return UNSOLVED;
539    }
540  }
541
542  LpGlpk::Value LpGlpk::_getPrimal(int i)
543  {
544    return lpx_get_col_prim(lp,i);
545  }
546
547  LpGlpk::Value LpGlpk::_getDual(int i)
548  {
549    return lpx_get_row_dual(lp,i);
550  }
551 
552  LpGlpk::Value LpGlpk::_getPrimalValue()
553  {
554    return lpx_get_obj_val(lp);
555  }
556  bool LpGlpk::_isBasicCol(int i) {
557    return (lpx_get_col_stat(lp, i)==LPX_BS);
558  }
559 
560 
561  LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()
562  {
563    int stat=  lpx_get_status(lp);
564    switch (stat) {
565    case LPX_UNDEF://Undefined (no solve has been run yet)
566      return UNDEFINED;
567    case LPX_NOFEAS://There is no feasible solution (primal, I guess)
568    case LPX_INFEAS://Infeasible
569      return INFEASIBLE;
570    case LPX_UNBND://Unbounded
571      return INFINITE;
572    case LPX_FEAS://Feasible
573      return FEASIBLE;
574    case LPX_OPT://Feasible
575      return OPTIMAL;
576    default:
577      return UNDEFINED; //to avoid gcc warning
578      //FIXME error
579    }
580  }
581
582  LpGlpk::SolutionStatus LpGlpk::_getDualStatus()
583  {
584//     std::cout<<"Itt megy: "<<lpx_get_dual_stat(lp)<<std::endl;
585//     std::cout<<"Itt a primal: "<<lpx_get_prim_stat(lp)<<std::endl;
586
587    switch (lpx_get_dual_stat(lp)) {
588    case LPX_D_UNDEF://Undefined (no solve has been run yet)
589      return UNDEFINED;
590    case LPX_D_NOFEAS://There is no dual feasible solution
591//    case LPX_D_INFEAS://Infeasible
592      return INFEASIBLE;
593    case LPX_D_FEAS://Feasible   
594      switch (lpx_get_status(lp)) {
595      case LPX_NOFEAS:
596        return INFINITE;
597      case LPX_OPT:
598        return OPTIMAL;
599      default:
600        return FEASIBLE;
601      }
602    default:
603      return UNDEFINED; //to avoid gcc warning
604      //FIXME error
605    }
606  }
607
608  LpGlpk::ProblemTypes LpGlpk::_getProblemType()
609  {
610      //int stat=  lpx_get_status(lp);
611    int statp=  lpx_get_prim_stat(lp);
612    int statd=  lpx_get_dual_stat(lp);
613    if (statp==LPX_P_FEAS && statd==LPX_D_FEAS)
614        return PRIMAL_DUAL_FEASIBLE;
615    if (statp==LPX_P_FEAS && statd==LPX_D_NOFEAS)
616        return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
617    if (statp==LPX_P_NOFEAS && statd==LPX_D_FEAS)
618        return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
619    if (statp==LPX_P_NOFEAS && statd==LPX_D_NOFEAS)
620        return PRIMAL_DUAL_INFEASIBLE;
621    //In all other cases
622    return UNKNOWN;
623  }
624
625  void LpGlpk::_setMax()
626  {
627    lpx_set_obj_dir(lp, LPX_MAX);
628  }
629
630  void LpGlpk::_setMin()
631  {
632    lpx_set_obj_dir(lp, LPX_MIN);
633  }
634
635  bool LpGlpk::_isMax()
636  {
637    return (lpx_get_obj_dir(lp)==LPX_MAX);
638  }
639
640 
641
642  void LpGlpk::messageLevel(int m)
643  {
644    lpx_set_int_parm(lp, LPX_K_MSGLEV, m);
645  }
646
647  void LpGlpk::presolver(bool b)
648  {
649    lpx_set_int_parm(lp, LPX_K_PRESOL, b);
650  }
651
652 
653} //END OF NAMESPACE LEMON
Note: See TracBrowser for help on using the repository browser.