COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/lp_glpk.cc @ 1431:ad44b1dd8013

Last change on this file since 1431:ad44b1dd8013 was 1431:ad44b1dd8013, checked in by athos, 15 years ago

Added function _setCoeff().

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