COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_glpk.cc @ 1895:5b01801efbc0

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