COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_glpk.cc @ 2366:bfbdded3763a

Last change on this file since 2366:bfbdded3763a was 2366:bfbdded3763a, checked in by Balazs Dezso, 17 years ago

Using const in lp interface
colByName functionality

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