lemon/lp_base.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 24 Feb 2009 06:52:17 +0000
changeset 536 97674155c135
parent 511 06787db0ef5f
child 540 9db62975c32b
permissions -rw-r--r--
Merge
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@459
   921
    virtual LpBase* _newSolver() const = 0;
deba@459
   922
    virtual LpBase* _cloneSolver() const = 0;
deba@458
   923
deba@459
   924
    virtual int _addColId(int col) { return cols.addIndex(col); }
deba@459
   925
    virtual int _addRowId(int row) { return rows.addIndex(row); }
deba@458
   926
deba@459
   927
    virtual void _eraseColId(int col) { cols.eraseIndex(col); }
deba@459
   928
    virtual void _eraseRowId(int row) { rows.eraseIndex(row); }
deba@458
   929
deba@458
   930
    virtual int _addCol() = 0;
deba@458
   931
    virtual int _addRow() = 0;
deba@458
   932
deba@458
   933
    virtual void _eraseCol(int col) = 0;
deba@458
   934
    virtual void _eraseRow(int row) = 0;
deba@458
   935
deba@459
   936
    virtual void _getColName(int col, std::string& name) const = 0;
deba@459
   937
    virtual void _setColName(int col, const std::string& name) = 0;
deba@458
   938
    virtual int _colByName(const std::string& name) const = 0;
deba@458
   939
deba@459
   940
    virtual void _getRowName(int row, std::string& name) const = 0;
deba@459
   941
    virtual void _setRowName(int row, const std::string& name) = 0;
deba@459
   942
    virtual int _rowByName(const std::string& name) const = 0;
deba@459
   943
deba@459
   944
    virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e) = 0;
deba@459
   945
    virtual void _getRowCoeffs(int i, InsertIterator b) const = 0;
deba@459
   946
deba@459
   947
    virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e) = 0;
deba@459
   948
    virtual void _getColCoeffs(int i, InsertIterator b) const = 0;
deba@459
   949
deba@458
   950
    virtual void _setCoeff(int row, int col, Value value) = 0;
deba@458
   951
    virtual Value _getCoeff(int row, int col) const = 0;
deba@459
   952
deba@458
   953
    virtual void _setColLowerBound(int i, Value value) = 0;
deba@458
   954
    virtual Value _getColLowerBound(int i) const = 0;
deba@459
   955
deba@458
   956
    virtual void _setColUpperBound(int i, Value value) = 0;
deba@458
   957
    virtual Value _getColUpperBound(int i) const = 0;
deba@459
   958
deba@459
   959
    virtual void _setRowLowerBound(int i, Value value) = 0;
deba@459
   960
    virtual Value _getRowLowerBound(int i) const = 0;
deba@459
   961
deba@459
   962
    virtual void _setRowUpperBound(int i, Value value) = 0;
deba@459
   963
    virtual Value _getRowUpperBound(int i) const = 0;
deba@459
   964
deba@459
   965
    virtual void _setObjCoeffs(ExprIterator b, ExprIterator e) = 0;
deba@459
   966
    virtual void _getObjCoeffs(InsertIterator b) const = 0;
deba@458
   967
deba@458
   968
    virtual void _setObjCoeff(int i, Value obj_coef) = 0;
deba@458
   969
    virtual Value _getObjCoeff(int i) const = 0;
deba@458
   970
deba@459
   971
    virtual void _setSense(Sense) = 0;
deba@459
   972
    virtual Sense _getSense() const = 0;
deba@458
   973
deba@459
   974
    virtual void _clear() = 0;
deba@458
   975
deba@459
   976
    virtual const char* _solverName() const = 0;
deba@458
   977
deba@458
   978
    //Own protected stuff
deba@458
   979
deba@458
   980
    //Constant component of the objective function
deba@458
   981
    Value obj_const_comp;
deba@458
   982
deba@459
   983
    LpBase() : rows(), cols(), obj_const_comp(0) {}
deba@459
   984
deba@458
   985
  public:
deba@458
   986
deba@459
   987
    /// Virtual destructor
deba@459
   988
    virtual ~LpBase() {}
deba@458
   989
deba@458
   990
    ///Creates a new LP problem
deba@459
   991
    LpBase* newSolver() {return _newSolver();}
deba@458
   992
    ///Makes a copy of the LP problem
deba@459
   993
    LpBase* cloneSolver() {return _cloneSolver();}
deba@459
   994
deba@459
   995
    ///Gives back the name of the solver.
deba@459
   996
    const char* solverName() const {return _solverName();}
deba@458
   997
deba@458
   998
    ///\name Build up and modify the LP
deba@458
   999
deba@458
  1000
    ///@{
deba@458
  1001
deba@458
  1002
    ///Add a new empty column (i.e a new variable) to the LP
deba@459
  1003
    Col addCol() { Col c; c._id = _addColId(_addCol()); return c;}
deba@458
  1004
deba@459
  1005
    ///\brief Adds several new columns (i.e variables) at once
deba@458
  1006
    ///
deba@459
  1007
    ///This magic function takes a container as its argument and fills
deba@459
  1008
    ///its elements with new columns (i.e. variables)
deba@458
  1009
    ///\param t can be
deba@458
  1010
    ///- a standard STL compatible iterable container with
deba@459
  1011
    ///\ref Col as its \c values_type like
deba@458
  1012
    ///\code
deba@459
  1013
    ///std::vector<LpBase::Col>
deba@459
  1014
    ///std::list<LpBase::Col>
deba@458
  1015
    ///\endcode
deba@458
  1016
    ///- a standard STL compatible iterable container with
deba@459
  1017
    ///\ref Col as its \c mapped_type like
deba@458
  1018
    ///\code
deba@459
  1019
    ///std::map<AnyType,LpBase::Col>
deba@458
  1020
    ///\endcode
deba@458
  1021
    ///- an iterable lemon \ref concepts::WriteMap "write map" like
deba@458
  1022
    ///\code
deba@459
  1023
    ///ListGraph::NodeMap<LpBase::Col>
deba@459
  1024
    ///ListGraph::ArcMap<LpBase::Col>
deba@458
  1025
    ///\endcode
deba@458
  1026
    ///\return The number of the created column.
deba@458
  1027
#ifdef DOXYGEN
deba@458
  1028
    template<class T>
deba@458
  1029
    int addColSet(T &t) { return 0;}
deba@458
  1030
#else
deba@458
  1031
    template<class T>
deba@459
  1032
    typename enable_if<typename T::value_type::LpCol,int>::type
deba@458
  1033
    addColSet(T &t,dummy<0> = 0) {
deba@458
  1034
      int s=0;
deba@458
  1035
      for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
deba@458
  1036
      return s;
deba@458
  1037
    }
deba@458
  1038
    template<class T>
deba@459
  1039
    typename enable_if<typename T::value_type::second_type::LpCol,
deba@458
  1040
                       int>::type
deba@458
  1041
    addColSet(T &t,dummy<1> = 1) {
deba@458
  1042
      int s=0;
deba@458
  1043
      for(typename T::iterator i=t.begin();i!=t.end();++i) {
deba@458
  1044
        i->second=addCol();
deba@458
  1045
        s++;
deba@458
  1046
      }
deba@458
  1047
      return s;
deba@458
  1048
    }
deba@458
  1049
    template<class T>
deba@459
  1050
    typename enable_if<typename T::MapIt::Value::LpCol,
deba@458
  1051
                       int>::type
deba@458
  1052
    addColSet(T &t,dummy<2> = 2) {
deba@458
  1053
      int s=0;
deba@458
  1054
      for(typename T::MapIt i(t); i!=INVALID; ++i)
deba@458
  1055
        {
deba@458
  1056
          i.set(addCol());
deba@458
  1057
          s++;
deba@458
  1058
        }
deba@458
  1059
      return s;
deba@458
  1060
    }
deba@458
  1061
#endif
deba@458
  1062
deba@458
  1063
    ///Set a column (i.e a dual constraint) of the LP
deba@458
  1064
deba@458
  1065
    ///\param c is the column to be modified
deba@458
  1066
    ///\param e is a dual linear expression (see \ref DualExpr)
deba@458
  1067
    ///a better one.
deba@459
  1068
    void col(Col c, const DualExpr &e) {
deba@458
  1069
      e.simplify();
deba@471
  1070
      _setColCoeffs(cols(id(c)), ExprIterator(e.comps.begin(), rows),
deba@471
  1071
                    ExprIterator(e.comps.end(), rows));
deba@458
  1072
    }
deba@458
  1073
deba@458
  1074
    ///Get a column (i.e a dual constraint) of the LP
deba@458
  1075
deba@459
  1076
    ///\param c is the column to get
deba@458
  1077
    ///\return the dual expression associated to the column
deba@458
  1078
    DualExpr col(Col c) const {
deba@458
  1079
      DualExpr e;
deba@459
  1080
      _getColCoeffs(cols(id(c)), InsertIterator(e.comps, rows));
deba@458
  1081
      return e;
deba@458
  1082
    }
deba@458
  1083
deba@458
  1084
    ///Add a new column to the LP
deba@458
  1085
deba@458
  1086
    ///\param e is a dual linear expression (see \ref DualExpr)
deba@459
  1087
    ///\param o is the corresponding component of the objective
deba@458
  1088
    ///function. It is 0 by default.
deba@458
  1089
    ///\return The created column.
deba@458
  1090
    Col addCol(const DualExpr &e, Value o = 0) {
deba@458
  1091
      Col c=addCol();
deba@458
  1092
      col(c,e);
deba@458
  1093
      objCoeff(c,o);
deba@458
  1094
      return c;
deba@458
  1095
    }
deba@458
  1096
deba@458
  1097
    ///Add a new empty row (i.e a new constraint) to the LP
deba@458
  1098
deba@458
  1099
    ///This function adds a new empty row (i.e a new constraint) to the LP.
deba@458
  1100
    ///\return The created row
deba@459
  1101
    Row addRow() { Row r; r._id = _addRowId(_addRow()); return r;}
deba@458
  1102
deba@459
  1103
    ///\brief Add several new rows (i.e constraints) at once
deba@458
  1104
    ///
deba@459
  1105
    ///This magic function takes a container as its argument and fills
deba@459
  1106
    ///its elements with new row (i.e. variables)
deba@458
  1107
    ///\param t can be
deba@458
  1108
    ///- a standard STL compatible iterable container with
deba@459
  1109
    ///\ref Row as its \c values_type like
deba@458
  1110
    ///\code
deba@459
  1111
    ///std::vector<LpBase::Row>
deba@459
  1112
    ///std::list<LpBase::Row>
deba@458
  1113
    ///\endcode
deba@458
  1114
    ///- a standard STL compatible iterable container with
deba@459
  1115
    ///\ref Row as its \c mapped_type like
deba@458
  1116
    ///\code
deba@459
  1117
    ///std::map<AnyType,LpBase::Row>
deba@458
  1118
    ///\endcode
deba@458
  1119
    ///- an iterable lemon \ref concepts::WriteMap "write map" like
deba@458
  1120
    ///\code
deba@459
  1121
    ///ListGraph::NodeMap<LpBase::Row>
deba@459
  1122
    ///ListGraph::ArcMap<LpBase::Row>
deba@458
  1123
    ///\endcode
deba@458
  1124
    ///\return The number of rows created.
deba@458
  1125
#ifdef DOXYGEN
deba@458
  1126
    template<class T>
deba@458
  1127
    int addRowSet(T &t) { return 0;}
deba@458
  1128
#else
deba@458
  1129
    template<class T>
deba@459
  1130
    typename enable_if<typename T::value_type::LpRow,int>::type
deba@459
  1131
    addRowSet(T &t, dummy<0> = 0) {
deba@458
  1132
      int s=0;
deba@458
  1133
      for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addRow();s++;}
deba@458
  1134
      return s;
deba@458
  1135
    }
deba@458
  1136
    template<class T>
deba@459
  1137
    typename enable_if<typename T::value_type::second_type::LpRow, int>::type
deba@459
  1138
    addRowSet(T &t, dummy<1> = 1) {
deba@458
  1139
      int s=0;
deba@458
  1140
      for(typename T::iterator i=t.begin();i!=t.end();++i) {
deba@458
  1141
        i->second=addRow();
deba@458
  1142
        s++;
deba@458
  1143
      }
deba@458
  1144
      return s;
deba@458
  1145
    }
deba@458
  1146
    template<class T>
deba@459
  1147
    typename enable_if<typename T::MapIt::Value::LpRow, int>::type
deba@459
  1148
    addRowSet(T &t, dummy<2> = 2) {
deba@458
  1149
      int s=0;
deba@458
  1150
      for(typename T::MapIt i(t); i!=INVALID; ++i)
deba@458
  1151
        {
deba@458
  1152
          i.set(addRow());
deba@458
  1153
          s++;
deba@458
  1154
        }
deba@458
  1155
      return s;
deba@458
  1156
    }
deba@458
  1157
#endif
deba@458
  1158
deba@458
  1159
    ///Set a row (i.e a constraint) of the LP
deba@458
  1160
deba@458
  1161
    ///\param r is the row to be modified
deba@458
  1162
    ///\param l is lower bound (-\ref INF means no bound)
deba@458
  1163
    ///\param e is a linear expression (see \ref Expr)
deba@458
  1164
    ///\param u is the upper bound (\ref INF means no bound)
deba@458
  1165
    void row(Row r, Value l, const Expr &e, Value u) {
deba@458
  1166
      e.simplify();
deba@459
  1167
      _setRowCoeffs(rows(id(r)), ExprIterator(e.comps.begin(), cols),
deba@459
  1168
                    ExprIterator(e.comps.end(), cols));
deba@459
  1169
      _setRowLowerBound(rows(id(r)),l - *e);
deba@459
  1170
      _setRowUpperBound(rows(id(r)),u - *e);
deba@458
  1171
    }
deba@458
  1172
deba@458
  1173
    ///Set a row (i.e a constraint) of the LP
deba@458
  1174
deba@458
  1175
    ///\param r is the row to be modified
deba@458
  1176
    ///\param c is a linear expression (see \ref Constr)
deba@458
  1177
    void row(Row r, const Constr &c) {
deba@458
  1178
      row(r, c.lowerBounded()?c.lowerBound():-INF,
deba@458
  1179
          c.expr(), c.upperBounded()?c.upperBound():INF);
deba@458
  1180
    }
deba@458
  1181
deba@458
  1182
deba@458
  1183
    ///Get a row (i.e a constraint) of the LP
deba@458
  1184
deba@458
  1185
    ///\param r is the row to get
deba@458
  1186
    ///\return the expression associated to the row
deba@458
  1187
    Expr row(Row r) const {
deba@458
  1188
      Expr e;
deba@459
  1189
      _getRowCoeffs(rows(id(r)), InsertIterator(e.comps, cols));
deba@458
  1190
      return e;
deba@458
  1191
    }
deba@458
  1192
deba@458
  1193
    ///Add a new row (i.e a new constraint) to the LP
deba@458
  1194
deba@458
  1195
    ///\param l is the lower bound (-\ref INF means no bound)
deba@458
  1196
    ///\param e is a linear expression (see \ref Expr)
deba@458
  1197
    ///\param u is the upper bound (\ref INF means no bound)
deba@458
  1198
    ///\return The created row.
deba@458
  1199
    Row addRow(Value l,const Expr &e, Value u) {
deba@458
  1200
      Row r=addRow();
deba@458
  1201
      row(r,l,e,u);
deba@458
  1202
      return r;
deba@458
  1203
    }
deba@458
  1204
deba@458
  1205
    ///Add a new row (i.e a new constraint) to the LP
deba@458
  1206
deba@458
  1207
    ///\param c is a linear expression (see \ref Constr)
deba@458
  1208
    ///\return The created row.
deba@458
  1209
    Row addRow(const Constr &c) {
deba@458
  1210
      Row r=addRow();
deba@458
  1211
      row(r,c);
deba@458
  1212
      return r;
deba@458
  1213
    }
deba@459
  1214
    ///Erase a column (i.e a variable) from the LP
deba@458
  1215
deba@459
  1216
    ///\param c is the column to be deleted
deba@459
  1217
    void erase(Col c) {
deba@459
  1218
      _eraseCol(cols(id(c)));
deba@459
  1219
      _eraseColId(cols(id(c)));
deba@458
  1220
    }
deba@459
  1221
    ///Erase a row (i.e a constraint) from the LP
deba@458
  1222
deba@458
  1223
    ///\param r is the row to be deleted
deba@459
  1224
    void erase(Row r) {
deba@459
  1225
      _eraseRow(rows(id(r)));
deba@459
  1226
      _eraseRowId(rows(id(r)));
deba@458
  1227
    }
deba@458
  1228
deba@458
  1229
    /// Get the name of a column
deba@458
  1230
deba@459
  1231
    ///\param c is the coresponding column
deba@458
  1232
    ///\return The name of the colunm
deba@458
  1233
    std::string colName(Col c) const {
deba@458
  1234
      std::string name;
deba@459
  1235
      _getColName(cols(id(c)), name);
deba@458
  1236
      return name;
deba@458
  1237
    }
deba@458
  1238
deba@458
  1239
    /// Set the name of a column
deba@458
  1240
deba@459
  1241
    ///\param c is the coresponding column
deba@458
  1242
    ///\param name The name to be given
deba@458
  1243
    void colName(Col c, const std::string& name) {
deba@459
  1244
      _setColName(cols(id(c)), name);
deba@458
  1245
    }
deba@458
  1246
deba@458
  1247
    /// Get the column by its name
deba@458
  1248
deba@458
  1249
    ///\param name The name of the column
deba@458
  1250
    ///\return the proper column or \c INVALID
deba@458
  1251
    Col colByName(const std::string& name) const {
deba@458
  1252
      int k = _colByName(name);
deba@459
  1253
      return k != -1 ? Col(cols[k]) : Col(INVALID);
deba@459
  1254
    }
deba@459
  1255
deba@459
  1256
    /// Get the name of a row
deba@459
  1257
deba@459
  1258
    ///\param r is the coresponding row
deba@459
  1259
    ///\return The name of the row
deba@459
  1260
    std::string rowName(Row r) const {
deba@459
  1261
      std::string name;
deba@459
  1262
      _getRowName(rows(id(r)), name);
deba@459
  1263
      return name;
deba@459
  1264
    }
deba@459
  1265
deba@459
  1266
    /// Set the name of a row
deba@459
  1267
deba@459
  1268
    ///\param r is the coresponding row
deba@459
  1269
    ///\param name The name to be given
deba@459
  1270
    void rowName(Row r, const std::string& name) {
deba@459
  1271
      _setRowName(rows(id(r)), name);
deba@459
  1272
    }
deba@459
  1273
deba@459
  1274
    /// Get the row by its name
deba@459
  1275
deba@459
  1276
    ///\param name The name of the row
deba@459
  1277
    ///\return the proper row or \c INVALID
deba@459
  1278
    Row rowByName(const std::string& name) const {
deba@459
  1279
      int k = _rowByName(name);
deba@459
  1280
      return k != -1 ? Row(rows[k]) : Row(INVALID);
deba@458
  1281
    }
deba@458
  1282
deba@458
  1283
    /// Set an element of the coefficient matrix of the LP
deba@458
  1284
deba@458
  1285
    ///\param r is the row of the element to be modified
deba@459
  1286
    ///\param c is the column of the element to be modified
deba@458
  1287
    ///\param val is the new value of the coefficient
deba@458
  1288
    void coeff(Row r, Col c, Value val) {
deba@459
  1289
      _setCoeff(rows(id(r)),cols(id(c)), val);
deba@458
  1290
    }
deba@458
  1291
deba@458
  1292
    /// Get an element of the coefficient matrix of the LP
deba@458
  1293
deba@459
  1294
    ///\param r is the row of the element
deba@459
  1295
    ///\param c is the column of the element
deba@458
  1296
    ///\return the corresponding coefficient
deba@458
  1297
    Value coeff(Row r, Col c) const {
deba@459
  1298
      return _getCoeff(rows(id(r)),cols(id(c)));
deba@458
  1299
    }
deba@458
  1300
deba@458
  1301
    /// Set the lower bound of a column (i.e a variable)
deba@458
  1302
deba@458
  1303
    /// The lower bound of a variable (column) has to be given by an
deba@458
  1304
    /// extended number of type Value, i.e. a finite number of type
deba@458
  1305
    /// Value or -\ref INF.
deba@458
  1306
    void colLowerBound(Col c, Value value) {
deba@459
  1307
      _setColLowerBound(cols(id(c)),value);
deba@458
  1308
    }
deba@458
  1309
deba@458
  1310
    /// Get the lower bound of a column (i.e a variable)
deba@458
  1311
deba@459
  1312
    /// This function returns the lower bound for column (variable) \c c
deba@458
  1313
    /// (this might be -\ref INF as well).
deba@459
  1314
    ///\return The lower bound for column \c c
deba@458
  1315
    Value colLowerBound(Col c) const {
deba@459
  1316
      return _getColLowerBound(cols(id(c)));
deba@458
  1317
    }
deba@458
  1318
deba@458
  1319
    ///\brief Set the lower bound of  several columns
deba@459
  1320
    ///(i.e variables) at once
deba@458
  1321
    ///
deba@458
  1322
    ///This magic function takes a container as its argument
deba@458
  1323
    ///and applies the function on all of its elements.
deba@459
  1324
    ///The lower bound of a variable (column) has to be given by an
deba@459
  1325
    ///extended number of type Value, i.e. a finite number of type
deba@459
  1326
    ///Value or -\ref INF.
deba@458
  1327
#ifdef DOXYGEN
deba@458
  1328
    template<class T>
deba@458
  1329
    void colLowerBound(T &t, Value value) { return 0;}
deba@458
  1330
#else
deba@458
  1331
    template<class T>
deba@459
  1332
    typename enable_if<typename T::value_type::LpCol,void>::type
deba@458
  1333
    colLowerBound(T &t, Value value,dummy<0> = 0) {
deba@458
  1334
      for(typename T::iterator i=t.begin();i!=t.end();++i) {
deba@458
  1335
        colLowerBound(*i, value);
deba@458
  1336
      }
deba@458
  1337
    }
deba@458
  1338
    template<class T>
deba@459
  1339
    typename enable_if<typename T::value_type::second_type::LpCol,
deba@458
  1340
                       void>::type
deba@458
  1341
    colLowerBound(T &t, Value value,dummy<1> = 1) {
deba@458
  1342
      for(typename T::iterator i=t.begin();i!=t.end();++i) {
deba@458
  1343
        colLowerBound(i->second, value);
deba@458
  1344
      }
deba@458
  1345
    }
deba@458
  1346
    template<class T>
deba@459
  1347
    typename enable_if<typename T::MapIt::Value::LpCol,
deba@458
  1348
                       void>::type
deba@458
  1349
    colLowerBound(T &t, Value value,dummy<2> = 2) {
deba@458
  1350
      for(typename T::MapIt i(t); i!=INVALID; ++i){
deba@458
  1351
        colLowerBound(*i, value);
deba@458
  1352
      }
deba@458
  1353
    }
deba@458
  1354
#endif
deba@458
  1355
deba@458
  1356
    /// Set the upper bound of a column (i.e a variable)
deba@458
  1357
deba@458
  1358
    /// The upper bound of a variable (column) has to be given by an
deba@458
  1359
    /// extended number of type Value, i.e. a finite number of type
deba@458
  1360
    /// Value or \ref INF.
deba@458
  1361
    void colUpperBound(Col c, Value value) {
deba@459
  1362
      _setColUpperBound(cols(id(c)),value);
deba@458
  1363
    };
deba@458
  1364
deba@458
  1365
    /// Get the upper bound of a column (i.e a variable)
deba@458
  1366
deba@459
  1367
    /// This function returns the upper bound for column (variable) \c c
deba@458
  1368
    /// (this might be \ref INF as well).
deba@459
  1369
    /// \return The upper bound for column \c c
deba@458
  1370
    Value colUpperBound(Col c) const {
deba@459
  1371
      return _getColUpperBound(cols(id(c)));
deba@458
  1372
    }
deba@458
  1373
deba@458
  1374
    ///\brief Set the upper bound of  several columns
deba@459
  1375
    ///(i.e variables) at once
deba@458
  1376
    ///
deba@458
  1377
    ///This magic function takes a container as its argument
deba@458
  1378
    ///and applies the function on all of its elements.
deba@459
  1379
    ///The upper bound of a variable (column) has to be given by an
deba@459
  1380
    ///extended number of type Value, i.e. a finite number of type
deba@459
  1381
    ///Value or \ref INF.
deba@458
  1382
#ifdef DOXYGEN
deba@458
  1383
    template<class T>
deba@458
  1384
    void colUpperBound(T &t, Value value) { return 0;}
deba@458
  1385
#else
tapolcai@514
  1386
    template<class T1>
tapolcai@514
  1387
    typename enable_if<typename T1::value_type::LpCol,void>::type
tapolcai@514
  1388
    colUpperBound(T1 &t, Value value,dummy<0> = 0) {
tapolcai@514
  1389
      for(typename T1::iterator i=t.begin();i!=t.end();++i) {
deba@458
  1390
        colUpperBound(*i, value);
deba@458
  1391
      }
deba@458
  1392
    }
tapolcai@514
  1393
    template<class T1>
tapolcai@514
  1394
    typename enable_if<typename T1::value_type::second_type::LpCol,
deba@458
  1395
                       void>::type
tapolcai@514
  1396
    colUpperBound(T1 &t, Value value,dummy<1> = 1) {
tapolcai@514
  1397
      for(typename T1::iterator i=t.begin();i!=t.end();++i) {
deba@458
  1398
        colUpperBound(i->second, value);
deba@458
  1399
      }
deba@458
  1400
    }
tapolcai@514
  1401
    template<class T1>
tapolcai@514
  1402
    typename enable_if<typename T1::MapIt::Value::LpCol,
deba@458
  1403
                       void>::type
tapolcai@514
  1404
    colUpperBound(T1 &t, Value value,dummy<2> = 2) {
tapolcai@514
  1405
      for(typename T1::MapIt i(t); i!=INVALID; ++i){
deba@458
  1406
        colUpperBound(*i, value);
deba@458
  1407
      }
deba@458
  1408
    }
deba@458
  1409
#endif
deba@458
  1410
deba@458
  1411
    /// Set the lower and the upper bounds of a column (i.e a variable)
deba@458
  1412
deba@458
  1413
    /// The lower and the upper bounds of
deba@458
  1414
    /// a variable (column) have to be given by an
deba@458
  1415
    /// extended number of type Value, i.e. a finite number of type
deba@458
  1416
    /// Value, -\ref INF or \ref INF.
deba@458
  1417
    void colBounds(Col c, Value lower, Value upper) {
deba@459
  1418
      _setColLowerBound(cols(id(c)),lower);
deba@459
  1419
      _setColUpperBound(cols(id(c)),upper);
deba@458
  1420
    }
deba@458
  1421
deba@458
  1422
    ///\brief Set the lower and the upper bound of several columns
deba@459
  1423
    ///(i.e variables) at once
deba@458
  1424
    ///
deba@458
  1425
    ///This magic function takes a container as its argument
deba@458
  1426
    ///and applies the function on all of its elements.
deba@458
  1427
    /// The lower and the upper bounds of
deba@458
  1428
    /// a variable (column) have to be given by an
deba@458
  1429
    /// extended number of type Value, i.e. a finite number of type
deba@458
  1430
    /// Value, -\ref INF or \ref INF.
deba@458
  1431
#ifdef DOXYGEN
deba@458
  1432
    template<class T>
deba@458
  1433
    void colBounds(T &t, Value lower, Value upper) { return 0;}
deba@458
  1434
#else
tapolcai@514
  1435
    template<class T2>
tapolcai@514
  1436
    typename enable_if<typename T2::value_type::LpCol,void>::type
tapolcai@514
  1437
    colBounds(T2 &t, Value lower, Value upper,dummy<0> = 0) {
tapolcai@514
  1438
      for(typename T2::iterator i=t.begin();i!=t.end();++i) {
deba@458
  1439
        colBounds(*i, lower, upper);
deba@458
  1440
      }
deba@458
  1441
    }
tapolcai@514
  1442
    template<class T2>
tapolcai@514
  1443
    typename enable_if<typename T2::value_type::second_type::LpCol, void>::type
tapolcai@514
  1444
    colBounds(T2 &t, Value lower, Value upper,dummy<1> = 1) {
tapolcai@514
  1445
      for(typename T2::iterator i=t.begin();i!=t.end();++i) {
deba@458
  1446
        colBounds(i->second, lower, upper);
deba@458
  1447
      }
deba@458
  1448
    }
tapolcai@514
  1449
    template<class T2>
tapolcai@514
  1450
    typename enable_if<typename T2::MapIt::Value::LpCol, void>::type
tapolcai@514
  1451
    colBounds(T2 &t, Value lower, Value upper,dummy<2> = 2) {
tapolcai@514
  1452
      for(typename T2::MapIt i(t); i!=INVALID; ++i){
deba@458
  1453
        colBounds(*i, lower, upper);
deba@458
  1454
      }
deba@458
  1455
    }
deba@458
  1456
#endif
deba@458
  1457
deba@459
  1458
    /// Set the lower bound of a row (i.e a constraint)
deba@458
  1459
deba@459
  1460
    /// The lower bound of a constraint (row) has to be given by an
deba@459
  1461
    /// extended number of type Value, i.e. a finite number of type
deba@459
  1462
    /// Value or -\ref INF.
deba@459
  1463
    void rowLowerBound(Row r, Value value) {
deba@459
  1464
      _setRowLowerBound(rows(id(r)),value);
deba@458
  1465
    }
deba@458
  1466
deba@459
  1467
    /// Get the lower bound of a row (i.e a constraint)
deba@458
  1468
deba@459
  1469
    /// This function returns the lower bound for row (constraint) \c c
deba@459
  1470
    /// (this might be -\ref INF as well).
deba@459
  1471
    ///\return The lower bound for row \c r
deba@459
  1472
    Value rowLowerBound(Row r) const {
deba@459
  1473
      return _getRowLowerBound(rows(id(r)));
deba@459
  1474
    }
deba@459
  1475
deba@459
  1476
    /// Set the upper bound of a row (i.e a constraint)
deba@459
  1477
deba@459
  1478
    /// The upper bound of a constraint (row) has to be given by an
deba@459
  1479
    /// extended number of type Value, i.e. a finite number of type
deba@459
  1480
    /// Value or -\ref INF.
deba@459
  1481
    void rowUpperBound(Row r, Value value) {
deba@459
  1482
      _setRowUpperBound(rows(id(r)),value);
deba@459
  1483
    }
deba@459
  1484
deba@459
  1485
    /// Get the upper bound of a row (i.e a constraint)
deba@459
  1486
deba@459
  1487
    /// This function returns the upper bound for row (constraint) \c c
deba@459
  1488
    /// (this might be -\ref INF as well).
deba@459
  1489
    ///\return The upper bound for row \c r
deba@459
  1490
    Value rowUpperBound(Row r) const {
deba@459
  1491
      return _getRowUpperBound(rows(id(r)));
deba@458
  1492
    }
deba@458
  1493
deba@458
  1494
    ///Set an element of the objective function
deba@459
  1495
    void objCoeff(Col c, Value v) {_setObjCoeff(cols(id(c)),v); };
deba@458
  1496
deba@458
  1497
    ///Get an element of the objective function
deba@459
  1498
    Value objCoeff(Col c) const { return _getObjCoeff(cols(id(c))); };
deba@458
  1499
deba@458
  1500
    ///Set the objective function
deba@458
  1501
deba@458
  1502
    ///\param e is a linear expression of type \ref Expr.
deba@459
  1503
    ///
deba@459
  1504
    void obj(const Expr& e) {
deba@459
  1505
      _setObjCoeffs(ExprIterator(e.comps.begin(), cols),
deba@459
  1506
                    ExprIterator(e.comps.end(), cols));
deba@459
  1507
      obj_const_comp = *e;
deba@458
  1508
    }
deba@458
  1509
deba@458
  1510
    ///Get the objective function
deba@458
  1511
deba@459
  1512
    ///\return the objective function as a linear expression of type
deba@459
  1513
    ///Expr.
deba@458
  1514
    Expr obj() const {
deba@458
  1515
      Expr e;
deba@459
  1516
      _getObjCoeffs(InsertIterator(e.comps, cols));
deba@459
  1517
      *e = obj_const_comp;
deba@458
  1518
      return e;
deba@458
  1519
    }
deba@458
  1520
deba@458
  1521
deba@459
  1522
    ///Set the direction of optimization
deba@459
  1523
    void sense(Sense sense) { _setSense(sense); }
deba@458
  1524
deba@459
  1525
    ///Query the direction of the optimization
deba@459
  1526
    Sense sense() const {return _getSense(); }
deba@458
  1527
deba@459
  1528
    ///Set the sense to maximization
deba@459
  1529
    void max() { _setSense(MAX); }
deba@459
  1530
deba@459
  1531
    ///Set the sense to maximization
deba@459
  1532
    void min() { _setSense(MIN); }
deba@459
  1533
deba@459
  1534
    ///Clears the problem
deba@459
  1535
    void clear() { _clear(); }
deba@458
  1536
deba@458
  1537
    ///@}
deba@458
  1538
deba@459
  1539
  };
deba@459
  1540
deba@459
  1541
  /// Addition
deba@459
  1542
deba@459
  1543
  ///\relates LpBase::Expr
deba@459
  1544
  ///
deba@459
  1545
  inline LpBase::Expr operator+(const LpBase::Expr &a, const LpBase::Expr &b) {
deba@459
  1546
    LpBase::Expr tmp(a);
deba@459
  1547
    tmp+=b;
deba@459
  1548
    return tmp;
deba@459
  1549
  }
deba@459
  1550
  ///Substraction
deba@459
  1551
deba@459
  1552
  ///\relates LpBase::Expr
deba@459
  1553
  ///
deba@459
  1554
  inline LpBase::Expr operator-(const LpBase::Expr &a, const LpBase::Expr &b) {
deba@459
  1555
    LpBase::Expr tmp(a);
deba@459
  1556
    tmp-=b;
deba@459
  1557
    return tmp;
deba@459
  1558
  }
deba@459
  1559
  ///Multiply with constant
deba@459
  1560
deba@459
  1561
  ///\relates LpBase::Expr
deba@459
  1562
  ///
deba@459
  1563
  inline LpBase::Expr operator*(const LpBase::Expr &a, const LpBase::Value &b) {
deba@459
  1564
    LpBase::Expr tmp(a);
deba@459
  1565
    tmp*=b;
deba@459
  1566
    return tmp;
deba@459
  1567
  }
deba@459
  1568
deba@459
  1569
  ///Multiply with constant
deba@459
  1570
deba@459
  1571
  ///\relates LpBase::Expr
deba@459
  1572
  ///
deba@459
  1573
  inline LpBase::Expr operator*(const LpBase::Value &a, const LpBase::Expr &b) {
deba@459
  1574
    LpBase::Expr tmp(b);
deba@459
  1575
    tmp*=a;
deba@459
  1576
    return tmp;
deba@459
  1577
  }
deba@459
  1578
  ///Divide with constant
deba@459
  1579
deba@459
  1580
  ///\relates LpBase::Expr
deba@459
  1581
  ///
deba@459
  1582
  inline LpBase::Expr operator/(const LpBase::Expr &a, const LpBase::Value &b) {
deba@459
  1583
    LpBase::Expr tmp(a);
deba@459
  1584
    tmp/=b;
deba@459
  1585
    return tmp;
deba@459
  1586
  }
deba@459
  1587
deba@459
  1588
  ///Create constraint
deba@459
  1589
deba@459
  1590
  ///\relates LpBase::Constr
deba@459
  1591
  ///
deba@459
  1592
  inline LpBase::Constr operator<=(const LpBase::Expr &e,
deba@459
  1593
                                   const LpBase::Expr &f) {
deba@459
  1594
    return LpBase::Constr(0, f - e, LpBase::INF);
deba@459
  1595
  }
deba@459
  1596
deba@459
  1597
  ///Create constraint
deba@459
  1598
deba@459
  1599
  ///\relates LpBase::Constr
deba@459
  1600
  ///
deba@459
  1601
  inline LpBase::Constr operator<=(const LpBase::Value &e,
deba@459
  1602
                                   const LpBase::Expr &f) {
deba@459
  1603
    return LpBase::Constr(e, f, LpBase::NaN);
deba@459
  1604
  }
deba@459
  1605
deba@459
  1606
  ///Create constraint
deba@459
  1607
deba@459
  1608
  ///\relates LpBase::Constr
deba@459
  1609
  ///
deba@459
  1610
  inline LpBase::Constr operator<=(const LpBase::Expr &e,
deba@459
  1611
                                   const LpBase::Value &f) {
deba@459
  1612
    return LpBase::Constr(- LpBase::INF, e, f);
deba@459
  1613
  }
deba@459
  1614
deba@459
  1615
  ///Create constraint
deba@459
  1616
deba@459
  1617
  ///\relates LpBase::Constr
deba@459
  1618
  ///
deba@459
  1619
  inline LpBase::Constr operator>=(const LpBase::Expr &e,
deba@459
  1620
                                   const LpBase::Expr &f) {
deba@459
  1621
    return LpBase::Constr(0, e - f, LpBase::INF);
deba@459
  1622
  }
deba@459
  1623
deba@459
  1624
deba@459
  1625
  ///Create constraint
deba@459
  1626
deba@459
  1627
  ///\relates LpBase::Constr
deba@459
  1628
  ///
deba@459
  1629
  inline LpBase::Constr operator>=(const LpBase::Value &e,
deba@459
  1630
                                   const LpBase::Expr &f) {
deba@459
  1631
    return LpBase::Constr(LpBase::NaN, f, e);
deba@459
  1632
  }
deba@459
  1633
deba@459
  1634
deba@459
  1635
  ///Create constraint
deba@459
  1636
deba@459
  1637
  ///\relates LpBase::Constr
deba@459
  1638
  ///
deba@459
  1639
  inline LpBase::Constr operator>=(const LpBase::Expr &e,
deba@459
  1640
                                   const LpBase::Value &f) {
deba@459
  1641
    return LpBase::Constr(f, e, LpBase::INF);
deba@459
  1642
  }
deba@459
  1643
deba@459
  1644
  ///Create constraint
deba@459
  1645
deba@459
  1646
  ///\relates LpBase::Constr
deba@459
  1647
  ///
deba@459
  1648
  inline LpBase::Constr operator==(const LpBase::Expr &e,
deba@459
  1649
                                   const LpBase::Value &f) {
deba@459
  1650
    return LpBase::Constr(f, e, f);
deba@459
  1651
  }
deba@459
  1652
deba@459
  1653
  ///Create constraint
deba@459
  1654
deba@459
  1655
  ///\relates LpBase::Constr
deba@459
  1656
  ///
deba@459
  1657
  inline LpBase::Constr operator==(const LpBase::Expr &e,
deba@459
  1658
                                   const LpBase::Expr &f) {
deba@459
  1659
    return LpBase::Constr(0, f - e, 0);
deba@459
  1660
  }
deba@459
  1661
deba@459
  1662
  ///Create constraint
deba@459
  1663
deba@459
  1664
  ///\relates LpBase::Constr
deba@459
  1665
  ///
deba@459
  1666
  inline LpBase::Constr operator<=(const LpBase::Value &n,
deba@459
  1667
                                   const LpBase::Constr &c) {
deba@459
  1668
    LpBase::Constr tmp(c);
alpar@511
  1669
    LEMON_ASSERT(isNaN(tmp.lowerBound()), "Wrong LP constraint");
deba@459
  1670
    tmp.lowerBound()=n;
deba@459
  1671
    return tmp;
deba@459
  1672
  }
deba@459
  1673
  ///Create constraint
deba@459
  1674
deba@459
  1675
  ///\relates LpBase::Constr
deba@459
  1676
  ///
deba@459
  1677
  inline LpBase::Constr operator<=(const LpBase::Constr &c,
deba@459
  1678
                                   const LpBase::Value &n)
deba@459
  1679
  {
deba@459
  1680
    LpBase::Constr tmp(c);
alpar@511
  1681
    LEMON_ASSERT(isNaN(tmp.upperBound()), "Wrong LP constraint");
deba@459
  1682
    tmp.upperBound()=n;
deba@459
  1683
    return tmp;
deba@459
  1684
  }
deba@459
  1685
deba@459
  1686
  ///Create constraint
deba@459
  1687
deba@459
  1688
  ///\relates LpBase::Constr
deba@459
  1689
  ///
deba@459
  1690
  inline LpBase::Constr operator>=(const LpBase::Value &n,
deba@459
  1691
                                   const LpBase::Constr &c) {
deba@459
  1692
    LpBase::Constr tmp(c);
alpar@511
  1693
    LEMON_ASSERT(isNaN(tmp.upperBound()), "Wrong LP constraint");
deba@459
  1694
    tmp.upperBound()=n;
deba@459
  1695
    return tmp;
deba@459
  1696
  }
deba@459
  1697
  ///Create constraint
deba@459
  1698
deba@459
  1699
  ///\relates LpBase::Constr
deba@459
  1700
  ///
deba@459
  1701
  inline LpBase::Constr operator>=(const LpBase::Constr &c,
deba@459
  1702
                                   const LpBase::Value &n)
deba@459
  1703
  {
deba@459
  1704
    LpBase::Constr tmp(c);
alpar@511
  1705
    LEMON_ASSERT(isNaN(tmp.lowerBound()), "Wrong LP constraint");
deba@459
  1706
    tmp.lowerBound()=n;
deba@459
  1707
    return tmp;
deba@459
  1708
  }
deba@459
  1709
deba@459
  1710
  ///Addition
deba@459
  1711
deba@459
  1712
  ///\relates LpBase::DualExpr
deba@459
  1713
  ///
deba@459
  1714
  inline LpBase::DualExpr operator+(const LpBase::DualExpr &a,
deba@459
  1715
                                    const LpBase::DualExpr &b) {
deba@459
  1716
    LpBase::DualExpr tmp(a);
deba@459
  1717
    tmp+=b;
deba@459
  1718
    return tmp;
deba@459
  1719
  }
deba@459
  1720
  ///Substraction
deba@459
  1721
deba@459
  1722
  ///\relates LpBase::DualExpr
deba@459
  1723
  ///
deba@459
  1724
  inline LpBase::DualExpr operator-(const LpBase::DualExpr &a,
deba@459
  1725
                                    const LpBase::DualExpr &b) {
deba@459
  1726
    LpBase::DualExpr tmp(a);
deba@459
  1727
    tmp-=b;
deba@459
  1728
    return tmp;
deba@459
  1729
  }
deba@459
  1730
  ///Multiply with constant
deba@459
  1731
deba@459
  1732
  ///\relates LpBase::DualExpr
deba@459
  1733
  ///
deba@459
  1734
  inline LpBase::DualExpr operator*(const LpBase::DualExpr &a,
deba@459
  1735
                                    const LpBase::Value &b) {
deba@459
  1736
    LpBase::DualExpr tmp(a);
deba@459
  1737
    tmp*=b;
deba@459
  1738
    return tmp;
deba@459
  1739
  }
deba@459
  1740
deba@459
  1741
  ///Multiply with constant
deba@459
  1742
deba@459
  1743
  ///\relates LpBase::DualExpr
deba@459
  1744
  ///
deba@459
  1745
  inline LpBase::DualExpr operator*(const LpBase::Value &a,
deba@459
  1746
                                    const LpBase::DualExpr &b) {
deba@459
  1747
    LpBase::DualExpr tmp(b);
deba@459
  1748
    tmp*=a;
deba@459
  1749
    return tmp;
deba@459
  1750
  }
deba@459
  1751
  ///Divide with constant
deba@459
  1752
deba@459
  1753
  ///\relates LpBase::DualExpr
deba@459
  1754
  ///
deba@459
  1755
  inline LpBase::DualExpr operator/(const LpBase::DualExpr &a,
deba@459
  1756
                                    const LpBase::Value &b) {
deba@459
  1757
    LpBase::DualExpr tmp(a);
deba@459
  1758
    tmp/=b;
deba@459
  1759
    return tmp;
deba@459
  1760
  }
deba@459
  1761
deba@459
  1762
  /// \ingroup lp_group
deba@459
  1763
  ///
deba@459
  1764
  /// \brief Common base class for LP solvers
deba@459
  1765
  ///
deba@459
  1766
  /// This class is an abstract base class for LP solvers. This class
deba@459
  1767
  /// provides a full interface for set and modify an LP problem,
deba@459
  1768
  /// solve it and retrieve the solution. You can use one of the
deba@459
  1769
  /// descendants as a concrete implementation, or the \c Lp
deba@459
  1770
  /// default LP solver. However, if you would like to handle LP
deba@459
  1771
  /// solvers as reference or pointer in a generic way, you can use
deba@459
  1772
  /// this class directly.
deba@459
  1773
  class LpSolver : virtual public LpBase {
deba@459
  1774
  public:
deba@459
  1775
deba@459
  1776
    /// The problem types for primal and dual problems
deba@459
  1777
    enum ProblemType {
deba@459
  1778
      ///Feasible solution hasn't been found (but may exist).
deba@459
  1779
      UNDEFINED = 0,
deba@459
  1780
      ///The problem has no feasible solution
deba@459
  1781
      INFEASIBLE = 1,
deba@459
  1782
      ///Feasible solution found
deba@459
  1783
      FEASIBLE = 2,
deba@459
  1784
      ///Optimal solution exists and found
deba@459
  1785
      OPTIMAL = 3,
deba@459
  1786
      ///The cost function is unbounded
deba@459
  1787
      UNBOUNDED = 4
deba@459
  1788
    };
deba@459
  1789
deba@459
  1790
    ///The basis status of variables
deba@459
  1791
    enum VarStatus {
deba@459
  1792
      /// The variable is in the basis
deba@459
  1793
      BASIC, 
deba@459
  1794
      /// The variable is free, but not basic
deba@459
  1795
      FREE,
deba@459
  1796
      /// The variable has active lower bound 
deba@459
  1797
      LOWER,
deba@459
  1798
      /// The variable has active upper bound
deba@459
  1799
      UPPER,
deba@459
  1800
      /// The variable is non-basic and fixed
deba@459
  1801
      FIXED
deba@459
  1802
    };
deba@459
  1803
deba@459
  1804
  protected:
deba@459
  1805
deba@459
  1806
    virtual SolveExitStatus _solve() = 0;
deba@459
  1807
deba@459
  1808
    virtual Value _getPrimal(int i) const = 0;
deba@459
  1809
    virtual Value _getDual(int i) const = 0;
deba@459
  1810
deba@459
  1811
    virtual Value _getPrimalRay(int i) const = 0;
deba@459
  1812
    virtual Value _getDualRay(int i) const = 0;
deba@459
  1813
deba@459
  1814
    virtual Value _getPrimalValue() const = 0;
deba@459
  1815
deba@459
  1816
    virtual VarStatus _getColStatus(int i) const = 0;
deba@459
  1817
    virtual VarStatus _getRowStatus(int i) const = 0;
deba@459
  1818
deba@459
  1819
    virtual ProblemType _getPrimalType() const = 0;
deba@459
  1820
    virtual ProblemType _getDualType() const = 0;
deba@459
  1821
deba@459
  1822
  public:
deba@458
  1823
deba@458
  1824
    ///\name Solve the LP
deba@458
  1825
deba@458
  1826
    ///@{
deba@458
  1827
deba@458
  1828
    ///\e Solve the LP problem at hand
deba@458
  1829
    ///
deba@458
  1830
    ///\return The result of the optimization procedure. Possible
deba@458
  1831
    ///values and their meanings can be found in the documentation of
deba@458
  1832
    ///\ref SolveExitStatus.
deba@458
  1833
    SolveExitStatus solve() { return _solve(); }
deba@458
  1834
deba@458
  1835
    ///@}
deba@458
  1836
deba@458
  1837
    ///\name Obtain the solution
deba@458
  1838
deba@458
  1839
    ///@{
deba@458
  1840
deba@459
  1841
    /// The type of the primal problem
deba@459
  1842
    ProblemType primalType() const {
deba@459
  1843
      return _getPrimalType();
deba@458
  1844
    }
deba@458
  1845
deba@459
  1846
    /// The type of the dual problem
deba@459
  1847
    ProblemType dualType() const {
deba@459
  1848
      return _getDualType();
deba@458
  1849
    }
deba@458
  1850
deba@459
  1851
    /// Return the primal value of the column
deba@459
  1852
deba@459
  1853
    /// Return the primal value of the column.
deba@459
  1854
    /// \pre The problem is solved.
deba@459
  1855
    Value primal(Col c) const { return _getPrimal(cols(id(c))); }
deba@459
  1856
deba@459
  1857
    /// Return the primal value of the expression
deba@459
  1858
deba@459
  1859
    /// Return the primal value of the expression, i.e. the dot
deba@459
  1860
    /// product of the primal solution and the expression.
deba@459
  1861
    /// \pre The problem is solved.
deba@459
  1862
    Value primal(const Expr& e) const {
deba@459
  1863
      double res = *e;
deba@459
  1864
      for (Expr::ConstCoeffIt c(e); c != INVALID; ++c) {
deba@459
  1865
        res += *c * primal(c);
deba@459
  1866
      }
deba@459
  1867
      return res;
deba@458
  1868
    }
deba@459
  1869
    /// Returns a component of the primal ray
deba@459
  1870
    
deba@459
  1871
    /// The primal ray is solution of the modified primal problem,
deba@459
  1872
    /// where we change each finite bound to 0, and we looking for a
deba@459
  1873
    /// negative objective value in case of minimization, and positive
deba@459
  1874
    /// objective value for maximization. If there is such solution,
deba@459
  1875
    /// that proofs the unsolvability of the dual problem, and if a
deba@459
  1876
    /// feasible primal solution exists, then the unboundness of
deba@459
  1877
    /// primal problem.
deba@459
  1878
    ///
deba@459
  1879
    /// \pre The problem is solved and the dual problem is infeasible.
deba@459
  1880
    /// \note Some solvers does not provide primal ray calculation
deba@459
  1881
    /// functions.
deba@459
  1882
    Value primalRay(Col c) const { return _getPrimalRay(cols(id(c))); }
deba@458
  1883
deba@459
  1884
    /// Return the dual value of the row
deba@459
  1885
deba@459
  1886
    /// Return the dual value of the row.
deba@459
  1887
    /// \pre The problem is solved.
deba@459
  1888
    Value dual(Row r) const { return _getDual(rows(id(r))); }
deba@459
  1889
deba@459
  1890
    /// Return the dual value of the dual expression
deba@459
  1891
deba@459
  1892
    /// Return the dual value of the dual expression, i.e. the dot
deba@459
  1893
    /// product of the dual solution and the dual expression.
deba@459
  1894
    /// \pre The problem is solved.
deba@459
  1895
    Value dual(const DualExpr& e) const {
deba@459
  1896
      double res = 0.0;
deba@459
  1897
      for (DualExpr::ConstCoeffIt r(e); r != INVALID; ++r) {
deba@459
  1898
        res += *r * dual(r);
deba@458
  1899
      }
deba@458
  1900
      return res;
deba@458
  1901
    }
deba@458
  1902
deba@459
  1903
    /// Returns a component of the dual ray
deba@459
  1904
    
deba@459
  1905
    /// The dual ray is solution of the modified primal problem, where
deba@459
  1906
    /// we change each finite bound to 0 (i.e. the objective function
deba@459
  1907
    /// coefficients in the primal problem), and we looking for a
deba@459
  1908
    /// ositive objective value. If there is such solution, that
deba@459
  1909
    /// proofs the unsolvability of the primal problem, and if a
deba@459
  1910
    /// feasible dual solution exists, then the unboundness of
deba@459
  1911
    /// dual problem.
deba@459
  1912
    ///
deba@459
  1913
    /// \pre The problem is solved and the primal problem is infeasible.
deba@459
  1914
    /// \note Some solvers does not provide dual ray calculation
deba@459
  1915
    /// functions.
deba@459
  1916
    Value dualRay(Row r) const { return _getDualRay(rows(id(r))); }
deba@458
  1917
deba@459
  1918
    /// Return the basis status of the column
deba@458
  1919
deba@459
  1920
    /// \see VarStatus
deba@459
  1921
    VarStatus colStatus(Col c) const { return _getColStatus(cols(id(c))); }
deba@459
  1922
deba@459
  1923
    /// Return the basis status of the row
deba@459
  1924
deba@459
  1925
    /// \see VarStatus
deba@459
  1926
    VarStatus rowStatus(Row r) const { return _getRowStatus(rows(id(r))); }
deba@459
  1927
deba@459
  1928
    ///The value of the objective function
deba@458
  1929
deba@458
  1930
    ///\return
deba@458
  1931
    ///- \ref INF or -\ref INF means either infeasibility or unboundedness
deba@458
  1932
    /// of the primal problem, depending on whether we minimize or maximize.
deba@458
  1933
    ///- \ref NaN if no primal solution is found.
deba@458
  1934
    ///- The (finite) objective value if an optimal solution is found.
deba@459
  1935
    Value primal() const { return _getPrimalValue()+obj_const_comp;}
deba@458
  1936
    ///@}
deba@458
  1937
deba@459
  1938
    LpSolver* newSolver() {return _newSolver();}
deba@459
  1939
    LpSolver* cloneSolver() {return _cloneSolver();}
deba@459
  1940
deba@459
  1941
  protected:
deba@459
  1942
deba@459
  1943
    virtual LpSolver* _newSolver() const = 0;
deba@459
  1944
    virtual LpSolver* _cloneSolver() const = 0;
deba@458
  1945
  };
deba@458
  1946
deba@458
  1947
deba@458
  1948
  /// \ingroup lp_group
deba@458
  1949
  ///
deba@458
  1950
  /// \brief Common base class for MIP solvers
deba@459
  1951
  ///
deba@459
  1952
  /// This class is an abstract base class for MIP solvers. This class
deba@459
  1953
  /// provides a full interface for set and modify an MIP problem,
deba@459
  1954
  /// solve it and retrieve the solution. You can use one of the
deba@459
  1955
  /// descendants as a concrete implementation, or the \c Lp
deba@459
  1956
  /// default MIP solver. However, if you would like to handle MIP
deba@459
  1957
  /// solvers as reference or pointer in a generic way, you can use
deba@459
  1958
  /// this class directly.
deba@459
  1959
  class MipSolver : virtual public LpBase {
deba@458
  1960
  public:
deba@458
  1961
deba@459
  1962
    /// The problem types for MIP problems
deba@459
  1963
    enum ProblemType {
deba@459
  1964
      ///Feasible solution hasn't been found (but may exist).
deba@459
  1965
      UNDEFINED = 0,
deba@459
  1966
      ///The problem has no feasible solution
deba@459
  1967
      INFEASIBLE = 1,
deba@459
  1968
      ///Feasible solution found
deba@459
  1969
      FEASIBLE = 2,
deba@459
  1970
      ///Optimal solution exists and found
deba@459
  1971
      OPTIMAL = 3,
deba@459
  1972
      ///The cost function is unbounded
deba@459
  1973
      ///
deba@459
  1974
      ///The Mip or at least the relaxed problem is unbounded
deba@459
  1975
      UNBOUNDED = 4
deba@459
  1976
    };
deba@459
  1977
deba@459
  1978
    ///\name Solve the MIP
deba@459
  1979
deba@459
  1980
    ///@{
deba@459
  1981
deba@459
  1982
    /// Solve the MIP problem at hand
deba@459
  1983
    ///
deba@459
  1984
    ///\return The result of the optimization procedure. Possible
deba@459
  1985
    ///values and their meanings can be found in the documentation of
deba@459
  1986
    ///\ref SolveExitStatus.
deba@459
  1987
    SolveExitStatus solve() { return _solve(); }
deba@459
  1988
deba@459
  1989
    ///@}
deba@459
  1990
deba@459
  1991
    ///\name Setting column type
deba@459
  1992
    ///@{
deba@459
  1993
deba@459
  1994
    ///Possible variable (column) types (e.g. real, integer, binary etc.)
deba@458
  1995
    enum ColTypes {
deba@459
  1996
      ///Continuous variable (default)
deba@458
  1997
      REAL = 0,
deba@458
  1998
      ///Integer variable
deba@459
  1999
      INTEGER = 1
deba@458
  2000
    };
deba@458
  2001
deba@459
  2002
    ///Sets the type of the given column to the given type
deba@459
  2003
deba@459
  2004
    ///Sets the type of the given column to the given type.
deba@458
  2005
    ///
deba@458
  2006
    void colType(Col c, ColTypes col_type) {
deba@459
  2007
      _setColType(cols(id(c)),col_type);
deba@458
  2008
    }
deba@458
  2009
deba@458
  2010
    ///Gives back the type of the column.
deba@459
  2011
deba@459
  2012
    ///Gives back the type of the column.
deba@458
  2013
    ///
deba@458
  2014
    ColTypes colType(Col c) const {
deba@459
  2015
      return _getColType(cols(id(c)));
deba@459
  2016
    }
deba@459
  2017
    ///@}
deba@459
  2018
deba@459
  2019
    ///\name Obtain the solution
deba@459
  2020
deba@459
  2021
    ///@{
deba@459
  2022
deba@459
  2023
    /// The type of the MIP problem
deba@459
  2024
    ProblemType type() const {
deba@459
  2025
      return _getType();
deba@458
  2026
    }
deba@458
  2027
deba@459
  2028
    /// Return the value of the row in the solution
deba@459
  2029
deba@459
  2030
    ///  Return the value of the row in the solution.
deba@459
  2031
    /// \pre The problem is solved.
deba@459
  2032
    Value sol(Col c) const { return _getSol(cols(id(c))); }
deba@459
  2033
deba@459
  2034
    /// Return the value of the expression in the solution
deba@459
  2035
deba@459
  2036
    /// Return the value of the expression in the solution, i.e. the
deba@459
  2037
    /// dot product of the solution and the expression.
deba@459
  2038
    /// \pre The problem is solved.
deba@459
  2039
    Value sol(const Expr& e) const {
deba@459
  2040
      double res = *e;
deba@459
  2041
      for (Expr::ConstCoeffIt c(e); c != INVALID; ++c) {
deba@459
  2042
        res += *c * sol(c);
deba@459
  2043
      }
deba@459
  2044
      return res;
deba@458
  2045
    }
deba@459
  2046
    ///The value of the objective function
deba@459
  2047
    
deba@459
  2048
    ///\return
deba@459
  2049
    ///- \ref INF or -\ref INF means either infeasibility or unboundedness
deba@459
  2050
    /// of the problem, depending on whether we minimize or maximize.
deba@459
  2051
    ///- \ref NaN if no primal solution is found.
deba@459
  2052
    ///- The (finite) objective value if an optimal solution is found.
deba@459
  2053
    Value solValue() const { return _getSolValue()+obj_const_comp;}
deba@459
  2054
    ///@}
deba@458
  2055
deba@458
  2056
  protected:
deba@458
  2057
deba@459
  2058
    virtual SolveExitStatus _solve() = 0;
deba@459
  2059
    virtual ColTypes _getColType(int col) const = 0;
deba@459
  2060
    virtual void _setColType(int col, ColTypes col_type) = 0;
deba@459
  2061
    virtual ProblemType _getType() const = 0;
deba@459
  2062
    virtual Value _getSol(int i) const = 0;
deba@459
  2063
    virtual Value _getSolValue() const = 0;
deba@458
  2064
deba@459
  2065
  public:
deba@459
  2066
deba@459
  2067
    MipSolver* newSolver() {return _newSolver();}
deba@459
  2068
    MipSolver* cloneSolver() {return _cloneSolver();}
deba@459
  2069
deba@459
  2070
  protected:
deba@459
  2071
deba@459
  2072
    virtual MipSolver* _newSolver() const = 0;
deba@459
  2073
    virtual MipSolver* _cloneSolver() const = 0;
deba@458
  2074
  };
deba@458
  2075
deba@458
  2076
deba@458
  2077
deba@458
  2078
} //namespace lemon
deba@458
  2079
deba@458
  2080
#endif //LEMON_LP_BASE_H