COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_glpk.cc @ 2276:1a8a66b6c6ce

Last change on this file since 2276:1a8a66b6c6ce was 2253:1645f6cc9667, checked in by Alpar Juttner, 17 years ago

Remove superfluous #ifndef boundaries

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