RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_LP_BASE_H

#define LEMON_LP_BASE_H

#include<iostream>

#include<vector>

#include<map>

#include<limits>

#include<lemon/math.h>

#include<lemon/error.h>

#include<lemon/assert.h>

#include<lemon/core.h>

#include<lemon/bits/solver_bits.h>

///\file

///\brief The interface of the LP solver interface.

///\ingroup lp_group

namespace lemon {

  ///Common base class for LP and MIP solvers

  ///Usually this class is not used directly, please use one of the concrete

  ///implementations of the solver interface.

  ///\ingroup lp_group

  class LpBase {

  protected:

    _solver_bits::VarIndex rows;

    _solver_bits::VarIndex cols;

  public:

    ///Possible outcomes of an LP solving procedure

    enum SolveExitStatus {

      /// = 0. It means that the problem has been successfully solved: either

      ///an optimal solution has been found or infeasibility/unboundedness

      ///has been proved.

      SOLVED = 0,

      /// = 1. Any other case (including the case when some user specified

      ///limit has been exceeded).

      UNSOLVED = 1

    };

    ///Direction of the optimization

    enum Sense {

      /// Minimization

      MIN,

      /// Maximization

      MAX

    };

    ///Enum for \c messageLevel() parameter

    enum MessageLevel {

      /// No output (default value).

      MESSAGE_NOTHING,

      /// Error messages only.

      MESSAGE_ERROR,

      /// Warnings.

      MESSAGE_WARNING,

      /// Normal output.

      MESSAGE_NORMAL,

      /// Verbose output.

      MESSAGE_VERBOSE

    };

    ///The floating point type used by the solver

    typedef double Value;

    ///The infinity constant

    static const Value INF;

    ///The not a number constant

    static const Value NaN;

    friend class Col;

    friend class ColIt;

    friend class Row;

    friend class RowIt;

    ///Refer to a column of the LP.

    ///This type is used to refer to a column of the LP.

    ///

    ///Its value remains valid and correct even after the addition or erase of

    ///other columns.

    ///

    ///\note This class is similar to other Item types in LEMON, like

    ///Node and Arc types in digraph.

    class Col {

      friend class LpBase;

    protected:

      int _id;

      explicit Col(int id) : _id(id) {}

    public:

      typedef Value ExprValue;

      typedef True LpCol;

      /// Default constructor

      /// \warning The default constructor sets the Col to an

      /// undefined value.

      Col() {}

      /// Invalid constructor \& conversion.

      /// This constructor initializes the Col to be invalid.

      /// \sa Invalid for more details.

      Col(const Invalid&) : _id(-1) {}

      /// Equality operator

      /// Two \ref Col "Col"s are equal if and only if they point to

      /// the same LP column or both are invalid.

      bool operator==(Col c) const  {return _id == c._id;}

      /// Inequality operator

      /// \sa operator==(Col c)

      ///

      bool operator!=(Col c) const  {return _id != c._id;}

      /// Artificial ordering operator.

      /// To allow the use of this object in std::map or similar

      /// associative container we require this.

      ///

      /// \note This operator only have to define some strict ordering of

      /// the items; this order has nothing to do with the iteration

      /// ordering of the items.

      bool operator<(Col c) const  {return _id < c._id;}

    };

    ///Iterator for iterate over the columns of an LP problem

    /// Its usage is quite simple, for example, you can count the number

    /// of columns in an LP \c lp:

    ///\code

    /// int count=0;

    /// for (LpBase::ColIt c(lp); c!=INVALID; ++c) ++count;

    ///\endcode

    class ColIt : public Col {

      const LpBase *_solver;

    public:

      /// Default constructor

      /// \warning The default constructor sets the iterator

      /// to an undefined value.

      ColIt() {}

      /// Sets the iterator to the first Col

      /// Sets the iterator to the first Col.

      ///

      ColIt(const LpBase &solver) : _solver(&solver)

      {

        _solver->cols.firstItem(_id);

      }

      /// Invalid constructor \& conversion

      /// Initialize the iterator to be invalid.

      /// \sa Invalid for more details.

      ColIt(const Invalid&) : Col(INVALID) {}

      /// Next column

      /// Assign the iterator to the next column.

      ///

      ColIt &operator++()

      {

        _solver->cols.nextItem(_id);

        return *this;

      }

    };

    /// \brief Returns the ID of the column.

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

    /// \brief Returns the column with the given ID.

    ///

    /// \pre The argument should be a valid column ID in the LP problem.

    static Col colFromId(int id) { return Col(id); }

    ///Refer to a row of the LP.

    ///This type is used to refer to a row of the LP.

    ///

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#include <sstream>

#include <lemon/lp_skeleton.h>

#include "test_tools.h"

#include <lemon/tolerance.h>

#include <lemon/config.h>

#ifdef LEMON_HAVE_GLPK

#include <lemon/glpk.h>

#endif

#ifdef LEMON_HAVE_CPLEX

#include <lemon/cplex.h>

#endif

#ifdef LEMON_HAVE_SOPLEX

#include <lemon/soplex.h>

#endif

#ifdef LEMON_HAVE_CLP

#include <lemon/clp.h>

#endif

using namespace lemon;

void lpTest(LpSolver& lp)

{

  typedef LpSolver LP;

  std::vector<LP::Col> x(10);

  //  for(int i=0;i<10;i++) x.push_back(lp.addCol());

  lp.addColSet(x);

  lp.colLowerBound(x,1);

  lp.colUpperBound(x,1);

  lp.colBounds(x,1,2);

  std::vector<LP::Col> y(10);

  lp.addColSet(y);

  lp.colLowerBound(y,1);

  lp.colUpperBound(y,1);

  lp.colBounds(y,1,2);

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

  z.insert(std::make_pair(12,INVALID));

  z.insert(std::make_pair(2,INVALID));

  z.insert(std::make_pair(7,INVALID));

  z.insert(std::make_pair(5,INVALID));

  lp.addColSet(z);

  lp.colLowerBound(z,1);

  lp.colUpperBound(z,1);

  lp.colBounds(z,1,2);

  {

    LP::Expr e,f,g;

    LP::Col p1,p2,p3,p4,p5;

    LP::Constr c;

    p1=lp.addCol();

    p2=lp.addCol();

    p3=lp.addCol();

    p4=lp.addCol();

    p5=lp.addCol();

    e[p1]=2;

    *e=12;

    e[p1]+=2;

    *e+=12;

    e[p1]-=2;

    *e-=12;

    e=2;

    e=2.2;

    e=p1;

    e=f;

    e+=2;

    e+=2.2;

    e+=p1;

    e+=f;

    e-=2;

    e-=2.2;

    e-=p1;

    e-=f;

    e*=2;

    e*=2.2;

    e/=2;

    e/=2.2;

    e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+

       (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+

       (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+

       2.2*f+f*2.2+f/2.2+

       2*f+f*2+f/2+

       2.2*p1+p1*2.2+p1/2.2+

       2*p1+p1*2+p1/2

       );

    c = (e  <= f  );

    c = (e  <= 2.2);

    c = (e  <= 2  );

    c = (e  <= p1 );

    c = (2.2<= f  );

    c = (2  <= f  );

    c = (p1 <= f  );

    c = (p1 <= p2 );

    c = (p1 <= 2.2);

    c = (p1 <= 2  );

    c = (2.2<= p2 );

    c = (2  <= p2 );

    c = (e  >= f  );

    c = (e  >= 2.2);

    c = (e  >= 2  );

    c = (e  >= p1 );

    c = (2.2>= f  );

    c = (2  >= f  );

    c = (p1 >= f  );

    c = (p1 >= p2 );

    c = (p1 >= 2.2);

    c = (p1 >= 2  );

    c = (2.2>= p2 );

    c = (2  >= p2 );

    c = (e  == f  );

    c = (e  == 2.2);

    c = (e  == 2  );

    c = (e  == p1 );

    c = (2.2== f  );

    c = (2  == f  );

    c = (p1 == f  );

    //c = (p1 == p2 );

    c = (p1 == 2.2);

    c = (p1 == 2  );

    c = (2.2== p2 );

    c = (2  == p2 );

    c = ((2 <= e) <= 3);

    c = ((2 <= p1) <= 3);

    c = ((2 >= e) >= 3);

    c = ((2 >= p1) >= 3);

    { //Tests for #430

      LP::Col v=lp.addCol();

      LP::Constr c = v >= -3;

      c = c <= 4;

      LP::Constr c2;

      c2 = -3 <= v <= 4;

    }

    e[x[3]]=2;

    e[x[3]]=4;

    e[x[3]]=1;

    *e=12;

    lp.addRow(-LP::INF,e,23);

    lp.addRow(-LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);

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

    lp.addRow(x[1]+x[3]<=x[5]-3);

    lp.addRow((-7<=x[1]+x[3]-12)<=3);

    lp.addRow(x[1]<=x[5]);

    std::ostringstream buf;

    e=((p1+p2)+(p1-0.99*p2));

    //e.prettyPrint(std::cout);

    //(e<=2).prettyPrint(std::cout);

    double tolerance=0.001;

    e.simplify(tolerance);