COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_glpk.cc @ 2328:b4931ae52069

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

Query functions have been implemented for GLPK (CPLEX breaks at the moment, I guess): These functions include:
retrieving one element of the coeff. matrix
retrieving one element of the obj function
lower bd for a variable
upper bound for a variable
lower and upper bounds for a row (these can not be handled separately at the moment)
direction of the optimization (is_max() function)

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