COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_glpk.cc @ 2381:0248790c66ea

Last change on this file since 2381:0248790c66ea was 2368:6b2e8b734ae7, checked in by Balazs Dezso, 17 years ago

Bug fixes
Documentation

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