COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_glpk.cc @ 1866:c2de2ed28e59

Last change on this file since 1866:c2de2ed28e59 was 1840:173b53b28d7c, checked in by marci, 14 years ago

max flow with lp column generation

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