lemon/lp_base.h
author Balazs Dezso <deba@inf.elte.hu>
Wed, 01 Apr 2009 22:54:00 +0200
changeset 565 7ab97e2a0c33
parent 514 2eb5c8ca2c91
child 576 745e182d0139
permissions -rw-r--r--
Fixing presolver and basis handling (#255)
deba@458
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@458
     2
 *
deba@458
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@458
     4
 *
deba@458
     5
 * Copyright (C) 2003-2008
deba@458
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@458
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@458
     8
 *
deba@458
     9
 * Permission to use, modify and distribute this software is granted
deba@458
    10
 * provided that this copyright notice appears in all copies. For
deba@458
    11
 * precise terms see the accompanying LICENSE file.
deba@458
    12
 *
deba@458
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@458
    14
 * express or implied, and with no claim as to its suitability for any
deba@458
    15
 * purpose.
deba@458
    16
 *
deba@458
    17
 */
deba@458
    18
deba@458
    19
#ifndef LEMON_LP_BASE_H
deba@458
    20
#define LEMON_LP_BASE_H
deba@458
    21
deba@458
    22
#include<iostream>
deba@458
    23
#include<vector>
deba@458
    24
#include<map>
deba@458
    25
#include<limits>
deba@458
    26
#include<lemon/math.h>
deba@458
    27
deba@459
    28
#include<lemon/error.h>
deba@459
    29
#include<lemon/assert.h>
deba@459
    30
deba@458
    31
#include<lemon/core.h>
deba@459
    32
#include<lemon/bits/solver_bits.h>
deba@458
    33
deba@458
    34
///\file
deba@458
    35
///\brief The interface of the LP solver interface.
deba@458
    36
///\ingroup lp_group
deba@458
    37
namespace lemon {
deba@458
    38
deba@459
    39
  ///Common base class for LP and MIP solvers
deba@458
    40
deba@459
    41
  ///Usually this class is not used directly, please use one of the concrete
deba@459
    42
  ///implementations of the solver interface.
deba@458
    43
  ///\ingroup lp_group
deba@459
    44
  class LpBase {
deba@458
    45
deba@458
    46
  protected:
deba@458
    47
deba@459
    48
    _solver_bits::VarIndex rows;
deba@459
    49
    _solver_bits::VarIndex cols;
deba@458
    50
deba@458
    51
  public:
deba@458
    52
deba@458
    53
    ///Possible outcomes of an LP solving procedure
deba@458
    54
    enum SolveExitStatus {
deba@458
    55
      ///This means that the problem has been successfully solved: either
deba@458
    56
      ///an optimal solution has been found or infeasibility/unboundedness
deba@458
    57
      ///has been proved.
deba@458
    58
      SOLVED = 0,
deba@458
    59
      ///Any other case (including the case when some user specified
deba@458
    60
      ///limit has been exceeded)
deba@458
    61
      UNSOLVED = 1
deba@458
    62
    };
deba@458
    63
deba@459
    64
    ///Direction of the optimization
deba@459
    65
    enum Sense {
deba@459
    66
      /// Minimization
deba@459
    67
      MIN,
deba@459
    68
      /// Maximization
deba@459
    69
      MAX
deba@458
    70
    };
deba@458
    71
deba@458
    72
    ///The floating point type used by the solver
deba@458
    73
    typedef double Value;
deba@458
    74
    ///The infinity constant
deba@458
    75
    static const Value INF;
deba@458
    76
    ///The not a number constant
deba@458
    77
    static const Value NaN;
deba@458
    78
deba@458
    79
    friend class Col;
deba@458
    80
    friend class ColIt;
deba@458
    81
    friend class Row;
deba@459
    82
    friend class RowIt;
deba@458
    83
deba@458
    84
    ///Refer to a column of the LP.
deba@458
    85
deba@458
    86
    ///This type is used to refer to a column of the LP.
deba@458
    87
    ///
deba@458
    88
    ///Its value remains valid and correct even after the addition or erase of
deba@458
    89
    ///other columns.
deba@458
    90
    ///
deba@459
    91
    ///\note This class is similar to other Item types in LEMON, like
deba@459
    92
    ///Node and Arc types in digraph.
deba@458
    93
    class Col {
deba@459
    94
      friend class LpBase;
deba@458
    95
    protected:
deba@459
    96
      int _id;
deba@459
    97
      explicit Col(int id) : _id(id) {}
deba@458
    98
    public:
deba@458
    99
      typedef Value ExprValue;
deba@459
   100
      typedef True LpCol;
deba@459
   101
      /// Default constructor
deba@459
   102
      
deba@459
   103
      /// \warning The default constructor sets the Col to an
deba@459
   104
      /// undefined value.
deba@458
   105
      Col() {}
deba@459
   106
      /// Invalid constructor \& conversion.
deba@459
   107
      
deba@459
   108
      /// This constructor initializes the Col to be invalid.
deba@459
   109
      /// \sa Invalid for more details.      
deba@459
   110
      Col(const Invalid&) : _id(-1) {}
deba@459
   111
      /// Equality operator
deba@459
   112
deba@459
   113
      /// Two \ref Col "Col"s are equal if and only if they point to
deba@459
   114
      /// the same LP column or both are invalid.
deba@459
   115
      bool operator==(Col c) const  {return _id == c._id;}
deba@459
   116
      /// Inequality operator
deba@459
   117
deba@459
   118
      /// \sa operator==(Col c)
deba@459
   119
      ///
deba@459
   120
      bool operator!=(Col c) const  {return _id != c._id;}
deba@459
   121
      /// Artificial ordering operator.
deba@459
   122
deba@459
   123
      /// To allow the use of this object in std::map or similar
deba@459
   124
      /// associative container we require this.
deba@459
   125
      ///
deba@459
   126
      /// \note This operator only have to define some strict ordering of
deba@459
   127
      /// the items; this order has nothing to do with the iteration
deba@459
   128
      /// ordering of the items.
deba@459
   129
      bool operator<(Col c) const  {return _id < c._id;}
deba@458
   130
    };
deba@458
   131
deba@459
   132
    ///Iterator for iterate over the columns of an LP problem
deba@459
   133
deba@459
   134
    /// Its usage is quite simple, for example you can count the number
deba@459
   135
    /// of columns in an LP \c lp:
deba@459
   136
    ///\code
deba@459
   137
    /// int count=0;
deba@459
   138
    /// for (LpBase::ColIt c(lp); c!=INVALID; ++c) ++count;
deba@459
   139
    ///\endcode
deba@458
   140
    class ColIt : public Col {
deba@459
   141
      const LpBase *_solver;
deba@458
   142
    public:
deba@459
   143
      /// Default constructor
deba@459
   144
      
deba@459
   145
      /// \warning The default constructor sets the iterator
deba@459
   146
      /// to an undefined value.
deba@458
   147
      ColIt() {}
deba@459
   148
      /// Sets the iterator to the first Col
deba@459
   149
      
deba@459
   150
      /// Sets the iterator to the first Col.
deba@459
   151
      ///
deba@459
   152
      ColIt(const LpBase &solver) : _solver(&solver)
deba@458
   153
      {
deba@459
   154
        _solver->cols.firstItem(_id);
deba@458
   155
      }
deba@459
   156
      /// Invalid constructor \& conversion
deba@459
   157
      
deba@459
   158
      /// Initialize the iterator to be invalid.
deba@459
   159
      /// \sa Invalid for more details.
deba@458
   160
      ColIt(const Invalid&) : Col(INVALID) {}
deba@459
   161
      /// Next column
deba@459
   162
      
deba@459
   163
      /// Assign the iterator to the next column.
deba@459
   164
      ///
deba@458
   165
      ColIt &operator++()
deba@458
   166
      {
deba@459
   167
        _solver->cols.nextItem(_id);
deba@458
   168
        return *this;
deba@458
   169
      }
deba@458
   170
    };
deba@458
   171
deba@459
   172
    /// \brief Returns the ID of the column.
deba@459
   173
    static int id(const Col& col) { return col._id; }
deba@459
   174
    /// \brief Returns the column with the given ID.
deba@459
   175
    ///
deba@459
   176
    /// \pre The argument should be a valid column ID in the LP problem.
deba@459
   177
    static Col colFromId(int id) { return Col(id); }
deba@458
   178
deba@458
   179
    ///Refer to a row of the LP.
deba@458
   180
deba@458
   181
    ///This type is used to refer to a row of the LP.
deba@458
   182
    ///
deba@458
   183
    ///Its value remains valid and correct even after the addition or erase of
deba@458
   184
    ///other rows.
deba@458
   185
    ///
deba@459
   186
    ///\note This class is similar to other Item types in LEMON, like
deba@459
   187
    ///Node and Arc types in digraph.
deba@458
   188
    class Row {
deba@459
   189
      friend class LpBase;
deba@458
   190
    protected:
deba@459
   191
      int _id;
deba@459
   192
      explicit Row(int id) : _id(id) {}
deba@458
   193
    public:
deba@458
   194
      typedef Value ExprValue;
deba@459
   195
      typedef True LpRow;
deba@459
   196
      /// Default constructor
deba@459
   197
      
deba@459
   198
      /// \warning The default constructor sets the Row to an
deba@459
   199
      /// undefined value.
deba@458
   200
      Row() {}
deba@459
   201
      /// Invalid constructor \& conversion.
deba@459
   202
      
deba@459
   203
      /// This constructor initializes the Row to be invalid.
deba@459
   204
      /// \sa Invalid for more details.      
deba@459
   205
      Row(const Invalid&) : _id(-1) {}
deba@459
   206
      /// Equality operator
deba@458
   207
deba@459
   208
      /// Two \ref Row "Row"s are equal if and only if they point to
deba@459
   209
      /// the same LP row or both are invalid.
deba@459
   210
      bool operator==(Row r) const  {return _id == r._id;}
deba@459
   211
      /// Inequality operator
deba@459
   212
      
deba@459
   213
      /// \sa operator==(Row r)
deba@459
   214
      ///
deba@459
   215
      bool operator!=(Row r) const  {return _id != r._id;}
deba@459
   216
      /// Artificial ordering operator.
deba@459
   217
deba@459
   218
      /// To allow the use of this object in std::map or similar
deba@459
   219
      /// associative container we require this.
deba@459
   220
      ///
deba@459
   221
      /// \note This operator only have to define some strict ordering of
deba@459
   222
      /// the items; this order has nothing to do with the iteration
deba@459
   223
      /// ordering of the items.
deba@459
   224
      bool operator<(Row r) const  {return _id < r._id;}
deba@458
   225
    };
deba@458
   226
deba@459
   227
    ///Iterator for iterate over the rows of an LP problem
deba@459
   228
deba@459
   229
    /// Its usage is quite simple, for example you can count the number
deba@459
   230
    /// of rows in an LP \c lp:
deba@459
   231
    ///\code
deba@459
   232
    /// int count=0;
deba@459
   233
    /// for (LpBase::RowIt c(lp); c!=INVALID; ++c) ++count;
deba@459
   234
    ///\endcode
deba@458
   235
    class RowIt : public Row {
deba@459
   236
      const LpBase *_solver;
deba@458
   237
    public:
deba@459
   238
      /// Default constructor
deba@459
   239
      
deba@459
   240
      /// \warning The default constructor sets the iterator
deba@459
   241
      /// to an undefined value.
deba@458
   242
      RowIt() {}
deba@459
   243
      /// Sets the iterator to the first Row
deba@459
   244
      
deba@459
   245
      /// Sets the iterator to the first Row.
deba@459
   246
      ///
deba@459
   247
      RowIt(const LpBase &solver) : _solver(&solver)
deba@458
   248
      {
deba@459
   249
        _solver->rows.firstItem(_id);
deba@458
   250
      }
deba@459
   251
      /// Invalid constructor \& conversion
deba@459
   252
      
deba@459
   253
      /// Initialize the iterator to be invalid.
deba@459
   254
      /// \sa Invalid for more details.
deba@458
   255
      RowIt(const Invalid&) : Row(INVALID) {}
deba@459
   256
      /// Next row
deba@459
   257
      
deba@459
   258
      /// Assign the iterator to the next row.
deba@459
   259
      ///
deba@458
   260
      RowIt &operator++()
deba@458
   261
      {
deba@459
   262
        _solver->rows.nextItem(_id);
deba@458
   263
        return *this;
deba@458
   264
      }
deba@458
   265
    };
deba@458
   266
deba@459
   267
    /// \brief Returns the ID of the row.
deba@459
   268
    static int id(const Row& row) { return row._id; }
deba@459
   269
    /// \brief Returns the row with the given ID.
deba@459
   270
    ///
deba@459
   271
    /// \pre The argument should be a valid row ID in the LP problem.
deba@459
   272
    static Row rowFromId(int id) { return Row(id); }
deba@458
   273
deba@458
   274
  public:
deba@458
   275
deba@458
   276
    ///Linear expression of variables and a constant component
deba@458
   277
deba@458
   278
    ///This data structure stores a linear expression of the variables
deba@458
   279
    ///(\ref Col "Col"s) and also has a constant component.
deba@458
   280
    ///
deba@458
   281
    ///There are several ways to access and modify the contents of this
deba@458
   282
    ///container.
deba@458
   283
    ///\code
deba@458
   284
    ///e[v]=5;
deba@458
   285
    ///e[v]+=12;
deba@458
   286
    ///e.erase(v);
deba@458
   287
    ///\endcode
deba@458
   288
    ///or you can also iterate through its elements.
deba@458
   289
    ///\code
deba@458
   290
    ///double s=0;
deba@459
   291
    ///for(LpBase::Expr::ConstCoeffIt i(e);i!=INVALID;++i)
deba@459
   292
    ///  s+=*i * primal(i);
deba@458
   293
    ///\endcode
deba@459
   294
    ///(This code computes the primal value of the expression).
deba@458
   295
    ///- Numbers (<tt>double</tt>'s)
deba@458
   296
    ///and variables (\ref Col "Col"s) directly convert to an
deba@458
   297
    ///\ref Expr and the usual linear operations are defined, so
deba@458
   298
    ///\code
deba@458
   299
    ///v+w
deba@458
   300
    ///2*v-3.12*(v-w/2)+2
deba@458
   301
    ///v*2.1+(3*v+(v*12+w+6)*3)/2
deba@458
   302
    ///\endcode
deba@459
   303
    ///are valid expressions.
deba@458
   304
    ///The usual assignment operations are also defined.
deba@458
   305
    ///\code
deba@458
   306
    ///e=v+w;
deba@458
   307
    ///e+=2*v-3.12*(v-w/2)+2;
deba@458
   308
    ///e*=3.4;
deba@458
   309
    ///e/=5;
deba@458
   310
    ///\endcode
deba@459
   311
    ///- The constant member can be set and read by dereference
deba@459
   312
    ///  operator (unary *)
deba@459
   313
    ///
deba@458
   314
    ///\code
deba@459
   315
    ///*e=12;
deba@459
   316
    ///double c=*e;
deba@458
   317
    ///\endcode
deba@458
   318
    ///
deba@458
   319
    ///\sa Constr
deba@459
   320
    class Expr {
deba@459
   321
      friend class LpBase;
deba@458
   322
    public:
deba@459
   323
      /// The key type of the expression
deba@459
   324
      typedef LpBase::Col Key;
deba@459
   325
      /// The value type of the expression
deba@459
   326
      typedef LpBase::Value Value;
deba@458
   327
deba@458
   328
    protected:
deba@459
   329
      Value const_comp;
deba@459
   330
      std::map<int, Value> comps;
deba@458
   331
deba@458
   332
    public:
deba@459
   333
      typedef True SolverExpr;
deba@459
   334
      /// Default constructor
deba@459
   335
      
deba@459
   336
      /// Construct an empty expression, the coefficients and
deba@459
   337
      /// the constant component are initialized to zero.
deba@459
   338
      Expr() : const_comp(0) {}
deba@459
   339
      /// Construct an expression from a column
deba@459
   340
deba@459
   341
      /// Construct an expression, which has a term with \c c variable
deba@459
   342
      /// and 1.0 coefficient.
deba@459
   343
      Expr(const Col &c) : const_comp(0) {
deba@459
   344
        typedef std::map<int, Value>::value_type pair_type;
deba@459
   345
        comps.insert(pair_type(id(c), 1));
deba@458
   346
      }
deba@459
   347
      /// Construct an expression from a constant
deba@459
   348
deba@459
   349
      /// Construct an expression, which's constant component is \c v.
deba@459
   350
      ///
deba@458
   351
      Expr(const Value &v) : const_comp(v) {}
deba@459
   352
      /// Returns the coefficient of the column
deba@459
   353
      Value operator[](const Col& c) const {
deba@459
   354
        std::map<int, Value>::const_iterator it=comps.find(id(c));
deba@459
   355
        if (it != comps.end()) {
deba@459
   356
          return it->second;
deba@459
   357
        } else {
deba@459
   358
          return 0;
deba@458
   359
        }
deba@458
   360
      }
deba@459
   361
      /// Returns the coefficient of the column
deba@459
   362
      Value& operator[](const Col& c) {
deba@459
   363
        return comps[id(c)];
deba@459
   364
      }
deba@459
   365
      /// Sets the coefficient of the column
deba@459
   366
      void set(const Col &c, const Value &v) {
deba@459
   367
        if (v != 0.0) {
deba@459
   368
          typedef std::map<int, Value>::value_type pair_type;
deba@459
   369
          comps.insert(pair_type(id(c), v));
deba@459
   370
        } else {
deba@459
   371
          comps.erase(id(c));
deba@459
   372
        }
deba@459
   373
      }
deba@459
   374
      /// Returns the constant component of the expression
deba@459
   375
      Value& operator*() { return const_comp; }
deba@459
   376
      /// Returns the constant component of the expression
deba@459
   377
      const Value& operator*() const { return const_comp; }
deba@459
   378
      /// \brief Removes the coefficients which's absolute value does
deba@459
   379
      /// not exceed \c epsilon. It also sets to zero the constant
deba@459
   380
      /// component, if it does not exceed epsilon in absolute value.
deba@459
   381
      void simplify(Value epsilon = 0.0) {
deba@459
   382
        std::map<int, Value>::iterator it=comps.begin();
deba@459
   383
        while (it != comps.end()) {
deba@459
   384
          std::map<int, Value>::iterator jt=it;
deba@459
   385
          ++jt;
deba@459
   386
          if (std::fabs((*it).second) <= epsilon) comps.erase(it);
deba@459
   387
          it=jt;
deba@459
   388
        }
deba@459
   389
        if (std::fabs(const_comp) <= epsilon) const_comp = 0;
deba@458
   390
      }
deba@458
   391
deba@459
   392
      void simplify(Value epsilon = 0.0) const {
deba@459
   393
        const_cast<Expr*>(this)->simplify(epsilon);
deba@458
   394
      }
deba@458
   395
deba@458
   396
      ///Sets all coefficients and the constant component to 0.
deba@458
   397
      void clear() {
deba@459
   398
        comps.clear();
deba@458
   399
        const_comp=0;
deba@458
   400
      }
deba@458
   401
deba@459
   402
      ///Compound assignment
deba@458
   403
      Expr &operator+=(const Expr &e) {
deba@459
   404
        for (std::map<int, Value>::const_iterator it=e.comps.begin();
deba@459
   405
             it!=e.comps.end(); ++it)
deba@459
   406
          comps[it->first]+=it->second;
deba@458
   407
        const_comp+=e.const_comp;
deba@458
   408
        return *this;
deba@458
   409
      }
deba@459
   410
      ///Compound assignment
deba@458
   411
      Expr &operator-=(const Expr &e) {
deba@459
   412
        for (std::map<int, Value>::const_iterator it=e.comps.begin();
deba@459
   413
             it!=e.comps.end(); ++it)
deba@459
   414
          comps[it->first]-=it->second;
deba@458
   415
        const_comp-=e.const_comp;
deba@458
   416
        return *this;
deba@458
   417
      }
deba@459
   418
      ///Multiply with a constant
deba@459
   419
      Expr &operator*=(const Value &v) {
deba@459
   420
        for (std::map<int, Value>::iterator it=comps.begin();
deba@459
   421
             it!=comps.end(); ++it)
deba@459
   422
          it->second*=v;
deba@459
   423
        const_comp*=v;
deba@458
   424
        return *this;
deba@458
   425
      }
deba@459
   426
      ///Division with a constant
deba@458
   427
      Expr &operator/=(const Value &c) {
deba@459
   428
        for (std::map<int, Value>::iterator it=comps.begin();
deba@459
   429
             it!=comps.end(); ++it)
deba@459
   430
          it->second/=c;
deba@458
   431
        const_comp/=c;
deba@458
   432
        return *this;
deba@458
   433
      }
deba@458
   434
deba@459
   435
      ///Iterator over the expression
deba@459
   436
      
deba@459
   437
      ///The iterator iterates over the terms of the expression. 
deba@459
   438
      /// 
deba@459
   439
      ///\code
deba@459
   440
      ///double s=0;
deba@459
   441
      ///for(LpBase::Expr::CoeffIt i(e);i!=INVALID;++i)
deba@459
   442
      ///  s+= *i * primal(i);
deba@459
   443
      ///\endcode
deba@459
   444
      class CoeffIt {
deba@459
   445
      private:
deba@459
   446
deba@459
   447
        std::map<int, Value>::iterator _it, _end;
deba@459
   448
deba@459
   449
      public:
deba@459
   450
deba@459
   451
        /// Sets the iterator to the first term
deba@459
   452
        
deba@459
   453
        /// Sets the iterator to the first term of the expression.
deba@459
   454
        ///
deba@459
   455
        CoeffIt(Expr& e)
deba@459
   456
          : _it(e.comps.begin()), _end(e.comps.end()){}
deba@459
   457
deba@459
   458
        /// Convert the iterator to the column of the term
deba@459
   459
        operator Col() const {
deba@459
   460
          return colFromId(_it->first);
deba@459
   461
        }
deba@459
   462
deba@459
   463
        /// Returns the coefficient of the term
deba@459
   464
        Value& operator*() { return _it->second; }
deba@459
   465
deba@459
   466
        /// Returns the coefficient of the term
deba@459
   467
        const Value& operator*() const { return _it->second; }
deba@459
   468
        /// Next term
deba@459
   469
        
deba@459
   470
        /// Assign the iterator to the next term.
deba@459
   471
        ///
deba@459
   472
        CoeffIt& operator++() { ++_it; return *this; }
deba@459
   473
deba@459
   474
        /// Equality operator
deba@459
   475
        bool operator==(Invalid) const { return _it == _end; }
deba@459
   476
        /// Inequality operator
deba@459
   477
        bool operator!=(Invalid) const { return _it != _end; }
deba@459
   478
      };
deba@459
   479
deba@459
   480
      /// Const iterator over the expression
deba@459
   481
      
deba@459
   482
      ///The iterator iterates over the terms of the expression. 
deba@459
   483
      /// 
deba@459
   484
      ///\code
deba@459
   485
      ///double s=0;
deba@459
   486
      ///for(LpBase::Expr::ConstCoeffIt i(e);i!=INVALID;++i)
deba@459
   487
      ///  s+=*i * primal(i);
deba@459
   488
      ///\endcode
deba@459
   489
      class ConstCoeffIt {
deba@459
   490
      private:
deba@459
   491
deba@459
   492
        std::map<int, Value>::const_iterator _it, _end;
deba@459
   493
deba@459
   494
      public:
deba@459
   495
deba@459
   496
        /// Sets the iterator to the first term
deba@459
   497
        
deba@459
   498
        /// Sets the iterator to the first term of the expression.
deba@459
   499
        ///
deba@459
   500
        ConstCoeffIt(const Expr& e)
deba@459
   501
          : _it(e.comps.begin()), _end(e.comps.end()){}
deba@459
   502
deba@459
   503
        /// Convert the iterator to the column of the term
deba@459
   504
        operator Col() const {
deba@459
   505
          return colFromId(_it->first);
deba@459
   506
        }
deba@459
   507
deba@459
   508
        /// Returns the coefficient of the term
deba@459
   509
        const Value& operator*() const { return _it->second; }
deba@459
   510
deba@459
   511
        /// Next term
deba@459
   512
        
deba@459
   513
        /// Assign the iterator to the next term.
deba@459
   514
        ///
deba@459
   515
        ConstCoeffIt& operator++() { ++_it; return *this; }
deba@459
   516
deba@459
   517
        /// Equality operator
deba@459
   518
        bool operator==(Invalid) const { return _it == _end; }
deba@459
   519
        /// Inequality operator
deba@459
   520
        bool operator!=(Invalid) const { return _it != _end; }
deba@459
   521
      };
deba@459
   522
deba@458
   523
    };
deba@458
   524
deba@458
   525
    ///Linear constraint
deba@458
   526
deba@458
   527
    ///This data stucture represents a linear constraint in the LP.
deba@458
   528
    ///Basically it is a linear expression with a lower or an upper bound
deba@458
   529
    ///(or both). These parts of the constraint can be obtained by the member
deba@458
   530
    ///functions \ref expr(), \ref lowerBound() and \ref upperBound(),
deba@458
   531
    ///respectively.
deba@458
   532
    ///There are two ways to construct a constraint.
deba@458
   533
    ///- You can set the linear expression and the bounds directly
deba@458
   534
    ///  by the functions above.
deba@458
   535
    ///- The operators <tt>\<=</tt>, <tt>==</tt> and  <tt>\>=</tt>
deba@458
   536
    ///  are defined between expressions, or even between constraints whenever
deba@458
   537
    ///  it makes sense. Therefore if \c e and \c f are linear expressions and
deba@458
   538
    ///  \c s and \c t are numbers, then the followings are valid expressions
deba@458
   539
    ///  and thus they can be used directly e.g. in \ref addRow() whenever
deba@458
   540
    ///  it makes sense.
deba@458
   541
    ///\code
deba@458
   542
    ///  e<=s
deba@458
   543
    ///  e<=f
deba@458
   544
    ///  e==f
deba@458
   545
    ///  s<=e<=t
deba@458
   546
    ///  e>=t
deba@458
   547
    ///\endcode
deba@459
   548
    ///\warning The validity of a constraint is checked only at run
deba@459
   549
    ///time, so e.g. \ref addRow(<tt>x[1]\<=x[2]<=5</tt>) will
deba@459
   550
    ///compile, but will fail an assertion.
deba@458
   551
    class Constr
deba@458
   552
    {
deba@458
   553
    public:
deba@459
   554
      typedef LpBase::Expr Expr;
deba@458
   555
      typedef Expr::Key Key;
deba@458
   556
      typedef Expr::Value Value;
deba@458
   557
deba@458
   558
    protected:
deba@458
   559
      Expr _expr;
deba@458
   560
      Value _lb,_ub;
deba@458
   561
    public:
deba@458
   562
      ///\e
deba@458
   563
      Constr() : _expr(), _lb(NaN), _ub(NaN) {}
deba@458
   564
      ///\e
deba@459
   565
      Constr(Value lb, const Expr &e, Value ub) :
deba@458
   566
        _expr(e), _lb(lb), _ub(ub) {}
deba@458
   567
      Constr(const Expr &e) :
deba@458
   568
        _expr(e), _lb(NaN), _ub(NaN) {}
deba@458
   569
      ///\e
deba@458
   570
      void clear()
deba@458
   571
      {
deba@458
   572
        _expr.clear();
deba@458
   573
        _lb=_ub=NaN;
deba@458
   574
      }
deba@458
   575
deba@458
   576
      ///Reference to the linear expression
deba@458
   577
      Expr &expr() { return _expr; }
deba@458
   578
      ///Cont reference to the linear expression
deba@458
   579
      const Expr &expr() const { return _expr; }
deba@458
   580
      ///Reference to the lower bound.
deba@458
   581
deba@458
   582
      ///\return
deba@458
   583
      ///- \ref INF "INF": the constraint is lower unbounded.
deba@458
   584
      ///- \ref NaN "NaN": lower bound has not been set.
deba@458
   585
      ///- finite number: the lower bound
deba@458
   586
      Value &lowerBound() { return _lb; }
deba@458
   587
      ///The const version of \ref lowerBound()
deba@458
   588
      const Value &lowerBound() const { return _lb; }
deba@458
   589
      ///Reference to the upper bound.
deba@458
   590
deba@458
   591
      ///\return
deba@458
   592
      ///- \ref INF "INF": the constraint is upper unbounded.
deba@458
   593
      ///- \ref NaN "NaN": upper bound has not been set.
deba@458
   594
      ///- finite number: the upper bound
deba@458
   595
      Value &upperBound() { return _ub; }
deba@458
   596
      ///The const version of \ref upperBound()
deba@458
   597
      const Value &upperBound() const { return _ub; }
deba@458
   598
      ///Is the constraint lower bounded?
deba@458
   599
      bool lowerBounded() const {
alpar@511
   600
        return _lb != -INF && !isNaN(_lb);
deba@458
   601
      }
deba@458
   602
      ///Is the constraint upper bounded?
deba@458
   603
      bool upperBounded() const {
alpar@511
   604
        return _ub != INF && !isNaN(_ub);
deba@458
   605
      }
deba@458
   606
deba@458
   607
    };
deba@458
   608
deba@458
   609
    ///Linear expression of rows
deba@458
   610
deba@458
   611
    ///This data structure represents a column of the matrix,
deba@458
   612
    ///thas is it strores a linear expression of the dual variables
deba@458
   613
    ///(\ref Row "Row"s).
deba@458
   614
    ///
deba@458
   615
    ///There are several ways to access and modify the contents of this
deba@458
   616
    ///container.
deba@458
   617
    ///\code
deba@458
   618
    ///e[v]=5;
deba@458
   619
    ///e[v]+=12;
deba@458
   620
    ///e.erase(v);
deba@458
   621
    ///\endcode
deba@458
   622
    ///or you can also iterate through its elements.
deba@458
   623
    ///\code
deba@458
   624
    ///double s=0;
deba@459
   625
    ///for(LpBase::DualExpr::ConstCoeffIt i(e);i!=INVALID;++i)
deba@459
   626
    ///  s+=*i;
deba@458
   627
    ///\endcode
deba@458
   628
    ///(This code computes the sum of all coefficients).
deba@458
   629
    ///- Numbers (<tt>double</tt>'s)
deba@458
   630
    ///and variables (\ref Row "Row"s) directly convert to an
deba@458
   631
    ///\ref DualExpr and the usual linear operations are defined, so
deba@458
   632
    ///\code
deba@458
   633
    ///v+w
deba@458
   634
    ///2*v-3.12*(v-w/2)
deba@458
   635
    ///v*2.1+(3*v+(v*12+w)*3)/2
deba@458
   636
    ///\endcode
deba@459
   637
    ///are valid \ref DualExpr dual expressions.
deba@458
   638
    ///The usual assignment operations are also defined.
deba@458
   639
    ///\code
deba@458
   640
    ///e=v+w;
deba@458
   641
    ///e+=2*v-3.12*(v-w/2);
deba@458
   642
    ///e*=3.4;
deba@458
   643
    ///e/=5;
deba@458
   644
    ///\endcode
deba@458
   645
    ///
deba@458
   646
    ///\sa Expr
deba@459
   647
    class DualExpr {
deba@459
   648
      friend class LpBase;
deba@458
   649
    public:
deba@459
   650
      /// The key type of the expression
deba@459
   651
      typedef LpBase::Row Key;
deba@459
   652
      /// The value type of the expression
deba@459
   653
      typedef LpBase::Value Value;
deba@458
   654
deba@458
   655
    protected:
deba@459
   656
      std::map<int, Value> comps;
deba@458
   657
deba@458
   658
    public:
deba@459
   659
      typedef True SolverExpr;
deba@459
   660
      /// Default constructor
deba@459
   661
      
deba@459
   662
      /// Construct an empty expression, the coefficients are
deba@459
   663
      /// initialized to zero.
deba@459
   664
      DualExpr() {}
deba@459
   665
      /// Construct an expression from a row
deba@459
   666
deba@459
   667
      /// Construct an expression, which has a term with \c r dual
deba@459
   668
      /// variable and 1.0 coefficient.
deba@459
   669
      DualExpr(const Row &r) {
deba@459
   670
        typedef std::map<int, Value>::value_type pair_type;
deba@459
   671
        comps.insert(pair_type(id(r), 1));
deba@458
   672
      }
deba@459
   673
      /// Returns the coefficient of the row
deba@459
   674
      Value operator[](const Row& r) const {
deba@459
   675
        std::map<int, Value>::const_iterator it = comps.find(id(r));
deba@459
   676
        if (it != comps.end()) {
deba@459
   677
          return it->second;
deba@459
   678
        } else {
deba@459
   679
          return 0;
deba@459
   680
        }
deba@458
   681
      }
deba@459
   682
      /// Returns the coefficient of the row
deba@459
   683
      Value& operator[](const Row& r) {
deba@459
   684
        return comps[id(r)];
deba@459
   685
      }
deba@459
   686
      /// Sets the coefficient of the row
deba@459
   687
      void set(const Row &r, const Value &v) {
deba@459
   688
        if (v != 0.0) {
deba@459
   689
          typedef std::map<int, Value>::value_type pair_type;
deba@459
   690
          comps.insert(pair_type(id(r), v));
deba@459
   691
        } else {
deba@459
   692
          comps.erase(id(r));
deba@459
   693
        }
deba@459
   694
      }
deba@459
   695
      /// \brief Removes the coefficients which's absolute value does
deba@459
   696
      /// not exceed \c epsilon. 
deba@459
   697
      void simplify(Value epsilon = 0.0) {
deba@459
   698
        std::map<int, Value>::iterator it=comps.begin();
deba@459
   699
        while (it != comps.end()) {
deba@459
   700
          std::map<int, Value>::iterator jt=it;
deba@459
   701
          ++jt;
deba@459
   702
          if (std::fabs((*it).second) <= epsilon) comps.erase(it);
deba@459
   703
          it=jt;
deba@458
   704
        }
deba@458
   705
      }
deba@458
   706
deba@459
   707
      void simplify(Value epsilon = 0.0) const {
deba@459
   708
        const_cast<DualExpr*>(this)->simplify(epsilon);
deba@458
   709
      }
deba@458
   710
deba@458
   711
      ///Sets all coefficients to 0.
deba@458
   712
      void clear() {
deba@459
   713
        comps.clear();
deba@459
   714
      }
deba@459
   715
      ///Compound assignment
deba@459
   716
      DualExpr &operator+=(const DualExpr &e) {
deba@459
   717
        for (std::map<int, Value>::const_iterator it=e.comps.begin();
deba@459
   718
             it!=e.comps.end(); ++it)
deba@459
   719
          comps[it->first]+=it->second;
deba@459
   720
        return *this;
deba@459
   721
      }
deba@459
   722
      ///Compound assignment
deba@459
   723
      DualExpr &operator-=(const DualExpr &e) {
deba@459
   724
        for (std::map<int, Value>::const_iterator it=e.comps.begin();
deba@459
   725
             it!=e.comps.end(); ++it)
deba@459
   726
          comps[it->first]-=it->second;
deba@459
   727
        return *this;
deba@459
   728
      }
deba@459
   729
      ///Multiply with a constant
deba@459
   730
      DualExpr &operator*=(const Value &v) {
deba@459
   731
        for (std::map<int, Value>::iterator it=comps.begin();
deba@459
   732
             it!=comps.end(); ++it)
deba@459
   733
          it->second*=v;
deba@459
   734
        return *this;
deba@459
   735
      }
deba@459
   736
      ///Division with a constant
deba@459
   737
      DualExpr &operator/=(const Value &v) {
deba@459
   738
        for (std::map<int, Value>::iterator it=comps.begin();
deba@459
   739
             it!=comps.end(); ++it)
deba@459
   740
          it->second/=v;
deba@459
   741
        return *this;
deba@458
   742
      }
deba@458
   743
deba@459
   744
      ///Iterator over the expression
deba@459
   745
      
deba@459
   746
      ///The iterator iterates over the terms of the expression. 
deba@459
   747
      /// 
deba@459
   748
      ///\code
deba@459
   749
      ///double s=0;
deba@459
   750
      ///for(LpBase::DualExpr::CoeffIt i(e);i!=INVALID;++i)
deba@459
   751
      ///  s+= *i * dual(i);
deba@459
   752
      ///\endcode
deba@459
   753
      class CoeffIt {
deba@459
   754
      private:
deba@459
   755
deba@459
   756
        std::map<int, Value>::iterator _it, _end;
deba@459
   757
deba@459
   758
      public:
deba@459
   759
deba@459
   760
        /// Sets the iterator to the first term
deba@459
   761
        
deba@459
   762
        /// Sets the iterator to the first term of the expression.
deba@459
   763
        ///
deba@459
   764
        CoeffIt(DualExpr& e)
deba@459
   765
          : _it(e.comps.begin()), _end(e.comps.end()){}
deba@459
   766
deba@459
   767
        /// Convert the iterator to the row of the term
deba@459
   768
        operator Row() const {
deba@459
   769
          return rowFromId(_it->first);
deba@459
   770
        }
deba@459
   771
deba@459
   772
        /// Returns the coefficient of the term
deba@459
   773
        Value& operator*() { return _it->second; }
deba@459
   774
deba@459
   775
        /// Returns the coefficient of the term
deba@459
   776
        const Value& operator*() const { return _it->second; }
deba@459
   777
deba@459
   778
        /// Next term
deba@459
   779
        
deba@459
   780
        /// Assign the iterator to the next term.
deba@459
   781
        ///
deba@459
   782
        CoeffIt& operator++() { ++_it; return *this; }
deba@459
   783
deba@459
   784
        /// Equality operator
deba@459
   785
        bool operator==(Invalid) const { return _it == _end; }
deba@459
   786
        /// Inequality operator
deba@459
   787
        bool operator!=(Invalid) const { return _it != _end; }
deba@459
   788
      };
deba@459
   789
deba@459
   790
      ///Iterator over the expression
deba@459
   791
      
deba@459
   792
      ///The iterator iterates over the terms of the expression. 
deba@459
   793
      /// 
deba@459
   794
      ///\code
deba@459
   795
      ///double s=0;
deba@459
   796
      ///for(LpBase::DualExpr::ConstCoeffIt i(e);i!=INVALID;++i)
deba@459
   797
      ///  s+= *i * dual(i);
deba@459
   798
      ///\endcode
deba@459
   799
      class ConstCoeffIt {
deba@459
   800
      private:
deba@459
   801
deba@459
   802
        std::map<int, Value>::const_iterator _it, _end;
deba@459
   803
deba@459
   804
      public:
deba@459
   805
deba@459
   806
        /// Sets the iterator to the first term
deba@459
   807
        
deba@459
   808
        /// Sets the iterator to the first term of the expression.
deba@459
   809
        ///
deba@459
   810
        ConstCoeffIt(const DualExpr& e)
deba@459
   811
          : _it(e.comps.begin()), _end(e.comps.end()){}
deba@459
   812
deba@459
   813
        /// Convert the iterator to the row of the term
deba@459
   814
        operator Row() const {
deba@459
   815
          return rowFromId(_it->first);
deba@459
   816
        }
deba@459
   817
deba@459
   818
        /// Returns the coefficient of the term
deba@459
   819
        const Value& operator*() const { return _it->second; }
deba@459
   820
deba@459
   821
        /// Next term
deba@459
   822
        
deba@459
   823
        /// Assign the iterator to the next term.
deba@459
   824
        ///
deba@459
   825
        ConstCoeffIt& operator++() { ++_it; return *this; }
deba@459
   826
deba@459
   827
        /// Equality operator
deba@459
   828
        bool operator==(Invalid) const { return _it == _end; }
deba@459
   829
        /// Inequality operator
deba@459
   830
        bool operator!=(Invalid) const { return _it != _end; }
deba@459
   831
      };
deba@458
   832
    };
deba@458
   833
deba@458
   834
deba@459
   835
  protected:
deba@458
   836
deba@459
   837
    class InsertIterator {
deba@459
   838
    private:
deba@459
   839
deba@459
   840
      std::map<int, Value>& _host;
deba@459
   841
      const _solver_bits::VarIndex& _index;
deba@459
   842
deba@458
   843
    public:
deba@458
   844
deba@458
   845
      typedef std::output_iterator_tag iterator_category;
deba@458
   846
      typedef void difference_type;
deba@458
   847
      typedef void value_type;
deba@458
   848
      typedef void reference;
deba@458
   849
      typedef void pointer;
deba@458
   850
deba@459
   851
      InsertIterator(std::map<int, Value>& host,
deba@459
   852
                   const _solver_bits::VarIndex& index)
deba@459
   853
        : _host(host), _index(index) {}
deba@458
   854
deba@459
   855
      InsertIterator& operator=(const std::pair<int, Value>& value) {
deba@459
   856
        typedef std::map<int, Value>::value_type pair_type;
deba@459
   857
        _host.insert(pair_type(_index[value.first], value.second));
deba@458
   858
        return *this;
deba@458
   859
      }
deba@458
   860
deba@459
   861
      InsertIterator& operator*() { return *this; }
deba@459
   862
      InsertIterator& operator++() { return *this; }
deba@459
   863
      InsertIterator operator++(int) { return *this; }
deba@458
   864
deba@458
   865
    };
deba@458
   866
deba@459
   867
    class ExprIterator {
deba@459
   868
    private:
deba@459
   869
      std::map<int, Value>::const_iterator _host_it;
deba@459
   870
      const _solver_bits::VarIndex& _index;
deba@458
   871
    public:
deba@458
   872
deba@459
   873
      typedef std::bidirectional_iterator_tag iterator_category;
deba@459
   874
      typedef std::ptrdiff_t difference_type;
deba@458
   875
      typedef const std::pair<int, Value> value_type;
deba@458
   876
      typedef value_type reference;
deba@459
   877
deba@458
   878
      class pointer {
deba@458
   879
      public:
deba@458
   880
        pointer(value_type& _value) : value(_value) {}
deba@458
   881
        value_type* operator->() { return &value; }
deba@458
   882
      private:
deba@458
   883
        value_type value;
deba@458
   884
      };
deba@458
   885
deba@459
   886
      ExprIterator(const std::map<int, Value>::const_iterator& host_it,
deba@459
   887
                   const _solver_bits::VarIndex& index)
deba@459
   888
        : _host_it(host_it), _index(index) {}
deba@458
   889
deba@458
   890
      reference operator*() {
deba@459
   891
        return std::make_pair(_index(_host_it->first), _host_it->second);
deba@458
   892
      }
deba@458
   893
deba@458
   894
      pointer operator->() {
deba@458
   895
        return pointer(operator*());
deba@458
   896
      }
deba@458
   897
deba@459
   898
      ExprIterator& operator++() { ++_host_it; return *this; }
deba@459
   899
      ExprIterator operator++(int) {
deba@459
   900
        ExprIterator tmp(*this); ++_host_it; return tmp;
deba@458
   901
      }
deba@458
   902
deba@459
   903
      ExprIterator& operator--() { --_host_it; return *this; }
deba@459
   904
      ExprIterator operator--(int) {
deba@459
   905
        ExprIterator tmp(*this); --_host_it; return tmp;
deba@458
   906
      }
deba@458
   907
deba@459
   908
      bool operator==(const ExprIterator& it) const {
deba@459
   909
        return _host_it == it._host_it;
deba@458
   910
      }
deba@458
   911
deba@459
   912
      bool operator!=(const ExprIterator& it) const {
deba@459
   913
        return _host_it != it._host_it;
deba@458
   914
      }
deba@458
   915
deba@458
   916
    };
deba@458
   917
deba@458
   918
  protected:
deba@458
   919
deba@459
   920
    //Abstract virtual functions
deba@458
   921
deba@459
   922
    virtual int _addColId(int col) { return cols.addIndex(col); }
deba@459
   923
    virtual int _addRowId(int row) { return rows.addIndex(row); }
deba@458
   924
deba@459
   925
    virtual void _eraseColId(int col) { cols.eraseIndex(col); }
deba@459
   926
    virtual void _eraseRowId(int row) { rows.eraseIndex(row); }
deba@458
   927
deba@458
   928
    virtual int _addCol() = 0;
deba@458
   929
    virtual int _addRow() = 0;
deba@458
   930
deba@458
   931
    virtual void _eraseCol(int col) = 0;
deba@458
   932
    virtual void _eraseRow(int row) = 0;
deba@458
   933
deba@459
   934
    virtual void _getColName(int col, std::string& name) const = 0;
deba@459
   935
    virtual void _setColName(int col, const std::string& name) = 0;
deba@458
   936
    virtual int _colByName(const std::string& name) const = 0;
deba@458
   937
deba@459
   938
    virtual void _getRowName(int row, std::string& name) const = 0;
deba@459
   939
    virtual void _setRowName(int row, const std::string& name) = 0;
deba@459
   940
    virtual int _rowByName(const std::string& name) const = 0;
deba@459
   941
deba@459
   942
    virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e) = 0;
deba@459
   943
    virtual void _getRowCoeffs(int i, InsertIterator b) const = 0;
deba@459
   944
deba@459
   945
    virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e) = 0;
deba@459
   946
    virtual void _getColCoeffs(int i, InsertIterator b) const = 0;
deba@459
   947
deba@458
   948
    virtual void _setCoeff(int row, int col, Value value) = 0;
deba@458
   949
    virtual Value _getCoeff(int row, int col) const = 0;
deba@459
   950
deba@458
   951
    virtual void _setColLowerBound(int i, Value value) = 0;
deba@458
   952
    virtual Value _getColLowerBound(int i) const = 0;
deba@459
   953
deba@458
   954
    virtual void _setColUpperBound(int i, Value value) = 0;
deba@458
   955
    virtual Value _getColUpperBound(int i) const = 0;
deba@459
   956
deba@459
   957
    virtual void _setRowLowerBound(int i, Value value) = 0;
deba@459
   958
    virtual Value _getRowLowerBound(int i) const = 0;
deba@459
   959
deba@459
   960
    virtual void _setRowUpperBound(int i, Value value) = 0;
deba@459
   961
    virtual Value _getRowUpperBound(int i) const = 0;
deba@459
   962
deba@459
   963
    virtual void _setObjCoeffs(ExprIterator b, ExprIterator e) = 0;
deba@459
   964
    virtual void _getObjCoeffs(InsertIterator b) const = 0;
deba@458
   965
deba@458
   966
    virtual void _setObjCoeff(int i, Value obj_coef) = 0;
deba@458
   967
    virtual Value _getObjCoeff(int i) const = 0;
deba@458
   968
deba@459
   969
    virtual void _setSense(Sense) = 0;
deba@459
   970
    virtual Sense _getSense() const = 0;
deba@458
   971
deba@459
   972
    virtual void _clear() = 0;
deba@458
   973
deba@459
   974
    virtual const char* _solverName() const = 0;
deba@458
   975
deba@458
   976
    //Own protected stuff
deba@458
   977
deba@458
   978
    //Constant component of the objective function
deba@458
   979
    Value obj_const_comp;
deba@458
   980
deba@459
   981
    LpBase() : rows(), cols(), obj_const_comp(0) {}
deba@459
   982
deba@458
   983
  public:
deba@458
   984
deba@459
   985
    /// Virtual destructor
deba@459
   986
    virtual ~LpBase() {}
deba@458
   987
deba@459
   988
    ///Gives back the name of the solver.
deba@459
   989
    const char* solverName() const {return _solverName();}
deba@458
   990
deba@458
   991
    ///\name Build up and modify the LP
deba@458
   992
deba@458
   993
    ///@{
deba@458
   994
deba@458
   995
    ///Add a new empty column (i.e a new variable) to the LP
deba@459
   996
    Col addCol() { Col c; c._id = _addColId(_addCol()); return c;}
deba@458
   997
deba@459
   998
    ///\brief Adds several new columns (i.e variables) at once
deba@458
   999
    ///
deba@459
  1000
    ///This magic function takes a container as its argument and fills
deba@459
  1001
    ///its elements with new columns (i.e. variables)
deba@458
  1002
    ///\param t can be
deba@458
  1003
    ///- a standard STL compatible iterable container with
deba@459
  1004
    ///\ref Col as its \c values_type like
deba@458
  1005
    ///\code
deba@459
  1006
    ///std::vector<LpBase::Col>
deba@459
  1007
    ///std::list<LpBase::Col>
deba@458
  1008
    ///\endcode
deba@458
  1009
    ///- a standard STL compatible iterable container with
deba@459
  1010
    ///\ref Col as its \c mapped_type like
deba@458
  1011
    ///\code
deba@459
  1012
    ///std::map<AnyType,LpBase::Col>
deba@458
  1013
    ///\endcode
deba@458
  1014
    ///- an iterable lemon \ref concepts::WriteMap "write map" like
deba@458
  1015
    ///\code
deba@459
  1016
    ///ListGraph::NodeMap<LpBase::Col>
deba@459
  1017
    ///ListGraph::ArcMap<LpBase::Col>
deba@458
  1018
    ///\endcode
deba@458
  1019
    ///\return The number of the created column.
deba@458
  1020
#ifdef DOXYGEN
deba@458
  1021
    template<class T>
deba@458
  1022
    int addColSet(T &t) { return 0;}
deba@458
  1023
#else
deba@458
  1024
    template<class T>
deba@459
  1025
    typename enable_if<typename T::value_type::LpCol,int>::type
deba@458
  1026
    addColSet(T &t,dummy<0> = 0) {
deba@458
  1027
      int s=0;
deba@458
  1028
      for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
deba@458
  1029
      return s;
deba@458
  1030
    }
deba@458
  1031
    template<class T>
deba@459
  1032
    typename enable_if<typename T::value_type::second_type::LpCol,
deba@458
  1033
                       int>::type
deba@458
  1034
    addColSet(T &t,dummy<1> = 1) {
deba@458
  1035
      int s=0;
deba@458
  1036
      for(typename T::iterator i=t.begin();i!=t.end();++i) {
deba@458
  1037
        i->second=addCol();
deba@458
  1038
        s++;
deba@458
  1039
      }
deba@458
  1040
      return s;
deba@458
  1041
    }
deba@458
  1042
    template<class T>
deba@459
  1043
    typename enable_if<typename T::MapIt::Value::LpCol,
deba@458
  1044
                       int>::type
deba@458
  1045
    addColSet(T &t,dummy<2> = 2) {
deba@458
  1046
      int s=0;
deba@458
  1047
      for(typename T::MapIt i(t); i!=INVALID; ++i)
deba@458
  1048
        {
deba@458
  1049
          i.set(addCol());
deba@458
  1050
          s++;
deba@458
  1051
        }
deba@458
  1052
      return s;
deba@458
  1053
    }
deba@458
  1054
#endif
deba@458
  1055
deba@458
  1056
    ///Set a column (i.e a dual constraint) of the LP
deba@458
  1057
deba@458
  1058
    ///\param c is the column to be modified
deba@458
  1059
    ///\param e is a dual linear expression (see \ref DualExpr)
deba@458
  1060
    ///a better one.
deba@459
  1061
    void col(Col c, const DualExpr &e) {
deba@458
  1062
      e.simplify();
deba@471
  1063
      _setColCoeffs(cols(id(c)), ExprIterator(e.comps.begin(), rows),
deba@471
  1064
                    ExprIterator(e.comps.end(), rows));
deba@458
  1065
    }
deba@458
  1066
deba@458
  1067
    ///Get a column (i.e a dual constraint) of the LP
deba@458
  1068
deba@459
  1069
    ///\param c is the column to get
deba@458
  1070
    ///\return the dual expression associated to the column
deba@458
  1071
    DualExpr col(Col c) const {
deba@458
  1072
      DualExpr e;
deba@459
  1073
      _getColCoeffs(cols(id(c)), InsertIterator(e.comps, rows));
deba@458
  1074
      return e;
deba@458
  1075
    }
deba@458
  1076
deba@458
  1077
    ///Add a new column to the LP
deba@458
  1078
deba@458
  1079
    ///\param e is a dual linear expression (see \ref DualExpr)
deba@459
  1080
    ///\param o is the corresponding component of the objective
deba@458
  1081
    ///function. It is 0 by default.
deba@458
  1082
    ///\return The created column.
deba@458
  1083
    Col addCol(const DualExpr &e, Value o = 0) {
deba@458
  1084
      Col c=addCol();
deba@458
  1085
      col(c,e);
deba@458
  1086
      objCoeff(c,o);
deba@458
  1087
      return c;
deba@458
  1088
    }
deba@458
  1089
deba@458
  1090
    ///Add a new empty row (i.e a new constraint) to the LP
deba@458
  1091
deba@458
  1092
    ///This function adds a new empty row (i.e a new constraint) to the LP.
deba@458
  1093
    ///\return The created row
deba@459
  1094
    Row addRow() { Row r; r._id = _addRowId(_addRow()); return r;}
deba@458
  1095
deba@459
  1096
    ///\brief Add several new rows (i.e constraints) at once
deba@458
  1097
    ///
deba@459
  1098
    ///This magic function takes a container as its argument and fills
deba@459
  1099
    ///its elements with new row (i.e. variables)
deba@458
  1100
    ///\param t can be
deba@458
  1101
    ///- a standard STL compatible iterable container with
deba@459
  1102
    ///\ref Row as its \c values_type like
deba@458
  1103
    ///\code
deba@459
  1104
    ///std::vector<LpBase::Row>
deba@459
  1105
    ///std::list<LpBase::Row>
deba@458
  1106
    ///\endcode
deba@458
  1107
    ///- a standard STL compatible iterable container with
deba@459
  1108
    ///\ref Row as its \c mapped_type like
deba@458
  1109
    ///\code
deba@459
  1110
    ///std::map<AnyType,LpBase::Row>
deba@458
  1111
    ///\endcode
deba@458
  1112
    ///- an iterable lemon \ref concepts::WriteMap "write map" like
deba@458
  1113
    ///\code
deba@459
  1114
    ///ListGraph::NodeMap<LpBase::Row>
deba@459
  1115
    ///ListGraph::ArcMap<LpBase::Row>
deba@458
  1116
    ///\endcode
deba@458
  1117
    ///\return The number of rows created.
deba@458
  1118
#ifdef DOXYGEN
deba@458
  1119
    template<class T>
deba@458
  1120
    int addRowSet(T &t) { return 0;}
deba@458
  1121
#else
deba@458
  1122
    template<class T>
deba@459
  1123
    typename enable_if<typename T::value_type::LpRow,int>::type
deba@459
  1124
    addRowSet(T &t, dummy<0> = 0) {
deba@458
  1125
      int s=0;
deba@458
  1126
      for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addRow();s++;}
deba@458
  1127
      return s;
deba@458
  1128
    }
deba@458
  1129
    template<class T>
deba@459
  1130
    typename enable_if<typename T::value_type::second_type::LpRow, int>::type
deba@459
  1131
    addRowSet(T &t, dummy<1> = 1) {
deba@458
  1132
      int s=0;
deba@458
  1133
      for(typename T::iterator i=t.begin();i!=t.end();++i) {
deba@458
  1134
        i->second=addRow();
deba@458
  1135
        s++;
deba@458
  1136
      }
deba@458
  1137
      return s;
deba@458
  1138
    }
deba@458
  1139
    template<class T>
deba@459
  1140
    typename enable_if<typename T::MapIt::Value::LpRow, int>::type
deba@459
  1141
    addRowSet(T &t, dummy<2> = 2) {
deba@458
  1142
      int s=0;
deba@458
  1143
      for(typename T::MapIt i(t); i!=INVALID; ++i)
deba@458
  1144
        {
deba@458
  1145
          i.set(addRow());
deba@458
  1146
          s++;
deba@458
  1147
        }
deba@458
  1148
      return s;
deba@458
  1149
    }
deba@458
  1150
#endif
deba@458
  1151
deba@458
  1152
    ///Set a row (i.e a constraint) of the LP
deba@458
  1153
deba@458
  1154
    ///\param r is the row to be modified
deba@458
  1155
    ///\param l is lower bound (-\ref INF means no bound)
deba@458
  1156
    ///\param e is a linear expression (see \ref Expr)
deba@458
  1157
    ///\param u is the upper bound (\ref INF means no bound)
deba@458
  1158
    void row(Row r, Value l, const Expr &e, Value u) {
deba@458
  1159
      e.simplify();
deba@459
  1160
      _setRowCoeffs(rows(id(r)), ExprIterator(e.comps.begin(), cols),
deba@459
  1161
                    ExprIterator(e.comps.end(), cols));
deba@459
  1162
      _setRowLowerBound(rows(id(r)),l - *e);
deba@459
  1163
      _setRowUpperBound(rows(id(r)),u - *e);
deba@458
  1164
    }
deba@458
  1165
deba@458
  1166
    ///Set a row (i.e a constraint) of the LP
deba@458
  1167
deba@458
  1168
    ///\param r is the row to be modified
deba@458
  1169
    ///\param c is a linear expression (see \ref Constr)
deba@458
  1170
    void row(Row r, const Constr &c) {
deba@458
  1171
      row(r, c.lowerBounded()?c.lowerBound():-INF,
deba@458
  1172
          c.expr(), c.upperBounded()?c.upperBound():INF);
deba@458
  1173
    }
deba@458
  1174
deba@458
  1175
deba@458
  1176
    ///Get a row (i.e a constraint) of the LP
deba@458
  1177
deba@458
  1178
    ///\param r is the row to get
deba@458
  1179
    ///\return the expression associated to the row
deba@458
  1180
    Expr row(Row r) const {
deba@458
  1181
      Expr e;
deba@459
  1182
      _getRowCoeffs(rows(id(r)), InsertIterator(e.comps, cols));
deba@458
  1183
      return e;
deba@458
  1184
    }
deba@458
  1185
deba@458
  1186
    ///Add a new row (i.e a new constraint) to the LP
deba@458
  1187
deba@458
  1188
    ///\param l is the lower bound (-\ref INF means no bound)
deba@458
  1189
    ///\param e is a linear expression (see \ref Expr)
deba@458
  1190
    ///\param u is the upper bound (\ref INF means no bound)
deba@458
  1191
    ///\return The created row.
deba@458
  1192
    Row addRow(Value l,const Expr &e, Value u) {
deba@458
  1193
      Row r=addRow();
deba@458
  1194
      row(r,l,e,u);
deba@458
  1195
      return r;
deba@458
  1196
    }
deba@458
  1197
deba@458
  1198
    ///Add a new row (i.e a new constraint) to the LP
deba@458
  1199
deba@458
  1200
    ///\param c is a linear expression (see \ref Constr)
deba@458
  1201
    ///\return The created row.
deba@458
  1202
    Row addRow(const Constr &c) {
deba@458
  1203
      Row r=addRow();
deba@458
  1204
      row(r,c);
deba@458
  1205
      return r;
deba@458
  1206
    }
deba@459
  1207
    ///Erase a column (i.e a variable) from the LP
deba@458
  1208
deba@459
  1209
    ///\param c is the column to be deleted
deba@459
  1210
    void erase(Col c) {
deba@459
  1211
      _eraseCol(cols(id(c)));
deba@459
  1212
      _eraseColId(cols(id(c)));
deba@458
  1213
    }
deba@459
  1214
    ///Erase a row (i.e a constraint) from the LP
deba@458
  1215
deba@458
  1216
    ///\param r is the row to be deleted
deba@459
  1217
    void erase(Row r) {
deba@459
  1218
      _eraseRow(rows(id(r)));
deba@459
  1219
      _eraseRowId(rows(id(r)));
deba@458
  1220
    }
deba@458
  1221
deba@458
  1222
    /// Get the name of a column
deba@458
  1223
deba@459
  1224
    ///\param c is the coresponding column
deba@458
  1225
    ///\return The name of the colunm
deba@458
  1226
    std::string colName(Col c) const {
deba@458
  1227
      std::string name;
deba@459
  1228
      _getColName(cols(id(c)), name);
deba@458
  1229
      return name;
deba@458
  1230
    }
deba@458
  1231
deba@458
  1232
    /// Set the name of a column
deba@458
  1233
deba@459
  1234
    ///\param c is the coresponding column
deba@458
  1235
    ///\param name The name to be given
deba@458
  1236
    void colName(Col c, const std::string& name) {
deba@459
  1237
      _setColName(cols(id(c)), name);
deba@458
  1238
    }
deba@458
  1239
deba@458
  1240
    /// Get the column by its name
deba@458
  1241
deba@458
  1242
    ///\param name The name of the column
deba@458
  1243
    ///\return the proper column or \c INVALID
deba@458
  1244
    Col colByName(const std::string& name) const {
deba@458
  1245
      int k = _colByName(name);
deba@459
  1246
      return k != -1 ? Col(cols[k]) : Col(INVALID);
deba@459
  1247
    }
deba@459
  1248
deba@459
  1249
    /// Get the name of a row
deba@459
  1250
deba@459
  1251
    ///\param r is the coresponding row
deba@459
  1252
    ///\return The name of the row
deba@459
  1253
    std::string rowName(Row r) const {
deba@459
  1254
      std::string name;
deba@459
  1255
      _getRowName(rows(id(r)), name);
deba@459
  1256
      return name;
deba@459
  1257
    }
deba@459
  1258
deba@459
  1259
    /// Set the name of a row
deba@459
  1260
deba@459
  1261
    ///\param r is the coresponding row
deba@459
  1262
    ///\param name The name to be given
deba@459
  1263
    void rowName(Row r, const std::string& name) {
deba@459
  1264
      _setRowName(rows(id(r)), name);
deba@459
  1265
    }
deba@459
  1266
deba@459
  1267
    /// Get the row by its name
deba@459
  1268
deba@459
  1269
    ///\param name The name of the row
deba@459
  1270
    ///\return the proper row or \c INVALID
deba@459
  1271
    Row rowByName(const std::string& name) const {
deba@459
  1272
      int k = _rowByName(name);
deba@459
  1273
      return k != -1 ? Row(rows[k]) : Row(INVALID);
deba@458
  1274
    }
deba@458
  1275
deba@458
  1276
    /// Set an element of the coefficient matrix of the LP
deba@458
  1277
deba@458
  1278
    ///\param r is the row of the element to be modified
deba@459
  1279
    ///\param c is the column of the element to be modified
deba@458
  1280
    ///\param val is the new value of the coefficient
deba@458
  1281
    void coeff(Row r, Col c, Value val) {
deba@459
  1282
      _setCoeff(rows(id(r)),cols(id(c)), val);
deba@458
  1283
    }
deba@458
  1284
deba@458
  1285
    /// Get an element of the coefficient matrix of the LP
deba@458
  1286
deba@459
  1287
    ///\param r is the row of the element
deba@459
  1288
    ///\param c is the column of the element
deba@458
  1289
    ///\return the corresponding coefficient
deba@458
  1290
    Value coeff(Row r, Col c) const {
deba@459
  1291
      return _getCoeff(rows(id(r)),cols(id(c)));
deba@458
  1292
    }
deba@458
  1293
deba@458
  1294
    /// Set the lower bound of a column (i.e a variable)
deba@458
  1295
deba@458
  1296
    /// The lower bound of a variable (column) has to be given by an
deba@458
  1297
    /// extended number of type Value, i.e. a finite number of type
deba@458
  1298
    /// Value or -\ref INF.
deba@458
  1299
    void colLowerBound(Col c, Value value) {
deba@459
  1300
      _setColLowerBound(cols(id(c)),value);
deba@458
  1301
    }
deba@458
  1302
deba@458
  1303
    /// Get the lower bound of a column (i.e a variable)
deba@458
  1304
deba@459
  1305
    /// This function returns the lower bound for column (variable) \c c
deba@458
  1306
    /// (this might be -\ref INF as well).
deba@459
  1307
    ///\return The lower bound for column \c c
deba@458
  1308
    Value colLowerBound(Col c) const {
deba@459
  1309
      return _getColLowerBound(cols(id(c)));
deba@458
  1310
    }
deba@458
  1311
deba@458
  1312
    ///\brief Set the lower bound of  several columns
deba@459
  1313
    ///(i.e variables) at once
deba@458
  1314
    ///
deba@458
  1315
    ///This magic function takes a container as its argument
deba@458
  1316
    ///and applies the function on all of its elements.
deba@459
  1317
    ///The lower bound of a variable (column) has to be given by an
deba@459
  1318
    ///extended number of type Value, i.e. a finite number of type
deba@459
  1319
    ///Value or -\ref INF.
deba@458
  1320
#ifdef DOXYGEN
deba@458
  1321
    template<class T>
deba@458
  1322
    void colLowerBound(T &t, Value value) { return 0;}
deba@458
  1323
#else
deba@458
  1324
    template<class T>
deba@459
  1325
    typename enable_if<typename T::value_type::LpCol,void>::type
deba@458
  1326
    colLowerBound(T &t, Value value,dummy<0> = 0) {
deba@458
  1327
      for(typename T::iterator i=t.begin();i!=t.end();++i) {
deba@458
  1328
        colLowerBound(*i, value);
deba@458
  1329
      }
deba@458
  1330
    }
deba@458
  1331
    template<class T>
deba@459
  1332
    typename enable_if<typename T::value_type::second_type::LpCol,
deba@458
  1333
                       void>::type
deba@458
  1334
    colLowerBound(T &t, Value value,dummy<1> = 1) {
deba@458
  1335
      for(typename T::iterator i=t.begin();i!=t.end();++i) {
deba@458
  1336
        colLowerBound(i->second, value);
deba@458
  1337
      }
deba@458
  1338
    }
deba@458
  1339
    template<class T>
deba@459
  1340
    typename enable_if<typename T::MapIt::Value::LpCol,
deba@458
  1341
                       void>::type
deba@458
  1342
    colLowerBound(T &t, Value value,dummy<2> = 2) {
deba@458
  1343
      for(typename T::MapIt i(t); i!=INVALID; ++i){
deba@458
  1344
        colLowerBound(*i, value);
deba@458
  1345
      }
deba@458
  1346
    }
deba@458
  1347
#endif
deba@458
  1348
deba@458
  1349
    /// Set the upper bound of a column (i.e a variable)
deba@458
  1350
deba@458
  1351
    /// The upper bound of a variable (column) has to be given by an
deba@458
  1352
    /// extended number of type Value, i.e. a finite number of type
deba@458
  1353
    /// Value or \ref INF.
deba@458
  1354
    void colUpperBound(Col c, Value value) {
deba@459
  1355
      _setColUpperBound(cols(id(c)),value);
deba@458
  1356
    };
deba@458
  1357
deba@458
  1358
    /// Get the upper bound of a column (i.e a variable)
deba@458
  1359
deba@459
  1360
    /// This function returns the upper bound for column (variable) \c c
deba@458
  1361
    /// (this might be \ref INF as well).
deba@459
  1362
    /// \return The upper bound for column \c c
deba@458
  1363
    Value colUpperBound(Col c) const {
deba@459
  1364
      return _getColUpperBound(cols(id(c)));
deba@458
  1365
    }
deba@458
  1366
deba@458
  1367
    ///\brief Set the upper bound of  several columns
deba@459
  1368
    ///(i.e variables) at once
deba@458
  1369
    ///
deba@458
  1370
    ///This magic function takes a container as its argument
deba@458
  1371
    ///and applies the function on all of its elements.
deba@459
  1372
    ///The upper bound of a variable (column) has to be given by an
deba@459
  1373
    ///extended number of type Value, i.e. a finite number of type
deba@459
  1374
    ///Value or \ref INF.
deba@458
  1375
#ifdef DOXYGEN
deba@458
  1376
    template<class T>
deba@458
  1377
    void colUpperBound(T &t, Value value) { return 0;}
deba@458
  1378
#else
tapolcai@514
  1379
    template<class T1>
tapolcai@514
  1380
    typename enable_if<typename T1::value_type::LpCol,void>::type
tapolcai@514
  1381
    colUpperBound(T1 &t, Value value,dummy<0> = 0) {
tapolcai@514
  1382
      for(typename T1::iterator i=t.begin();i!=t.end();++i) {
deba@458
  1383
        colUpperBound(*i, value);
deba@458
  1384
      }
deba@458
  1385
    }
tapolcai@514
  1386
    template<class T1>
tapolcai@514
  1387
    typename enable_if<typename T1::value_type::second_type::LpCol,
deba@458
  1388
                       void>::type
tapolcai@514
  1389
    colUpperBound(T1 &t, Value value,dummy<1> = 1) {
tapolcai@514
  1390
      for(typename T1::iterator i=t.begin();i!=t.end();++i) {
deba@458
  1391
        colUpperBound(i->second, value);
deba@458
  1392
      }
deba@458
  1393
    }
tapolcai@514
  1394
    template<class T1>
tapolcai@514
  1395
    typename enable_if<typename T1::MapIt::Value::LpCol,
deba@458
  1396
                       void>::type
tapolcai@514
  1397
    colUpperBound(T1 &t, Value value,dummy<2> = 2) {
tapolcai@514
  1398
      for(typename T1::MapIt i(t); i!=INVALID; ++i){
deba@458
  1399
        colUpperBound(*i, value);
deba@458
  1400
      }
deba@458
  1401
    }
deba@458
  1402
#endif
deba@458
  1403
deba@458
  1404
    /// Set the lower and the upper bounds of a column (i.e a variable)
deba@458
  1405
deba@458
  1406
    /// The lower and the upper bounds of
deba@458
  1407
    /// a variable (column) have to be given by an
deba@458
  1408
    /// extended number of type Value, i.e. a finite number of type
deba@458
  1409
    /// Value, -\ref INF or \ref INF.
deba@458
  1410
    void colBounds(Col c, Value lower, Value upper) {
deba@459
  1411
      _setColLowerBound(cols(id(c)),lower);
deba@459
  1412
      _setColUpperBound(cols(id(c)),upper);
deba@458
  1413
    }
deba@458
  1414
deba@458
  1415
    ///\brief Set the lower and the upper bound of several columns
deba@459
  1416
    ///(i.e variables) at once
deba@458
  1417
    ///
deba@458
  1418
    ///This magic function takes a container as its argument
deba@458
  1419
    ///and applies the function on all of its elements.
deba@458
  1420
    /// The lower and the upper bounds of
deba@458
  1421
    /// a variable (column) have to be given by an
deba@458
  1422
    /// extended number of type Value, i.e. a finite number of type
deba@458
  1423
    /// Value, -\ref INF or \ref INF.
deba@458
  1424
#ifdef DOXYGEN
deba@458
  1425
    template<class T>
deba@458
  1426
    void colBounds(T &t, Value lower, Value upper) { return 0;}
deba@458
  1427
#else
tapolcai@514
  1428
    template<class T2>
tapolcai@514
  1429
    typename enable_if<typename T2::value_type::LpCol,void>::type
tapolcai@514
  1430
    colBounds(T2 &t, Value lower, Value upper,dummy<0> = 0) {
tapolcai@514
  1431
      for(typename T2::iterator i=t.begin();i!=t.end();++i) {
deba@458
  1432
        colBounds(*i, lower, upper);
deba@458
  1433
      }
deba@458
  1434
    }
tapolcai@514
  1435
    template<class T2>
tapolcai@514
  1436
    typename enable_if<typename T2::value_type::second_type::LpCol, void>::type
tapolcai@514
  1437
    colBounds(T2 &t, Value lower, Value upper,dummy<1> = 1) {
tapolcai@514
  1438
      for(typename T2::iterator i=t.begin();i!=t.end();++i) {
deba@458
  1439
        colBounds(i->second, lower, upper);
deba@458
  1440
      }
deba@458
  1441
    }
tapolcai@514
  1442
    template<class T2>
tapolcai@514
  1443
    typename enable_if<typename T2::MapIt::Value::LpCol, void>::type
tapolcai@514
  1444
    colBounds(T2 &t, Value lower, Value upper,dummy<2> = 2) {
tapolcai@514
  1445
      for(typename T2::MapIt i(t); i!=INVALID; ++i){
deba@458
  1446
        colBounds(*i, lower, upper);
deba@458
  1447
      }
deba@458
  1448
    }
deba@458
  1449
#endif
deba@458
  1450
deba@459
  1451
    /// Set the lower bound of a row (i.e a constraint)
deba@458
  1452
deba@459
  1453
    /// The lower bound of a constraint (row) has to be given by an
deba@459
  1454
    /// extended number of type Value, i.e. a finite number of type
deba@459
  1455
    /// Value or -\ref INF.
deba@459
  1456
    void rowLowerBound(Row r, Value value) {
deba@459
  1457
      _setRowLowerBound(rows(id(r)),value);
deba@458
  1458
    }
deba@458
  1459
deba@459
  1460
    /// Get the lower bound of a row (i.e a constraint)
deba@458
  1461
deba@459
  1462
    /// This function returns the lower bound for row (constraint) \c c
deba@459
  1463
    /// (this might be -\ref INF as well).
deba@459
  1464
    ///\return The lower bound for row \c r
deba@459
  1465
    Value rowLowerBound(Row r) const {
deba@459
  1466
      return _getRowLowerBound(rows(id(r)));
deba@459
  1467
    }
deba@459
  1468
deba@459
  1469
    /// Set the upper bound of a row (i.e a constraint)
deba@459
  1470
deba@459
  1471
    /// The upper bound of a constraint (row) has to be given by an
deba@459
  1472
    /// extended number of type Value, i.e. a finite number of type
deba@459
  1473
    /// Value or -\ref INF.
deba@459
  1474
    void rowUpperBound(Row r, Value value) {
deba@459
  1475
      _setRowUpperBound(rows(id(r)),value);
deba@459
  1476
    }
deba@459
  1477
deba@459
  1478
    /// Get the upper bound of a row (i.e a constraint)
deba@459
  1479
deba@459
  1480
    /// This function returns the upper bound for row (constraint) \c c
deba@459
  1481
    /// (this might be -\ref INF as well).
deba@459
  1482
    ///\return The upper bound for row \c r
deba@459
  1483
    Value rowUpperBound(Row r) const {
deba@459
  1484
      return _getRowUpperBound(rows(id(r)));
deba@458
  1485
    }
deba@458
  1486
deba@458
  1487
    ///Set an element of the objective function
deba@459
  1488
    void objCoeff(Col c, Value v) {_setObjCoeff(cols(id(c)),v); };
deba@458
  1489
deba@458
  1490
    ///Get an element of the objective function
deba@459
  1491
    Value objCoeff(Col c) const { return _getObjCoeff(cols(id(c))); };
deba@458
  1492
deba@458
  1493
    ///Set the objective function
deba@458
  1494
deba@458
  1495
    ///\param e is a linear expression of type \ref Expr.
deba@459
  1496
    ///
deba@459
  1497
    void obj(const Expr& e) {
deba@459
  1498
      _setObjCoeffs(ExprIterator(e.comps.begin(), cols),
deba@459
  1499
                    ExprIterator(e.comps.end(), cols));
deba@459
  1500
      obj_const_comp = *e;
deba@458
  1501
    }
deba@458
  1502
deba@458
  1503
    ///Get the objective function
deba@458
  1504
deba@459
  1505
    ///\return the objective function as a linear expression of type
deba@459
  1506
    ///Expr.
deba@458
  1507
    Expr obj() const {
deba@458
  1508
      Expr e;
deba@459
  1509
      _getObjCoeffs(InsertIterator(e.comps, cols));
deba@459
  1510
      *e = obj_const_comp;
deba@458
  1511
      return e;
deba@458
  1512
    }
deba@458
  1513
deba@458
  1514
deba@459
  1515
    ///Set the direction of optimization
deba@459
  1516
    void sense(Sense sense) { _setSense(sense); }
deba@458
  1517
deba@459
  1518
    ///Query the direction of the optimization
deba@459
  1519
    Sense sense() const {return _getSense(); }
deba@458
  1520
deba@459
  1521
    ///Set the sense to maximization
deba@459
  1522
    void max() { _setSense(MAX); }
deba@459
  1523
deba@459
  1524
    ///Set the sense to maximization
deba@459
  1525
    void min() { _setSense(MIN); }
deba@459
  1526
deba@459
  1527
    ///Clears the problem
deba@459
  1528
    void clear() { _clear(); }
deba@458
  1529
deba@458
  1530
    ///@}
deba@458
  1531
deba@459
  1532
  };
deba@459
  1533
deba@459
  1534
  /// Addition
deba@459
  1535
deba@459
  1536
  ///\relates LpBase::Expr
deba@459
  1537
  ///
deba@459
  1538
  inline LpBase::Expr operator+(const LpBase::Expr &a, const LpBase::Expr &b) {
deba@459
  1539
    LpBase::Expr tmp(a);
deba@459
  1540
    tmp+=b;
deba@459
  1541
    return tmp;
deba@459
  1542
  }
deba@459
  1543
  ///Substraction
deba@459
  1544
deba@459
  1545
  ///\relates LpBase::Expr
deba@459
  1546
  ///
deba@459
  1547
  inline LpBase::Expr operator-(const LpBase::Expr &a, const LpBase::Expr &b) {
deba@459
  1548
    LpBase::Expr tmp(a);
deba@459
  1549
    tmp-=b;
deba@459
  1550
    return tmp;
deba@459
  1551
  }
deba@459
  1552
  ///Multiply with constant
deba@459
  1553
deba@459
  1554
  ///\relates LpBase::Expr
deba@459
  1555
  ///
deba@459
  1556
  inline LpBase::Expr operator*(const LpBase::Expr &a, const LpBase::Value &b) {
deba@459
  1557
    LpBase::Expr tmp(a);
deba@459
  1558
    tmp*=b;
deba@459
  1559
    return tmp;
deba@459
  1560
  }
deba@459
  1561
deba@459
  1562
  ///Multiply with constant
deba@459
  1563
deba@459
  1564
  ///\relates LpBase::Expr
deba@459
  1565
  ///
deba@459
  1566
  inline LpBase::Expr operator*(const LpBase::Value &a, const LpBase::Expr &b) {
deba@459
  1567
    LpBase::Expr tmp(b);
deba@459
  1568
    tmp*=a;
deba@459
  1569
    return tmp;
deba@459
  1570
  }
deba@459
  1571
  ///Divide with constant
deba@459
  1572
deba@459
  1573
  ///\relates LpBase::Expr
deba@459
  1574
  ///
deba@459
  1575
  inline LpBase::Expr operator/(const LpBase::Expr &a, const LpBase::Value &b) {
deba@459
  1576
    LpBase::Expr tmp(a);
deba@459
  1577
    tmp/=b;
deba@459
  1578
    return tmp;
deba@459
  1579
  }
deba@459
  1580
deba@459
  1581
  ///Create constraint
deba@459
  1582
deba@459
  1583
  ///\relates LpBase::Constr
deba@459
  1584
  ///
deba@459
  1585
  inline LpBase::Constr operator<=(const LpBase::Expr &e,
deba@459
  1586
                                   const LpBase::Expr &f) {
deba@459
  1587
    return LpBase::Constr(0, f - e, LpBase::INF);
deba@459
  1588
  }
deba@459
  1589
deba@459
  1590
  ///Create constraint
deba@459
  1591
deba@459
  1592
  ///\relates LpBase::Constr
deba@459
  1593
  ///
deba@459
  1594
  inline LpBase::Constr operator<=(const LpBase::Value &e,
deba@459
  1595
                                   const LpBase::Expr &f) {
deba@459
  1596
    return LpBase::Constr(e, f, LpBase::NaN);
deba@459
  1597
  }
deba@459
  1598
deba@459
  1599
  ///Create constraint
deba@459
  1600
deba@459
  1601
  ///\relates LpBase::Constr
deba@459
  1602
  ///
deba@459
  1603
  inline LpBase::Constr operator<=(const LpBase::Expr &e,
deba@459
  1604
                                   const LpBase::Value &f) {
deba@459
  1605
    return LpBase::Constr(- LpBase::INF, e, f);
deba@459
  1606
  }
deba@459
  1607
deba@459
  1608
  ///Create constraint
deba@459
  1609
deba@459
  1610
  ///\relates LpBase::Constr
deba@459
  1611
  ///
deba@459
  1612
  inline LpBase::Constr operator>=(const LpBase::Expr &e,
deba@459
  1613
                                   const LpBase::Expr &f) {
deba@459
  1614
    return LpBase::Constr(0, e - f, LpBase::INF);
deba@459
  1615
  }
deba@459
  1616
deba@459
  1617
deba@459
  1618
  ///Create constraint
deba@459
  1619
deba@459
  1620
  ///\relates LpBase::Constr
deba@459
  1621
  ///
deba@459
  1622
  inline LpBase::Constr operator>=(const LpBase::Value &e,
deba@459
  1623
                                   const LpBase::Expr &f) {
deba@459
  1624
    return LpBase::Constr(LpBase::NaN, f, e);
deba@459
  1625
  }
deba@459
  1626
deba@459
  1627
deba@459
  1628
  ///Create constraint
deba@459
  1629
deba@459
  1630
  ///\relates LpBase::Constr
deba@459
  1631
  ///
deba@459
  1632
  inline LpBase::Constr operator>=(const LpBase::Expr &e,
deba@459
  1633
                                   const LpBase::Value &f) {
deba@459
  1634
    return LpBase::Constr(f, e, LpBase::INF);
deba@459
  1635
  }
deba@459
  1636
deba@459
  1637
  ///Create constraint
deba@459
  1638
deba@459
  1639
  ///\relates LpBase::Constr
deba@459
  1640
  ///
deba@459
  1641
  inline LpBase::Constr operator==(const LpBase::Expr &e,
deba@459
  1642
                                   const LpBase::Value &f) {
deba@459
  1643
    return LpBase::Constr(f, e, f);
deba@459
  1644
  }
deba@459
  1645
deba@459
  1646
  ///Create constraint
deba@459
  1647
deba@459
  1648
  ///\relates LpBase::Constr
deba@459
  1649
  ///
deba@459
  1650
  inline LpBase::Constr operator==(const LpBase::Expr &e,
deba@459
  1651
                                   const LpBase::Expr &f) {
deba@459
  1652
    return LpBase::Constr(0, f - e, 0);
deba@459
  1653
  }
deba@459
  1654
deba@459
  1655
  ///Create constraint
deba@459
  1656
deba@459
  1657
  ///\relates LpBase::Constr
deba@459
  1658
  ///
deba@459
  1659
  inline LpBase::Constr operator<=(const LpBase::Value &n,
deba@459
  1660
                                   const LpBase::Constr &c) {
deba@459
  1661
    LpBase::Constr tmp(c);
alpar@511
  1662
    LEMON_ASSERT(isNaN(tmp.lowerBound()), "Wrong LP constraint");
deba@459
  1663
    tmp.lowerBound()=n;
deba@459
  1664
    return tmp;
deba@459
  1665
  }
deba@459
  1666
  ///Create constraint
deba@459
  1667
deba@459
  1668
  ///\relates LpBase::Constr
deba@459
  1669
  ///
deba@459
  1670
  inline LpBase::Constr operator<=(const LpBase::Constr &c,
deba@459
  1671
                                   const LpBase::Value &n)
deba@459
  1672
  {
deba@459
  1673
    LpBase::Constr tmp(c);
alpar@511
  1674
    LEMON_ASSERT(isNaN(tmp.upperBound()), "Wrong LP constraint");
deba@459
  1675
    tmp.upperBound()=n;
deba@459
  1676
    return tmp;
deba@459
  1677
  }
deba@459
  1678
deba@459
  1679
  ///Create constraint
deba@459
  1680
deba@459
  1681
  ///\relates LpBase::Constr
deba@459
  1682
  ///
deba@459
  1683
  inline LpBase::Constr operator>=(const LpBase::Value &n,
deba@459
  1684
                                   const LpBase::Constr &c) {
deba@459
  1685
    LpBase::Constr tmp(c);
alpar@511
  1686
    LEMON_ASSERT(isNaN(tmp.upperBound()), "Wrong LP constraint");
deba@459
  1687
    tmp.upperBound()=n;
deba@459
  1688
    return tmp;
deba@459
  1689
  }
deba@459
  1690
  ///Create constraint
deba@459
  1691
deba@459
  1692
  ///\relates LpBase::Constr
deba@459
  1693
  ///
deba@459
  1694
  inline LpBase::Constr operator>=(const LpBase::Constr &c,
deba@459
  1695
                                   const LpBase::Value &n)
deba@459
  1696
  {
deba@459
  1697
    LpBase::Constr tmp(c);
alpar@511
  1698
    LEMON_ASSERT(isNaN(tmp.lowerBound()), "Wrong LP constraint");
deba@459
  1699
    tmp.lowerBound()=n;
deba@459
  1700
    return tmp;
deba@459
  1701
  }
deba@459
  1702
deba@459
  1703
  ///Addition
deba@459
  1704
deba@459
  1705
  ///\relates LpBase::DualExpr
deba@459
  1706
  ///
deba@459
  1707
  inline LpBase::DualExpr operator+(const LpBase::DualExpr &a,
deba@459
  1708
                                    const LpBase::DualExpr &b) {
deba@459
  1709
    LpBase::DualExpr tmp(a);
deba@459
  1710
    tmp+=b;
deba@459
  1711
    return tmp;
deba@459
  1712
  }
deba@459
  1713
  ///Substraction
deba@459
  1714
deba@459
  1715
  ///\relates LpBase::DualExpr
deba@459
  1716
  ///
deba@459
  1717
  inline LpBase::DualExpr operator-(const LpBase::DualExpr &a,
deba@459
  1718
                                    const LpBase::DualExpr &b) {
deba@459
  1719
    LpBase::DualExpr tmp(a);
deba@459
  1720
    tmp-=b;
deba@459
  1721
    return tmp;
deba@459
  1722
  }
deba@459
  1723
  ///Multiply with constant
deba@459
  1724
deba@459
  1725
  ///\relates LpBase::DualExpr
deba@459
  1726
  ///
deba@459
  1727
  inline LpBase::DualExpr operator*(const LpBase::DualExpr &a,
deba@459
  1728
                                    const LpBase::Value &b) {
deba@459
  1729
    LpBase::DualExpr tmp(a);
deba@459
  1730
    tmp*=b;
deba@459
  1731
    return tmp;
deba@459
  1732
  }
deba@459
  1733
deba@459
  1734
  ///Multiply with constant
deba@459
  1735
deba@459
  1736
  ///\relates LpBase::DualExpr
deba@459
  1737
  ///
deba@459
  1738
  inline LpBase::DualExpr operator*(const LpBase::Value &a,
deba@459
  1739
                                    const LpBase::DualExpr &b) {
deba@459
  1740
    LpBase::DualExpr tmp(b);
deba@459
  1741
    tmp*=a;
deba@459
  1742
    return tmp;
deba@459
  1743
  }
deba@459
  1744
  ///Divide with constant
deba@459
  1745
deba@459
  1746
  ///\relates LpBase::DualExpr
deba@459
  1747
  ///
deba@459
  1748
  inline LpBase::DualExpr operator/(const LpBase::DualExpr &a,
deba@459
  1749
                                    const LpBase::Value &b) {
deba@459
  1750
    LpBase::DualExpr tmp(a);
deba@459
  1751
    tmp/=b;
deba@459
  1752
    return tmp;
deba@459
  1753
  }
deba@459
  1754
deba@459
  1755
  /// \ingroup lp_group
deba@459
  1756
  ///
deba@459
  1757
  /// \brief Common base class for LP solvers
deba@459
  1758
  ///
deba@459
  1759
  /// This class is an abstract base class for LP solvers. This class
deba@459
  1760
  /// provides a full interface for set and modify an LP problem,
deba@459
  1761
  /// solve it and retrieve the solution. You can use one of the
deba@459
  1762
  /// descendants as a concrete implementation, or the \c Lp
deba@459
  1763
  /// default LP solver. However, if you would like to handle LP
deba@459
  1764
  /// solvers as reference or pointer in a generic way, you can use
deba@459
  1765
  /// this class directly.
deba@459
  1766
  class LpSolver : virtual public LpBase {
deba@459
  1767
  public:
deba@459
  1768
deba@459
  1769
    /// The problem types for primal and dual problems
deba@459
  1770
    enum ProblemType {
deba@459
  1771
      ///Feasible solution hasn't been found (but may exist).
deba@459
  1772
      UNDEFINED = 0,
deba@459
  1773
      ///The problem has no feasible solution
deba@459
  1774
      INFEASIBLE = 1,
deba@459
  1775
      ///Feasible solution found
deba@459
  1776
      FEASIBLE = 2,
deba@459
  1777
      ///Optimal solution exists and found
deba@459
  1778
      OPTIMAL = 3,
deba@459
  1779
      ///The cost function is unbounded
deba@459
  1780
      UNBOUNDED = 4
deba@459
  1781
    };
deba@459
  1782
deba@459
  1783
    ///The basis status of variables
deba@459
  1784
    enum VarStatus {
deba@459
  1785
      /// The variable is in the basis
deba@459
  1786
      BASIC, 
deba@459
  1787
      /// The variable is free, but not basic
deba@459
  1788
      FREE,
deba@459
  1789
      /// The variable has active lower bound 
deba@459
  1790
      LOWER,
deba@459
  1791
      /// The variable has active upper bound
deba@459
  1792
      UPPER,
deba@459
  1793
      /// The variable is non-basic and fixed
deba@459
  1794
      FIXED
deba@459
  1795
    };
deba@459
  1796
deba@459
  1797
  protected:
deba@459
  1798
deba@459
  1799
    virtual SolveExitStatus _solve() = 0;
deba@459
  1800
deba@459
  1801
    virtual Value _getPrimal(int i) const = 0;
deba@459
  1802
    virtual Value _getDual(int i) const = 0;
deba@459
  1803
deba@459
  1804
    virtual Value _getPrimalRay(int i) const = 0;
deba@459
  1805
    virtual Value _getDualRay(int i) const = 0;
deba@459
  1806
deba@459
  1807
    virtual Value _getPrimalValue() const = 0;
deba@459
  1808
deba@459
  1809
    virtual VarStatus _getColStatus(int i) const = 0;
deba@459
  1810
    virtual VarStatus _getRowStatus(int i) const = 0;
deba@459
  1811
deba@459
  1812
    virtual ProblemType _getPrimalType() const = 0;
deba@459
  1813
    virtual ProblemType _getDualType() const = 0;
deba@459
  1814
deba@459
  1815
  public:
deba@458
  1816
alpar@540
  1817
    ///Allocate a new LP problem instance
alpar@540
  1818
    virtual LpSolver* newSolver() const = 0;
alpar@540
  1819
    ///Make a copy of the LP problem
alpar@540
  1820
    virtual LpSolver* cloneSolver() const = 0;
alpar@540
  1821
deba@458
  1822
    ///\name Solve the LP
deba@458
  1823
deba@458
  1824
    ///@{
deba@458
  1825
deba@458
  1826
    ///\e Solve the LP problem at hand
deba@458
  1827
    ///
deba@458
  1828
    ///\return The result of the optimization procedure. Possible
deba@458
  1829
    ///values and their meanings can be found in the documentation of
deba@458
  1830
    ///\ref SolveExitStatus.
deba@458
  1831
    SolveExitStatus solve() { return _solve(); }
deba@458
  1832
deba@458
  1833
    ///@}
deba@458
  1834
deba@458
  1835
    ///\name Obtain the solution
deba@458
  1836
deba@458
  1837
    ///@{
deba@458
  1838
deba@459
  1839
    /// The type of the primal problem
deba@459
  1840
    ProblemType primalType() const {
deba@459
  1841
      return _getPrimalType();
deba@458
  1842
    }
deba@458
  1843
deba@459
  1844
    /// The type of the dual problem
deba@459
  1845
    ProblemType dualType() const {
deba@459
  1846
      return _getDualType();
deba@458
  1847
    }
deba@458
  1848
deba@459
  1849
    /// Return the primal value of the column
deba@459
  1850
deba@459
  1851
    /// Return the primal value of the column.
deba@459
  1852
    /// \pre The problem is solved.
deba@459
  1853
    Value primal(Col c) const { return _getPrimal(cols(id(c))); }
deba@459
  1854
deba@459
  1855
    /// Return the primal value of the expression
deba@459
  1856
deba@459
  1857
    /// Return the primal value of the expression, i.e. the dot
deba@459
  1858
    /// product of the primal solution and the expression.
deba@459
  1859
    /// \pre The problem is solved.
deba@459
  1860
    Value primal(const Expr& e) const {
deba@459
  1861
      double res = *e;
deba@459
  1862
      for (Expr::ConstCoeffIt c(e); c != INVALID; ++c) {
deba@459
  1863
        res += *c * primal(c);
deba@459
  1864
      }
deba@459
  1865
      return res;
deba@458
  1866
    }
deba@459
  1867
    /// Returns a component of the primal ray
deba@459
  1868
    
deba@459
  1869
    /// The primal ray is solution of the modified primal problem,
deba@459
  1870
    /// where we change each finite bound to 0, and we looking for a
deba@459
  1871
    /// negative objective value in case of minimization, and positive
deba@459
  1872
    /// objective value for maximization. If there is such solution,
deba@459
  1873
    /// that proofs the unsolvability of the dual problem, and if a
deba@459
  1874
    /// feasible primal solution exists, then the unboundness of
deba@459
  1875
    /// primal problem.
deba@459
  1876
    ///
deba@459
  1877
    /// \pre The problem is solved and the dual problem is infeasible.
deba@459
  1878
    /// \note Some solvers does not provide primal ray calculation
deba@459
  1879
    /// functions.
deba@459
  1880
    Value primalRay(Col c) const { return _getPrimalRay(cols(id(c))); }
deba@458
  1881
deba@459
  1882
    /// Return the dual value of the row
deba@459
  1883
deba@459
  1884
    /// Return the dual value of the row.
deba@459
  1885
    /// \pre The problem is solved.
deba@459
  1886
    Value dual(Row r) const { return _getDual(rows(id(r))); }
deba@459
  1887
deba@459
  1888
    /// Return the dual value of the dual expression
deba@459
  1889
deba@459
  1890
    /// Return the dual value of the dual expression, i.e. the dot
deba@459
  1891
    /// product of the dual solution and the dual expression.
deba@459
  1892
    /// \pre The problem is solved.
deba@459
  1893
    Value dual(const DualExpr& e) const {
deba@459
  1894
      double res = 0.0;
deba@459
  1895
      for (DualExpr::ConstCoeffIt r(e); r != INVALID; ++r) {
deba@459
  1896
        res += *r * dual(r);
deba@458
  1897
      }
deba@458
  1898
      return res;
deba@458
  1899
    }
deba@458
  1900
deba@459
  1901
    /// Returns a component of the dual ray
deba@459
  1902
    
deba@459
  1903
    /// The dual ray is solution of the modified primal problem, where
deba@459
  1904
    /// we change each finite bound to 0 (i.e. the objective function
deba@459
  1905
    /// coefficients in the primal problem), and we looking for a
deba@459
  1906
    /// ositive objective value. If there is such solution, that
deba@459
  1907
    /// proofs the unsolvability of the primal problem, and if a
deba@459
  1908
    /// feasible dual solution exists, then the unboundness of
deba@459
  1909
    /// dual problem.
deba@459
  1910
    ///
deba@459
  1911
    /// \pre The problem is solved and the primal problem is infeasible.
deba@459
  1912
    /// \note Some solvers does not provide dual ray calculation
deba@459
  1913
    /// functions.
deba@459
  1914
    Value dualRay(Row r) const { return _getDualRay(rows(id(r))); }
deba@458
  1915
deba@459
  1916
    /// Return the basis status of the column
deba@458
  1917
deba@459
  1918
    /// \see VarStatus
deba@459
  1919
    VarStatus colStatus(Col c) const { return _getColStatus(cols(id(c))); }
deba@459
  1920
deba@459
  1921
    /// Return the basis status of the row
deba@459
  1922
deba@459
  1923
    /// \see VarStatus
deba@459
  1924
    VarStatus rowStatus(Row r) const { return _getRowStatus(rows(id(r))); }
deba@459
  1925
deba@459
  1926
    ///The value of the objective function
deba@458
  1927
deba@458
  1928
    ///\return
deba@458
  1929
    ///- \ref INF or -\ref INF means either infeasibility or unboundedness
deba@458
  1930
    /// of the primal problem, depending on whether we minimize or maximize.
deba@458
  1931
    ///- \ref NaN if no primal solution is found.
deba@458
  1932
    ///- The (finite) objective value if an optimal solution is found.
deba@459
  1933
    Value primal() const { return _getPrimalValue()+obj_const_comp;}
deba@458
  1934
    ///@}
deba@458
  1935
deba@459
  1936
  protected:
deba@459
  1937
deba@458
  1938
  };
deba@458
  1939
deba@458
  1940
deba@458
  1941
  /// \ingroup lp_group
deba@458
  1942
  ///
deba@458
  1943
  /// \brief Common base class for MIP solvers
deba@459
  1944
  ///
deba@459
  1945
  /// This class is an abstract base class for MIP solvers. This class
deba@459
  1946
  /// provides a full interface for set and modify an MIP problem,
deba@459
  1947
  /// solve it and retrieve the solution. You can use one of the
deba@459
  1948
  /// descendants as a concrete implementation, or the \c Lp
deba@459
  1949
  /// default MIP solver. However, if you would like to handle MIP
deba@459
  1950
  /// solvers as reference or pointer in a generic way, you can use
deba@459
  1951
  /// this class directly.
deba@459
  1952
  class MipSolver : virtual public LpBase {
deba@458
  1953
  public:
deba@458
  1954
deba@459
  1955
    /// The problem types for MIP problems
deba@459
  1956
    enum ProblemType {
deba@459
  1957
      ///Feasible solution hasn't been found (but may exist).
deba@459
  1958
      UNDEFINED = 0,
deba@459
  1959
      ///The problem has no feasible solution
deba@459
  1960
      INFEASIBLE = 1,
deba@459
  1961
      ///Feasible solution found
deba@459
  1962
      FEASIBLE = 2,
deba@459
  1963
      ///Optimal solution exists and found
deba@459
  1964
      OPTIMAL = 3,
deba@459
  1965
      ///The cost function is unbounded
deba@459
  1966
      ///
deba@459
  1967
      ///The Mip or at least the relaxed problem is unbounded
deba@459
  1968
      UNBOUNDED = 4
deba@459
  1969
    };
deba@459
  1970
alpar@540
  1971
    ///Allocate a new MIP problem instance
alpar@540
  1972
    virtual MipSolver* newSolver() const = 0;
alpar@540
  1973
    ///Make a copy of the MIP problem
alpar@540
  1974
    virtual MipSolver* cloneSolver() const = 0;
alpar@540
  1975
deba@459
  1976
    ///\name Solve the MIP
deba@459
  1977
deba@459
  1978
    ///@{
deba@459
  1979
deba@459
  1980
    /// Solve the MIP problem at hand
deba@459
  1981
    ///
deba@459
  1982
    ///\return The result of the optimization procedure. Possible
deba@459
  1983
    ///values and their meanings can be found in the documentation of
deba@459
  1984
    ///\ref SolveExitStatus.
deba@459
  1985
    SolveExitStatus solve() { return _solve(); }
deba@459
  1986
deba@459
  1987
    ///@}
deba@459
  1988
deba@459
  1989
    ///\name Setting column type
deba@459
  1990
    ///@{
deba@459
  1991
deba@459
  1992
    ///Possible variable (column) types (e.g. real, integer, binary etc.)
deba@458
  1993
    enum ColTypes {
deba@459
  1994
      ///Continuous variable (default)
deba@458
  1995
      REAL = 0,
deba@458
  1996
      ///Integer variable
deba@459
  1997
      INTEGER = 1
deba@458
  1998
    };
deba@458
  1999
deba@459
  2000
    ///Sets the type of the given column to the given type
deba@459
  2001
deba@459
  2002
    ///Sets the type of the given column to the given type.
deba@458
  2003
    ///
deba@458
  2004
    void colType(Col c, ColTypes col_type) {
deba@459
  2005
      _setColType(cols(id(c)),col_type);
deba@458
  2006
    }
deba@458
  2007
deba@458
  2008
    ///Gives back the type of the column.
deba@459
  2009
deba@459
  2010
    ///Gives back the type of the column.
deba@458
  2011
    ///
deba@458
  2012
    ColTypes colType(Col c) const {
deba@459
  2013
      return _getColType(cols(id(c)));
deba@459
  2014
    }
deba@459
  2015
    ///@}
deba@459
  2016
deba@459
  2017
    ///\name Obtain the solution
deba@459
  2018
deba@459
  2019
    ///@{
deba@459
  2020
deba@459
  2021
    /// The type of the MIP problem
deba@459
  2022
    ProblemType type() const {
deba@459
  2023
      return _getType();
deba@458
  2024
    }
deba@458
  2025
deba@459
  2026
    /// Return the value of the row in the solution
deba@459
  2027
deba@459
  2028
    ///  Return the value of the row in the solution.
deba@459
  2029
    /// \pre The problem is solved.
deba@459
  2030
    Value sol(Col c) const { return _getSol(cols(id(c))); }
deba@459
  2031
deba@459
  2032
    /// Return the value of the expression in the solution
deba@459
  2033
deba@459
  2034
    /// Return the value of the expression in the solution, i.e. the
deba@459
  2035
    /// dot product of the solution and the expression.
deba@459
  2036
    /// \pre The problem is solved.
deba@459
  2037
    Value sol(const Expr& e) const {
deba@459
  2038
      double res = *e;
deba@459
  2039
      for (Expr::ConstCoeffIt c(e); c != INVALID; ++c) {
deba@459
  2040
        res += *c * sol(c);
deba@459
  2041
      }
deba@459
  2042
      return res;
deba@458
  2043
    }
deba@459
  2044
    ///The value of the objective function
deba@459
  2045
    
deba@459
  2046
    ///\return
deba@459
  2047
    ///- \ref INF or -\ref INF means either infeasibility or unboundedness
deba@459
  2048
    /// of the problem, depending on whether we minimize or maximize.
deba@459
  2049
    ///- \ref NaN if no primal solution is found.
deba@459
  2050
    ///- The (finite) objective value if an optimal solution is found.
deba@459
  2051
    Value solValue() const { return _getSolValue()+obj_const_comp;}
deba@459
  2052
    ///@}
deba@458
  2053
deba@458
  2054
  protected:
deba@458
  2055
deba@459
  2056
    virtual SolveExitStatus _solve() = 0;
deba@459
  2057
    virtual ColTypes _getColType(int col) const = 0;
deba@459
  2058
    virtual void _setColType(int col, ColTypes col_type) = 0;
deba@459
  2059
    virtual ProblemType _getType() const = 0;
deba@459
  2060
    virtual Value _getSol(int i) const = 0;
deba@459
  2061
    virtual Value _getSolValue() const = 0;
deba@458
  2062
deba@458
  2063
  };
deba@458
  2064
deba@458
  2065
deba@458
  2066
deba@458
  2067
} //namespace lemon
deba@458
  2068
deba@458
  2069
#endif //LEMON_LP_BASE_H