COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_glpk.cc @ 2321:e23a610bed51

Last change on this file since 2321:e23a610bed51 was 2321:e23a610bed51, checked in by Alpar Juttner, 13 years ago

Copy constructor for LpGlpk?

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