COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_glpk.cc @ 1435:8e85e6bbefdf

Last change on this file since 1435:8e85e6bbefdf was 1435:8e85e6bbefdf, checked in by Akos Ladanyi, 19 years ago

trunk/src/* move to trunk/

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