COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_glpk.cc @ 2363:2aabce558574

Last change on this file since 2363:2aabce558574 was 2363:2aabce558574, checked in by Balazs Dezso, 13 years ago

Changes on the LP interface

_FixId => LpId?

  • handling of not common ids soplex

LpGlpk? row and col erase bug fix

  • calling lpx_std_basis before simplex

LpSoplex?

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