↑ Collapse diff ↑
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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_BITS_LP_SOLVER_ID_H
20
#define LEMON_BITS_LP_SOLVER_ID_H
21

	
22
namespace lemon {
23

	
24
  namespace _lp_bits {
25

	
26
    struct LpIdImpl {
27
      std::vector<int> index;
28
      std::vector<int> cross;
29
      int first_index;
30
      int first_free;
31
    };
32

	
33
    class LpId {
34
    public:
35

	
36
      class IdHandler {
37
      public:
38
        virtual ~IdHandler() {}
39
        virtual int addId(LpIdImpl&) = 0;
40
        virtual void eraseId(LpIdImpl&, int xn) = 0;
41
      };
42

	
43
      LpId(int min_index = 0) {
44
        id_handler = 0;
45
        impl.first_free = -1;
46
        impl.first_index = min_index;
47
        impl.cross.resize(impl.first_index);
48
      }
49

	
50
      LpId(const LpId& li) {
51
        id_handler = 0;
52
        impl = li.impl;
53
      }
54

	
55
      LpId& operator=(const LpId& li) {
56
        id_handler = 0;
57
        impl = li.impl;
58
        return *this;
59
      }
60

	
61
      void setIdHandler(IdHandler& ih) {
62
        id_handler = &ih;
63
      }
64

	
65
      int fixId(int fn) const {return impl.cross[fn];}
66
      int floatingId(int xn) const {return impl.index[xn];}
67

	
68
      int addId() {
69
        if (id_handler == 0) {
70
          int xn, fn = impl.cross.size();
71
          if (impl.first_free == -1) {
72
            xn = impl.index.size();
73
            impl.index.push_back(fn);
74
          } else {
75
            xn = impl.first_free;
76
            impl.first_free = impl.index[impl.first_free];
77
            impl.index[xn] = fn;
78
          }
79
          impl.cross.push_back(xn);
80
          return xn;
81
        } else {
82
          return id_handler->addId(impl);
83
        }
84
      }
85

	
86
      void eraseId(int xn) {
87
        if (id_handler == 0) {
88
          int fn = impl.index[xn];
89
          impl.index[xn] = impl.first_free;
90
          impl.first_free = xn;
91
          for(int i = fn + 1; i < int(impl.cross.size()); ++i) {
92
            impl.cross[i - 1] = impl.cross[i];
93
            impl.index[impl.cross[i]]--;
94
          }
95
          impl.cross.pop_back();
96
        } else {
97
          id_handler->eraseId(impl, xn);
98
        }
99
      }
100

	
101
      void firstFloating(int& fn) const {
102
        fn = impl.first_index;
103
        if (fn == int(impl.cross.size())) fn = -1;
104
      }
105

	
106
      void nextFloating(int& fn) const {
107
        ++fn;
108
        if (fn == int(impl.cross.size())) fn = -1;
109
      }
110

	
111
      void firstFix(int& xn) const {
112
        int fn;
113
        firstFloating(fn);
114
        xn = fn != -1 ? fixId(fn) : -1;
115
      }
116

	
117
      void nextFix(int& xn) const {
118
        int fn = floatingId(xn);
119
        nextFloating(fn);
120
        xn = fn != -1 ? fixId(fn) : -1;
121
      }
122

	
123
    protected:
124
      LpIdImpl impl;
125
      IdHandler *id_handler;
126
    };
127

	
128
    class RelocateIdHandler : public LpId::IdHandler {
129
    public:
130

	
131
      virtual int addId(LpIdImpl& impl) {
132
        int xn, fn = impl.cross.size();
133
        if (impl.first_free == -1) {
134
          xn = impl.index.size();
135
          impl.index.push_back(fn);
136
        } else {
137
          xn = impl.first_free;
138
          impl.first_free = impl.index[impl.first_free];
139
          impl.index[xn] = fn;
140
        }
141
        impl.cross.push_back(xn);
142
        return xn;
143
      }
144

	
145
      virtual void eraseId(LpIdImpl& impl, int xn) {
146
        int fn = impl.index[xn];
147
        impl.index[xn] = impl.first_free;
148
        impl.first_free = xn;
149
        impl.cross[fn] = impl.cross.back();
150
        impl.index[impl.cross.back()] = fn;
151
        impl.cross.pop_back();
152
      }
153
    };
154
  }
155
}
156

	
157
#endif
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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_H
20
#define LEMON_LP_H
21

	
22
#include<lemon/config.h>
23

	
24

	
25
#ifdef HAVE_GLPK
26
#include <lemon/lp_glpk.h>
27
#include <lemon/mip_glpk.h>
28
#elif HAVE_CPLEX
29
#include <lemon/lp_cplex.h>
30
#include <lemon/mip_cplex.h>
31
#elif HAVE_SOPLEX
32
#include <lemon/lp_soplex.h>
33
#endif
34

	
35
///\file
36
///\brief Defines a default LP solver
37
///\ingroup lp_group
38
namespace lemon {
39

	
40
#ifdef DOXYGEN
41
  ///The default LP solver identifier
42

	
43
  ///The default LP solver identifier.
44
  ///\ingroup lp_group
45
  ///
46
  ///Currently, the possible values are \c GLPK or \c CPLEX
47
#define DEFAULT_LP SOLVER
48
  ///The default LP solver
49

	
50
  ///The default LP solver.
51
  ///\ingroup lp_group
52
  ///
53
  ///Currently, it is either \c LpGlpk or \c LpCplex
54
  typedef LpGlpk Lp;
55
  ///The default LP solver identifier string
56

	
57
  ///The default LP solver identifier string.
58
  ///\ingroup lp_group
59
  ///
60
  ///Currently, the possible values are "GLPK" or "CPLEX"
61
  const char default_solver_name[]="SOLVER";
62

	
63
  ///The default ILP solver.
64

	
65
  ///The default ILP solver.
66
  ///\ingroup lp_group
67
  ///
68
  ///Currently, it is either \c LpGlpk or \c LpCplex
69
  typedef MipGlpk Mip;
70
#else
71
#ifdef HAVE_GLPK
72
#define DEFAULT_LP GLPK
73
  typedef LpGlpk Lp;
74
  typedef MipGlpk Mip;
75
  const char default_solver_name[]="GLPK";
76
#elif HAVE_CPLEX
77
#define DEFAULT_LP CPLEX
78
  typedef LpCplex Lp;
79
  typedef MipCplex Mip;
80
  const char default_solver_name[]="CPLEX";
81
#elif HAVE_SOPLEX
82
#define DEFAULT_LP SOPLEX
83
  typedef LpSoplex Lp;
84
  const char default_solver_name[]="SOPLEX";
85
#endif
86
#endif
87

	
88
} //namespace lemon
89

	
90
#endif //LEMON_LP_H
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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 The implementation of the LP solver interface.
21

	
22
#include <lemon/lp_base.h>
23
namespace lemon {
24

	
25
  const LpSolverBase::Value
26
  LpSolverBase::INF = std::numeric_limits<Value>::infinity();
27
  const LpSolverBase::Value
28
  LpSolverBase::NaN = std::numeric_limits<Value>::quiet_NaN();
29

	
30
//   const LpSolverBase::Constr::Value
31
//   LpSolverBase::Constr::INF = std::numeric_limits<Value>::infinity();
32
//   const LpSolverBase::Constr::Value
33
//   LpSolverBase::Constr::NaN = std::numeric_limits<Value>::quiet_NaN();
34

	
35
} //namespace lemon
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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_BASE_H
20
#define LEMON_LP_BASE_H
21

	
22
#include<iostream>
23
#include<vector>
24
#include<map>
25
#include<limits>
26
#include<lemon/math.h>
27

	
28
#include<lemon/core.h>
29
#include<lemon/bits/lp_id.h>
30

	
31
///\file
32
///\brief The interface of the LP solver interface.
33
///\ingroup lp_group
34
namespace lemon {
35

	
36
  /// Function to decide whether a floating point value is finite or not.
37

	
38
  /// Retruns true if the argument is not infinity, minus infinity or NaN.
39
  /// It does the same as the isfinite() function defined by C99.
40
  template <typename T>
41
  bool isFinite(T value)
42
  {
43
    typedef std::numeric_limits<T> Lim;
44
    if ((Lim::has_infinity && (value == Lim::infinity() || value ==
45
                               -Lim::infinity())) ||
46
        ((Lim::has_quiet_NaN || Lim::has_signaling_NaN) && value != value))
47
    {
48
      return false;
49
    }
50
    return true;
51
  }
52

	
53
  ///Common base class for LP solvers
54

	
55
  ///\todo Much more docs
56
  ///\ingroup lp_group
57
  class LpSolverBase {
58

	
59
  protected:
60

	
61
    _lp_bits::LpId rows;
62
    _lp_bits::LpId cols;
63

	
64
  public:
65

	
66
    ///Possible outcomes of an LP solving procedure
67
    enum SolveExitStatus {
68
      ///This means that the problem has been successfully solved: either
69
      ///an optimal solution has been found or infeasibility/unboundedness
70
      ///has been proved.
71
      SOLVED = 0,
72
      ///Any other case (including the case when some user specified
73
      ///limit has been exceeded)
74
      UNSOLVED = 1
75
    };
76

	
77
      ///\e
78
    enum SolutionStatus {
79
      ///Feasible solution hasn't been found (but may exist).
80

	
81
      ///\todo NOTFOUND might be a better name.
82
      ///
83
      UNDEFINED = 0,
84
      ///The problem has no feasible solution
85
      INFEASIBLE = 1,
86
      ///Feasible solution found
87
      FEASIBLE = 2,
88
      ///Optimal solution exists and found
89
      OPTIMAL = 3,
90
      ///The cost function is unbounded
91

	
92
      ///\todo Give a feasible solution and an infinite ray (and the
93
      ///corresponding bases)
94
      INFINITE = 4
95
    };
96

	
97
    ///\e The type of the investigated LP problem
98
    enum ProblemTypes {
99
      ///Primal-dual feasible
100
      PRIMAL_DUAL_FEASIBLE = 0,
101
      ///Primal feasible dual infeasible
102
      PRIMAL_FEASIBLE_DUAL_INFEASIBLE = 1,
103
      ///Primal infeasible dual feasible
104
      PRIMAL_INFEASIBLE_DUAL_FEASIBLE = 2,
105
      ///Primal-dual infeasible
106
      PRIMAL_DUAL_INFEASIBLE = 3,
107
      ///Could not determine so far
108
      UNKNOWN = 4
109
    };
110

	
111
    ///The floating point type used by the solver
112
    typedef double Value;
113
    ///The infinity constant
114
    static const Value INF;
115
    ///The not a number constant
116
    static const Value NaN;
117

	
118
    static inline bool isNaN(const Value& v) { return v!=v; }
119

	
120
    friend class Col;
121
    friend class ColIt;
122
    friend class Row;
123

	
124
    ///Refer to a column of the LP.
125

	
126
    ///This type is used to refer to a column of the LP.
127
    ///
128
    ///Its value remains valid and correct even after the addition or erase of
129
    ///other columns.
130
    ///
131
    ///\todo Document what can one do with a Col (INVALID, comparing,
132
    ///it is similar to Node/Edge)
133
    class Col {
134
    protected:
135
      int id;
136
      friend class LpSolverBase;
137
      friend class MipSolverBase;
138
      explicit Col(int _id) : id(_id) {}
139
    public:
140
      typedef Value ExprValue;
141
      typedef True LpSolverCol;
142
      Col() {}
143
      Col(const Invalid&) : id(-1) {}
144
      bool operator< (Col c) const  {return id< c.id;}
145
      bool operator> (Col c) const  {return id> c.id;}
146
      bool operator==(Col c) const  {return id==c.id;}
147
      bool operator!=(Col c) const  {return id!=c.id;}
148
    };
149

	
150
    class ColIt : public Col {
151
      const LpSolverBase *_lp;
152
    public:
153
      ColIt() {}
154
      ColIt(const LpSolverBase &lp) : _lp(&lp)
155
      {
156
        _lp->cols.firstFix(id);
157
      }
158
      ColIt(const Invalid&) : Col(INVALID) {}
159
      ColIt &operator++()
160
      {
161
        _lp->cols.nextFix(id);
162
        return *this;
163
      }
164
    };
165

	
166
    static int id(const Col& col) { return col.id; }
167

	
168

	
169
    ///Refer to a row of the LP.
170

	
171
    ///This type is used to refer to a row of the LP.
172
    ///
173
    ///Its value remains valid and correct even after the addition or erase of
174
    ///other rows.
175
    ///
176
    ///\todo Document what can one do with a Row (INVALID, comparing,
177
    ///it is similar to Node/Edge)
178
    class Row {
179
    protected:
180
      int id;
181
      friend class LpSolverBase;
182
      explicit Row(int _id) : id(_id) {}
183
    public:
184
      typedef Value ExprValue;
185
      typedef True LpSolverRow;
186
      Row() {}
187
      Row(const Invalid&) : id(-1) {}
188

	
189
      bool operator< (Row c) const  {return id< c.id;}
190
      bool operator> (Row c) const  {return id> c.id;}
191
      bool operator==(Row c) const  {return id==c.id;}
192
      bool operator!=(Row c) const  {return id!=c.id;}
193
    };
194

	
195
    class RowIt : public Row {
196
      const LpSolverBase *_lp;
197
    public:
198
      RowIt() {}
199
      RowIt(const LpSolverBase &lp) : _lp(&lp)
200
      {
201
        _lp->rows.firstFix(id);
202
      }
203
      RowIt(const Invalid&) : Row(INVALID) {}
204
      RowIt &operator++()
205
      {
206
        _lp->rows.nextFix(id);
207
        return *this;
208
      }
209
    };
210

	
211
    static int id(const Row& row) { return row.id; }
212

	
213
  protected:
214

	
215
    int _lpId(const Col& c) const {
216
      return cols.floatingId(id(c));
217
    }
218

	
219
    int _lpId(const Row& r) const {
220
      return rows.floatingId(id(r));
221
    }
222

	
223
    Col _item(int i, Col) const {
224
      return Col(cols.fixId(i));
225
    }
226

	
227
    Row _item(int i, Row) const {
228
      return Row(rows.fixId(i));
229
    }
230

	
231

	
232
  public:
233

	
234
    ///Linear expression of variables and a constant component
235

	
236
    ///This data structure stores a linear expression of the variables
237
    ///(\ref Col "Col"s) and also has a constant component.
238
    ///
239
    ///There are several ways to access and modify the contents of this
240
    ///container.
241
    ///- Its it fully compatible with \c std::map<Col,double>, so for expamle
242
    ///if \c e is an Expr and \c v and \c w are of type \ref Col, then you can
243
    ///read and modify the coefficients like
244
    ///these.
245
    ///\code
246
    ///e[v]=5;
247
    ///e[v]+=12;
248
    ///e.erase(v);
249
    ///\endcode
250
    ///or you can also iterate through its elements.
251
    ///\code
252
    ///double s=0;
253
    ///for(LpSolverBase::Expr::iterator i=e.begin();i!=e.end();++i)
254
    ///  s+=i->second;
255
    ///\endcode
256
    ///(This code computes the sum of all coefficients).
257
    ///- Numbers (<tt>double</tt>'s)
258
    ///and variables (\ref Col "Col"s) directly convert to an
259
    ///\ref Expr and the usual linear operations are defined, so
260
    ///\code
261
    ///v+w
262
    ///2*v-3.12*(v-w/2)+2
263
    ///v*2.1+(3*v+(v*12+w+6)*3)/2
264
    ///\endcode
265
    ///are valid \ref Expr "Expr"essions.
266
    ///The usual assignment operations are also defined.
267
    ///\code
268
    ///e=v+w;
269
    ///e+=2*v-3.12*(v-w/2)+2;
270
    ///e*=3.4;
271
    ///e/=5;
272
    ///\endcode
273
    ///- The constant member can be set and read by \ref constComp()
274
    ///\code
275
    ///e.constComp()=12;
276
    ///double c=e.constComp();
277
    ///\endcode
278
    ///
279
    ///\note \ref clear() not only sets all coefficients to 0 but also
280
    ///clears the constant components.
281
    ///
282
    ///\sa Constr
283
    ///
284
    class Expr : public std::map<Col,Value>
285
    {
286
    public:
287
      typedef LpSolverBase::Col Key;
288
      typedef LpSolverBase::Value Value;
289

	
290
    protected:
291
      typedef std::map<Col,Value> Base;
292

	
293
      Value const_comp;
294
    public:
295
      typedef True IsLinExpression;
296
      ///\e
297
      Expr() : Base(), const_comp(0) { }
298
      ///\e
299
      Expr(const Key &v) : const_comp(0) {
300
        Base::insert(std::make_pair(v, 1));
301
      }
302
      ///\e
303
      Expr(const Value &v) : const_comp(v) {}
304
      ///\e
305
      void set(const Key &v,const Value &c) {
306
        Base::insert(std::make_pair(v, c));
307
      }
308
      ///\e
309
      Value &constComp() { return const_comp; }
310
      ///\e
311
      const Value &constComp() const { return const_comp; }
312

	
313
      ///Removes the components with zero coefficient.
314
      void simplify() {
315
        for (Base::iterator i=Base::begin(); i!=Base::end();) {
316
          Base::iterator j=i;
317
          ++j;
318
          if ((*i).second==0) Base::erase(i);
319
          i=j;
320
        }
321
      }
322

	
323
      void simplify() const {
324
        const_cast<Expr*>(this)->simplify();
325
      }
326

	
327
      ///Removes the coefficients closer to zero than \c tolerance.
328
      void simplify(double &tolerance) {
329
        for (Base::iterator i=Base::begin(); i!=Base::end();) {
330
          Base::iterator j=i;
331
          ++j;
332
          if (std::fabs((*i).second)<tolerance) Base::erase(i);
333
          i=j;
334
        }
335
      }
336

	
337
      ///Sets all coefficients and the constant component to 0.
338
      void clear() {
339
        Base::clear();
340
        const_comp=0;
341
      }
342

	
343
      ///\e
344
      Expr &operator+=(const Expr &e) {
345
        for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
346
          (*this)[j->first]+=j->second;
347
        const_comp+=e.const_comp;
348
        return *this;
349
      }
350
      ///\e
351
      Expr &operator-=(const Expr &e) {
352
        for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
353
          (*this)[j->first]-=j->second;
354
        const_comp-=e.const_comp;
355
        return *this;
356
      }
357
      ///\e
358
      Expr &operator*=(const Value &c) {
359
        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
360
          j->second*=c;
361
        const_comp*=c;
362
        return *this;
363
      }
364
      ///\e
365
      Expr &operator/=(const Value &c) {
366
        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
367
          j->second/=c;
368
        const_comp/=c;
369
        return *this;
370
      }
371

	
372
    };
373

	
374
    ///Linear constraint
375

	
376
    ///This data stucture represents a linear constraint in the LP.
377
    ///Basically it is a linear expression with a lower or an upper bound
378
    ///(or both). These parts of the constraint can be obtained by the member
379
    ///functions \ref expr(), \ref lowerBound() and \ref upperBound(),
380
    ///respectively.
381
    ///There are two ways to construct a constraint.
382
    ///- You can set the linear expression and the bounds directly
383
    ///  by the functions above.
384
    ///- The operators <tt>\<=</tt>, <tt>==</tt> and  <tt>\>=</tt>
385
    ///  are defined between expressions, or even between constraints whenever
386
    ///  it makes sense. Therefore if \c e and \c f are linear expressions and
387
    ///  \c s and \c t are numbers, then the followings are valid expressions
388
    ///  and thus they can be used directly e.g. in \ref addRow() whenever
389
    ///  it makes sense.
390
    ///\code
391
    ///  e<=s
392
    ///  e<=f
393
    ///  e==f
394
    ///  s<=e<=t
395
    ///  e>=t
396
    ///\endcode
397
    ///\warning The validity of a constraint is checked only at run time, so
398
    ///e.g. \ref addRow(<tt>x[1]\<=x[2]<=5</tt>) will compile, but will throw 
399
    ///an assertion.
400
    class Constr
401
    {
402
    public:
403
      typedef LpSolverBase::Expr Expr;
404
      typedef Expr::Key Key;
405
      typedef Expr::Value Value;
406

	
407
    protected:
408
      Expr _expr;
409
      Value _lb,_ub;
410
    public:
411
      ///\e
412
      Constr() : _expr(), _lb(NaN), _ub(NaN) {}
413
      ///\e
414
      Constr(Value lb,const Expr &e,Value ub) :
415
        _expr(e), _lb(lb), _ub(ub) {}
416
      ///\e
417
      Constr(const Expr &e,Value ub) :
418
        _expr(e), _lb(NaN), _ub(ub) {}
419
      ///\e
420
      Constr(Value lb,const Expr &e) :
421
        _expr(e), _lb(lb), _ub(NaN) {}
422
      ///\e
423
      Constr(const Expr &e) :
424
        _expr(e), _lb(NaN), _ub(NaN) {}
425
      ///\e
426
      void clear()
427
      {
428
        _expr.clear();
429
        _lb=_ub=NaN;
430
      }
431

	
432
      ///Reference to the linear expression
433
      Expr &expr() { return _expr; }
434
      ///Cont reference to the linear expression
435
      const Expr &expr() const { return _expr; }
436
      ///Reference to the lower bound.
437

	
438
      ///\return
439
      ///- \ref INF "INF": the constraint is lower unbounded.
440
      ///- \ref NaN "NaN": lower bound has not been set.
441
      ///- finite number: the lower bound
442
      Value &lowerBound() { return _lb; }
443
      ///The const version of \ref lowerBound()
444
      const Value &lowerBound() const { return _lb; }
445
      ///Reference to the upper bound.
446

	
447
      ///\return
448
      ///- \ref INF "INF": the constraint is upper unbounded.
449
      ///- \ref NaN "NaN": upper bound has not been set.
450
      ///- finite number: the upper bound
451
      Value &upperBound() { return _ub; }
452
      ///The const version of \ref upperBound()
453
      const Value &upperBound() const { return _ub; }
454
      ///Is the constraint lower bounded?
455
      bool lowerBounded() const {
456
        return isFinite(_lb);
457
      }
458
      ///Is the constraint upper bounded?
459
      bool upperBounded() const {
460
        return isFinite(_ub);
461
      }
462

	
463
    };
464

	
465
    ///Linear expression of rows
466

	
467
    ///This data structure represents a column of the matrix,
468
    ///thas is it strores a linear expression of the dual variables
469
    ///(\ref Row "Row"s).
470
    ///
471
    ///There are several ways to access and modify the contents of this
472
    ///container.
473
    ///- Its it fully compatible with \c std::map<Row,double>, so for expamle
474
    ///if \c e is an DualExpr and \c v
475
    ///and \c w are of type \ref Row, then you can
476
    ///read and modify the coefficients like
477
    ///these.
478
    ///\code
479
    ///e[v]=5;
480
    ///e[v]+=12;
481
    ///e.erase(v);
482
    ///\endcode
483
    ///or you can also iterate through its elements.
484
    ///\code
485
    ///double s=0;
486
    ///for(LpSolverBase::DualExpr::iterator i=e.begin();i!=e.end();++i)
487
    ///  s+=i->second;
488
    ///\endcode
489
    ///(This code computes the sum of all coefficients).
490
    ///- Numbers (<tt>double</tt>'s)
491
    ///and variables (\ref Row "Row"s) directly convert to an
492
    ///\ref DualExpr and the usual linear operations are defined, so
493
    ///\code
494
    ///v+w
495
    ///2*v-3.12*(v-w/2)
496
    ///v*2.1+(3*v+(v*12+w)*3)/2
497
    ///\endcode
498
    ///are valid \ref DualExpr "DualExpr"essions.
499
    ///The usual assignment operations are also defined.
500
    ///\code
501
    ///e=v+w;
502
    ///e+=2*v-3.12*(v-w/2);
503
    ///e*=3.4;
504
    ///e/=5;
505
    ///\endcode
506
    ///
507
    ///\sa Expr
508
    ///
509
    class DualExpr : public std::map<Row,Value>
510
    {
511
    public:
512
      typedef LpSolverBase::Row Key;
513
      typedef LpSolverBase::Value Value;
514

	
515
    protected:
516
      typedef std::map<Row,Value> Base;
517

	
518
    public:
519
      typedef True IsLinExpression;
520
      ///\e
521
      DualExpr() : Base() { }
522
      ///\e
523
      DualExpr(const Key &v) {
524
        Base::insert(std::make_pair(v, 1));
525
      }
526
      ///\e
527
      void set(const Key &v,const Value &c) {
528
        Base::insert(std::make_pair(v, c));
529
      }
530

	
531
      ///Removes the components with zero coefficient.
532
      void simplify() {
533
        for (Base::iterator i=Base::begin(); i!=Base::end();) {
534
          Base::iterator j=i;
535
          ++j;
536
          if ((*i).second==0) Base::erase(i);
537
          i=j;
538
        }
539
      }
540

	
541
      void simplify() const {
542
        const_cast<DualExpr*>(this)->simplify();
543
      }
544

	
545
      ///Removes the coefficients closer to zero than \c tolerance.
546
      void simplify(double &tolerance) {
547
        for (Base::iterator i=Base::begin(); i!=Base::end();) {
548
          Base::iterator j=i;
549
          ++j;
550
          if (std::fabs((*i).second)<tolerance) Base::erase(i);
551
          i=j;
552
        }
553
      }
554

	
555
      ///Sets all coefficients to 0.
556
      void clear() {
557
        Base::clear();
558
      }
559

	
560
      ///\e
561
      DualExpr &operator+=(const DualExpr &e) {
562
        for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
563
          (*this)[j->first]+=j->second;
564
        return *this;
565
      }
566
      ///\e
567
      DualExpr &operator-=(const DualExpr &e) {
568
        for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
569
          (*this)[j->first]-=j->second;
570
        return *this;
571
      }
572
      ///\e
573
      DualExpr &operator*=(const Value &c) {
574
        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
575
          j->second*=c;
576
        return *this;
577
      }
578
      ///\e
579
      DualExpr &operator/=(const Value &c) {
580
        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
581
          j->second/=c;
582
        return *this;
583
      }
584
    };
585

	
586

	
587
  private:
588

	
589
    template <typename _Expr>
590
    class MappedOutputIterator {
591
    public:
592

	
593
      typedef std::insert_iterator<_Expr> Base;
594

	
595
      typedef std::output_iterator_tag iterator_category;
596
      typedef void difference_type;
597
      typedef void value_type;
598
      typedef void reference;
599
      typedef void pointer;
600

	
601
      MappedOutputIterator(const Base& _base, const LpSolverBase& _lp)
602
        : base(_base), lp(_lp) {}
603

	
604
      MappedOutputIterator& operator*() {
605
        return *this;
606
      }
607

	
608
      MappedOutputIterator& operator=(const std::pair<int, Value>& value) {
609
        *base = std::make_pair(lp._item(value.first, typename _Expr::Key()),
610
                               value.second);
611
        return *this;
612
      }
613

	
614
      MappedOutputIterator& operator++() {
615
        ++base;
616
        return *this;
617
      }
618

	
619
      MappedOutputIterator operator++(int) {
620
        MappedOutputIterator tmp(*this);
621
        ++base;
622
        return tmp;
623
      }
624

	
625
      bool operator==(const MappedOutputIterator& it) const {
626
        return base == it.base;
627
      }
628

	
629
      bool operator!=(const MappedOutputIterator& it) const {
630
        return base != it.base;
631
      }
632

	
633
    private:
634
      Base base;
635
      const LpSolverBase& lp;
636
    };
637

	
638
    template <typename Expr>
639
    class MappedInputIterator {
640
    public:
641

	
642
      typedef typename Expr::const_iterator Base;
643

	
644
      typedef typename Base::iterator_category iterator_category;
645
      typedef typename Base::difference_type difference_type;
646
      typedef const std::pair<int, Value> value_type;
647
      typedef value_type reference;
648
      class pointer {
649
      public:
650
        pointer(value_type& _value) : value(_value) {}
651
        value_type* operator->() { return &value; }
652
      private:
653
        value_type value;
654
      };
655

	
656
      MappedInputIterator(const Base& _base, const LpSolverBase& _lp)
657
        : base(_base), lp(_lp) {}
658

	
659
      reference operator*() {
660
        return std::make_pair(lp._lpId(base->first), base->second);
661
      }
662

	
663
      pointer operator->() {
664
        return pointer(operator*());
665
      }
666

	
667
      MappedInputIterator& operator++() {
668
        ++base;
669
        return *this;
670
      }
671

	
672
      MappedInputIterator operator++(int) {
673
        MappedInputIterator tmp(*this);
674
        ++base;
675
        return tmp;
676
      }
677

	
678
      bool operator==(const MappedInputIterator& it) const {
679
        return base == it.base;
680
      }
681

	
682
      bool operator!=(const MappedInputIterator& it) const {
683
        return base != it.base;
684
      }
685

	
686
    private:
687
      Base base;
688
      const LpSolverBase& lp;
689
    };
690

	
691
  protected:
692

	
693
    /// STL compatible iterator for lp col
694
    typedef MappedInputIterator<Expr> ConstRowIterator;
695
    /// STL compatible iterator for lp row
696
    typedef MappedInputIterator<DualExpr> ConstColIterator;
697

	
698
    /// STL compatible iterator for lp col
699
    typedef MappedOutputIterator<Expr> RowIterator;
700
    /// STL compatible iterator for lp row
701
    typedef MappedOutputIterator<DualExpr> ColIterator;
702

	
703
    //Abstract virtual functions
704
    virtual LpSolverBase* _newLp() = 0;
705
    virtual LpSolverBase* _copyLp(){
706
      LpSolverBase* newlp = _newLp();
707

	
708
      std::map<Col, Col> ref;
709
      for (LpSolverBase::ColIt it(*this); it != INVALID; ++it) {
710
        Col ccol = newlp->addCol();
711
        ref[it] = ccol;
712
        newlp->colName(ccol, colName(it));
713
        newlp->colLowerBound(ccol, colLowerBound(it));
714
        newlp->colUpperBound(ccol, colUpperBound(it));
715
      }
716

	
717
      for (LpSolverBase::RowIt it(*this); it != INVALID; ++it) {
718
        Expr e = row(it), ce;
719
        for (Expr::iterator jt = e.begin(); jt != e.end(); ++jt) {
720
          ce[ref[jt->first]] = jt->second;
721
        }
722
        ce += e.constComp();
723
        Row r = newlp->addRow(ce);
724

	
725
        double lower, upper;
726
        getRowBounds(it, lower, upper);
727
        newlp->rowBounds(r, lower, upper);
728
      }
729

	
730
      return newlp;
731
    };
732

	
733
    virtual int _addCol() = 0;
734
    virtual int _addRow() = 0;
735

	
736
    virtual void _eraseCol(int col) = 0;
737
    virtual void _eraseRow(int row) = 0;
738

	
739
    virtual void _getColName(int col, std::string & name) const = 0;
740
    virtual void _setColName(int col, const std::string & name) = 0;
741
    virtual int _colByName(const std::string& name) const = 0;
742

	
743
    virtual void _setRowCoeffs(int i, ConstRowIterator b,
744
                               ConstRowIterator e) = 0;
745
    virtual void _getRowCoeffs(int i, RowIterator b) const = 0;
746
    virtual void _setColCoeffs(int i, ConstColIterator b,
747
                               ConstColIterator e) = 0;
748
    virtual void _getColCoeffs(int i, ColIterator b) const = 0;
749
    virtual void _setCoeff(int row, int col, Value value) = 0;
750
    virtual Value _getCoeff(int row, int col) const = 0;
751
    virtual void _setColLowerBound(int i, Value value) = 0;
752
    virtual Value _getColLowerBound(int i) const = 0;
753
    virtual void _setColUpperBound(int i, Value value) = 0;
754
    virtual Value _getColUpperBound(int i) const = 0;
755
    virtual void _setRowBounds(int i, Value lower, Value upper) = 0;
756
    virtual void _getRowBounds(int i, Value &lower, Value &upper) const = 0;
757

	
758
    virtual void _setObjCoeff(int i, Value obj_coef) = 0;
759
    virtual Value _getObjCoeff(int i) const = 0;
760
    virtual void _clearObj()=0;
761

	
762
    virtual SolveExitStatus _solve() = 0;
763
    virtual Value _getPrimal(int i) const = 0;
764
    virtual Value _getDual(int i) const = 0;
765
    virtual Value _getPrimalValue() const = 0;
766
    virtual bool _isBasicCol(int i) const = 0;
767
    virtual SolutionStatus _getPrimalStatus() const = 0;
768
    virtual SolutionStatus _getDualStatus() const = 0;
769
    virtual ProblemTypes _getProblemType() const = 0;
770

	
771
    virtual void _setMax() = 0;
772
    virtual void _setMin() = 0;
773

	
774

	
775
    virtual bool _isMax() const = 0;
776

	
777
    //Own protected stuff
778

	
779
    //Constant component of the objective function
780
    Value obj_const_comp;
781

	
782
  public:
783

	
784
    ///\e
785
    LpSolverBase() : obj_const_comp(0) {}
786

	
787
    ///\e
788
    virtual ~LpSolverBase() {}
789

	
790
    ///Creates a new LP problem
791
    LpSolverBase* newLp() {return _newLp();}
792
    ///Makes a copy of the LP problem
793
    LpSolverBase* copyLp() {return _copyLp();}
794

	
795
    ///\name Build up and modify the LP
796

	
797
    ///@{
798

	
799
    ///Add a new empty column (i.e a new variable) to the LP
800
    Col addCol() { Col c; _addCol(); c.id = cols.addId(); return c;}
801

	
802
    ///\brief Adds several new columns
803
    ///(i.e a variables) at once
804
    ///
805
    ///This magic function takes a container as its argument
806
    ///and fills its elements
807
    ///with new columns (i.e. variables)
808
    ///\param t can be
809
    ///- a standard STL compatible iterable container with
810
    ///\ref Col as its \c values_type
811
    ///like
812
    ///\code
813
    ///std::vector<LpSolverBase::Col>
814
    ///std::list<LpSolverBase::Col>
815
    ///\endcode
816
    ///- a standard STL compatible iterable container with
817
    ///\ref Col as its \c mapped_type
818
    ///like
819
    ///\code
820
    ///std::map<AnyType,LpSolverBase::Col>
821
    ///\endcode
822
    ///- an iterable lemon \ref concepts::WriteMap "write map" like
823
    ///\code
824
    ///ListGraph::NodeMap<LpSolverBase::Col>
825
    ///ListGraph::EdgeMap<LpSolverBase::Col>
826
    ///\endcode
827
    ///\return The number of the created column.
828
#ifdef DOXYGEN
829
    template<class T>
830
    int addColSet(T &t) { return 0;}
831
#else
832
    template<class T>
833
    typename enable_if<typename T::value_type::LpSolverCol,int>::type
834
    addColSet(T &t,dummy<0> = 0) {
835
      int s=0;
836
      for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
837
      return s;
838
    }
839
    template<class T>
840
    typename enable_if<typename T::value_type::second_type::LpSolverCol,
841
                       int>::type
842
    addColSet(T &t,dummy<1> = 1) {
843
      int s=0;
844
      for(typename T::iterator i=t.begin();i!=t.end();++i) {
845
        i->second=addCol();
846
        s++;
847
      }
848
      return s;
849
    }
850
    template<class T>
851
    typename enable_if<typename T::MapIt::Value::LpSolverCol,
852
                       int>::type
853
    addColSet(T &t,dummy<2> = 2) {
854
      int s=0;
855
      for(typename T::MapIt i(t); i!=INVALID; ++i)
856
        {
857
          i.set(addCol());
858
          s++;
859
        }
860
      return s;
861
    }
862
#endif
863

	
864
    ///Set a column (i.e a dual constraint) of the LP
865

	
866
    ///\param c is the column to be modified
867
    ///\param e is a dual linear expression (see \ref DualExpr)
868
    ///a better one.
869
    void col(Col c,const DualExpr &e) {
870
      e.simplify();
871
      _setColCoeffs(_lpId(c), ConstColIterator(e.begin(), *this),
872
                    ConstColIterator(e.end(), *this));
873
    }
874

	
875
    ///Get a column (i.e a dual constraint) of the LP
876

	
877
    ///\param r is the column to get
878
    ///\return the dual expression associated to the column
879
    DualExpr col(Col c) const {
880
      DualExpr e;
881
      _getColCoeffs(_lpId(c), ColIterator(std::inserter(e, e.end()), *this));
882
      return e;
883
    }
884

	
885
    ///Add a new column to the LP
886

	
887
    ///\param e is a dual linear expression (see \ref DualExpr)
888
    ///\param obj is the corresponding component of the objective
889
    ///function. It is 0 by default.
890
    ///\return The created column.
891
    Col addCol(const DualExpr &e, Value o = 0) {
892
      Col c=addCol();
893
      col(c,e);
894
      objCoeff(c,o);
895
      return c;
896
    }
897

	
898
    ///Add a new empty row (i.e a new constraint) to the LP
899

	
900
    ///This function adds a new empty row (i.e a new constraint) to the LP.
901
    ///\return The created row
902
    Row addRow() { Row r; _addRow(); r.id = rows.addId(); return r;}
903

	
904
    ///\brief Add several new rows
905
    ///(i.e a constraints) at once
906
    ///
907
    ///This magic function takes a container as its argument
908
    ///and fills its elements
909
    ///with new row (i.e. variables)
910
    ///\param t can be
911
    ///- a standard STL compatible iterable container with
912
    ///\ref Row as its \c values_type
913
    ///like
914
    ///\code
915
    ///std::vector<LpSolverBase::Row>
916
    ///std::list<LpSolverBase::Row>
917
    ///\endcode
918
    ///- a standard STL compatible iterable container with
919
    ///\ref Row as its \c mapped_type
920
    ///like
921
    ///\code
922
    ///std::map<AnyType,LpSolverBase::Row>
923
    ///\endcode
924
    ///- an iterable lemon \ref concepts::WriteMap "write map" like
925
    ///\code
926
    ///ListGraph::NodeMap<LpSolverBase::Row>
927
    ///ListGraph::EdgeMap<LpSolverBase::Row>
928
    ///\endcode
929
    ///\return The number of rows created.
930
#ifdef DOXYGEN
931
    template<class T>
932
    int addRowSet(T &t) { return 0;}
933
#else
934
    template<class T>
935
    typename enable_if<typename T::value_type::LpSolverRow,int>::type
936
    addRowSet(T &t,dummy<0> = 0) {
937
      int s=0;
938
      for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addRow();s++;}
939
      return s;
940
    }
941
    template<class T>
942
    typename enable_if<typename T::value_type::second_type::LpSolverRow,
943
                       int>::type
944
    addRowSet(T &t,dummy<1> = 1) {
945
      int s=0;
946
      for(typename T::iterator i=t.begin();i!=t.end();++i) {
947
        i->second=addRow();
948
        s++;
949
      }
950
      return s;
951
    }
952
    template<class T>
953
    typename enable_if<typename T::MapIt::Value::LpSolverRow,
954
                       int>::type
955
    addRowSet(T &t,dummy<2> = 2) {
956
      int s=0;
957
      for(typename T::MapIt i(t); i!=INVALID; ++i)
958
        {
959
          i.set(addRow());
960
          s++;
961
        }
962
      return s;
963
    }
964
#endif
965

	
966
    ///Set a row (i.e a constraint) of the LP
967

	
968
    ///\param r is the row to be modified
969
    ///\param l is lower bound (-\ref INF means no bound)
970
    ///\param e is a linear expression (see \ref Expr)
971
    ///\param u is the upper bound (\ref INF means no bound)
972
    ///\bug This is a temporary function. The interface will change to
973
    ///a better one.
974
    ///\todo Option to control whether a constraint with a single variable is
975
    ///added or not.
976
    void row(Row r, Value l, const Expr &e, Value u) {
977
      e.simplify();
978
      _setRowCoeffs(_lpId(r), ConstRowIterator(e.begin(), *this),
979
                    ConstRowIterator(e.end(), *this));
980
      _setRowBounds(_lpId(r),l-e.constComp(),u-e.constComp());
981
    }
982

	
983
    ///Set a row (i.e a constraint) of the LP
984

	
985
    ///\param r is the row to be modified
986
    ///\param c is a linear expression (see \ref Constr)
987
    void row(Row r, const Constr &c) {
988
      row(r, c.lowerBounded()?c.lowerBound():-INF,
989
          c.expr(), c.upperBounded()?c.upperBound():INF);
990
    }
991

	
992

	
993
    ///Get a row (i.e a constraint) of the LP
994

	
995
    ///\param r is the row to get
996
    ///\return the expression associated to the row
997
    Expr row(Row r) const {
998
      Expr e;
999
      _getRowCoeffs(_lpId(r), RowIterator(std::inserter(e, e.end()), *this));
1000
      return e;
1001
    }
1002

	
1003
    ///Add a new row (i.e a new constraint) to the LP
1004

	
1005
    ///\param l is the lower bound (-\ref INF means no bound)
1006
    ///\param e is a linear expression (see \ref Expr)
1007
    ///\param u is the upper bound (\ref INF means no bound)
1008
    ///\return The created row.
1009
    ///\bug This is a temporary function. The interface will change to
1010
    ///a better one.
1011
    Row addRow(Value l,const Expr &e, Value u) {
1012
      Row r=addRow();
1013
      row(r,l,e,u);
1014
      return r;
1015
    }
1016

	
1017
    ///Add a new row (i.e a new constraint) to the LP
1018

	
1019
    ///\param c is a linear expression (see \ref Constr)
1020
    ///\return The created row.
1021
    Row addRow(const Constr &c) {
1022
      Row r=addRow();
1023
      row(r,c);
1024
      return r;
1025
    }
1026
    ///Erase a coloumn (i.e a variable) from the LP
1027

	
1028
    ///\param c is the coloumn to be deleted
1029
    ///\todo Please check this
1030
    void eraseCol(Col c) {
1031
      _eraseCol(_lpId(c));
1032
      cols.eraseId(c.id);
1033
    }
1034
    ///Erase a  row (i.e a constraint) from the LP
1035

	
1036
    ///\param r is the row to be deleted
1037
    ///\todo Please check this
1038
    void eraseRow(Row r) {
1039
      _eraseRow(_lpId(r));
1040
      rows.eraseId(r.id);
1041
    }
1042

	
1043
    /// Get the name of a column
1044

	
1045
    ///\param c is the coresponding coloumn
1046
    ///\return The name of the colunm
1047
    std::string colName(Col c) const {
1048
      std::string name;
1049
      _getColName(_lpId(c), name);
1050
      return name;
1051
    }
1052

	
1053
    /// Set the name of a column
1054

	
1055
    ///\param c is the coresponding coloumn
1056
    ///\param name The name to be given
1057
    void colName(Col c, const std::string& name) {
1058
      _setColName(_lpId(c), name);
1059
    }
1060

	
1061
    /// Get the column by its name
1062

	
1063
    ///\param name The name of the column
1064
    ///\return the proper column or \c INVALID
1065
    Col colByName(const std::string& name) const {
1066
      int k = _colByName(name);
1067
      return k != -1 ? Col(cols.fixId(k)) : Col(INVALID);
1068
    }
1069

	
1070
    /// Set an element of the coefficient matrix of the LP
1071

	
1072
    ///\param r is the row of the element to be modified
1073
    ///\param c is the coloumn of the element to be modified
1074
    ///\param val is the new value of the coefficient
1075

	
1076
    void coeff(Row r, Col c, Value val) {
1077
      _setCoeff(_lpId(r),_lpId(c), val);
1078
    }
1079

	
1080
    /// Get an element of the coefficient matrix of the LP
1081

	
1082
    ///\param r is the row of the element in question
1083
    ///\param c is the coloumn of the element in question
1084
    ///\return the corresponding coefficient
1085

	
1086
    Value coeff(Row r, Col c) const {
1087
      return _getCoeff(_lpId(r),_lpId(c));
1088
    }
1089

	
1090
    /// Set the lower bound of a column (i.e a variable)
1091

	
1092
    /// The lower bound of a variable (column) has to be given by an
1093
    /// extended number of type Value, i.e. a finite number of type
1094
    /// Value or -\ref INF.
1095
    void colLowerBound(Col c, Value value) {
1096
      _setColLowerBound(_lpId(c),value);
1097
    }
1098

	
1099
    /// Get the lower bound of a column (i.e a variable)
1100

	
1101
    /// This function returns the lower bound for column (variable) \t c
1102
    /// (this might be -\ref INF as well).
1103
    ///\return The lower bound for coloumn \t c
1104
    Value colLowerBound(Col c) const {
1105
      return _getColLowerBound(_lpId(c));
1106
    }
1107

	
1108
    ///\brief Set the lower bound of  several columns
1109
    ///(i.e a variables) at once
1110
    ///
1111
    ///This magic function takes a container as its argument
1112
    ///and applies the function on all of its elements.
1113
    /// The lower bound of a variable (column) has to be given by an
1114
    /// extended number of type Value, i.e. a finite number of type
1115
    /// Value or -\ref INF.
1116
#ifdef DOXYGEN
1117
    template<class T>
1118
    void colLowerBound(T &t, Value value) { return 0;}
1119
#else
1120
    template<class T>
1121
    typename enable_if<typename T::value_type::LpSolverCol,void>::type
1122
    colLowerBound(T &t, Value value,dummy<0> = 0) {
1123
      for(typename T::iterator i=t.begin();i!=t.end();++i) {
1124
        colLowerBound(*i, value);
1125
      }
1126
    }
1127
    template<class T>
1128
    typename enable_if<typename T::value_type::second_type::LpSolverCol,
1129
                       void>::type
1130
    colLowerBound(T &t, Value value,dummy<1> = 1) {
1131
      for(typename T::iterator i=t.begin();i!=t.end();++i) {
1132
        colLowerBound(i->second, value);
1133
      }
1134
    }
1135
    template<class T>
1136
    typename enable_if<typename T::MapIt::Value::LpSolverCol,
1137
                       void>::type
1138
    colLowerBound(T &t, Value value,dummy<2> = 2) {
1139
      for(typename T::MapIt i(t); i!=INVALID; ++i){
1140
        colLowerBound(*i, value);
1141
      }
1142
    }
1143
#endif
1144

	
1145
    /// Set the upper bound of a column (i.e a variable)
1146

	
1147
    /// The upper bound of a variable (column) has to be given by an
1148
    /// extended number of type Value, i.e. a finite number of type
1149
    /// Value or \ref INF.
1150
    void colUpperBound(Col c, Value value) {
1151
      _setColUpperBound(_lpId(c),value);
1152
    };
1153

	
1154
    /// Get the upper bound of a column (i.e a variable)
1155

	
1156
    /// This function returns the upper bound for column (variable) \t c
1157
    /// (this might be \ref INF as well).
1158
    ///\return The upper bound for coloumn \t c
1159
    Value colUpperBound(Col c) const {
1160
      return _getColUpperBound(_lpId(c));
1161
    }
1162

	
1163
    ///\brief Set the upper bound of  several columns
1164
    ///(i.e a variables) at once
1165
    ///
1166
    ///This magic function takes a container as its argument
1167
    ///and applies the function on all of its elements.
1168
    /// The upper bound of a variable (column) has to be given by an
1169
    /// extended number of type Value, i.e. a finite number of type
1170
    /// Value or \ref INF.
1171
#ifdef DOXYGEN
1172
    template<class T>
1173
    void colUpperBound(T &t, Value value) { return 0;}
1174
#else
1175
    template<class T>
1176
    typename enable_if<typename T::value_type::LpSolverCol,void>::type
1177
    colUpperBound(T &t, Value value,dummy<0> = 0) {
1178
      for(typename T::iterator i=t.begin();i!=t.end();++i) {
1179
        colUpperBound(*i, value);
1180
      }
1181
    }
1182
    template<class T>
1183
    typename enable_if<typename T::value_type::second_type::LpSolverCol,
1184
                       void>::type
1185
    colUpperBound(T &t, Value value,dummy<1> = 1) {
1186
      for(typename T::iterator i=t.begin();i!=t.end();++i) {
1187
        colUpperBound(i->second, value);
1188
      }
1189
    }
1190
    template<class T>
1191
    typename enable_if<typename T::MapIt::Value::LpSolverCol,
1192
                       void>::type
1193
    colUpperBound(T &t, Value value,dummy<2> = 2) {
1194
      for(typename T::MapIt i(t); i!=INVALID; ++i){
1195
        colUpperBound(*i, value);
1196
      }
1197
    }
1198
#endif
1199

	
1200
    /// Set the lower and the upper bounds of a column (i.e a variable)
1201

	
1202
    /// The lower and the upper bounds of
1203
    /// a variable (column) have to be given by an
1204
    /// extended number of type Value, i.e. a finite number of type
1205
    /// Value, -\ref INF or \ref INF.
1206
    void colBounds(Col c, Value lower, Value upper) {
1207
      _setColLowerBound(_lpId(c),lower);
1208
      _setColUpperBound(_lpId(c),upper);
1209
    }
1210

	
1211
    ///\brief Set the lower and the upper bound of several columns
1212
    ///(i.e a variables) at once
1213
    ///
1214
    ///This magic function takes a container as its argument
1215
    ///and applies the function on all of its elements.
1216
    /// The lower and the upper bounds of
1217
    /// a variable (column) have to be given by an
1218
    /// extended number of type Value, i.e. a finite number of type
1219
    /// Value, -\ref INF or \ref INF.
1220
#ifdef DOXYGEN
1221
    template<class T>
1222
    void colBounds(T &t, Value lower, Value upper) { return 0;}
1223
#else
1224
    template<class T>
1225
    typename enable_if<typename T::value_type::LpSolverCol,void>::type
1226
    colBounds(T &t, Value lower, Value upper,dummy<0> = 0) {
1227
      for(typename T::iterator i=t.begin();i!=t.end();++i) {
1228
        colBounds(*i, lower, upper);
1229
      }
1230
    }
1231
    template<class T>
1232
    typename enable_if<typename T::value_type::second_type::LpSolverCol,
1233
                       void>::type
1234
    colBounds(T &t, Value lower, Value upper,dummy<1> = 1) {
1235
      for(typename T::iterator i=t.begin();i!=t.end();++i) {
1236
        colBounds(i->second, lower, upper);
1237
      }
1238
    }
1239
    template<class T>
1240
    typename enable_if<typename T::MapIt::Value::LpSolverCol,
1241
                       void>::type
1242
    colBounds(T &t, Value lower, Value upper,dummy<2> = 2) {
1243
      for(typename T::MapIt i(t); i!=INVALID; ++i){
1244
        colBounds(*i, lower, upper);
1245
      }
1246
    }
1247
#endif
1248

	
1249

	
1250
    /// Set the lower and the upper bounds of a row (i.e a constraint)
1251

	
1252
    /// The lower and the upper bound of a constraint (row) have to be
1253
    /// given by an extended number of type Value, i.e. a finite
1254
    /// number of type Value, -\ref INF or \ref INF. There is no
1255
    /// separate function for the lower and the upper bound because
1256
    /// that would have been hard to implement for CPLEX.
1257
    void rowBounds(Row c, Value lower, Value upper) {
1258
      _setRowBounds(_lpId(c),lower, upper);
1259
    }
1260

	
1261
    /// Get the lower and the upper bounds of a row (i.e a constraint)
1262

	
1263
    /// The lower and the upper bound of
1264
    /// a constraint (row) are
1265
    /// extended numbers of type Value, i.e.  finite numbers of type
1266
    /// Value, -\ref INF or \ref INF.
1267
    /// \todo There is no separate function for the
1268
    /// lower and the upper bound because we had problems with the
1269
    /// implementation of the setting functions for CPLEX:
1270
    /// check out whether this can be done for these functions.
1271
    void getRowBounds(Row c, Value &lower, Value &upper) const {
1272
      _getRowBounds(_lpId(c),lower, upper);
1273
    }
1274

	
1275
    ///Set an element of the objective function
1276
    void objCoeff(Col c, Value v) {_setObjCoeff(_lpId(c),v); };
1277

	
1278
    ///Get an element of the objective function
1279
    Value objCoeff(Col c) const { return _getObjCoeff(_lpId(c)); };
1280

	
1281
    ///Set the objective function
1282

	
1283
    ///\param e is a linear expression of type \ref Expr.
1284
    void obj(Expr e) {
1285
      _clearObj();
1286
      for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
1287
        objCoeff((*i).first,(*i).second);
1288
      obj_const_comp=e.constComp();
1289
    }
1290

	
1291
    ///Get the objective function
1292

	
1293
    ///\return the objective function as a linear expression of type \ref Expr.
1294
    Expr obj() const {
1295
      Expr e;
1296
      for (ColIt it(*this); it != INVALID; ++it) {
1297
        double c = objCoeff(it);
1298
        if (c != 0.0) {
1299
          e.insert(std::make_pair(it, c));
1300
        }
1301
      }
1302
      return e;
1303
    }
1304

	
1305

	
1306
    ///Maximize
1307
    void max() { _setMax(); }
1308
    ///Minimize
1309
    void min() { _setMin(); }
1310

	
1311
    ///Query function: is this a maximization problem?
1312
    bool isMax() const {return _isMax(); }
1313

	
1314
    ///Query function: is this a minimization problem?
1315
    bool isMin() const {return !isMax(); }
1316

	
1317
    ///@}
1318

	
1319

	
1320
    ///\name Solve the LP
1321

	
1322
    ///@{
1323

	
1324
    ///\e Solve the LP problem at hand
1325
    ///
1326
    ///\return The result of the optimization procedure. Possible
1327
    ///values and their meanings can be found in the documentation of
1328
    ///\ref SolveExitStatus.
1329
    ///
1330
    ///\todo Which method is used to solve the problem
1331
    SolveExitStatus solve() { return _solve(); }
1332

	
1333
    ///@}
1334

	
1335
    ///\name Obtain the solution
1336

	
1337
    ///@{
1338

	
1339
    /// The status of the primal problem (the original LP problem)
1340
    SolutionStatus primalStatus() const {
1341
      return _getPrimalStatus();
1342
    }
1343

	
1344
    /// The status of the dual (of the original LP) problem
1345
    SolutionStatus dualStatus() const {
1346
      return _getDualStatus();
1347
    }
1348

	
1349
    ///The type of the original LP problem
1350
    ProblemTypes problemType() const {
1351
      return _getProblemType();
1352
    }
1353

	
1354
    ///\e
1355
    Value primal(Col c) const { return _getPrimal(_lpId(c)); }
1356
    ///\e
1357
    Value primal(const Expr& e) const {
1358
      double res = e.constComp();
1359
      for (std::map<Col, double>::const_iterator it = e.begin();
1360
           it != e.end(); ++it) {
1361
        res += _getPrimal(_lpId(it->first)) * it->second;
1362
      }
1363
      return res;
1364
    }
1365

	
1366
    ///\e
1367
    Value dual(Row r) const { return _getDual(_lpId(r)); }
1368
    ///\e
1369
    Value dual(const DualExpr& e) const {
1370
      double res = 0.0;
1371
      for (std::map<Row, double>::const_iterator it = e.begin();
1372
           it != e.end(); ++it) {
1373
        res += _getPrimal(_lpId(it->first)) * it->second;
1374
      }
1375
      return res;
1376
    }
1377

	
1378
    ///\e
1379
    bool isBasicCol(Col c) const { return _isBasicCol(_lpId(c)); }
1380

	
1381
    ///\e
1382

	
1383
    ///\return
1384
    ///- \ref INF or -\ref INF means either infeasibility or unboundedness
1385
    /// of the primal problem, depending on whether we minimize or maximize.
1386
    ///- \ref NaN if no primal solution is found.
1387
    ///- The (finite) objective value if an optimal solution is found.
1388
    Value primalValue() const { return _getPrimalValue()+obj_const_comp;}
1389
    ///@}
1390

	
1391
  };
1392

	
1393

	
1394
  /// \ingroup lp_group
1395
  ///
1396
  /// \brief Common base class for MIP solvers
1397
  /// \todo Much more docs
1398
  class MipSolverBase : virtual public LpSolverBase{
1399
  public:
1400

	
1401
    ///Possible variable (coloumn) types (e.g. real, integer, binary etc.)
1402
    enum ColTypes {
1403
      ///Continuous variable
1404
      REAL = 0,
1405
      ///Integer variable
1406

	
1407
      ///Unfortunately, cplex 7.5 somewhere writes something like
1408
      ///#define INTEGER 'I'
1409
      INT = 1
1410
      ///\todo No support for other types yet.
1411
    };
1412

	
1413
    ///Sets the type of the given coloumn to the given type
1414
    ///
1415
    ///Sets the type of the given coloumn to the given type.
1416
    void colType(Col c, ColTypes col_type) {
1417
      _colType(_lpId(c),col_type);
1418
    }
1419

	
1420
    ///Gives back the type of the column.
1421
    ///
1422
    ///Gives back the type of the column.
1423
    ColTypes colType(Col c) const {
1424
      return _colType(_lpId(c));
1425
    }
1426

	
1427
    ///Sets the type of the given Col to integer or remove that property.
1428
    ///
1429
    ///Sets the type of the given Col to integer or remove that property.
1430
    void integer(Col c, bool enable) {
1431
      if (enable)
1432
        colType(c,INT);
1433
      else
1434
        colType(c,REAL);
1435
    }
1436

	
1437
    ///Gives back whether the type of the column is integer or not.
1438
    ///
1439
    ///Gives back the type of the column.
1440
    ///\return true if the column has integer type and false if not.
1441
    bool integer(Col c) const {
1442
      return (colType(c)==INT);
1443
    }
1444

	
1445
    /// The status of the MIP problem
1446
    SolutionStatus mipStatus() const {
1447
      return _getMipStatus();
1448
    }
1449

	
1450
  protected:
1451

	
1452
    virtual ColTypes _colType(int col) const = 0;
1453
    virtual void _colType(int col, ColTypes col_type) = 0;
1454
    virtual SolutionStatus _getMipStatus() const = 0;
1455

	
1456
  };
1457

	
1458
  ///\relates LpSolverBase::Expr
1459
  ///
1460
  inline LpSolverBase::Expr operator+(const LpSolverBase::Expr &a,
1461
                                      const LpSolverBase::Expr &b)
1462
  {
1463
    LpSolverBase::Expr tmp(a);
1464
    tmp+=b;
1465
    return tmp;
1466
  }
1467
  ///\e
1468

	
1469
  ///\relates LpSolverBase::Expr
1470
  ///
1471
  inline LpSolverBase::Expr operator-(const LpSolverBase::Expr &a,
1472
                                      const LpSolverBase::Expr &b)
1473
  {
1474
    LpSolverBase::Expr tmp(a);
1475
    tmp-=b;
1476
    return tmp;
1477
  }
1478
  ///\e
1479

	
1480
  ///\relates LpSolverBase::Expr
1481
  ///
1482
  inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
1483
                                      const LpSolverBase::Value &b)
1484
  {
1485
    LpSolverBase::Expr tmp(a);
1486
    tmp*=b;
1487
    return tmp;
1488
  }
1489

	
1490
  ///\e
1491

	
1492
  ///\relates LpSolverBase::Expr
1493
  ///
1494
  inline LpSolverBase::Expr operator*(const LpSolverBase::Value &a,
1495
                                      const LpSolverBase::Expr &b)
1496
  {
1497
    LpSolverBase::Expr tmp(b);
1498
    tmp*=a;
1499
    return tmp;
1500
  }
1501
  ///\e
1502

	
1503
  ///\relates LpSolverBase::Expr
1504
  ///
1505
  inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
1506
                                      const LpSolverBase::Value &b)
1507
  {
1508
    LpSolverBase::Expr tmp(a);
1509
    tmp/=b;
1510
    return tmp;
1511
  }
1512

	
1513
  ///\e
1514

	
1515
  ///\relates LpSolverBase::Constr
1516
  ///
1517
  inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
1518
                                         const LpSolverBase::Expr &f)
1519
  {
1520
    return LpSolverBase::Constr(-LpSolverBase::INF,e-f,0);
1521
  }
1522

	
1523
  ///\e
1524

	
1525
  ///\relates LpSolverBase::Constr
1526
  ///
1527
  inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &e,
1528
                                         const LpSolverBase::Expr &f)
1529
  {
1530
    return LpSolverBase::Constr(e,f);
1531
  }
1532

	
1533
  ///\e
1534

	
1535
  ///\relates LpSolverBase::Constr
1536
  ///
1537
  inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
1538
                                         const LpSolverBase::Value &f)
1539
  {
1540
    return LpSolverBase::Constr(-LpSolverBase::INF,e,f);
1541
  }
1542

	
1543
  ///\e
1544

	
1545
  ///\relates LpSolverBase::Constr
1546
  ///
1547
  inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
1548
                                         const LpSolverBase::Expr &f)
1549
  {
1550
    return LpSolverBase::Constr(-LpSolverBase::INF,f-e,0);
1551
  }
1552

	
1553

	
1554
  ///\e
1555

	
1556
  ///\relates LpSolverBase::Constr
1557
  ///
1558
  inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &e,
1559
                                         const LpSolverBase::Expr &f)
1560
  {
1561
    return LpSolverBase::Constr(f,e);
1562
  }
1563

	
1564

	
1565
  ///\e
1566

	
1567
  ///\relates LpSolverBase::Constr
1568
  ///
1569
  inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
1570
                                         const LpSolverBase::Value &f)
1571
  {
1572
    return LpSolverBase::Constr(f,e,LpSolverBase::INF);
1573
  }
1574

	
1575
  ///\e
1576

	
1577
  ///\relates LpSolverBase::Constr
1578
  ///
1579
  inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
1580
                                         const LpSolverBase::Value &f)
1581
  {
1582
    return LpSolverBase::Constr(f,e,f);
1583
  }
1584

	
1585
  ///\e
1586

	
1587
  ///\relates LpSolverBase::Constr
1588
  ///
1589
  inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
1590
                                         const LpSolverBase::Expr &f)
1591
  {
1592
    return LpSolverBase::Constr(0,e-f,0);
1593
  }
1594

	
1595
  ///\e
1596

	
1597
  ///\relates LpSolverBase::Constr
1598
  ///
1599
  inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &n,
1600
                                         const LpSolverBase::Constr&c)
1601
  {
1602
    LpSolverBase::Constr tmp(c);
1603
    LEMON_ASSERT(LpSolverBase::isNaN(tmp.lowerBound()), "Wrong LP constraint");
1604
    tmp.lowerBound()=n;
1605
    return tmp;
1606
  }
1607
  ///\e
1608

	
1609
  ///\relates LpSolverBase::Constr
1610
  ///
1611
  inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
1612
                                         const LpSolverBase::Value &n)
1613
  {
1614
    LpSolverBase::Constr tmp(c);
1615
    LEMON_ASSERT(LpSolverBase::isNaN(tmp.upperBound()), "Wrong LP constraint");
1616
    tmp.upperBound()=n;
1617
    return tmp;
1618
  }
1619

	
1620
  ///\e
1621

	
1622
  ///\relates LpSolverBase::Constr
1623
  ///
1624
  inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &n,
1625
                                         const LpSolverBase::Constr&c)
1626
  {
1627
    LpSolverBase::Constr tmp(c);
1628
    LEMON_ASSERT(LpSolverBase::isNaN(tmp.upperBound()), "Wrong LP constraint");
1629
    tmp.upperBound()=n;
1630
    return tmp;
1631
  }
1632
  ///\e
1633

	
1634
  ///\relates LpSolverBase::Constr
1635
  ///
1636
  inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
1637
                                         const LpSolverBase::Value &n)
1638
  {
1639
    LpSolverBase::Constr tmp(c);
1640
    LEMON_ASSERT(LpSolverBase::isNaN(tmp.lowerBound()), "Wrong LP constraint");
1641
    tmp.lowerBound()=n;
1642
    return tmp;
1643
  }
1644

	
1645
  ///\e
1646

	
1647
  ///\relates LpSolverBase::DualExpr
1648
  ///
1649
  inline LpSolverBase::DualExpr operator+(const LpSolverBase::DualExpr &a,
1650
                                          const LpSolverBase::DualExpr &b)
1651
  {
1652
    LpSolverBase::DualExpr tmp(a);
1653
    tmp+=b;
1654
    return tmp;
1655
  }
1656
  ///\e
1657

	
1658
  ///\relates LpSolverBase::DualExpr
1659
  ///
1660
  inline LpSolverBase::DualExpr operator-(const LpSolverBase::DualExpr &a,
1661
                                          const LpSolverBase::DualExpr &b)
1662
  {
1663
    LpSolverBase::DualExpr tmp(a);
1664
    tmp-=b;
1665
    return tmp;
1666
  }
1667
  ///\e
1668

	
1669
  ///\relates LpSolverBase::DualExpr
1670
  ///
1671
  inline LpSolverBase::DualExpr operator*(const LpSolverBase::DualExpr &a,
1672
                                          const LpSolverBase::Value &b)
1673
  {
1674
    LpSolverBase::DualExpr tmp(a);
1675
    tmp*=b;
1676
    return tmp;
1677
  }
1678

	
1679
  ///\e
1680

	
1681
  ///\relates LpSolverBase::DualExpr
1682
  ///
1683
  inline LpSolverBase::DualExpr operator*(const LpSolverBase::Value &a,
1684
                                          const LpSolverBase::DualExpr &b)
1685
  {
1686
    LpSolverBase::DualExpr tmp(b);
1687
    tmp*=a;
1688
    return tmp;
1689
  }
1690
  ///\e
1691

	
1692
  ///\relates LpSolverBase::DualExpr
1693
  ///
1694
  inline LpSolverBase::DualExpr operator/(const LpSolverBase::DualExpr &a,
1695
                                          const LpSolverBase::Value &b)
1696
  {
1697
    LpSolverBase::DualExpr tmp(a);
1698
    tmp/=b;
1699
    return tmp;
1700
  }
1701

	
1702

	
1703
} //namespace lemon
1704

	
1705
#endif //LEMON_LP_BASE_H
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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
#include <iostream>
20
#include <vector>
21
#include <lemon/lp_cplex.h>
22

	
23
extern "C" {
24
#include <ilcplex/cplex.h>
25
}
26

	
27

	
28
///\file
29
///\brief Implementation of the LEMON-CPLEX lp solver interface.
30
namespace lemon {
31

	
32
  LpCplex::LpCplex() {
33
    //    env = CPXopenCPLEXdevelop(&status);
34
    env = CPXopenCPLEX(&status);
35
    lp = CPXcreateprob(env, &status, "LP problem");
36
  }
37

	
38
  LpCplex::LpCplex(const LpCplex& cplex) : LpSolverBase() {
39
    env = CPXopenCPLEX(&status);
40
    lp = CPXcloneprob(env, cplex.lp, &status);
41
    rows = cplex.rows;
42
    cols = cplex.cols;
43
  }
44

	
45
  LpCplex::~LpCplex() {
46
    CPXfreeprob(env,&lp);
47
    CPXcloseCPLEX(&env);
48
  }
49

	
50
  LpSolverBase* LpCplex::_newLp()
51
  {
52
    //The first approach opens a new environment
53
    return new LpCplex();
54
  }
55

	
56
  LpSolverBase* LpCplex::_copyLp() {
57
    return new LpCplex(*this);
58
  }
59

	
60
  int LpCplex::_addCol()
61
  {
62
    int i = CPXgetnumcols(env, lp);
63
    Value lb[1],ub[1];
64
    lb[0]=-INF;
65
    ub[0]=INF;
66
    status = CPXnewcols(env, lp, 1, NULL, lb, ub, NULL, NULL);
67
    return i;
68
  }
69

	
70

	
71
  int LpCplex::_addRow()
72
  {
73
    //We want a row that is not constrained
74
    char sense[1];
75
    sense[0]='L';//<= constraint
76
    Value rhs[1];
77
    rhs[0]=INF;
78
    int i = CPXgetnumrows(env, lp);
79
    status = CPXnewrows(env, lp, 1, rhs, sense, NULL, NULL);
80
    return i;
81
  }
82

	
83

	
84
  void LpCplex::_eraseCol(int i) {
85
    CPXdelcols(env, lp, i, i);
86
  }
87

	
88
  void LpCplex::_eraseRow(int i) {
89
    CPXdelrows(env, lp, i, i);
90
  }
91

	
92
  void LpCplex::_getColName(int col, std::string &name) const
93
  {
94
    ///\bug Untested
95
    int storespace;
96
    CPXgetcolname(env, lp, 0, 0, 0, &storespace, col, col);
97
    if (storespace == 0) {
98
      name.clear();
99
      return;
100
    }
101

	
102
    storespace *= -1;
103
    std::vector<char> buf(storespace);
104
    char *names[1];
105
    int dontcare;
106
    ///\bug return code unchecked for error
107
    CPXgetcolname(env, lp, names, &*buf.begin(), storespace,
108
                  &dontcare, col, col);
109
    name = names[0];
110
  }
111

	
112
  void LpCplex::_setColName(int col, const std::string &name)
113
  {
114
    ///\bug Untested
115
    char *names[1];
116
    names[0] = const_cast<char*>(name.c_str());
117
    ///\bug return code unchecked for error
118
    CPXchgcolname(env, lp, 1, &col, names);
119
  }
120

	
121
  int LpCplex::_colByName(const std::string& name) const
122
  {
123
    int index;
124
    if (CPXgetcolindex(env, lp,
125
                       const_cast<char*>(name.c_str()), &index) == 0) {
126
      return index;
127
    }
128
    return -1;
129
  }
130

	
131
  ///\warning Data at index 0 is ignored in the arrays.
132
  void LpCplex::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e)
133
  {
134
    std::vector<int> indices;
135
    std::vector<int> rowlist;
136
    std::vector<Value> values;
137

	
138
    for(ConstRowIterator it=b; it!=e; ++it) {
139
      indices.push_back(it->first);
140
      values.push_back(it->second);
141
      rowlist.push_back(i);
142
    }
143

	
144
    status = CPXchgcoeflist(env, lp, values.size(),
145
                            &rowlist[0], &indices[0], &values[0]);
146
  }
147

	
148
  void LpCplex::_getRowCoeffs(int i, RowIterator b) const {
149
    int tmp1, tmp2, tmp3, length;
150
    CPXgetrows(env, lp, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
151

	
152
    length = -length;
153
    std::vector<int> indices(length);
154
    std::vector<double> values(length);
155

	
156
    CPXgetrows(env, lp, &tmp1, &tmp2, &indices[0], &values[0],
157
               length, &tmp3, i, i);
158

	
159
    for (int i = 0; i < length; ++i) {
160
      *b = std::make_pair(indices[i], values[i]);
161
      ++b;
162
    }
163

	
164
    /// \todo implement
165
  }
166

	
167
  void LpCplex::_setColCoeffs(int i, ConstColIterator b, ConstColIterator e)
168
  {
169
    std::vector<int> indices;
170
    std::vector<int> collist;
171
    std::vector<Value> values;
172

	
173
    for(ConstColIterator it=b; it!=e; ++it) {
174
      indices.push_back(it->first);
175
      values.push_back(it->second);
176
      collist.push_back(i);
177
    }
178

	
179
    status = CPXchgcoeflist(env, lp, values.size(),
180
                            &indices[0], &collist[0], &values[0]);
181
  }
182

	
183
  void LpCplex::_getColCoeffs(int i, ColIterator b) const {
184

	
185
    int tmp1, tmp2, tmp3, length;
186
    CPXgetcols(env, lp, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
187

	
188
    length = -length;
189
    std::vector<int> indices(length);
190
    std::vector<double> values(length);
191

	
192
    CPXgetcols(env, lp, &tmp1, &tmp2, &indices[0], &values[0],
193
               length, &tmp3, i, i);
194

	
195
    for (int i = 0; i < length; ++i) {
196
      *b = std::make_pair(indices[i], values[i]);
197
      ++b;
198
    }
199

	
200
  }
201

	
202
  void LpCplex::_setCoeff(int row, int col, Value value)
203
  {
204
    CPXchgcoef(env, lp, row, col, value);
205
  }
206

	
207
  LpCplex::Value LpCplex::_getCoeff(int row, int col) const
208
  {
209
    LpCplex::Value value;
210
    CPXgetcoef(env, lp, row, col, &value);
211
    return value;
212
  }
213

	
214
  void LpCplex::_setColLowerBound(int i, Value value)
215
  {
216
    int indices[1];
217
    indices[0]=i;
218
    char lu[1];
219
    lu[0]='L';
220
    Value bd[1];
221
    bd[0]=value;
222
    status = CPXchgbds(env, lp, 1, indices, lu, bd);
223

	
224
  }
225

	
226
  LpCplex::Value LpCplex::_getColLowerBound(int i) const
227
  {
228
    LpCplex::Value x;
229
    CPXgetlb (env, lp, &x, i, i);
230
    if (x <= -CPX_INFBOUND) x = -INF;
231
    return x;
232
  }
233

	
234
  void LpCplex::_setColUpperBound(int i, Value value)
235
  {
236
    int indices[1];
237
    indices[0]=i;
238
    char lu[1];
239
    lu[0]='U';
240
    Value bd[1];
241
    bd[0]=value;
242
    status = CPXchgbds(env, lp, 1, indices, lu, bd);
243
  }
244

	
245
  LpCplex::Value LpCplex::_getColUpperBound(int i) const
246
  {
247
    LpCplex::Value x;
248
    CPXgetub (env, lp, &x, i, i);
249
    if (x >= CPX_INFBOUND) x = INF;
250
    return x;
251
  }
252

	
253
  //This will be easier to implement
254
  void LpCplex::_setRowBounds(int i, Value lb, Value ub)
255
  {
256
    //Bad parameter
257
    if (lb==INF || ub==-INF) {
258
      //FIXME error
259
    }
260

	
261
    int cnt=1;
262
    int indices[1];
263
    indices[0]=i;
264
    char sense[1];
265

	
266
    if (lb==-INF){
267
      sense[0]='L';
268
      CPXchgsense(env, lp, cnt, indices, sense);
269
      CPXchgcoef(env, lp, i, -1, ub);
270

	
271
    }
272
    else{
273
      if (ub==INF){
274
        sense[0]='G';
275
        CPXchgsense(env, lp, cnt, indices, sense);
276
        CPXchgcoef(env, lp, i, -1, lb);
277
      }
278
      else{
279
        if (lb == ub){
280
          sense[0]='E';
281
          CPXchgsense(env, lp, cnt, indices, sense);
282
          CPXchgcoef(env, lp, i, -1, lb);
283
        }
284
        else{
285
          sense[0]='R';
286
          CPXchgsense(env, lp, cnt, indices, sense);
287
          CPXchgcoef(env, lp, i, -1, lb);
288
          CPXchgcoef(env, lp, i, -2, ub-lb);
289
        }
290
      }
291
    }
292
  }
293

	
294
//   void LpCplex::_setRowLowerBound(int i, Value value)
295
//   {
296
//     //Not implemented, obsolete
297
//   }
298

	
299
//   void LpCplex::_setRowUpperBound(int i, Value value)
300
//   {
301
//     //Not implemented, obsolete
302
// //     //TODO Ezt kell meg megirni
303
// //     //type of the problem
304
// //     char sense[1];
305
// //     status = CPXgetsense(env, lp, sense, i, i);
306
// //     Value rhs[1];
307
// //     status = CPXgetrhs(env, lp, rhs, i, i);
308

	
309
// //     switch (sense[0]) {
310
// //     case 'L'://<= constraint
311
// //       break;
312
// //     case 'E'://= constraint
313
// //       break;
314
// //     case 'G'://>= constraint
315
// //       break;
316
// //     case 'R'://ranged constraint
317
// //       break;
318
// //     default: ;
319
// //       //FIXME error
320
// //     }
321

	
322
// //     status = CPXchgcoef(env, lp, i, -2, value_rng);
323
//   }
324

	
325
  void LpCplex::_getRowBounds(int i, Value &lb, Value &ub) const
326
  {
327
    char sense;
328
    CPXgetsense(env, lp, &sense,i,i);
329
    lb=-INF;
330
    ub=INF;
331
    switch (sense)
332
      {
333
      case 'L':
334
        CPXgetcoef(env, lp, i, -1, &ub);
335
        break;
336
      case 'G':
337
        CPXgetcoef(env, lp, i, -1, &lb);
338
        break;
339
      case 'E':
340
        CPXgetcoef(env, lp, i, -1, &lb);
341
        ub=lb;
342
        break;
343
      case 'R':
344
        CPXgetcoef(env, lp, i, -1, &lb);
345
        Value x;
346
        CPXgetcoef(env, lp, i, -2, &x);
347
        ub=lb+x;
348
        break;
349
      }
350
  }
351

	
352
  void LpCplex::_setObjCoeff(int i, Value obj_coef)
353
  {
354
    CPXchgcoef(env, lp, -1, i, obj_coef);
355
  }
356

	
357
  LpCplex::Value LpCplex::_getObjCoeff(int i) const
358
  {
359
    Value x;
360
    CPXgetcoef(env, lp, -1, i, &x);
361
    return x;
362
  }
363

	
364
  void LpCplex::_clearObj()
365
  {
366
    for (int i=0;i< CPXgetnumcols(env, lp);++i){
367
      CPXchgcoef(env, lp, -1, i, 0);
368
    }
369

	
370
  }
371
  // The routine returns zero unless an error occurred during the
372
  // optimization. Examples of errors include exhausting available
373
  // memory (CPXERR_NO_MEMORY) or encountering invalid data in the
374
  // CPLEX problem object (CPXERR_NO_PROBLEM). Exceeding a
375
  // user-specified CPLEX limit, or proving the model infeasible or
376
  // unbounded, are not considered errors. Note that a zero return
377
  // value does not necessarily mean that a solution exists. Use query
378
  // routines CPXsolninfo, CPXgetstat, and CPXsolution to obtain
379
  // further information about the status of the optimization.
380
  LpCplex::SolveExitStatus LpCplex::_solve()
381
  {
382
    //CPX_PARAM_LPMETHOD
383
    status = CPXlpopt(env, lp);
384
    //status = CPXprimopt(env, lp);
385
#if CPX_VERSION >= 800
386
    if (status)
387
    {
388
      return UNSOLVED;
389
    }
390
    else
391
    {
392
      switch (CPXgetstat(env, lp))
393
      {
394
        case CPX_STAT_OPTIMAL:
395
        case CPX_STAT_INFEASIBLE:
396
        case CPX_STAT_UNBOUNDED:
397
          return SOLVED;
398
        default:
399
          return UNSOLVED;
400
      }
401
    }
402
#else
403
    if (status == 0){
404
      //We want to exclude some cases
405
      switch (CPXgetstat(env, lp)){
406
      case CPX_OBJ_LIM:
407
      case CPX_IT_LIM_FEAS:
408
      case CPX_IT_LIM_INFEAS:
409
      case CPX_TIME_LIM_FEAS:
410
      case CPX_TIME_LIM_INFEAS:
411
        return UNSOLVED;
412
      default:
413
        return SOLVED;
414
      }
415
    }
416
    else{
417
      return UNSOLVED;
418
    }
419
#endif
420
  }
421

	
422
  LpCplex::Value LpCplex::_getPrimal(int i) const
423
  {
424
    Value x;
425
    CPXgetx(env, lp, &x, i, i);
426
    return x;
427
  }
428

	
429
  LpCplex::Value LpCplex::_getDual(int i) const
430
  {
431
    Value y;
432
    CPXgetpi(env, lp, &y, i, i);
433
    return y;
434
  }
435

	
436
  LpCplex::Value LpCplex::_getPrimalValue() const
437
  {
438
    Value objval;
439
    //method = CPXgetmethod (env, lp);
440
    //printf("CPXgetprobtype %d \n",CPXgetprobtype(env,lp));
441
    CPXgetobjval(env, lp, &objval);
442
    //printf("Objective value: %g \n",objval);
443
    return objval;
444
  }
445
  bool LpCplex::_isBasicCol(int i) const
446
  {
447
    std::vector<int> cstat(CPXgetnumcols(env, lp));
448
    CPXgetbase(env, lp, &*cstat.begin(), NULL);
449
    return (cstat[i]==CPX_BASIC);
450
  }
451

	
452
//7.5-os cplex statusai (Vigyazat: a 9.0-asei masok!)
453
// This table lists the statuses, returned by the CPXgetstat()
454
// routine, for solutions to LP problems or mixed integer problems. If
455
// no solution exists, the return value is zero.
456

	
457
// For Simplex, Barrier
458
// 1          CPX_OPTIMAL
459
//          Optimal solution found
460
// 2          CPX_INFEASIBLE
461
//          Problem infeasible
462
// 3    CPX_UNBOUNDED
463
//          Problem unbounded
464
// 4          CPX_OBJ_LIM
465
//          Objective limit exceeded in Phase II
466
// 5          CPX_IT_LIM_FEAS
467
//          Iteration limit exceeded in Phase II
468
// 6          CPX_IT_LIM_INFEAS
469
//          Iteration limit exceeded in Phase I
470
// 7          CPX_TIME_LIM_FEAS
471
//          Time limit exceeded in Phase II
472
// 8          CPX_TIME_LIM_INFEAS
473
//          Time limit exceeded in Phase I
474
// 9          CPX_NUM_BEST_FEAS
475
//          Problem non-optimal, singularities in Phase II
476
// 10         CPX_NUM_BEST_INFEAS
477
//          Problem non-optimal, singularities in Phase I
478
// 11         CPX_OPTIMAL_INFEAS
479
//          Optimal solution found, unscaled infeasibilities
480
// 12         CPX_ABORT_FEAS
481
//          Aborted in Phase II
482
// 13         CPX_ABORT_INFEAS
483
//          Aborted in Phase I
484
// 14          CPX_ABORT_DUAL_INFEAS
485
//          Aborted in barrier, dual infeasible
486
// 15          CPX_ABORT_PRIM_INFEAS
487
//          Aborted in barrier, primal infeasible
488
// 16          CPX_ABORT_PRIM_DUAL_INFEAS
489
//          Aborted in barrier, primal and dual infeasible
490
// 17          CPX_ABORT_PRIM_DUAL_FEAS
491
//          Aborted in barrier, primal and dual feasible
492
// 18          CPX_ABORT_CROSSOVER
493
//          Aborted in crossover
494
// 19          CPX_INForUNBD
495
//          Infeasible or unbounded
496
// 20   CPX_PIVOT
497
//       User pivot used
498
//
499
//     Ezeket hova tegyem:
500
// ??case CPX_ABORT_DUAL_INFEAS
501
// ??case CPX_ABORT_CROSSOVER
502
// ??case CPX_INForUNBD
503
// ??case CPX_PIVOT
504

	
505
//Some more interesting stuff:
506

	
507
// CPX_PARAM_LPMETHOD  1062  int  LPMETHOD
508
// 0 Automatic
509
// 1 Primal Simplex
510
// 2 Dual Simplex
511
// 3 Network Simplex
512
// 4 Standard Barrier
513
// Default: 0
514
// Description: Method for linear optimization.
515
// Determines which algorithm is used when CPXlpopt() (or "optimize"
516
// in the Interactive Optimizer) is called. Currently the behavior of
517
// the "Automatic" setting is that CPLEX simply invokes the dual
518
// simplex method, but this capability may be expanded in the future
519
// so that CPLEX chooses the method based on problem characteristics
520
#if CPX_VERSION < 900
521
  void statusSwitch(CPXENVptr env,int& stat){
522
    int lpmethod;
523
    CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);
524
    if (lpmethod==2){
525
      if (stat==CPX_UNBOUNDED){
526
        stat=CPX_INFEASIBLE;
527
      }
528
      else{
529
        if (stat==CPX_INFEASIBLE)
530
          stat=CPX_UNBOUNDED;
531
      }
532
    }
533
  }
534
#else
535
  void statusSwitch(CPXENVptr,int&){}
536
#endif
537

	
538
  LpCplex::SolutionStatus LpCplex::_getPrimalStatus() const
539
  {
540
    //Unboundedness not treated well: the following is from cplex 9.0 doc
541
    // About Unboundedness
542

	
543
    // The treatment of models that are unbounded involves a few
544
    // subtleties. Specifically, a declaration of unboundedness means that
545
    // ILOG CPLEX has determined that the model has an unbounded
546
    // ray. Given any feasible solution x with objective z, a multiple of
547
    // the unbounded ray can be added to x to give a feasible solution
548
    // with objective z-1 (or z+1 for maximization models). Thus, if a
549
    // feasible solution exists, then the optimal objective is
550
    // unbounded. Note that ILOG CPLEX has not necessarily concluded that
551
    // a feasible solution exists. Users can call the routine CPXsolninfo
552
    // to determine whether ILOG CPLEX has also concluded that the model
553
    // has a feasible solution.
554

	
555
    int stat = CPXgetstat(env, lp);
556
#if CPX_VERSION >= 800
557
    switch (stat)
558
    {
559
      case CPX_STAT_OPTIMAL:
560
        return OPTIMAL;
561
      case CPX_STAT_UNBOUNDED:
562
        return INFINITE;
563
      case CPX_STAT_INFEASIBLE:
564
        return INFEASIBLE;
565
      default:
566
        return UNDEFINED;
567
    }
568
#else
569
    statusSwitch(env,stat);
570
    //CPXgetstat(env, lp);
571
    //printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL);
572
    switch (stat) {
573
    case 0:
574
      return UNDEFINED; //Undefined
575
    case CPX_OPTIMAL://Optimal
576
      return OPTIMAL;
577
    case CPX_UNBOUNDED://Unbounded
578
      return INFEASIBLE;//In case of dual simplex
579
      //return INFINITE;
580
    case CPX_INFEASIBLE://Infeasible
581
 //    case CPX_IT_LIM_INFEAS:
582
//     case CPX_TIME_LIM_INFEAS:
583
//     case CPX_NUM_BEST_INFEAS:
584
//     case CPX_OPTIMAL_INFEAS:
585
//     case CPX_ABORT_INFEAS:
586
//     case CPX_ABORT_PRIM_INFEAS:
587
//     case CPX_ABORT_PRIM_DUAL_INFEAS:
588
      return INFINITE;//In case of dual simplex
589
      //return INFEASIBLE;
590
//     case CPX_OBJ_LIM:
591
//     case CPX_IT_LIM_FEAS:
592
//     case CPX_TIME_LIM_FEAS:
593
//     case CPX_NUM_BEST_FEAS:
594
//     case CPX_ABORT_FEAS:
595
//     case CPX_ABORT_PRIM_DUAL_FEAS:
596
//       return FEASIBLE;
597
    default:
598
      return UNDEFINED; //Everything else comes here
599
      //FIXME error
600
    }
601
#endif
602
  }
603

	
604
//9.0-as cplex verzio statusai
605
// CPX_STAT_ABORT_DUAL_OBJ_LIM
606
// CPX_STAT_ABORT_IT_LIM
607
// CPX_STAT_ABORT_OBJ_LIM
608
// CPX_STAT_ABORT_PRIM_OBJ_LIM
609
// CPX_STAT_ABORT_TIME_LIM
610
// CPX_STAT_ABORT_USER
611
// CPX_STAT_FEASIBLE_RELAXED
612
// CPX_STAT_INFEASIBLE
613
// CPX_STAT_INForUNBD
614
// CPX_STAT_NUM_BEST
615
// CPX_STAT_OPTIMAL
616
// CPX_STAT_OPTIMAL_FACE_UNBOUNDED
617
// CPX_STAT_OPTIMAL_INFEAS
618
// CPX_STAT_OPTIMAL_RELAXED
619
// CPX_STAT_UNBOUNDED
620

	
621
  LpCplex::SolutionStatus LpCplex::_getDualStatus() const
622
  {
623
    int stat = CPXgetstat(env, lp);
624
#if CPX_VERSION >= 800
625
    switch (stat)
626
    {
627
      case CPX_STAT_OPTIMAL:
628
        return OPTIMAL;
629
      case CPX_STAT_UNBOUNDED:
630
        return INFEASIBLE;
631
      default:
632
        return UNDEFINED;
633
    }
634
#else
635
    statusSwitch(env,stat);
636
    switch (stat) {
637
    case 0:
638
      return UNDEFINED; //Undefined
639
    case CPX_OPTIMAL://Optimal
640
      return OPTIMAL;
641
    case CPX_UNBOUNDED:
642
     return INFEASIBLE;
643
    default:
644
      return UNDEFINED; //Everything else comes here
645
      //FIXME error
646
    }
647
#endif
648
  }
649

	
650
  LpCplex::ProblemTypes LpCplex::_getProblemType() const
651
  {
652
    int stat = CPXgetstat(env, lp);
653
#if CPX_VERSION >= 800
654
    switch (stat)
655
    {
656
      case CPX_STAT_OPTIMAL:
657
        return PRIMAL_DUAL_FEASIBLE;
658
      case CPX_STAT_UNBOUNDED:
659
         return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
660
      default:
661
        return UNKNOWN;
662
    }
663
#else
664
    switch (stat) {
665
    case CPX_OPTIMAL://Optimal
666
        return PRIMAL_DUAL_FEASIBLE;
667
    case CPX_UNBOUNDED:
668
         return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
669
//         return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
670
//         return PRIMAL_DUAL_INFEASIBLE;
671

	
672
//Seems to be that this is all we can say for sure
673
    default:
674
        //In all other cases
675
        return UNKNOWN;
676
      //FIXME error
677
    }
678
#endif
679
  }
680

	
681
  void LpCplex::_setMax()
682
  {
683
    CPXchgobjsen(env, lp, CPX_MAX);
684
   }
685
  void LpCplex::_setMin()
686
  {
687
    CPXchgobjsen(env, lp, CPX_MIN);
688
   }
689

	
690
  bool LpCplex::_isMax() const
691
  {
692
    if (CPXgetobjsen(env, lp)==CPX_MAX)
693
      return true;
694
    else
695
      return false;
696
  }
697

	
698
} //namespace lemon
699

	
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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_CPLEX_H
20
#define LEMON_LP_CPLEX_H
21

	
22
///\file
23
///\brief Header of the LEMON-CPLEX lp solver interface.
24

	
25
#include <lemon/lp_base.h>
26

	
27
struct cpxenv;
28
struct cpxlp;
29

	
30
namespace lemon {
31

	
32

	
33
  /// \brief Interface for the CPLEX solver
34
  ///
35
  /// This class implements an interface for the CPLEX LP solver.
36
  class LpCplex :virtual public LpSolverBase {
37

	
38
  public:
39

	
40
    typedef LpSolverBase Parent;
41

	
42
    /// \e
43
    int status;
44
    cpxenv* env;
45
    cpxlp* lp;
46

	
47

	
48
    /// \e
49
    LpCplex();
50
    /// \e
51
    LpCplex(const LpCplex&);
52
    /// \e
53
    ~LpCplex();
54

	
55
  protected:
56
    virtual LpSolverBase* _newLp();
57
    virtual LpSolverBase* _copyLp();
58

	
59

	
60
    virtual int _addCol();
61
    virtual int _addRow();
62
    virtual void _eraseCol(int i);
63
    virtual void _eraseRow(int i);
64
    virtual void _getColName(int col, std::string & name) const;
65
    virtual void _setColName(int col, const std::string & name);
66
    virtual int _colByName(const std::string& name) const;
67
    virtual void _setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e);
68
    virtual void _getRowCoeffs(int i, RowIterator b) const;
69
    virtual void _setColCoeffs(int i, ConstColIterator b, ConstColIterator e);
70
    virtual void _getColCoeffs(int i, ColIterator b) const;
71
    virtual void _setCoeff(int row, int col, Value value);
72
    virtual Value _getCoeff(int row, int col) const;
73

	
74
    virtual void _setColLowerBound(int i, Value value);
75
    virtual Value _getColLowerBound(int i) const;
76
    virtual void _setColUpperBound(int i, Value value);
77
    virtual Value _getColUpperBound(int i) const;
78

	
79
//     virtual void _setRowLowerBound(int i, Value value);
80
//     virtual void _setRowUpperBound(int i, Value value);
81
    virtual void _setRowBounds(int i, Value lower, Value upper);
82
    virtual void _getRowBounds(int i, Value &lb, Value &ub) const;
83
    virtual void _setObjCoeff(int i, Value obj_coef);
84
    virtual Value _getObjCoeff(int i) const;
85
    virtual void _clearObj();
86

	
87

	
88
    virtual SolveExitStatus _solve();
89
    virtual Value _getPrimal(int i) const;
90
    virtual Value _getDual(int i) const;
91
    virtual Value _getPrimalValue() const;
92
    virtual bool _isBasicCol(int i) const;
93

	
94
    virtual SolutionStatus _getPrimalStatus() const;
95
    virtual SolutionStatus _getDualStatus() const;
96
    virtual ProblemTypes _getProblemType() const;
97

	
98

	
99
    virtual void _setMax();
100
    virtual void _setMin();
101

	
102
    virtual bool _isMax() const;
103

	
104
  public:
105

	
106
    cpxenv* cplexEnv() { return env; }
107
    cpxlp* cplexLp() { return lp; }
108

	
109
  };
110
} //END OF NAMESPACE LEMON
111

	
112
#endif //LEMON_LP_CPLEX_H
113

	
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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>
24

	
25
extern "C" {
26
#include <glpk.h>
27
}
28

	
29
#if GLP_MAJOR_VERSION > 4 || (GLP_MAJOR_VERSION == 4 && GLP_MINOR_VERSION > 15)
30
#define LEMON_glp(func) (glp_##func)
31
#define LEMON_lpx(func) (lpx_##func)
32

	
33
#define LEMON_GLP(def) (GLP_##def)
34
#define LEMON_LPX(def) (LPX_##def)
35

	
36
#else
37

	
38
#define LEMON_glp(func) (lpx_##func)
39
#define LEMON_lpx(func) (lpx_##func)
40

	
41
#define LEMON_GLP(def) (LPX_##def)
42
#define LEMON_LPX(def) (LPX_##def)
43

	
44
#endif
45

	
46
namespace lemon {
47

	
48
  LpGlpk::LpGlpk() : Parent() {
49
    solved = false;
50
    rows = _lp_bits::LpId(1);
51
    cols = _lp_bits::LpId(1);
52
    lp = LEMON_glp(create_prob)();
53
    LEMON_glp(create_index)(lp);
54
    messageLevel(0);
55
  }
56

	
57
  LpGlpk::LpGlpk(const LpGlpk &glp) : Parent() {
58
    solved = false;
59
    rows = _lp_bits::LpId(1);
60
    cols = _lp_bits::LpId(1);
61
    lp = LEMON_glp(create_prob)();
62
    LEMON_glp(create_index)(lp);
63
    messageLevel(0);
64
    //Coefficient matrix, row bounds
65
    LEMON_glp(add_rows)(lp, LEMON_glp(get_num_rows)(glp.lp));
66
    LEMON_glp(add_cols)(lp, LEMON_glp(get_num_cols)(glp.lp));
67
    int len;
68
    std::vector<int> ind(1+LEMON_glp(get_num_cols)(glp.lp));
69
    std::vector<Value> val(1+LEMON_glp(get_num_cols)(glp.lp));
70
    for (int i=1;i<=LEMON_glp(get_num_rows)(glp.lp);++i)
71
      {
72
        len=LEMON_glp(get_mat_row)(glp.lp,i,&*ind.begin(),&*val.begin());
73
        LEMON_glp(set_mat_row)(lp, i,len,&*ind.begin(),&*val.begin());
74
        LEMON_glp(set_row_bnds)(lp,i,
75
                                LEMON_glp(get_row_type)(glp.lp,i),
76
                                LEMON_glp(get_row_lb)(glp.lp,i),
77
                                LEMON_glp(get_row_ub)(glp.lp,i));
78
      }
79

	
80
    //Objective function, coloumn bounds
81
    LEMON_glp(set_obj_dir)(lp, LEMON_glp(get_obj_dir)(glp.lp));
82
    //Objectif function's constant term treated separately
83
    LEMON_glp(set_obj_coef)(lp,0,LEMON_glp(get_obj_coef)(glp.lp,0));
84
    for (int i=1;i<=LEMON_glp(get_num_cols)(glp.lp);++i)
85
      {
86
        LEMON_glp(set_obj_coef)(lp,i,
87
                                LEMON_glp(get_obj_coef)(glp.lp,i));
88
        LEMON_glp(set_col_bnds)(lp,i,
89
                                LEMON_glp(get_col_type)(glp.lp,i),
90
                                LEMON_glp(get_col_lb)(glp.lp,i),
91
                                LEMON_glp(get_col_ub)(glp.lp,i));
92
      }
93
    rows = glp.rows;
94
    cols = glp.cols;
95
  }
96

	
97
  LpGlpk::~LpGlpk() {
98
    LEMON_glp(delete_prob)(lp);
99
  }
100

	
101
  int LpGlpk::_addCol() {
102
    int i=LEMON_glp(add_cols)(lp, 1);
103
    LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(FR), 0.0, 0.0);
104
    solved = false;
105
    return i;
106
  }
107

	
108
  ///\e
109

	
110

	
111
  LpSolverBase* LpGlpk::_newLp()
112
  {
113
    LpGlpk* newlp = new LpGlpk;
114
    return newlp;
115
  }
116

	
117
  ///\e
118

	
119
  LpSolverBase* LpGlpk::_copyLp()
120
  {
121
    LpGlpk *newlp = new LpGlpk(*this);
122
    return newlp;
123
  }
124

	
125
  int LpGlpk::_addRow() {
126
    int i=LEMON_glp(add_rows)(lp, 1);
127
    solved = false;
128
    return i;
129
  }
130

	
131

	
132
  void LpGlpk::_eraseCol(int i) {
133
    int ca[2];
134
    ca[1]=i;
135
    LEMON_glp(del_cols)(lp, 1, ca);
136
    solved = false;
137
  }
138

	
139
  void LpGlpk::_eraseRow(int i) {
140
    int ra[2];
141
    ra[1]=i;
142
    LEMON_glp(del_rows)(lp, 1, ra);
143
    solved = false;
144
  }
145

	
146
  void LpGlpk::_getColName(int c, std::string & name) const
147
  {
148

	
149
    const char *n = LEMON_glp(get_col_name)(lp,c);
150
    name = n?n:"";
151
  }
152

	
153

	
154
  void LpGlpk::_setColName(int c, const std::string & name)
155
  {
156
    LEMON_glp(set_col_name)(lp,c,const_cast<char*>(name.c_str()));
157

	
158
  }
159

	
160
  int LpGlpk::_colByName(const std::string& name) const
161
  {
162
    int k = LEMON_glp(find_col)(lp, const_cast<char*>(name.c_str()));
163
    return k > 0 ? k : -1;
164
  }
165

	
166

	
167
  void LpGlpk::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e)
168
  {
169
    std::vector<int> indices;
170
    std::vector<Value> values;
171

	
172
    indices.push_back(0);
173
    values.push_back(0);
174

	
175
    for(ConstRowIterator it=b; it!=e; ++it) {
176
      indices.push_back(it->first);
177
      values.push_back(it->second);
178
    }
179

	
180
    LEMON_glp(set_mat_row)(lp, i, values.size() - 1,
181
                                &indices[0], &values[0]);
182

	
183
    solved = false;
184
  }
185

	
186
  void LpGlpk::_getRowCoeffs(int ix, RowIterator b) const
187
  {
188
    int length = LEMON_glp(get_mat_row)(lp, ix, 0, 0);
189

	
190
    std::vector<int> indices(length + 1);
191
    std::vector<Value> values(length + 1);
192

	
193
    LEMON_glp(get_mat_row)(lp, ix, &indices[0], &values[0]);
194

	
195
    for (int i = 1; i <= length; ++i) {
196
      *b = std::make_pair(indices[i], values[i]);
197
      ++b;
198
    }
199
  }
200

	
201
  void LpGlpk::_setColCoeffs(int ix, ConstColIterator b, ConstColIterator e) {
202

	
203
    std::vector<int> indices;
204
    std::vector<Value> values;
205

	
206
    indices.push_back(0);
207
    values.push_back(0);
208

	
209
    for(ConstColIterator it=b; it!=e; ++it) {
210
      indices.push_back(it->first);
211
      values.push_back(it->second);
212
    }
213

	
214
    LEMON_glp(set_mat_col)(lp, ix, values.size() - 1,
215
                                &indices[0], &values[0]);
216

	
217
    solved = false;
218
  }
219

	
220
  void LpGlpk::_getColCoeffs(int ix, ColIterator b) const
221
  {
222
    int length = LEMON_glp(get_mat_col)(lp, ix, 0, 0);
223

	
224
    std::vector<int> indices(length + 1);
225
    std::vector<Value> values(length + 1);
226

	
227
    LEMON_glp(get_mat_col)(lp, ix, &indices[0], &values[0]);
228

	
229
    for (int i = 1; i <= length; ++i) {
230
      *b = std::make_pair(indices[i], values[i]);
231
      ++b;
232
    }
233
  }
234

	
235
  void LpGlpk::_setCoeff(int ix, int jx, Value value)
236
  {
237

	
238
    if (LEMON_glp(get_num_cols)(lp) < LEMON_glp(get_num_rows)(lp)) {
239

	
240
      int length=LEMON_glp(get_mat_row)(lp, ix, 0, 0);
241

	
242
      std::vector<int> indices(length + 2);
243
      std::vector<Value> values(length + 2);
244

	
245
      LEMON_glp(get_mat_row)(lp, ix, &indices[0], &values[0]);
246

	
247
      //The following code does not suppose that the elements of the
248
      //array indices are sorted
249
      bool found=false;
250
      for (int i = 1; i <= length; ++i) {
251
        if (indices[i]==jx){
252
          found=true;
253
          values[i]=value;
254
          break;
255
        }
256
      }
257
      if (!found){
258
        ++length;
259
        indices[length]=jx;
260
        values[length]=value;
261
      }
262

	
263
      LEMON_glp(set_mat_row)(lp, ix, length, &indices[0], &values[0]);
264

	
265
    } else {
266

	
267
      int length=LEMON_glp(get_mat_col)(lp, jx, 0, 0);
268

	
269
      std::vector<int> indices(length + 2);
270
      std::vector<Value> values(length + 2);
271

	
272
      LEMON_glp(get_mat_col)(lp, jx, &indices[0], &values[0]);
273

	
274
      //The following code does not suppose that the elements of the
275
      //array indices are sorted
276
      bool found=false;
277
      for (int i = 1; i <= length; ++i) {
278
        if (indices[i]==ix){
279
          found=true;
280
          values[i]=value;
281
          break;
282
        }
283
      }
284
      if (!found){
285
        ++length;
286
        indices[length]=ix;
287
        values[length]=value;
288
      }
289

	
290
      LEMON_glp(set_mat_col)(lp, jx, length, &indices[0], &values[0]);
291
    }
292

	
293
    solved = false;
294
  }
295

	
296
  LpGlpk::Value LpGlpk::_getCoeff(int ix, int jx) const
297
  {
298

	
299
    int length=LEMON_glp(get_mat_row)(lp, ix, 0, 0);
300

	
301
    std::vector<int> indices(length + 1);
302
    std::vector<Value> values(length + 1);
303

	
304
    LEMON_glp(get_mat_row)(lp, ix, &indices[0], &values[0]);
305

	
306
    //The following code does not suppose that the elements of the
307
    //array indices are sorted
308
    for (int i = 1; i <= length; ++i) {
309
      if (indices[i]==jx){
310
        return values[i];
311
      }
312
    }
313
    return 0;
314

	
315
  }
316

	
317

	
318
  void LpGlpk::_setColLowerBound(int i, Value lo)
319
  {
320
    if (lo==INF) {
321
      //FIXME error
322
    }
323
    int b=LEMON_glp(get_col_type)(lp, i);
324
    double up=LEMON_glp(get_col_ub)(lp, i);
325
    if (lo==-INF) {
326
      switch (b) {
327
      case LEMON_GLP(FR):
328
      case LEMON_GLP(LO):
329
        LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(FR), lo, up);
330
        break;
331
      case LEMON_GLP(UP):
332
        break;
333
      case LEMON_GLP(DB):
334
      case LEMON_GLP(FX):
335
        LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(UP), lo, up);
336
        break;
337
      default: ;
338
        //FIXME error
339
      }
340
    } else {
341
      switch (b) {
342
      case LEMON_GLP(FR):
343
      case LEMON_GLP(LO):
344
        LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(LO), lo, up);
345
        break;
346
      case LEMON_GLP(UP):
347
      case LEMON_GLP(DB):
348
      case LEMON_GLP(FX):
349
        if (lo==up)
350
          LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(FX), lo, up);
351
        else
352
          LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(DB), lo, up);
353
        break;
354
      default: ;
355
        //FIXME error
356
      }
357
    }
358

	
359
    solved = false;
360
  }
361

	
362
  LpGlpk::Value LpGlpk::_getColLowerBound(int i) const
363
  {
364
    int b=LEMON_glp(get_col_type)(lp, i);
365
      switch (b) {
366
      case LEMON_GLP(LO):
367
      case LEMON_GLP(DB):
368
      case LEMON_GLP(FX):
369
        return LEMON_glp(get_col_lb)(lp, i);
370
      default: ;
371
        return -INF;
372
      }
373
  }
374

	
375
  void LpGlpk::_setColUpperBound(int i, Value up)
376
  {
377
    if (up==-INF) {
378
      //FIXME error
379
    }
380
    int b=LEMON_glp(get_col_type)(lp, i);
381
    double lo=LEMON_glp(get_col_lb)(lp, i);
382
    if (up==INF) {
383
      switch (b) {
384
      case LEMON_GLP(FR):
385
      case LEMON_GLP(LO):
386
        break;
387
      case LEMON_GLP(UP):
388
        LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(FR), lo, up);
389
        break;
390
      case LEMON_GLP(DB):
391
      case LEMON_GLP(FX):
392
        LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(LO), lo, up);
393
        break;
394
      default: ;
395
        //FIXME error
396
      }
397
    } else {
398
      switch (b) {
399
      case LEMON_GLP(FR):
400
        LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(UP), lo, up);
401
        break;
402
      case LEMON_GLP(UP):
403
        LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(UP), lo, up);
404
        break;
405
      case LEMON_GLP(LO):
406
      case LEMON_GLP(DB):
407
      case LEMON_GLP(FX):
408
        if (lo==up)
409
          LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(FX), lo, up);
410
        else
411
          LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(DB), lo, up);
412
        break;
413
      default: ;
414
        //FIXME error
415
      }
416
    }
417

	
418
    solved = false;
419
  }
420

	
421
  LpGlpk::Value LpGlpk::_getColUpperBound(int i) const
422
  {
423
    int b=LEMON_glp(get_col_type)(lp, i);
424
      switch (b) {
425
      case LEMON_GLP(UP):
426
      case LEMON_GLP(DB):
427
      case LEMON_GLP(FX):
428
        return LEMON_glp(get_col_ub)(lp, i);
429
      default: ;
430
        return INF;
431
      }
432
  }
433

	
434
  void LpGlpk::_setRowBounds(int i, Value lb, Value ub)
435
  {
436
    //Bad parameter
437
    if (lb==INF || ub==-INF) {
438
      //FIXME error
439
    }
440

	
441
    if (lb == -INF){
442
      if (ub == INF){
443
        LEMON_glp(set_row_bnds)(lp, i, LEMON_GLP(FR), lb, ub);
444
      }
445
      else{
446
        LEMON_glp(set_row_bnds)(lp, i, LEMON_GLP(UP), lb, ub);
447
      }
448
    }
449
    else{
450
      if (ub==INF){
451
        LEMON_glp(set_row_bnds)(lp, i, LEMON_GLP(LO), lb, ub);
452

	
453
      }
454
      else{
455
        if (lb == ub){
456
          LEMON_glp(set_row_bnds)(lp, i, LEMON_GLP(FX), lb, ub);
457
        }
458
        else{
459
          LEMON_glp(set_row_bnds)(lp, i, LEMON_GLP(DB), lb, ub);
460
        }
461
      }
462
    }
463

	
464
    solved = false;
465
  }
466

	
467
  void LpGlpk::_getRowBounds(int i, Value &lb, Value &ub) const
468
  {
469

	
470
    int b=LEMON_glp(get_row_type)(lp, i);
471
    switch (b) {
472
    case LEMON_GLP(FR):
473
    case LEMON_GLP(UP):
474
      lb = -INF;
475
        break;
476
    default:
477
      lb=LEMON_glp(get_row_lb)(lp, i);
478
    }
479

	
480
    switch (b) {
481
    case LEMON_GLP(FR):
482
    case LEMON_GLP(LO):
483
      ub = INF;
484
        break;
485
    default:
486
      ub=LEMON_glp(get_row_ub)(lp, i);
487
    }
488

	
489
  }
490

	
491
  void LpGlpk::_setObjCoeff(int i, Value obj_coef)
492
  {
493
    //i=0 means the constant term (shift)
494
    LEMON_glp(set_obj_coef)(lp, i, obj_coef);
495

	
496
    solved = false;
497
  }
498

	
499
  LpGlpk::Value LpGlpk::_getObjCoeff(int i) const {
500
    //i=0 means the constant term (shift)
501
    return LEMON_glp(get_obj_coef)(lp, i);
502
  }
503

	
504
  void LpGlpk::_clearObj()
505
  {
506
    for (int i=0;i<=LEMON_glp(get_num_cols)(lp);++i){
507
      LEMON_glp(set_obj_coef)(lp, i, 0);
508
    }
509

	
510
    solved = false;
511
  }
512

	
513
  LpGlpk::SolveExitStatus LpGlpk::_solve()
514
  {
515
    // A way to check the problem to be solved
516
    //LEMON_glp(write_cpxlp(lp,"naittvan.cpx");
517

	
518
    LEMON_lpx(std_basis)(lp);
519
    int i =  LEMON_lpx(simplex)(lp);
520

	
521
    switch (i) {
522
    case LEMON_LPX(E_OK):
523
      solved = true;
524
      return SOLVED;
525
    default:
526
      return UNSOLVED;
527
    }
528
  }
529

	
530
  LpGlpk::Value LpGlpk::_getPrimal(int i) const
531
  {
532
    return LEMON_glp(get_col_prim)(lp,i);
533
  }
534

	
535
  LpGlpk::Value LpGlpk::_getDual(int i) const
536
  {
537
    return LEMON_glp(get_row_dual)(lp,i);
538
  }
539

	
540
  LpGlpk::Value LpGlpk::_getPrimalValue() const
541
  {
542
    return LEMON_glp(get_obj_val)(lp);
543
  }
544
  bool LpGlpk::_isBasicCol(int i) const
545
  {
546
    return (LEMON_glp(get_col_stat)(lp, i)==LEMON_GLP(BS));
547
  }
548

	
549

	
550
  LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus() const
551
  {
552
    if (!solved) return UNDEFINED;
553
    int stat=  LEMON_lpx(get_status)(lp);
554
    switch (stat) {
555
    case LEMON_LPX(UNDEF)://Undefined (no solve has been run yet)
556
      return UNDEFINED;
557
    case LEMON_LPX(NOFEAS)://There is no feasible solution (primal, I guess)
558
    case LEMON_LPX(INFEAS)://Infeasible
559
      return INFEASIBLE;
560
    case LEMON_LPX(UNBND)://Unbounded
561
      return INFINITE;
562
    case LEMON_LPX(FEAS)://Feasible
563
      return FEASIBLE;
564
    case LEMON_LPX(OPT)://Feasible
565
      return OPTIMAL;
566
    default:
567
      return UNDEFINED; //to avoid gcc warning
568
      //FIXME error
569
    }
570
  }
571

	
572
  LpGlpk::SolutionStatus LpGlpk::_getDualStatus() const
573
  {
574
    if (!solved) return UNDEFINED;
575
    switch (LEMON_lpx(get_dual_stat)(lp)) {
576
    case LEMON_LPX(D_UNDEF)://Undefined (no solve has been run yet)
577
      return UNDEFINED;
578
    case LEMON_LPX(D_NOFEAS)://There is no dual feasible solution
579
//    case LEMON_LPX(D_INFEAS://Infeasible
580
      return INFEASIBLE;
581
    case LEMON_LPX(D_FEAS)://Feasible
582
      switch (LEMON_lpx(get_status)(lp)) {
583
      case LEMON_LPX(NOFEAS):
584
        return INFINITE;
585
      case LEMON_LPX(OPT):
586
        return OPTIMAL;
587
      default:
588
        return FEASIBLE;
589
      }
590
    default:
591
      return UNDEFINED; //to avoid gcc warning
592
      //FIXME error
593
    }
594
  }
595

	
596
  LpGlpk::ProblemTypes LpGlpk::_getProblemType() const
597
  {
598
    if (!solved) return UNKNOWN;
599
      //int stat=  LEMON_glp(get_status(lp);
600
    int statp=  LEMON_lpx(get_prim_stat)(lp);
601
    int statd=  LEMON_lpx(get_dual_stat)(lp);
602
    if (statp==LEMON_LPX(P_FEAS) && statd==LEMON_LPX(D_FEAS))
603
        return PRIMAL_DUAL_FEASIBLE;
604
    if (statp==LEMON_LPX(P_FEAS) && statd==LEMON_LPX(D_NOFEAS))
605
        return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
606
    if (statp==LEMON_LPX(P_NOFEAS) && statd==LEMON_LPX(D_FEAS))
607
        return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
608
    if (statp==LEMON_LPX(P_NOFEAS) && statd==LEMON_LPX(D_NOFEAS))
609
        return PRIMAL_DUAL_INFEASIBLE;
610
    //In all other cases
611
    return UNKNOWN;
612
  }
613

	
614
  void LpGlpk::_setMax()
615
  {
616
    solved = false;
617
    LEMON_glp(set_obj_dir)(lp, LEMON_GLP(MAX));
618
  }
619

	
620
  void LpGlpk::_setMin()
621
  {
622
    solved = false;
623
    LEMON_glp(set_obj_dir)(lp, LEMON_GLP(MIN));
624
  }
625

	
626
  bool LpGlpk::_isMax() const
627
  {
628
    return (LEMON_glp(get_obj_dir)(lp)==LEMON_GLP(MAX));
629
  }
630

	
631

	
632

	
633
  void LpGlpk::messageLevel(int m)
634
  {
635
    LEMON_lpx(set_int_parm)(lp, LEMON_LPX(K_MSGLEV), m);
636
  }
637

	
638
  void LpGlpk::presolver(bool b)
639
  {
640
    LEMON_lpx(set_int_parm)(lp, LEMON_LPX(K_PRESOL), b);
641
  }
642

	
643

	
644
} //END OF NAMESPACE LEMON
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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_H
20
#define LEMON_LP_GLPK_H
21

	
22
///\file
23
///\brief Header of the LEMON-GLPK lp solver interface.
24
///\ingroup lp_group
25

	
26
#include <lemon/lp_base.h>
27

	
28
// forward declaration
29
#ifndef _GLP_PROB
30
#define _GLP_PROB
31
typedef struct { double _prob; } glp_prob;
32
/* LP/MIP problem object */
33
#endif
34

	
35
namespace lemon {
36

	
37

	
38
  /// \brief Interface for the GLPK LP solver
39
  ///
40
  /// This class implements an interface for the GLPK LP solver.
41
  ///\ingroup lp_group
42
  class LpGlpk : virtual public LpSolverBase {
43
  protected:
44

	
45
    typedef glp_prob LPX;
46
    glp_prob* lp;
47
    bool solved;
48

	
49
  public:
50

	
51
    typedef LpSolverBase Parent;
52

	
53
    LpGlpk();
54
    LpGlpk(const LpGlpk &);
55
    ~LpGlpk();
56

	
57
  protected:
58
    virtual LpSolverBase* _newLp();
59
    virtual LpSolverBase* _copyLp();
60

	
61
    virtual int _addCol();
62
    virtual int _addRow();
63
    virtual void _eraseCol(int i);
64
    virtual void _eraseRow(int i);
65
    virtual void _getColName(int col, std::string & name) const;
66
    virtual void _setColName(int col, const std::string & name);
67
    virtual int _colByName(const std::string& name) const;
68
    virtual void _setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e);
69
    virtual void _getRowCoeffs(int i, RowIterator b) const;
70
    virtual void _setColCoeffs(int i, ConstColIterator b, ConstColIterator e);
71
    virtual void _getColCoeffs(int i, ColIterator b) const;
72
    virtual void _setCoeff(int row, int col, Value value);
73
    virtual Value _getCoeff(int row, int col) const;
74

	
75
    virtual void _setColLowerBound(int i, Value value);
76
    virtual Value _getColLowerBound(int i) const;
77
    virtual void _setColUpperBound(int i, Value value);
78
    virtual Value _getColUpperBound(int i) const;
79

	
80
    virtual void _setRowBounds(int i, Value lower, Value upper);
81
    virtual void _getRowBounds(int i, Value &lb, Value &ub) const;
82
    virtual void _setObjCoeff(int i, Value obj_coef);
83
    virtual Value _getObjCoeff(int i) const;
84
    virtual void _clearObj();
85

	
86
    ///\e
87

	
88
    ///\todo It should be clarified
89
    ///
90
    virtual SolveExitStatus _solve();
91
    virtual Value _getPrimal(int i) const;
92
    virtual Value _getDual(int i) const;
93
    virtual Value _getPrimalValue() const;
94
    virtual bool _isBasicCol(int i) const;
95
    ///\e
96

	
97
    ///\todo It should be clarified
98
    ///
99
    virtual SolutionStatus _getPrimalStatus() const;
100
    virtual SolutionStatus _getDualStatus() const;
101
    virtual ProblemTypes _getProblemType() const;
102

	
103
    virtual void _setMax();
104
    virtual void _setMin();
105

	
106
    virtual bool _isMax() const;
107

	
108
  public:
109
    ///Set the verbosity of the messages
110

	
111
    ///Set the verbosity of the messages
112
    ///
113
    ///\param m is the level of the messages output by the solver routines.
114
    ///The possible values are:
115
    ///- 0 --- no output (default value)
116
    ///- 1 --- error messages only
117
    ///- 2 --- normal output
118
    ///- 3 --- full output (includes informational messages)
119
    void messageLevel(int m);
120
    ///Turns on or off the presolver
121

	
122
    ///Turns on (\c b is \c true) or off (\c b is \c false) the presolver
123
    ///
124
    ///The presolver is off by default.
125
    void presolver(bool b);
126

	
127
    ///Pointer to the underlying GLPK data structure.
128
    LPX *lpx() {return lp;}
129

	
130
    ///Returns the constraint identifier understood by GLPK.
131
    int lpxRow(Row r) { return _lpId(r); }
132

	
133
    ///Returns the variable identifier understood by GLPK.
134
    int lpxCol(Col c) { return _lpId(c); }
135
  };
136
} //END OF NAMESPACE LEMON
137

	
138
#endif //LEMON_LP_GLPK_H
139

	
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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
#include <lemon/lp_skeleton.h>
20

	
21
///\file
22
///\brief A skeleton file to implement LP solver interfaces
23
namespace lemon {
24

	
25
  LpSolverBase* LpSkeleton::_newLp()
26
  {
27
    LpSolverBase *tmp=0;
28
    return tmp;
29
  }
30

	
31
  LpSolverBase* LpSkeleton::_copyLp()
32
  {
33
    LpSolverBase *tmp=0;
34
    return tmp;
35
  }
36

	
37
  int LpSkeleton::_addCol()
38
  {
39
    return ++col_num;
40
  }
41

	
42
  int LpSkeleton::_addRow()
43
  {
44
    return ++row_num;
45
  }
46

	
47
  void LpSkeleton::_eraseCol(int ) {
48
  }
49

	
50
  void LpSkeleton::_eraseRow(int) {
51
  }
52

	
53
  void LpSkeleton::_getColName(int, std::string &) const {
54
  }
55

	
56

	
57
  void LpSkeleton::_setColName(int, const std::string &) {
58
  }
59

	
60
  int LpSkeleton::_colByName(const std::string&) const { return -1; }
61

	
62

	
63
  void LpSkeleton::_setRowCoeffs(int, ConstRowIterator, ConstRowIterator) {
64
  }
65

	
66
  void LpSkeleton::_getRowCoeffs(int, RowIterator) const {
67
  }
68

	
69
  void LpSkeleton::_setColCoeffs(int, ConstColIterator, ConstColIterator) {
70
  }
71

	
72
  void LpSkeleton::_getColCoeffs(int, ColIterator) const {
73
  }
74

	
75
  void LpSkeleton::_setCoeff(int, int, Value )
76
  {
77
  }
78

	
79
  LpSkeleton::Value LpSkeleton::_getCoeff(int, int) const
80
  {
81
    return 0;
82
  }
83

	
84

	
85
  void LpSkeleton::_setColLowerBound(int, Value)
86
  {
87
  }
88

	
89
  LpSkeleton::Value LpSkeleton::_getColLowerBound(int) const
90
  {
91
    return 0;
92
  }
93

	
94
  void LpSkeleton::_setColUpperBound(int, Value)
95
  {
96
  }
97

	
98
  LpSkeleton::Value LpSkeleton::_getColUpperBound(int) const
99
  {
100
    return 0;
101
  }
102

	
103
//   void LpSkeleton::_setRowLowerBound(int, Value)
104
//   {
105
//   }
106

	
107
//   void LpSkeleton::_setRowUpperBound(int, Value)
108
//   {
109
//   }
110

	
111
  void LpSkeleton::_setRowBounds(int, Value, Value)
112
  {
113
  }
114

	
115
  void LpSkeleton::_getRowBounds(int, Value&, Value&) const
116
  {
117
  }
118

	
119
  void LpSkeleton::_setObjCoeff(int, Value)
120
  {
121
  }
122

	
123
  LpSkeleton::Value LpSkeleton::_getObjCoeff(int) const
124
  {
125
    return 0;
126
  }
127

	
128
  void LpSkeleton::_setMax()
129
  {
130
  }
131

	
132
  void LpSkeleton::_setMin()
133
  {
134
  }
135

	
136
  bool LpSkeleton::_isMax() const
137
  {
138
    return true;
139
  }
140

	
141

	
142
  void LpSkeleton::_clearObj()
143
  {
144
  }
145

	
146
  LpSkeleton::SolveExitStatus LpSkeleton::_solve()
147
  {
148
    return SOLVED;
149
  }
150

	
151
  LpSkeleton::Value LpSkeleton::_getPrimal(int) const
152
  {
153
    return 0;
154
  }
155

	
156
  LpSkeleton::Value LpSkeleton::_getDual(int) const
157
  {
158
    return 0;
159
  }
160

	
161
  LpSkeleton::Value LpSkeleton::_getPrimalValue() const
162
  {
163
    return 0;
164
  }
165

	
166
  LpSkeleton::SolutionStatus LpSkeleton::_getPrimalStatus() const
167
  {
168
    return UNDEFINED;
169
  }
170

	
171
  LpSkeleton::SolutionStatus LpSkeleton::_getDualStatus() const
172
  {
173
    return UNDEFINED;
174
  }
175

	
176
  LpSkeleton::ProblemTypes LpSkeleton::_getProblemType() const
177
  {
178
    return UNKNOWN;
179
  }
180

	
181
  bool LpSkeleton::_isBasicCol(int) const
182
  {
183
    return true;
184
  }
185

	
186
} //namespace lemon
187

	
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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_SKELETON
20
#define LEMON_LP_SKELETON
21

	
22
#include <lemon/lp_base.h>
23

	
24
///\file
25
///\brief A skeleton file to implement LP solver interfaces
26
namespace lemon {
27

	
28
  ///A skeleton class to implement LP solver interfaces
29
  class LpSkeleton :public LpSolverBase {
30
    int col_num,row_num;
31

	
32
  protected:
33

	
34
    ///\e
35
    virtual LpSolverBase* _newLp();
36
    ///\e
37
    virtual LpSolverBase* _copyLp();
38
    /// \e
39
    virtual int _addCol();
40
    /// \e
41
    virtual int _addRow();
42
    /// \e
43
    virtual void _eraseCol(int i);
44
    /// \e
45
    virtual void _eraseRow(int i);
46
    /// \e
47
    virtual void _getColName(int col, std::string & name) const;
48
    /// \e
49
    virtual void _setColName(int col, const std::string & name);
50
    /// \e
51
    virtual int _colByName(const std::string& name) const;
52

	
53
    /// \e
54
    virtual void _setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e);
55
    /// \e
56
    virtual void _getRowCoeffs(int i, RowIterator b) const;
57
    /// \e
58
    virtual void _setColCoeffs(int i, ConstColIterator b, ConstColIterator e);
59
    /// \e
60
    virtual void _getColCoeffs(int i, ColIterator b) const;
61

	
62
    /// Set one element of the coefficient matrix
63
    virtual void _setCoeff(int row, int col, Value value);
64

	
65
    /// Get one element of the coefficient matrix
66
    virtual Value _getCoeff(int row, int col) const;
67

	
68
    /// The lower bound of a variable (column) have to be given by an
69
    /// extended number of type Value, i.e. a finite number of type
70
    /// Value or -\ref INF.
71
    virtual void _setColLowerBound(int i, Value value);
72
    /// \e
73

	
74
    /// The lower bound of a variable (column) is an
75
    /// extended number of type Value, i.e. a finite number of type
76
    /// Value or -\ref INF.
77
    virtual Value _getColLowerBound(int i) const;
78

	
79
    /// The upper bound of a variable (column) have to be given by an
80
    /// extended number of type Value, i.e. a finite number of type
81
    /// Value or \ref INF.
82
    virtual void _setColUpperBound(int i, Value value);
83
    /// \e
84

	
85
    /// The upper bound of a variable (column) is an
86
    /// extended number of type Value, i.e. a finite number of type
87
    /// Value or \ref INF.
88
    virtual Value _getColUpperBound(int i) const;
89

	
90
//     /// The lower bound of a linear expression (row) have to be given by an
91
//     /// extended number of type Value, i.e. a finite number of type
92
//     /// Value or -\ref INF.
93
//     virtual void _setRowLowerBound(int i, Value value);
94
//     /// \e
95

	
96
//     /// The upper bound of a linear expression (row) have to be given by an
97
//     /// extended number of type Value, i.e. a finite number of type
98
//     /// Value or \ref INF.
99
//     virtual void _setRowUpperBound(int i, Value value);
100

	
101
    /// The lower and upper bound of a linear expression (row) have to be
102
    /// given by an
103
    /// extended number of type Value, i.e. a finite number of type
104
    /// Value or +/-\ref INF.
105
    virtual void _setRowBounds(int i, Value lb, Value ub);
106
    /// \e
107

	
108

	
109
    /// The lower and the upper bound of
110
    /// a constraint (row) are
111
    /// extended numbers of type Value, i.e.  finite numbers of type
112
    /// Value, -\ref INF or \ref INF.
113
    virtual void _getRowBounds(int i, Value &lb, Value &ub) const;
114
    /// \e
115

	
116

	
117
    /// \e
118
    virtual void _clearObj();
119
    /// \e
120
    virtual void _setObjCoeff(int i, Value obj_coef);
121

	
122
    /// \e
123
    virtual Value _getObjCoeff(int i) const;
124

	
125
    ///\e
126

	
127
    ///\bug Wrong interface
128
    ///
129
    virtual SolveExitStatus _solve();
130

	
131
    ///\e
132

	
133
    ///\bug Wrong interface
134
    ///
135
    virtual Value _getPrimal(int i) const;
136

	
137
    ///\e
138

	
139
    ///\bug Wrong interface
140
    ///
141
    virtual Value _getDual(int i) const;
142

	
143
    ///\e
144

	
145
    ///\bug Wrong interface
146
    ///
147
    virtual Value _getPrimalValue() const;
148

	
149
    ///\e
150

	
151
    ///\bug Wrong interface
152
    ///
153
    virtual SolutionStatus _getPrimalStatus() const;
154

	
155
    ////e
156
    virtual SolutionStatus _getDualStatus() const;
157

	
158

	
159
    ///\e
160
    virtual ProblemTypes _getProblemType() const;
161

	
162
    ///\e
163
    virtual void _setMax();
164
    ///\e
165
    virtual void _setMin();
166

	
167
    ///\e
168
    virtual bool _isMax() const;
169

	
170

	
171

	
172
    ///\e
173
    virtual bool _isBasicCol(int i) const;
174

	
175

	
176

	
177
  public:
178
    LpSkeleton() : LpSolverBase(), col_num(0), row_num(0) {}
179
  };
180

	
181
} //namespace lemon
182

	
183
#endif // LEMON_LP_SKELETON
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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
#include<iostream>
20
#include<lemon/lp_soplex.h>
21

	
22
#include <soplex/soplex.h>
23

	
24

	
25
///\file
26
///\brief Implementation of the LEMON-SOPLEX lp solver interface.
27
namespace lemon {
28

	
29
  LpSoplex::LpSoplex() : LpSolverBase() {
30
    rows.setIdHandler(relocateIdHandler);
31
    cols.setIdHandler(relocateIdHandler);
32
    soplex = new soplex::SoPlex;
33
    solved = false;
34
  }
35

	
36
  LpSoplex::~LpSoplex() {
37
    delete soplex;
38
  }
39

	
40
  LpSoplex::LpSoplex(const LpSoplex& lp) : LpSolverBase() {
41
    rows = lp.rows;
42
    rows.setIdHandler(relocateIdHandler);
43

	
44
    cols = lp.cols;
45
    cols.setIdHandler(relocateIdHandler);
46

	
47
    soplex = new soplex::SoPlex;
48
    (*static_cast<soplex::SPxLP*>(soplex)) = *(lp.soplex);
49

	
50
    colNames = lp.colNames;
51
    invColNames = lp.invColNames;
52

	
53
    primal_value = lp.primal_value;
54
    dual_value = lp.dual_value;
55

	
56
  }
57

	
58
  LpSolverBase* LpSoplex::_newLp() {
59
    LpSoplex* newlp = new LpSoplex();
60
    return newlp;
61
  }
62

	
63
  LpSolverBase* LpSoplex::_copyLp() {
64
    LpSoplex* newlp = new LpSoplex(*this);
65
    return newlp;
66
  }
67

	
68
  int LpSoplex::_addCol() {
69
    soplex::LPCol c;
70
    c.setLower(-soplex::infinity);
71
    c.setUpper(soplex::infinity);
72
    soplex->addCol(c);
73

	
74
    colNames.push_back(std::string());
75
    primal_value.push_back(0.0);
76
    solved = false;
77

	
78
    return soplex->nCols() - 1;
79
  }
80

	
81
  int LpSoplex::_addRow() {
82
    soplex::LPRow r;
83
    r.setLhs(-soplex::infinity);
84
    r.setRhs(soplex::infinity);
85
    soplex->addRow(r);
86

	
87
    dual_value.push_back(0.0);
88
    solved = false;
89

	
90
    return soplex->nRows() - 1;
91
  }
92

	
93

	
94
  void LpSoplex::_eraseCol(int i) {
95
    soplex->removeCol(i);
96
    invColNames.erase(colNames[i]);
97
    colNames[i] = colNames.back();
98
    invColNames[colNames.back()] = i;
99
    colNames.pop_back();
100
    primal_value[i] = primal_value.back();
101
    primal_value.pop_back();
102
    solved = false;
103
  }
104

	
105
  void LpSoplex::_eraseRow(int i) {
106
    soplex->removeRow(i);
107
    dual_value[i] = dual_value.back();
108
    dual_value.pop_back();
109
    solved = false;
110
  }
111

	
112
  void LpSoplex::_getColName(int c, std::string &name) const {
113
    name = colNames[c];
114
  }
115

	
116
  void LpSoplex::_setColName(int c, const std::string &name) {
117
    invColNames.erase(colNames[c]);
118
    colNames[c] = name;
119
    if (!name.empty()) {
120
      invColNames.insert(std::make_pair(name, c));
121
    }
122
  }
123

	
124
  int LpSoplex::_colByName(const std::string& name) const {
125
    std::map<std::string, int>::const_iterator it =
126
      invColNames.find(name);
127
    if (it != invColNames.end()) {
128
      return it->second;
129
    } else {
130
      return -1;
131
    }
132
  }
133

	
134

	
135
  void LpSoplex::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e) {
136
    for (int j = 0; j < soplex->nCols(); ++j) {
137
      soplex->changeElement(i, j, 0.0);
138
    }
139
    for(ConstRowIterator it = b; it != e; ++it) {
140
      soplex->changeElement(i, it->first, it->second);
141
    }
142
    solved = false;
143
  }
144

	
145
  void LpSoplex::_getRowCoeffs(int i, RowIterator b) const {
146
    const soplex::SVector& vec = soplex->rowVector(i);
147
    for (int k = 0; k < vec.size(); ++k) {
148
      *b = std::make_pair(vec.index(k), vec.value(k));
149
      ++b;
150
    }
151
  }
152

	
153
  void LpSoplex::_setColCoeffs(int j, ConstColIterator b, ConstColIterator e) {
154
    for (int i = 0; i < soplex->nRows(); ++i) {
155
      soplex->changeElement(i, j, 0.0);
156
    }
157
    for(ConstColIterator it = b; it != e; ++it) {
158
      soplex->changeElement(it->first, j, it->second);
159
    }
160
    solved = false;
161
  }
162

	
163
  void LpSoplex::_getColCoeffs(int i, ColIterator b) const {
164
    const soplex::SVector& vec = soplex->colVector(i);
165
    for (int k = 0; k < vec.size(); ++k) {
166
      *b = std::make_pair(vec.index(k), vec.value(k));
167
      ++b;
168
    }
169
  }
170

	
171
  void LpSoplex::_setCoeff(int i, int j, Value value) {
172
    soplex->changeElement(i, j, value);
173
    solved = false;
174
  }
175

	
176
  LpSoplex::Value LpSoplex::_getCoeff(int i, int j) const {
177
    return soplex->rowVector(i)[j];
178
  }
179

	
180
  void LpSoplex::_setColLowerBound(int i, Value value) {
181
    soplex->changeLower(i, value != -INF ? value : -soplex::infinity);
182
    solved = false;
183
  }
184

	
185
  LpSoplex::Value LpSoplex::_getColLowerBound(int i) const {
186
    double value = soplex->lower(i);
187
    return value != -soplex::infinity ? value : -INF;
188
  }
189

	
190
  void LpSoplex::_setColUpperBound(int i, Value value) {
191
    soplex->changeUpper(i, value != INF ? value : soplex::infinity);
192
    solved = false;
193
  }
194

	
195
  LpSoplex::Value LpSoplex::_getColUpperBound(int i) const {
196
    double value = soplex->upper(i);
197
    return value != soplex::infinity ? value : INF;
198
  }
199

	
200
  void LpSoplex::_setRowBounds(int i, Value lb, Value ub) {
201
    soplex->changeRange(i, lb != -INF ? lb : -soplex::infinity,
202
                        ub != INF ? ub : soplex::infinity);
203
    solved = false;
204
  }
205
  void LpSoplex::_getRowBounds(int i, Value &lower, Value &upper) const {
206
    lower = soplex->lhs(i);
207
    if (lower == -soplex::infinity) lower = -INF;
208
    upper = soplex->rhs(i);
209
    if (upper == -soplex::infinity) upper = INF;
210
  }
211

	
212
  void LpSoplex::_setObjCoeff(int i, Value obj_coef) {
213
    soplex->changeObj(i, obj_coef);
214
    solved = false;
215
  }
216

	
217
  LpSoplex::Value LpSoplex::_getObjCoeff(int i) const {
218
    return soplex->obj(i);
219
  }
220

	
221
  void LpSoplex::_clearObj() {
222
    for (int i = 0; i < soplex->nCols(); ++i) {
223
      soplex->changeObj(i, 0.0);
224
    }
225
    solved = false;
226
  }
227

	
228
  LpSoplex::SolveExitStatus LpSoplex::_solve() {
229
    soplex::SPxSolver::Status status = soplex->solve();
230

	
231
    soplex::Vector pv(primal_value.size(), &primal_value[0]);
232
    soplex->getPrimal(pv);
233

	
234
    soplex::Vector dv(dual_value.size(), &dual_value[0]);
235
    soplex->getDual(dv);
236

	
237
    switch (status) {
238
    case soplex::SPxSolver::OPTIMAL:
239
    case soplex::SPxSolver::INFEASIBLE:
240
    case soplex::SPxSolver::UNBOUNDED:
241
      solved = true;
242
      return SOLVED;
243
    default:
244
      return UNSOLVED;
245
    }
246
  }
247

	
248
  LpSoplex::Value LpSoplex::_getPrimal(int i) const {
249
    return primal_value[i];
250
  }
251

	
252
  LpSoplex::Value LpSoplex::_getDual(int i) const {
253
    return dual_value[i];
254
  }
255

	
256
  LpSoplex::Value LpSoplex::_getPrimalValue() const {
257
    return soplex->objValue();
258
  }
259

	
260
  bool LpSoplex::_isBasicCol(int i) const {
261
    return soplex->getBasisColStatus(i) == soplex::SPxSolver::BASIC;
262
  }
263

	
264
  LpSoplex::SolutionStatus LpSoplex::_getPrimalStatus() const {
265
    if (!solved) return UNDEFINED;
266
    switch (soplex->status()) {
267
    case soplex::SPxSolver::OPTIMAL:
268
      return OPTIMAL;
269
    case soplex::SPxSolver::UNBOUNDED:
270
      return INFINITE;
271
    case soplex::SPxSolver::INFEASIBLE:
272
      return INFEASIBLE;
273
    default:
274
      return UNDEFINED;
275
    }
276
  }
277

	
278
  LpSoplex::SolutionStatus LpSoplex::_getDualStatus() const {
279
    if (!solved) return UNDEFINED;
280
    switch (soplex->status()) {
281
    case soplex::SPxSolver::OPTIMAL:
282
      return OPTIMAL;
283
    case soplex::SPxSolver::UNBOUNDED:
284
      return INFEASIBLE;
285
    default:
286
      return UNDEFINED;
287
    }
288
  }
289

	
290
  LpSoplex::ProblemTypes LpSoplex::_getProblemType() const {
291
    if (!solved) return UNKNOWN;
292
    switch (soplex->status()) {
293
    case soplex::SPxSolver::OPTIMAL:
294
      return PRIMAL_DUAL_FEASIBLE;
295
    case soplex::SPxSolver::UNBOUNDED:
296
      return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
297
    default:
298
      return UNKNOWN;
299
    }
300
  }
301

	
302
  void LpSoplex::_setMax() {
303
    soplex->changeSense(soplex::SPxSolver::MAXIMIZE);
304
    solved = false;
305
  }
306
  void LpSoplex::_setMin() {
307
    soplex->changeSense(soplex::SPxSolver::MINIMIZE);
308
    solved = false;
309
  }
310
  bool LpSoplex::_isMax() const {
311
    return soplex->spxSense() == soplex::SPxSolver::MAXIMIZE;
312
  }
313

	
314

	
315
} //namespace lemon
316

	
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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_SOPLEX_H
20
#define LEMON_LP_SOPLEX_H
21

	
22
///\file
23
///\brief Header of the LEMON-SOPLEX lp solver interface.
24

	
25
#include <vector>
26
#include <string>
27

	
28
#include <lemon/lp_base.h>
29

	
30
// Forward declaration
31
namespace soplex {
32
  class SoPlex;
33
}
34

	
35
namespace lemon {
36

	
37
  /// \ingroup lp_group
38
  ///
39
  /// \brief Interface for the SOPLEX solver
40
  ///
41
  /// This class implements an interface for the SoPlex LP solver.
42
  /// The SoPlex library is an object oriented lp solver library
43
  /// developed at the Konrad-Zuse-Zentrum f�r Informationstechnik
44
  /// Berlin (ZIB). You can find detailed information about it at the
45
  /// <tt>http://soplex.zib.de</tt> address.
46
  class LpSoplex :virtual public LpSolverBase {
47
  protected:
48

	
49
    _lp_bits::RelocateIdHandler relocateIdHandler;
50

	
51
    soplex::SoPlex* soplex;
52
    bool solved;
53

	
54
    std::vector<std::string> colNames;
55
    std::map<std::string, int> invColNames;
56

	
57
    std::vector<Value> primal_value;
58
    std::vector<Value> dual_value;
59

	
60

	
61
  public:
62

	
63
    typedef LpSolverBase Parent;
64

	
65

	
66
    /// \e
67
    LpSoplex();
68
    /// \e
69
    LpSoplex(const LpSoplex&);
70
    /// \e
71
    ~LpSoplex();
72

	
73
  protected:
74

	
75
    virtual LpSolverBase* _newLp();
76
    virtual LpSolverBase* _copyLp();
77

	
78
    virtual int _addCol();
79
    virtual int _addRow();
80
    virtual void _eraseCol(int i);
81
    virtual void _eraseRow(int i);
82
    virtual void _getColName(int col, std::string & name) const;
83
    virtual void _setColName(int col, const std::string & name);
84
    virtual int _colByName(const std::string& name) const;
85
    virtual void _setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e);
86
    virtual void _getRowCoeffs(int i, RowIterator b) const;
87
    virtual void _setColCoeffs(int i, ConstColIterator b, ConstColIterator e);
88
    virtual void _getColCoeffs(int i, ColIterator b) const;
89
    virtual void _setCoeff(int row, int col, Value value);
90
    virtual Value _getCoeff(int row, int col) const;
91
    virtual void _setColLowerBound(int i, Value value);
92
    virtual Value _getColLowerBound(int i) const;
93
    virtual void _setColUpperBound(int i, Value value);
94
    virtual Value _getColUpperBound(int i) const;
95
    virtual void _setRowBounds(int i, Value lower, Value upper);
96
    virtual void _getRowBounds(int i, Value &lower, Value &upper) const;
97
    virtual void _setObjCoeff(int i, Value obj_coef);
98
    virtual Value _getObjCoeff(int i) const;
99
    virtual void _clearObj();
100

	
101
    virtual SolveExitStatus _solve();
102
    virtual Value _getPrimal(int i) const;
103
    virtual Value _getDual(int i) const;
104
    virtual Value _getPrimalValue() const;
105
    virtual bool _isBasicCol(int i) const;
106

	
107
    virtual SolutionStatus _getPrimalStatus() const;
108
    virtual SolutionStatus _getDualStatus() const;
109
    virtual ProblemTypes _getProblemType() const;
110

	
111

	
112
    virtual void _setMax();
113
    virtual void _setMin();
114
    virtual bool _isMax() const;
115

	
116
  };
117
} //END OF NAMESPACE LEMON
118

	
119
#endif //LEMON_LP_SOPLEX_H
120

	
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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-CPLEX mip solver interface.
21

	
22
#include <lemon/mip_cplex.h>
23

	
24
extern "C" {
25
#include <ilcplex/cplex.h>
26
}
27

	
28
namespace lemon {
29

	
30
  MipCplex::MipCplex() {
31
    //This is unnecessary: setting integrality constraints on
32
    //variables will set this, too
33

	
34
    ///\todo The constant CPXPROB_MIP is
35
    ///called CPXPROB_MILP in later versions
36
#if CPX_VERSION < 800
37
    CPXchgprobtype( env,  lp, CPXPROB_MIP);
38
#else
39
    CPXchgprobtype( env,  lp, CPXPROB_MILP);
40
#endif
41

	
42
  }
43

	
44
  void MipCplex::_colType(int i, MipCplex::ColTypes col_type){
45

	
46
    // Note If a variable is to be changed to binary, a call to CPXchgbds
47
    // should also be made to change the bounds to 0 and 1.
48

	
49
    int indices[1];
50
    indices[0]=i;
51
    char ctype[1];
52
    switch (col_type){
53
      case INT:
54
        ctype[0]=CPX_INTEGER;//'I'
55
        break;
56
      case REAL:
57
        ctype[0]=CPX_CONTINUOUS        ;//'C'
58
        break;
59
    default:;
60
        //FIXME problem
61
    }
62
    CPXchgctype (env, lp, 1, indices, ctype);
63
  }
64

	
65
  MipCplex::ColTypes MipCplex::_colType(int i) const {
66

	
67
    char ctype[1];
68
    CPXgetctype (env, lp, ctype, i, i);
69
    switch (ctype[0]){
70

	
71
    case CPX_INTEGER:
72
      return INT;
73
    case CPX_CONTINUOUS:
74
      return REAL;
75
    default:
76
      return REAL;//Error!
77
    }
78

	
79
  }
80

	
81
  LpCplex::SolveExitStatus MipCplex::_solve(){
82

	
83
    status = CPXmipopt (env, lp);
84
    if (status==0)
85
      return SOLVED;
86
    else
87
      return UNSOLVED;
88

	
89
  }
90

	
91

	
92
  LpCplex::SolutionStatus MipCplex::_getMipStatus() const {
93

	
94
    int stat = CPXgetstat(env, lp);
95

	
96
    //Fortunately, MIP statuses did not change for cplex 8.0
97
    switch (stat)
98
    {
99
      case CPXMIP_OPTIMAL:
100
        // Optimal integer solution has been found.
101
      case CPXMIP_OPTIMAL_TOL:
102
        // Optimal soluton with the tolerance defined by epgap or epagap has
103
        // been found.
104
        return OPTIMAL;
105
        //This also exists in later issues
106
        //    case CPXMIP_UNBOUNDED:
107
        //return INFINITE;
108
      case CPXMIP_INFEASIBLE:
109
        return INFEASIBLE;
110
      default:
111
        return UNDEFINED;
112
    }
113
    //Unboundedness not treated well: the following is from cplex 9.0 doc
114
    // About Unboundedness
115

	
116
    // The treatment of models that are unbounded involves a few
117
    // subtleties. Specifically, a declaration of unboundedness means that
118
    // ILOG CPLEX has determined that the model has an unbounded
119
    // ray. Given any feasible solution x with objective z, a multiple of
120
    // the unbounded ray can be added to x to give a feasible solution
121
    // with objective z-1 (or z+1 for maximization models). Thus, if a
122
    // feasible solution exists, then the optimal objective is
123
    // unbounded. Note that ILOG CPLEX has not necessarily concluded that
124
    // a feasible solution exists. Users can call the routine CPXsolninfo
125
    // to determine whether ILOG CPLEX has also concluded that the model
126
    // has a feasible solution.
127

	
128
  }
129

	
130
  MipCplex::Value MipCplex::_getPrimal(int i) const {
131
    Value x;
132
    CPXgetmipx(env, lp, &x, i, i);
133
    return x;
134
  }
135

	
136
  MipCplex::Value MipCplex::_getPrimalValue() const {
137
    Value objval;
138
    CPXgetmipobjval(env, lp, &objval);
139
    return objval;
140
  }
141
} //END OF NAMESPACE LEMON
Ignore white space 12 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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_MIP_CPLEX_H
20
#define LEMON_MIP_CPLEX_H
21

	
22
///\file
23
///\brief Header of the LEMON-CPLEX mip solver interface.
24
///\ingroup lp_group
25

	
26

	
27
#include <lemon/lp_cplex.h>
28

	
29
namespace lemon {
30

	
31
  /// \brief Interface for the CPLEX MIP solver
32
  ///
33
  /// This class implements an interface for the CPLEX MIP solver.
34
  ///\ingroup lp_group
35
  class MipCplex : public MipSolverBase, public LpCplex{
36

	
37
  public:
38

	
39
    typedef MipSolverBase ParentMip;
40
    typedef LpCplex ParentLp;
41

	
42
    MipCplex();
43
    //~MipCplex();
44

	
45

	
46

	
47

	
48
  protected:
49

	
50
    virtual ColTypes _colType(int col) const;
51
    virtual void _colType(int col, ColTypes col_type);
52

	
53
    virtual LpCplex::SolveExitStatus _solve();
54
    virtual LpCplex::SolutionStatus _getMipStatus() const;
55
    virtual ParentLp::Value _getPrimal(int i) const;
56
    virtual ParentLp::Value _getPrimalValue() const;
57
  };
58

	
59
} //END OF NAMESPACE LEMON
60

	
61
#endif // END OF LEMON_MIP_CPLEX_H
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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 mip solver interface.
21

	
22
#include <lemon/mip_glpk.h>
23

	
24
extern "C" {
25
#include <glpk.h>
26
}
27

	
28
#if GLP_MAJOR_VERSION > 4 || (GLP_MAJOR_VERSION == 4 && GLP_MINOR_VERSION > 15)
29
#define LEMON_glp(func) (glp_##func)
30
#define LEMON_lpx(func) (lpx_##func)
31

	
32
#define LEMON_GLP(def) (GLP_##def)
33
#define LEMON_LPX(def) (LPX_##def)
34

	
35
#else
36

	
37
#define LEMON_glp(func) (lpx_##func)
38
#define LEMON_lpx(func) (lpx_##func)
39

	
40
#define LEMON_GLP(def) (LPX_##def)
41
#define LEMON_LPX(def) (LPX_##def)
42

	
43
#endif
44

	
45
namespace lemon {
46

	
47
  MipGlpk::MipGlpk() {
48
#if !(GLP_MAJOR_VERSION > 4 || \
49
      (GLP_MAJOR_VERSION == 4 && GLP_MINOR_VERSION > 15))
50
    LEMON_lpx(set_class)(lp,LEMON_GLP(MIP));
51
#endif
52
  }
53

	
54
  void MipGlpk::_colType(int i, MipGlpk::ColTypes col_type){
55
    switch (col_type){
56
      case INT:
57
        LEMON_glp(set_col_kind)(lp,i,LEMON_GLP(IV));
58
        break;
59
      case REAL:
60
        LEMON_glp(set_col_kind)(lp,i,LEMON_GLP(CV));
61
        break;
62
    default:;
63
        //FIXME problem
64
    }
65
  }
66

	
67
  MipGlpk::ColTypes MipGlpk::_colType(int i) const {
68
    switch (LEMON_glp(get_col_kind)(lp,i)){
69
    case LEMON_GLP(IV):
70
      return INT;//Or binary
71
    case LEMON_GLP(CV):
72
      return REAL;
73
    default:
74
      return REAL;//Error!
75
    }
76

	
77
  }
78

	
79
  LpGlpk::SolveExitStatus MipGlpk::_solve() {
80
    int result = LEMON_lpx(simplex)(lp);
81

	
82
    // hack: mip does not contain integer variable
83
#if GLP_MAJOR_VERSION == 4 && GLP_MINOR_VERSION == 16
84
    int tmp = -1;
85
    if (LEMON_glp(get_num_int(lp)) == 0) {
86
      tmp = LEMON_lpx(add_cols)(lp, 1);
87
      LEMON_glp(set_col_bnds)(lp, tmp, LEMON_GLP(FX), 0.0, 0.0);
88
      LEMON_glp(set_col_kind)(lp, tmp, LEMON_GLP(IV));
89
    }
90
#endif
91

	
92
    if (LEMON_lpx(get_status)(lp)==LEMON_LPX(OPT)) {
93
      //Maybe we could try the routine lpx_intopt(lp), a revised
94
      //version of lpx_integer
95

	
96
      result = LEMON_lpx(integer)(lp);
97
      switch (result){
98
      case LEMON_LPX(E_OK):
99
        solved = true;
100
        break;
101
      default:
102
        solved = false;
103
      }
104
    } else {
105
      solved = false;
106
    }
107
#if GLP_MAJOR_VERSION == 4 && GLP_MINOR_VERSION == 16
108
    if (tmp != -1) {
109
      int tmpa[2];
110
      tmpa[1] = tmp;
111
      LEMON_lpx(del_cols)(lp, 1, tmpa);
112
    }
113
#endif
114
    return solved ? SOLVED : UNSOLVED;
115
  }
116

	
117

	
118
  LpGlpk::SolutionStatus MipGlpk::_getMipStatus() const {
119

	
120
    if (LEMON_lpx(get_status)(lp)==LEMON_LPX(OPT)){
121
      //Meg kell nezni: ha az LP is infinite, akkor ez is, ha az is
122
      //infeasible, akkor ez is, de ez lehet maskepp is infeasible.
123
      int stat= LEMON_lpx(mip_status)(lp);
124

	
125
      switch (stat) {
126
      case LEMON_LPX(I_UNDEF)://Undefined (no solve has been run yet)
127
        return UNDEFINED;
128
      case LEMON_LPX(I_NOFEAS)://There is no feasible integral solution
129
        return INFEASIBLE;
130
        //     case LEMON_LPX(UNBND)://Unbounded
131
        //       return INFINITE;
132
      case LEMON_LPX(I_FEAS)://Feasible
133
        return FEASIBLE;
134
      case LEMON_LPX(I_OPT)://Feasible
135
        return OPTIMAL;
136
      default:
137
        return UNDEFINED; //to avoid gcc warning
138
      //FIXME error
139
      }
140
    }
141
    else
142
      return UNDEFINED; //Maybe we could refine this: what does the LP
143
                        //relaxation look like
144

	
145
  }
146

	
147
  MipGlpk::Value MipGlpk::_getPrimal(int i) const {
148
    return LEMON_glp(mip_col_val)(lp,i);
149
  }
150

	
151
  MipGlpk::Value MipGlpk::_getPrimalValue() const {
152
    return LEMON_glp(mip_obj_val)(lp);
153
  }
154
} //END OF NAMESPACE LEMON
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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_MIP_GLPK_H
20
#define LEMON_MIP_GLPK_H
21

	
22
///\file
23
///\brief Header of the LEMON-GLPK mip solver interface.
24
///\ingroup lp_group
25

	
26

	
27
#include <lemon/lp_glpk.h>
28

	
29
namespace lemon {
30
  /// \brief Interface for the GLPK MIP solver
31
  ///
32
  /// This class implements an interface for the GLPK MIP solver.
33
  ///\ingroup lp_group
34
  class MipGlpk : public MipSolverBase, public LpGlpk{
35

	
36
  public:
37

	
38
    typedef MipSolverBase ParentMip;
39
    typedef LpGlpk ParentLp;
40

	
41
    MipGlpk();
42
    //~MipGlpk();
43

	
44

	
45

	
46
  protected:
47

	
48
    virtual ColTypes _colType(int col) const;
49
    virtual void _colType(int col, ColTypes col_type);
50

	
51
    virtual LpGlpk::SolveExitStatus _solve();
52
    virtual LpGlpk::SolutionStatus _getMipStatus() const;
53
    virtual ParentLp::Value _getPrimal(int i) const;
54
    virtual ParentLp::Value _getPrimalValue() const;
55
  };
56

	
57
} //END OF NAMESPACE LEMON
58

	
59
#endif // END OF LEMON_MIP_GLPK_H
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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
#include <sstream>
20
#include <lemon/lp_skeleton.h>
21
#include "test_tools.h"
22
#include <lemon/tolerance.h>
23

	
24
#ifdef HAVE_CONFIG_H
25
#include <lemon/config.h>
26
#endif
27

	
28
#ifdef HAVE_GLPK
29
#include <lemon/lp_glpk.h>
30
#endif
31

	
32
#ifdef HAVE_CPLEX
33
#include <lemon/lp_cplex.h>
34
#endif
35

	
36
#ifdef HAVE_SOPLEX
37
#include <lemon/lp_soplex.h>
38
#endif
39

	
40
using namespace lemon;
41

	
42
void lpTest(LpSolverBase & lp)
43
{
44

	
45

	
46

	
47
  typedef LpSolverBase LP;
48

	
49
  std::vector<LP::Col> x(10);
50
  //  for(int i=0;i<10;i++) x.push_back(lp.addCol());
51
  lp.addColSet(x);
52
  lp.colLowerBound(x,1);
53
  lp.colUpperBound(x,1);
54
  lp.colBounds(x,1,2);
55
#ifndef GYORSITAS
56

	
57
  std::vector<LP::Col> y(10);
58
  lp.addColSet(y);
59

	
60
  lp.colLowerBound(y,1);
61
  lp.colUpperBound(y,1);
62
  lp.colBounds(y,1,2);
63

	
64
  std::map<int,LP::Col> z;
65

	
66
  z.insert(std::make_pair(12,INVALID));
67
  z.insert(std::make_pair(2,INVALID));
68
  z.insert(std::make_pair(7,INVALID));
69
  z.insert(std::make_pair(5,INVALID));
70

	
71
  lp.addColSet(z);
72

	
73
  lp.colLowerBound(z,1);
74
  lp.colUpperBound(z,1);
75
  lp.colBounds(z,1,2);
76

	
77
  {
78
    LP::Expr e,f,g;
79
    LP::Col p1,p2,p3,p4,p5;
80
    LP::Constr c;
81

	
82
    p1=lp.addCol();
83
    p2=lp.addCol();
84
    p3=lp.addCol();
85
    p4=lp.addCol();
86
    p5=lp.addCol();
87

	
88
    e[p1]=2;
89
    e.constComp()=12;
90
    e[p1]+=2;
91
    e.constComp()+=12;
92
    e[p1]-=2;
93
    e.constComp()-=12;
94

	
95
    e=2;
96
    e=2.2;
97
    e=p1;
98
    e=f;
99

	
100
    e+=2;
101
    e+=2.2;
102
    e+=p1;
103
    e+=f;
104

	
105
    e-=2;
106
    e-=2.2;
107
    e-=p1;
108
    e-=f;
109

	
110
    e*=2;
111
    e*=2.2;
112
    e/=2;
113
    e/=2.2;
114

	
115
    e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+
116
       (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+
117
       (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+
118
       2.2*f+f*2.2+f/2.2+
119
       2*f+f*2+f/2+
120
       2.2*p1+p1*2.2+p1/2.2+
121
       2*p1+p1*2+p1/2
122
       );
123

	
124

	
125
    c = (e  <= f  );
126
    c = (e  <= 2.2);
127
    c = (e  <= 2  );
128
    c = (e  <= p1 );
129
    c = (2.2<= f  );
130
    c = (2  <= f  );
131
    c = (p1 <= f  );
132
    c = (p1 <= p2 );
133
    c = (p1 <= 2.2);
134
    c = (p1 <= 2  );
135
    c = (2.2<= p2 );
136
    c = (2  <= p2 );
137

	
138
    c = (e  >= f  );
139
    c = (e  >= 2.2);
140
    c = (e  >= 2  );
141
    c = (e  >= p1 );
142
    c = (2.2>= f  );
143
    c = (2  >= f  );
144
    c = (p1 >= f  );
145
    c = (p1 >= p2 );
146
    c = (p1 >= 2.2);
147
    c = (p1 >= 2  );
148
    c = (2.2>= p2 );
149
    c = (2  >= p2 );
150

	
151
    c = (e  == f  );
152
    c = (e  == 2.2);
153
    c = (e  == 2  );
154
    c = (e  == p1 );
155
    c = (2.2== f  );
156
    c = (2  == f  );
157
    c = (p1 == f  );
158
    //c = (p1 == p2 );
159
    c = (p1 == 2.2);
160
    c = (p1 == 2  );
161
    c = (2.2== p2 );
162
    c = (2  == p2 );
163

	
164
    c = (2 <= e <= 3);
165
    c = (2 <= p1<= 3);
166

	
167
    c = (2 >= e >= 3);
168
    c = (2 >= p1>= 3);
169

	
170
    e[x[3]]=2;
171
    e[x[3]]=4;
172
    e[x[3]]=1;
173
    e.constComp()=12;
174

	
175
    lp.addRow(LP::INF,e,23);
176
    lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
177
    lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
178

	
179
    lp.addRow(x[1]+x[3]<=x[5]-3);
180
    lp.addRow(-7<=x[1]+x[3]-12<=3);
181
    lp.addRow(x[1]<=x[5]);
182

	
183
    std::ostringstream buf;
184

	
185

	
186
    //Checking the simplify function
187

	
188
//     //How to check the simplify function? A map gives no information
189
//     //on the question whether a given key is or is not stored in it, or
190
//     //it does?
191
//   Yes, it does, using the find() function.
192
    e=((p1+p2)+(p1-p2));
193
    e.simplify();
194
    buf << "Coeff. of p2 should be 0";
195
    //    std::cout<<e[p1]<<e[p2]<<e[p3]<<std::endl;
196
    check(e.find(p2)==e.end(), buf.str());
197

	
198

	
199

	
200

	
201
    e=((p1+p2)+(p1-0.99*p2));
202
    //e.prettyPrint(std::cout);
203
    //(e<=2).prettyPrint(std::cout);
204
    double tolerance=0.001;
205
    e.simplify(tolerance);
206
    buf << "Coeff. of p2 should be 0.01";
207
    check(e[p2]>0, buf.str());
208

	
209
    tolerance=0.02;
210
    e.simplify(tolerance);
211
    buf << "Coeff. of p2 should be 0";
212
    check(e.find(p2)==e.end(), buf.str());
213

	
214

	
215
  }
216

	
217
  {
218
    LP::DualExpr e,f,g;
219
    LP::Row p1 = INVALID, p2 = INVALID, p3 = INVALID,
220
      p4 = INVALID, p5 = INVALID;
221

	
222
    e[p1]=2;
223
    e[p1]+=2;
224
    e[p1]-=2;
225

	
226
    e=p1;
227
    e=f;
228

	
229
    e+=p1;
230
    e+=f;
231

	
232
    e-=p1;
233
    e-=f;
234

	
235
    e*=2;
236
    e*=2.2;
237
    e/=2;
238
    e/=2.2;
239

	
240
    e=((p1+p2)+(p1-p2)+
241
       (p1+f)+(f+p1)+(f+g)+
242
       (p1-f)+(f-p1)+(f-g)+
243
       2.2*f+f*2.2+f/2.2+
244
       2*f+f*2+f/2+
245
       2.2*p1+p1*2.2+p1/2.2+
246
       2*p1+p1*2+p1/2
247
       );
248
  }
249

	
250
#endif
251
}
252

	
253
void solveAndCheck(LpSolverBase& lp, LpSolverBase::SolutionStatus stat,
254
                   double exp_opt) {
255
  using std::string;
256
  lp.solve();
257
  //int decimal,sign;
258
  std::ostringstream buf;
259
  buf << "Primalstatus should be: " << int(stat);
260

	
261
  //  itoa(stat,buf1, 10);
262
  check(lp.primalStatus()==stat, buf.str());
263

	
264
  if (stat ==  LpSolverBase::OPTIMAL) {
265
    std::ostringstream sbuf;
266
    sbuf << "Wrong optimal value: the right optimum is " << exp_opt;
267
    check(std::abs(lp.primalValue()-exp_opt) < 1e-3, sbuf.str());
268
    //+ecvt(exp_opt,2)
269
  }
270
}
271

	
272
void aTest(LpSolverBase & lp)
273
{
274
  typedef LpSolverBase LP;
275

	
276
 //The following example is very simple
277

	
278
  typedef LpSolverBase::Row Row;
279
  typedef LpSolverBase::Col Col;
280

	
281

	
282
  Col x1 = lp.addCol();
283
  Col x2 = lp.addCol();
284

	
285

	
286
  //Constraints
287
  Row upright=lp.addRow(x1+x2 <=1);
288
  lp.addRow(x1+x2 >=-1);
289
  lp.addRow(x1-x2 <=1);
290
  lp.addRow(x1-x2 >=-1);
291
  //Nonnegativity of the variables
292
  lp.colLowerBound(x1, 0);
293
  lp.colLowerBound(x2, 0);
294
  //Objective function
295
  lp.obj(x1+x2);
296

	
297
  lp.max();
298

	
299
  //Testing the problem retrieving routines
300
  check(lp.objCoeff(x1)==1,"First term should be 1 in the obj function!");
301
  check(lp.isMax(),"This is a maximization!");
302
  check(lp.coeff(upright,x1)==1,"The coefficient in question is 1!");
303
  //  std::cout<<lp.colLowerBound(x1)<<std::endl;
304
  check(  lp.colLowerBound(x1)==0,
305
          "The lower bound for variable x1 should be 0.");
306
  check(  lp.colUpperBound(x1)==LpSolverBase::INF,
307
          "The upper bound for variable x1 should be infty.");
308
  LpSolverBase::Value lb,ub;
309
  lp.getRowBounds(upright,lb,ub);
310
  check(  lb==-LpSolverBase::INF,
311
          "The lower bound for the first row should be -infty.");
312
  check(  ub==1,"The upper bound for the first row should be 1.");
313
  LpSolverBase::Expr e = lp.row(upright);
314
  check(  e.size() == 2, "The row retrieval gives back wrong expression.");
315
  check(  e[x1] == 1, "The first coefficient should 1.");
316
  check(  e[x2] == 1, "The second coefficient should 1.");
317

	
318
  LpSolverBase::DualExpr de = lp.col(x1);
319
  check(  de.size() == 4, "The col retrieval gives back wrong expression.");
320
  check(  de[upright] == 1, "The first coefficient should 1.");
321

	
322
  LpSolverBase* clp = lp.copyLp();
323

	
324
  //Testing the problem retrieving routines
325
  check(clp->objCoeff(x1)==1,"First term should be 1 in the obj function!");
326
  check(clp->isMax(),"This is a maximization!");
327
  check(clp->coeff(upright,x1)==1,"The coefficient in question is 1!");
328
  //  std::cout<<lp.colLowerBound(x1)<<std::endl;
329
  check(  clp->colLowerBound(x1)==0,
330
          "The lower bound for variable x1 should be 0.");
331
  check(  clp->colUpperBound(x1)==LpSolverBase::INF,
332
          "The upper bound for variable x1 should be infty.");
333

	
334
  clp->getRowBounds(upright,lb,ub);
335
  check(  lb==-LpSolverBase::INF,
336
          "The lower bound for the first row should be -infty.");
337
  check(  ub==1,"The upper bound for the first row should be 1.");
338
  e = clp->row(upright);
339
  check(  e.size() == 2, "The row retrieval gives back wrong expression.");
340
  check(  e[x1] == 1, "The first coefficient should 1.");
341
  check(  e[x2] == 1, "The second coefficient should 1.");
342

	
343
  de = clp->col(x1);
344
  check(  de.size() == 4, "The col retrieval gives back wrong expression.");
345
  check(  de[upright] == 1, "The first coefficient should 1.");
346

	
347
  delete clp;
348

	
349
  //Maximization of x1+x2
350
  //over the triangle with vertices (0,0) (0,1) (1,0)
351
  double expected_opt=1;
352
  solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
353

	
354
  //Minimization
355
  lp.min();
356
  expected_opt=0;
357
  solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
358

	
359
  //Vertex (-1,0) instead of (0,0)
360
  lp.colLowerBound(x1, -LpSolverBase::INF);
361
  expected_opt=-1;
362
  solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
363

	
364
  //Erase one constraint and return to maximization
365
  lp.eraseRow(upright);
366
  lp.max();
367
  expected_opt=LpSolverBase::INF;
368
  solveAndCheck(lp, LpSolverBase::INFINITE, expected_opt);
369

	
370
  //Infeasibilty
371
  lp.addRow(x1+x2 <=-2);
372
  solveAndCheck(lp, LpSolverBase::INFEASIBLE, expected_opt);
373

	
374
  //Change problem and forget to solve
375
  lp.min();
376
  check(lp.primalStatus()==LpSolverBase::UNDEFINED,
377
        "Primalstatus should be UNDEFINED");
378

	
379

	
380
//   lp.solve();
381
//   if (lp.primalStatus()==LpSolverBase::OPTIMAL){
382
//     std::cout<< "Z = "<<lp.primalValue()
383
//              << " (error = " << lp.primalValue()-expected_opt
384
//              << "); x1 = "<<lp.primal(x1)
385
//              << "; x2 = "<<lp.primal(x2)
386
//              <<std::endl;
387

	
388
//   }
389
//   else{
390
//     std::cout<<lp.primalStatus()<<std::endl;
391
//     std::cout<<"Optimal solution not found!"<<std::endl;
392
//   }
393

	
394

	
395

	
396
}
397

	
398

	
399
int main()
400
{
401
  LpSkeleton lp_skel;
402
  lpTest(lp_skel);
403

	
404
#ifdef HAVE_GLPK
405
  LpGlpk lp_glpk1,lp_glpk2;
406
  lpTest(lp_glpk1);
407
  aTest(lp_glpk2);
408
#endif
409

	
410
#ifdef HAVE_CPLEX
411
  LpCplex lp_cplex1,lp_cplex2;
412
  lpTest(lp_cplex1);
413
  aTest(lp_cplex2);
414
#endif
415

	
416
#ifdef HAVE_SOPLEX
417
  LpSoplex lp_soplex1,lp_soplex2;
418
  lpTest(lp_soplex1);
419
  aTest(lp_soplex2);
420
#endif
421

	
422
  return 0;
423
}
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2008
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
#include "test_tools.h"
20

	
21

	
22
#ifdef HAVE_CONFIG_H
23
#include <lemon/config.h>
24
#endif
25

	
26
#ifdef HAVE_CPLEX
27
#include <lemon/mip_cplex.h>
28
#endif
29

	
30
#ifdef HAVE_GLPK
31
#include <lemon/mip_glpk.h>
32
#endif
33

	
34

	
35
using namespace lemon;
36

	
37
void solveAndCheck(MipSolverBase& lp, MipSolverBase::SolutionStatus stat,
38
                   double exp_opt) {
39
  using std::string;
40

	
41
  lp.solve();
42
  //int decimal,sign;
43
  std::ostringstream buf;
44
  buf << "Primalstatus should be: " << int(stat)
45
      <<" and it is "<<int(lp.mipStatus());
46

	
47

	
48
  //  itoa(stat,buf1, 10);
49
  check(lp.mipStatus()==stat, buf.str());
50

	
51
  if (stat ==  MipSolverBase::OPTIMAL) {
52
    std::ostringstream sbuf;
53
    buf << "Wrong optimal value: the right optimum is " << exp_opt;
54
    check(std::abs(lp.primalValue()-exp_opt) < 1e-3, sbuf.str());
55
    //+ecvt(exp_opt,2)
56
  }
57
}
58

	
59
void aTest(MipSolverBase& mip)
60
{
61
 //The following example is very simple
62

	
63

	
64
  typedef MipSolverBase::Row Row;
65
  typedef MipSolverBase::Col Col;
66

	
67

	
68

	
69
  Col x1 = mip.addCol();
70
  Col x2 = mip.addCol();
71

	
72

	
73
  //Objective function
74
  mip.obj(x1);
75

	
76
  mip.max();
77

	
78

	
79
  //Unconstrained optimization
80
  mip.solve();
81
  //Check it out!
82

	
83
  //Constraints
84
  mip.addRow(2*x1+x2 <=2);
85
  mip.addRow(x1-2*x2 <=0);
86

	
87
  //Nonnegativity of the variable x1
88
  mip.colLowerBound(x1, 0);
89

	
90
  //Maximization of x1
91
  //over the triangle with vertices (0,0),(4/5,2/5),(0,2)
92
  double expected_opt=4.0/5.0;
93
  solveAndCheck(mip, MipSolverBase::OPTIMAL, expected_opt);
94

	
95
  //Restrict x2 to integer
96
  mip.colType(x2,MipSolverBase::INT);
97
  expected_opt=1.0/2.0;
98
  solveAndCheck(mip, MipSolverBase::OPTIMAL, expected_opt);
99

	
100

	
101
  //Restrict both to integer
102
  mip.colType(x1,MipSolverBase::INT);
103
  expected_opt=0;
104
  solveAndCheck(mip, MipSolverBase::OPTIMAL, expected_opt);
105

	
106

	
107

	
108
}
109

	
110

	
111
int main()
112
{
113

	
114
#ifdef HAVE_GLPK
115
  MipGlpk mip1;
116
  aTest(mip1);
117
#endif
118

	
119
#ifdef HAVE_CPLEX
120
  MipCplex mip2;
121
  aTest(mip2);
122
#endif
123

	
124
  return 0;
125

	
126
}
Ignore white space 6 line context
... ...
@@ -47,15 +47,15 @@
47 47
if test "$GXX" = yes -a "$ICC" = no; then
48 48
  WARNINGCXXFLAGS="-Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
49 49
fi
50 50
AC_SUBST([WARNINGCXXFLAGS])
51 51

	
52 52
dnl Checks for libraries.
53
#LX_CHECK_GLPK
54
#LX_CHECK_CPLEX
55
#LX_CHECK_SOPLEX
53
LX_CHECK_GLPK
54
LX_CHECK_CPLEX
55
LX_CHECK_SOPLEX
56 56

	
57 57
AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
58 58
AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
59 59

	
60 60
dnl Disable/enable building the demo programs.
61 61
AC_ARG_ENABLE([demo],
... ...
@@ -114,16 +114,16 @@
114 114
echo
115 115
echo Package version............... : $PACKAGE-$VERSION
116 116
echo
117 117
echo C++ compiler.................. : $CXX
118 118
echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
119 119
echo
120
#echo GLPK support.................. : $lx_glpk_found
121
#echo CPLEX support................. : $lx_cplex_found
122
#echo SOPLEX support................ : $lx_soplex_found
123
#echo
120
echo GLPK support.................. : $lx_glpk_found
121
echo CPLEX support................. : $lx_cplex_found
122
echo SOPLEX support................ : $lx_soplex_found
123
echo
124 124
echo Build demo programs........... : $enable_demo
125 125
echo Build additional tools........ : $enable_tools
126 126
echo
127 127
echo The packace will be installed in
128 128
echo -n '  '
129 129
echo $prefix.
Ignore white space 6 line context
1 1
INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
2 2

	
3 3
ADD_LIBRARY(lemon
4 4
  arg_parser.cc
5 5
  base.cc
6 6
  color.cc
7
  lp_base.cc
8
  lp_skeleton.cc
9
  lp_utils.cc
7 10
  random.cc)
8 11

	
9 12
INSTALL(
10 13
  TARGETS lemon
11 14
  ARCHIVE DESTINATION lib
12 15
  COMPONENT library)
Ignore white space 6 line context
... ...
@@ -7,16 +7,38 @@
7 7
lib_LTLIBRARIES += lemon/libemon.la
8 8

	
9 9
lemon_libemon_la_SOURCES = \
10 10
	lemon/arg_parser.cc \
11 11
	lemon/base.cc \
12 12
	lemon/color.cc \
13
	lemon/lp_base.cc \
14
	lemon/lp_skeleton.cc \
13 15
	lemon/random.cc
14 16

	
15
#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) $(AM_CXXFLAGS)
16
#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
17

	
18
lemon_libemon_la_CXXFLAGS = \
19
	$(GLPK_CFLAGS) \
20
	$(CPLEX_CFLAGS) \
21
	$(SOPLEX_CXXFLAGS)
22

	
23
lemon_libemon_la_LDFLAGS = \
24
	$(GLPK_LIBS) \
25
	$(CPLEX_LIBS) \
26
	$(SOPLEX_LIBS)
27

	
28
if HAVE_GLPK
29
lemon_libemon_la_SOURCES += lemon/lp_glpk.cc lemon/mip_glpk.cc
30
endif
31

	
32
if HAVE_CPLEX
33
lemon_libemon_la_SOURCES += lemon/lp_cplex.cc lemon/mip_cplex.cc
34
endif
35

	
36
if HAVE_SOPLEX
37
lemon_libemon_la_SOURCES += lemon/lp_soplex.cc
38
endif
17 39

	
18 40
lemon_HEADERS += \
19 41
	lemon/adaptors.h \
20 42
	lemon/arg_parser.h \
21 43
	lemon/assert.h \
22 44
	lemon/bfs.h \
... ...
@@ -38,12 +60,20 @@
38 60
	lemon/hypercube_graph.h \
39 61
	lemon/kruskal.h \
40 62
	lemon/hao_orlin.h \
41 63
	lemon/lgf_reader.h \
42 64
	lemon/lgf_writer.h \
43 65
	lemon/list_graph.h \
66
	lemon/lp.h \
67
	lemon/lp_base.h \
68
	lemon/lp_cplex.h \
69
	lemon/lp_glpk.h \
70
	lemon/lp_skeleton.h \
71
	lemon/lp_soplex.h \
72
	lemon/mip_cplex.h \
73
	lemon/mip_glpk.h \
44 74
	lemon/maps.h \
45 75
	lemon/math.h \
46 76
	lemon/max_matching.h \
47 77
	lemon/nauty_reader.h \
48 78
	lemon/path.h \
49 79
	lemon/preflow.h \
... ...
@@ -61,12 +91,13 @@
61 91
	lemon/bits/base_extender.h \
62 92
	lemon/bits/bezier.h \
63 93
	lemon/bits/default_map.h \
64 94
	lemon/bits/enable_if.h \
65 95
	lemon/bits/graph_adaptor_extender.h \
66 96
	lemon/bits/graph_extender.h \
97
	lemon/bits/lp_id.h \
67 98
	lemon/bits/map_extender.h \
68 99
	lemon/bits/path_dump.h \
69 100
	lemon/bits/traits.h \
70 101
	lemon/bits/variant.h \
71 102
	lemon/bits/vector_map.h
72 103

	
Ignore white space 6 line context
... ...
@@ -6,6 +6,9 @@
6 6

	
7 7
/* Define to 1 if you have CPLEX. */
8 8
#undef HAVE_CPLEX
9 9

	
10 10
/* Define to 1 if you have GLPK. */
11 11
#undef HAVE_GLPK
12

	
13
/* Define to 1 if you have SOPLEX */
14
#undef HAVE_SOPLEX
... ...
 No newline at end of file
Ignore white space 6 line context
... ...
@@ -15,12 +15,14 @@
15 15
  graph_copy_test
16 16
  graph_test
17 17
  graph_utils_test
18 18
  hao_orlin_test
19 19
  heap_test
20 20
  kruskal_test
21
  lp_test
22
  mip_test
21 23
  maps_test
22 24
  max_matching_test
23 25
  radix_sort_test
24 26
  path_test
25 27
  preflow_test
26 28
  random_test
Ignore white space 6 line context
... ...
@@ -30,12 +30,19 @@
30 30
	test/suurballe_test \
31 31
	test/test_tools_fail \
32 32
	test/test_tools_pass \
33 33
	test/time_measure_test \
34 34
	test/unionfind_test
35 35

	
36
if HAVE_LP
37
check_PROGRAMS += test/lp_test
38
endif HAVE_LP
39
if HAVE_MIP
40
check_PROGRAMS += test/mip_test
41
endif HAVE_MIP
42

	
36 43
TESTS += $(check_PROGRAMS)
37 44
XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
38 45

	
39 46
test_bfs_test_SOURCES = test/bfs_test.cc
40 47
test_circulation_test_SOURCES = test/circulation_test.cc
41 48
test_counter_test_SOURCES = test/counter_test.cc
... ...
@@ -48,13 +55,15 @@
48 55
test_graph_copy_test_SOURCES = test/graph_copy_test.cc
49 56
test_graph_test_SOURCES = test/graph_test.cc
50 57
test_graph_utils_test_SOURCES = test/graph_utils_test.cc
51 58
test_heap_test_SOURCES = test/heap_test.cc
52 59
test_kruskal_test_SOURCES = test/kruskal_test.cc
53 60
test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
61
test_lp_test_SOURCES = test/lp_test.cc
54 62
test_maps_test_SOURCES = test/maps_test.cc
63
test_mip_test_SOURCES = test/mip_test.cc
55 64
test_max_matching_test_SOURCES = test/max_matching_test.cc
56 65
test_path_test_SOURCES = test/path_test.cc
57 66
test_preflow_test_SOURCES = test/preflow_test.cc
58 67
test_radix_sort_test_SOURCES = test/radix_sort_test.cc
59 68
test_suurballe_test_SOURCES = test/suurballe_test.cc
60 69
test_random_test_SOURCES = test/random_test.cc
0 comments (0 inline)