COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_glpk.cc @ 2364:3a5e67bd42d2

Last change on this file since 2364:3a5e67bd42d2 was 2364:3a5e67bd42d2, checked in by Balazs Dezso, 13 years ago

Lp row and col getter function
lp section reader and writer for lemon IO

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