COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_glpk.cc @ 2231:06faf3f06d67

Last change on this file since 2231:06faf3f06d67 was 1956:a055123339d5, checked in by Alpar Juttner, 18 years ago

Unified copyright notices

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