COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_glpk.cc @ 2325:d6ec469aa019

Last change on this file since 2325:d6ec469aa019 was 2324:18fc834761d9, checked in by athos, 14 years ago

Some query functions got implemented, but only for GLPK.

File size: 12.8 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    ///\todo This is not yet implemented!!!
219    return 0;
220  }
221
222
223  void LpGlpk::_setColLowerBound(int i, Value lo)
224  {
225    if (lo==INF) {
226      //FIXME error
227    }
228    int b=lpx_get_col_type(lp, i);
229    double up=lpx_get_col_ub(lp, i);   
230    if (lo==-INF) {
231      switch (b) {
232      case LPX_FR:
233      case LPX_LO:
234        lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
235        break;
236      case LPX_UP:
237        break;
238      case LPX_DB:
239      case LPX_FX:
240        lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
241        break;
242      default: ;
243        //FIXME error
244      }
245    } else {
246      switch (b) {
247      case LPX_FR:
248      case LPX_LO:
249        lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
250        break;
251      case LPX_UP:       
252      case LPX_DB:
253      case LPX_FX:
254        if (lo==up)
255          lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
256        else
257          lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
258        break;
259      default: ;
260        //FIXME error
261      }
262    }
263
264  }
265 
266  void LpGlpk::_setColUpperBound(int i, Value up)
267  {
268    if (up==-INF) {
269      //FIXME error
270    }
271    int b=lpx_get_col_type(lp, i);
272    double lo=lpx_get_col_lb(lp, i);
273    if (up==INF) {
274      switch (b) {
275      case LPX_FR:
276      case LPX_LO:
277        break;
278      case LPX_UP:
279        lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
280        break;
281      case LPX_DB:
282      case LPX_FX:
283        lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
284        break;
285      default: ;
286        //FIXME error
287      }
288    } else {
289      switch (b) {
290      case LPX_FR:
291        lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
292        break;
293      case LPX_UP:
294        lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
295        break;
296      case LPX_LO:
297      case LPX_DB:
298      case LPX_FX:
299        if (lo==up)
300          lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
301        else
302          lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
303        break;
304      default: ;
305        //FIXME error
306      }
307    }
308  }
309 
310//   void LpGlpk::_setRowLowerBound(int i, Value lo)
311//   {
312//     if (lo==INF) {
313//       //FIXME error
314//     }
315//     int b=lpx_get_row_type(lp, i);
316//     double up=lpx_get_row_ub(lp, i);
317//     if (lo==-INF) {
318//       switch (b) {
319//       case LPX_FR:
320//       case LPX_LO:
321//      lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
322//      break;
323//       case LPX_UP:
324//      break;
325//       case LPX_DB:
326//       case LPX_FX:
327//      lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
328//      break;
329//       default: ;
330//      //FIXME error
331//       }
332//     } else {
333//       switch (b) {
334//       case LPX_FR:
335//       case LPX_LO:
336//      lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
337//      break;
338//       case LPX_UP:     
339//       case LPX_DB:
340//       case LPX_FX:
341//      if (lo==up)
342//        lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
343//      else
344//        lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
345//      break;
346//       default: ;
347//      //FIXME error
348//       }
349//     }
350//   }
351 
352//   void LpGlpk::_setRowUpperBound(int i, Value up)
353//   {
354//     if (up==-INF) {
355//       //FIXME error
356//     }
357//     int b=lpx_get_row_type(lp, i);
358//     double lo=lpx_get_row_lb(lp, i);
359//     if (up==INF) {
360//       switch (b) {
361//       case LPX_FR:
362//       case LPX_LO:
363//      break;
364//       case LPX_UP:
365//      lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
366//      break;
367//       case LPX_DB:
368//       case LPX_FX:
369//      lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
370//      break;
371//       default: ;
372//      //FIXME error
373//       }
374//     } else {
375//       switch (b) {
376//       case LPX_FR:
377//      lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
378//      break;
379//       case LPX_UP:
380//      lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
381//      break;
382//       case LPX_LO:
383//       case LPX_DB:
384//       case LPX_FX:
385//      if (lo==up)
386//        lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
387//      else
388//        lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
389//      break;
390//       default: ;
391//      //FIXME error
392//       }
393//     }
394//   }
395
396  void LpGlpk::_setRowBounds(int i, Value lb, Value ub)
397  {
398    //Bad parameter
399    if (lb==INF || ub==-INF) {
400      //FIXME error
401    }
402
403    if (lb == -INF){
404      if (ub == INF){
405        lpx_set_row_bnds(lp, i, LPX_FR, lb, ub);
406      }
407      else{
408        lpx_set_row_bnds(lp, i, LPX_UP, lb, ub);
409      }
410    }
411    else{
412      if (ub==INF){
413        lpx_set_row_bnds(lp, i, LPX_LO, lb, ub);
414
415      }
416      else{
417        if (lb == ub){
418          lpx_set_row_bnds(lp, i, LPX_FX, lb, ub);
419        }
420        else{
421          lpx_set_row_bnds(lp, i, LPX_DB, lb, ub);
422        }
423      }
424    }
425
426  }
427 
428  void LpGlpk::_setObjCoeff(int i, Value obj_coef)
429  {
430    //i=0 means the constant term (shift)
431    lpx_set_obj_coef(lp, i, obj_coef);
432  }
433
434  LpGlpk::Value LpGlpk::_getObjCoeff(int i){
435    //i=0 means the constant term (shift)
436    return lpx_get_obj_coef(lp, i);
437  }
438
439  void LpGlpk::_clearObj()
440  {
441    for (int i=0;i<=lpx_get_num_cols(lp);++i){
442      lpx_set_obj_coef(lp, i, 0);
443    }
444  }
445//   void LpGlpk::_setObj(int length,
446//                     int  const * indices,
447//                     Value  const * values )
448//   {
449//     Value new_values[1+lpx_num_cols()];
450//     for (i=0;i<=lpx_num_cols();++i){
451//       new_values[i]=0;
452//     }
453//     for (i=1;i<=length;++i){
454//       new_values[indices[i]]=values[i];
455//     }
456   
457//     for (i=0;i<=lpx_num_cols();++i){
458//       lpx_set_obj_coef(lp, i, new_values[i]);
459//     }
460//   }
461
462  LpGlpk::SolveExitStatus LpGlpk::_solve()
463  {
464    int i =  lpx_simplex(lp);
465    switch (i) {
466    case LPX_E_OK:
467      return SOLVED;
468    default:
469      return UNSOLVED;
470    }
471  }
472
473  LpGlpk::Value LpGlpk::_getPrimal(int i)
474  {
475    return lpx_get_col_prim(lp,i);
476  }
477
478  LpGlpk::Value LpGlpk::_getDual(int i)
479  {
480    return lpx_get_row_dual(lp,i);
481  }
482 
483  LpGlpk::Value LpGlpk::_getPrimalValue()
484  {
485    return lpx_get_obj_val(lp);
486  }
487  bool LpGlpk::_isBasicCol(int i) {
488    return (lpx_get_col_stat(lp, i)==LPX_BS);
489  }
490 
491 
492  LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus()
493  {
494    int stat=  lpx_get_status(lp);
495    switch (stat) {
496    case LPX_UNDEF://Undefined (no solve has been run yet)
497      return UNDEFINED;
498    case LPX_NOFEAS://There is no feasible solution (primal, I guess)
499    case LPX_INFEAS://Infeasible
500      return INFEASIBLE;
501    case LPX_UNBND://Unbounded
502      return INFINITE;
503    case LPX_FEAS://Feasible
504      return FEASIBLE;
505    case LPX_OPT://Feasible
506      return OPTIMAL;
507    default:
508      return UNDEFINED; //to avoid gcc warning
509      //FIXME error
510    }
511  }
512
513  LpGlpk::SolutionStatus LpGlpk::_getDualStatus()
514  {
515//     std::cout<<"Itt megy: "<<lpx_get_dual_stat(lp)<<std::endl;
516//     std::cout<<"Itt a primal: "<<lpx_get_prim_stat(lp)<<std::endl;
517
518    switch (lpx_get_dual_stat(lp)) {
519    case LPX_D_UNDEF://Undefined (no solve has been run yet)
520      return UNDEFINED;
521    case LPX_D_NOFEAS://There is no dual feasible solution
522//    case LPX_D_INFEAS://Infeasible
523      return INFEASIBLE;
524    case LPX_D_FEAS://Feasible   
525      switch (lpx_get_status(lp)) {
526      case LPX_NOFEAS:
527        return INFINITE;
528      case LPX_OPT:
529        return OPTIMAL;
530      default:
531        return FEASIBLE;
532      }
533    default:
534      return UNDEFINED; //to avoid gcc warning
535      //FIXME error
536    }
537  }
538
539  LpGlpk::ProblemTypes LpGlpk::_getProblemType()
540  {
541      //int stat=  lpx_get_status(lp);
542    int statp=  lpx_get_prim_stat(lp);
543    int statd=  lpx_get_dual_stat(lp);
544    if (statp==LPX_P_FEAS && statd==LPX_D_FEAS)
545        return PRIMAL_DUAL_FEASIBLE;
546    if (statp==LPX_P_FEAS && statd==LPX_D_NOFEAS)
547        return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
548    if (statp==LPX_P_NOFEAS && statd==LPX_D_FEAS)
549        return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
550    if (statp==LPX_P_NOFEAS && statd==LPX_D_NOFEAS)
551        return PRIMAL_DUAL_INFEASIBLE;
552    //In all other cases
553    return UNKNOWN;
554  }
555
556  void LpGlpk::_setMax()
557  {
558    lpx_set_obj_dir(lp, LPX_MAX);
559  }
560
561  void LpGlpk::_setMin()
562  {
563    lpx_set_obj_dir(lp, LPX_MIN);
564  }
565
566  bool LpGlpk::_isMax()
567  {
568    return (lpx_get_obj_dir(lp)==LPX_MAX);
569  }
570
571 
572
573  void LpGlpk::messageLevel(int m)
574  {
575    lpx_set_int_parm(lp, LPX_K_MSGLEV, m);
576  }
577
578  void LpGlpk::presolver(bool b)
579  {
580    lpx_set_int_parm(lp, LPX_K_PRESOL, b);
581  }
582
583 
584} //END OF NAMESPACE LEMON
Note: See TracBrowser for help on using the repository browser.