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.

    ///

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

    ///other rows.

    ///

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

    ///Node and Arc types in digraph.

    class Row {

      friend class LpBase;

    protected:

      int _id;

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

    public:

      typedef Value ExprValue;

      typedef True LpRow;

      /// Default constructor

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

      /// undefined value.

      Row() {}

      /// Invalid constructor \& conversion.

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

      /// \sa Invalid for more details.

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

      /// Equality operator

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

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

      bool operator==(Row r) const  {return _id == r._id;}

      /// Inequality operator

      /// \sa operator==(Row r)

      ///

      bool operator!=(Row r) const  {return _id != r._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<(Row r) const  {return _id < r._id;}

    };

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

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

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

    ///\code

    /// int count=0;

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

    ///\endcode

    class RowIt : public Row {

      const LpBase *_solver;

    public:

      /// Default constructor

      /// \warning The default constructor sets the iterator

      /// to an undefined value.

      RowIt() {}

      /// Sets the iterator to the first Row

      /// Sets the iterator to the first Row.

      ///

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

      {

        _solver->rows.firstItem(_id);

      }

      /// Invalid constructor \& conversion

      /// Initialize the iterator to be invalid.

      /// \sa Invalid for more details.

      RowIt(const Invalid&) : Row(INVALID) {}

      /// Next row

      /// Assign the iterator to the next row.

      ///

      RowIt &operator++()

      {

        _solver->rows.nextItem(_id);

        return *this;

      }

    };

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

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

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

    ///

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

    static Row rowFromId(int id) { return Row(id); }

  public:

    ///Linear expression of variables and a constant component

    ///This data structure stores a linear expression of the variables

    ///(\ref Col "Col"s) and also has a constant component.

    ///

    ///There are several ways to access and modify the contents of this

    ///container.

    ///\code

    ///e[v]=5;

    ///e[v]+=12;

    ///e.erase(v);

    ///\endcode

    ///or you can also iterate through its elements.

    ///\code

    ///double s=0;

    ///for(LpBase::Expr::ConstCoeffIt i(e);i!=INVALID;++i)

    ///  s+=*i * primal(i);

    ///\endcode

    ///(This code computes the primal value of the expression).

    ///- Numbers (<tt>double</tt>'s)

    ///and variables (\ref Col "Col"s) directly convert to an

    ///\ref Expr and the usual linear operations are defined, so

    ///\code

    ///v+w

    ///2*v-3.12*(v-w/2)+2

    ///v*2.1+(3*v+(v*12+w+6)*3)/2

    ///\endcode

    ///are valid expressions.

    ///The usual assignment operations are also defined.

    ///\code

    ///e=v+w;

    ///e+=2*v-3.12*(v-w/2)+2;

    ///e*=3.4;

    ///e/=5;

    ///\endcode

    ///- The constant member can be set and read by dereference

    ///  operator (unary *)

    ///

    ///\code

    ///*e=12;

    ///double c=*e;

    ///\endcode

    ///

    ///\sa Constr

    class Expr {

      friend class LpBase;

    public:

      /// The key type of the expression

      typedef LpBase::Col Key;

      /// The value type of the expression

      typedef LpBase::Value Value;

    protected:

      Value const_comp;

      std::map<int, Value> comps;

    public:

      typedef True SolverExpr;

      /// Default constructor

      /// Construct an empty expression, the coefficients and

      /// the constant component are initialized to zero.

      Expr() : const_comp(0) {}

      /// Construct an expression from a column

      /// Construct an expression, which has a term with \c c variable

      /// and 1.0 coefficient.

      Expr(const Col &c) : const_comp(0) {

        typedef std::map<int, Value>::value_type pair_type;

        comps.insert(pair_type(id(c), 1));

      }

      /// Construct an expression from a constant

      /// Construct an expression, which's constant component is \c v.

      ///

      Expr(const Value &v) : const_comp(v) {}

      /// Returns the coefficient of the column

      Value operator[](const Col& c) const {

        std::map<int, Value>::const_iterator it=comps.find(id(c));

        if (it != comps.end()) {

          return it->second;

        } else {

          return 0;

        }

      }

      /// Returns the coefficient of the column

      Value& operator[](const Col& c) {

        return comps[id(c)];

      }

      /// Sets the coefficient of the column

      void set(const Col &c, const Value &v) {

        if (v != 0.0) {

          typedef std::map<int, Value>::value_type pair_type;

          comps.insert(pair_type(id(c), v));

        } else {

          comps.erase(id(c));

        }

      }

      /// Returns the constant component of the expression

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

 *

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

 *

 * Copyright (C) 2003-2011

 * 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 <lemon/list_graph.h>

#include <lemon/lgf_reader.h>

#include "test_tools.h"

using namespace lemon;

char test_lgf[] =

  "@nodes\n"

  "label\n"

  "0\n"

  "1\n"

  "@arcs\n"

  "     label\n"

  "0 1  0\n"

  "1 0  1\n"

  "@attributes\n"

  "source 0\n"

  "target 1\n";

char test_lgf_nomap[] =

  "@nodes\n"

  "label\n"

  "0\n"

  "1\n"

  "@arcs\n"

  "     -\n"

  "0 1\n";

char test_lgf_bad1[] =

  "@nodes\n"

  "label\n"

  "0\n"

  "1\n"

  "@arcs\n"

  "     - another\n"

  "0 1\n";

char test_lgf_bad2[] =

  "@nodes\n"

  "label\n"

  "0\n"

  "1\n"

  "@arcs\n"

  "     label -\n"

  "0 1\n";

int main()

{

  {

    ListDigraph d;

    ListDigraph::Node s,t;

    ListDigraph::ArcMap<int> label(d);

    std::istringstream input(test_lgf);

    digraphReader(d, input).

      node("source", s).

      node("target", t).

      arcMap("label", label).

      run();

    check(countNodes(d) == 2,"There should be 2 nodes");

    check(countArcs(d) == 2,"There should be 2 arcs");

  }

  {

    ListGraph g;

    ListGraph::Node s,t;

    ListGraph::EdgeMap<int> label(g);

    std::istringstream input(test_lgf);

    graphReader(g, input).

      node("source", s).

      node("target", t).

      edgeMap("label", label).

      run();

    check(countNodes(g) == 2,"There should be 2 nodes");

    check(countEdges(g) == 2,"There should be 2 arcs");

  }

  {

    ListDigraph d;

    std::istringstream input(test_lgf_nomap);

    digraphReader(d, input).

      run();

    check(countNodes(d) == 2,"There should be 2 nodes");

    check(countArcs(d) == 1,"There should be 1 arc");

  }

  {

    ListGraph g;

    std::istringstream input(test_lgf_nomap);

    graphReader(g, input).

      run();

    check(countNodes(g) == 2,"There should be 2 nodes");

    check(countEdges(g) == 1,"There should be 1 edge");

  }

  {

    ListDigraph d;

    std::istringstream input(test_lgf_bad1);

    bool ok=false;

    try {

      digraphReader(d, input).

        run();

    }

      {

        ok = true;

      }

    check(ok,"FormatError exception should have occured");

  }

  {

    ListGraph g;

    std::istringstream input(test_lgf_bad1);

    bool ok=false;

    try {

      graphReader(g, input).

        run();

    }

    catch (FormatError&)

      {

        ok = true;

      }

    check(ok,"FormatError exception should have occured");

  }

  {

    ListDigraph d;

    std::istringstream input(test_lgf_bad2);

    bool ok=false;

    try {

      digraphReader(d, input).

        run();

    }

    catch (FormatError&)

      {

        ok = true;

      }

    check(ok,"FormatError exception should have occured");

  }

  {

    ListGraph g;

    std::istringstream input(test_lgf_bad2);

    bool ok=false;

    try {

      graphReader(g, input).

        run();

    }

    catch (FormatError&)

      {

        ok = true;

      }

    check(ok,"FormatError exception should have occured");

  }

}

/* -*- 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);

    buf << "Coeff. of p2 should be 0.01";

    check(e[p2]>0, buf.str());

    tolerance=0.02;

    e.simplify(tolerance);

    buf << "Coeff. of p2 should be 0";

    check(const_cast<const LpSolver::Expr&>(e)[p2]==0, buf.str());

    //Test for clone/new

    LP* lpnew = lp.newSolver();

    LP* lpclone = lp.cloneSolver();

    delete lpnew;

    delete lpclone;

  }

  {

    LP::DualExpr e,f,g;

    LP::Row p1 = INVALID, p2 = INVALID, p3 = INVALID,

      p4 = INVALID, p5 = INVALID;

    e[p1]=2;

    e[p1]+=2;

    e[p1]-=2;

    e=p1;

    e=f;

    e+=p1;

    e+=f;

    e-=p1;

    e-=f;

    e*=2;

    e*=2.2;

    e/=2;

    e/=2.2;

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

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

       (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

       );

  }

}

void solveAndCheck(LpSolver& lp, LpSolver::ProblemType stat,

                   double exp_opt) {

  using std::string;

  lp.solve();

  std::ostringstream buf;

  buf << "PrimalType should be: " << int(stat) << int(lp.primalType());

  check(lp.primalType()==stat, buf.str());

  if (stat ==  LpSolver::OPTIMAL) {

    std::ostringstream sbuf;

    sbuf << "Wrong optimal value (" << lp.primal() <<") with "

         << lp.solverName() <<"\n     the right optimum is " << exp_opt;

    check(std::abs(lp.primal()-exp_opt) < 1e-3, sbuf.str());

  }

}

void aTest(LpSolver & lp)

{

  typedef LpSolver LP;

 //The following example is very simple

  typedef LpSolver::Row Row;

  typedef LpSolver::Col Col;

  Col x1 = lp.addCol();

  Col x2 = lp.addCol();

  //Constraints

  Row upright=lp.addRow(x1+2*x2 <=1);

  lp.addRow(x1+x2 >=-1);

  lp.addRow(x1-x2 <=1);

  lp.addRow(x1-x2 >=-1);

  //Nonnegativity of the variables

  lp.colLowerBound(x1, 0);

  lp.colLowerBound(x2, 0);

  //Objective function

  lp.obj(x1+x2);

  lp.sense(lp.MAX);

  //Testing the problem retrieving routines

  check(lp.objCoeff(x1)==1,"First term should be 1 in the obj function!");

  check(lp.sense() == lp.MAX,"This is a maximization!");

  check(lp.coeff(upright,x1)==1,"The coefficient in question is 1!");

  check(lp.colLowerBound(x1)==0,

        "The lower bound for variable x1 should be 0.");

  check(lp.colUpperBound(x1)==LpSolver::INF,

        "The upper bound for variable x1 should be infty.");

  check(lp.rowLowerBound(upright) == -LpSolver::INF,

        "The lower bound for the first row should be -infty.");

  check(lp.rowUpperBound(upright)==1,

        "The upper bound for the first row should be 1.");

  LpSolver::Expr e = lp.row(upright);

  check(e[x1] == 1, "The first coefficient should 1.");

  check(e[x2] == 2, "The second coefficient should 1.");

  lp.row(upright, x1+x2 <=1);

  e = lp.row(upright);

  check(e[x1] == 1, "The first coefficient should 1.");

  check(e[x2] == 1, "The second coefficient should 1.");

  LpSolver::DualExpr de = lp.col(x1);

  check(  de[upright] == 1, "The first coefficient should 1.");

  LpSolver* clp = lp.cloneSolver();

  //Testing the problem retrieving routines

  check(clp->objCoeff(x1)==1,"First term should be 1 in the obj function!");

  check(clp->sense() == clp->MAX,"This is a maximization!");

  check(clp->coeff(upright,x1)==1,"The coefficient in question is 1!");

  //  std::cout<<lp.colLowerBound(x1)<<std::endl;

  check(clp->colLowerBound(x1)==0,

        "The lower bound for variable x1 should be 0.");

  check(clp->colUpperBound(x1)==LpSolver::INF,

        "The upper bound for variable x1 should be infty.");

  check(lp.rowLowerBound(upright)==-LpSolver::INF,

        "The lower bound for the first row should be -infty.");

  check(lp.rowUpperBound(upright)==1,

        "The upper bound for the first row should be 1.");

  e = clp->row(upright);

  check(e[x1] == 1, "The first coefficient should 1.");

  check(e[x2] == 1, "The second coefficient should 1.");

  de = clp->col(x1);

  check(de[upright] == 1, "The first coefficient should 1.");

  delete clp;

  //Maximization of x1+x2

  //over the triangle with vertices (0,0) (0,1) (1,0)

  double expected_opt=1;

  solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);

  //Minimization

  lp.sense(lp.MIN);

  expected_opt=0;

  solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);

  //Vertex (-1,0) instead of (0,0)

  lp.colLowerBound(x1, -LpSolver::INF);

  expected_opt=-1;

  solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);

  //Erase one constraint and return to maximization

  lp.erase(upright);

  lp.sense(lp.MAX);

  expected_opt=LpSolver::INF;

  solveAndCheck(lp, LpSolver::UNBOUNDED, expected_opt);

  //Infeasibilty

  lp.addRow(x1+x2 <=-2);

  solveAndCheck(lp, LpSolver::INFEASIBLE, expected_opt);

}

template<class LP>

void cloneTest()

{

  //Test for clone/new

  LP* lp = new LP();

  LP* lpnew = lp->newSolver();

  LP* lpclone = lp->cloneSolver();

  delete lp;

  delete lpnew;

  delete lpclone;

}

int main()

{

  LpSkeleton lp_skel;

  lpTest(lp_skel);

#ifdef LEMON_HAVE_GLPK

  {