1.1 --- a/configure.ac Mon Jan 12 12:22:11 2009 +0000
1.2 +++ b/configure.ac Tue Dec 02 21:40:33 2008 +0100
1.3 @@ -50,9 +50,9 @@
1.4 AC_SUBST([WARNINGCXXFLAGS])
1.5
1.6 dnl Checks for libraries.
1.7 -#LX_CHECK_GLPK
1.8 -#LX_CHECK_CPLEX
1.9 -#LX_CHECK_SOPLEX
1.10 +LX_CHECK_GLPK
1.11 +LX_CHECK_CPLEX
1.12 +LX_CHECK_SOPLEX
1.13
1.14 AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
1.15 AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
1.16 @@ -117,10 +117,10 @@
1.17 echo C++ compiler.................. : $CXX
1.18 echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
1.19 echo
1.20 -#echo GLPK support.................. : $lx_glpk_found
1.21 -#echo CPLEX support................. : $lx_cplex_found
1.22 -#echo SOPLEX support................ : $lx_soplex_found
1.23 -#echo
1.24 +echo GLPK support.................. : $lx_glpk_found
1.25 +echo CPLEX support................. : $lx_cplex_found
1.26 +echo SOPLEX support................ : $lx_soplex_found
1.27 +echo
1.28 echo Build demo programs........... : $enable_demo
1.29 echo Build additional tools........ : $enable_tools
1.30 echo
2.1 --- a/lemon/CMakeLists.txt Mon Jan 12 12:22:11 2009 +0000
2.2 +++ b/lemon/CMakeLists.txt Tue Dec 02 21:40:33 2008 +0100
2.3 @@ -4,6 +4,9 @@
2.4 arg_parser.cc
2.5 base.cc
2.6 color.cc
2.7 + lp_base.cc
2.8 + lp_skeleton.cc
2.9 + lp_utils.cc
2.10 random.cc)
2.11
2.12 INSTALL(
3.1 --- a/lemon/Makefile.am Mon Jan 12 12:22:11 2009 +0000
3.2 +++ b/lemon/Makefile.am Tue Dec 02 21:40:33 2008 +0100
3.3 @@ -10,10 +10,32 @@
3.4 lemon/arg_parser.cc \
3.5 lemon/base.cc \
3.6 lemon/color.cc \
3.7 + lemon/lp_base.cc \
3.8 + lemon/lp_skeleton.cc \
3.9 lemon/random.cc
3.10
3.11 -#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) $(AM_CXXFLAGS)
3.12 -#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
3.13 +
3.14 +lemon_libemon_la_CXXFLAGS = \
3.15 + $(GLPK_CFLAGS) \
3.16 + $(CPLEX_CFLAGS) \
3.17 + $(SOPLEX_CXXFLAGS)
3.18 +
3.19 +lemon_libemon_la_LDFLAGS = \
3.20 + $(GLPK_LIBS) \
3.21 + $(CPLEX_LIBS) \
3.22 + $(SOPLEX_LIBS)
3.23 +
3.24 +if HAVE_GLPK
3.25 +lemon_libemon_la_SOURCES += lemon/lp_glpk.cc lemon/mip_glpk.cc
3.26 +endif
3.27 +
3.28 +if HAVE_CPLEX
3.29 +lemon_libemon_la_SOURCES += lemon/lp_cplex.cc lemon/mip_cplex.cc
3.30 +endif
3.31 +
3.32 +if HAVE_SOPLEX
3.33 +lemon_libemon_la_SOURCES += lemon/lp_soplex.cc
3.34 +endif
3.35
3.36 lemon_HEADERS += \
3.37 lemon/adaptors.h \
3.38 @@ -41,6 +63,14 @@
3.39 lemon/lgf_reader.h \
3.40 lemon/lgf_writer.h \
3.41 lemon/list_graph.h \
3.42 + lemon/lp.h \
3.43 + lemon/lp_base.h \
3.44 + lemon/lp_cplex.h \
3.45 + lemon/lp_glpk.h \
3.46 + lemon/lp_skeleton.h \
3.47 + lemon/lp_soplex.h \
3.48 + lemon/mip_cplex.h \
3.49 + lemon/mip_glpk.h \
3.50 lemon/maps.h \
3.51 lemon/math.h \
3.52 lemon/max_matching.h \
3.53 @@ -64,6 +94,7 @@
3.54 lemon/bits/enable_if.h \
3.55 lemon/bits/graph_adaptor_extender.h \
3.56 lemon/bits/graph_extender.h \
3.57 + lemon/bits/lp_id.h \
3.58 lemon/bits/map_extender.h \
3.59 lemon/bits/path_dump.h \
3.60 lemon/bits/traits.h \
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/bits/lp_id.h Tue Dec 02 21:40:33 2008 +0100
4.3 @@ -0,0 +1,157 @@
4.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library.
4.7 + *
4.8 + * Copyright (C) 2003-2008
4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 + *
4.12 + * Permission to use, modify and distribute this software is granted
4.13 + * provided that this copyright notice appears in all copies. For
4.14 + * precise terms see the accompanying LICENSE file.
4.15 + *
4.16 + * This software is provided "AS IS" with no warranty of any kind,
4.17 + * express or implied, and with no claim as to its suitability for any
4.18 + * purpose.
4.19 + *
4.20 + */
4.21 +
4.22 +#ifndef LEMON_BITS_LP_SOLVER_ID_H
4.23 +#define LEMON_BITS_LP_SOLVER_ID_H
4.24 +
4.25 +namespace lemon {
4.26 +
4.27 + namespace _lp_bits {
4.28 +
4.29 + struct LpIdImpl {
4.30 + std::vector<int> index;
4.31 + std::vector<int> cross;
4.32 + int first_index;
4.33 + int first_free;
4.34 + };
4.35 +
4.36 + class LpId {
4.37 + public:
4.38 +
4.39 + class IdHandler {
4.40 + public:
4.41 + virtual ~IdHandler() {}
4.42 + virtual int addId(LpIdImpl&) = 0;
4.43 + virtual void eraseId(LpIdImpl&, int xn) = 0;
4.44 + };
4.45 +
4.46 + LpId(int min_index = 0) {
4.47 + id_handler = 0;
4.48 + impl.first_free = -1;
4.49 + impl.first_index = min_index;
4.50 + impl.cross.resize(impl.first_index);
4.51 + }
4.52 +
4.53 + LpId(const LpId& li) {
4.54 + id_handler = 0;
4.55 + impl = li.impl;
4.56 + }
4.57 +
4.58 + LpId& operator=(const LpId& li) {
4.59 + id_handler = 0;
4.60 + impl = li.impl;
4.61 + return *this;
4.62 + }
4.63 +
4.64 + void setIdHandler(IdHandler& ih) {
4.65 + id_handler = &ih;
4.66 + }
4.67 +
4.68 + int fixId(int fn) const {return impl.cross[fn];}
4.69 + int floatingId(int xn) const {return impl.index[xn];}
4.70 +
4.71 + int addId() {
4.72 + if (id_handler == 0) {
4.73 + int xn, fn = impl.cross.size();
4.74 + if (impl.first_free == -1) {
4.75 + xn = impl.index.size();
4.76 + impl.index.push_back(fn);
4.77 + } else {
4.78 + xn = impl.first_free;
4.79 + impl.first_free = impl.index[impl.first_free];
4.80 + impl.index[xn] = fn;
4.81 + }
4.82 + impl.cross.push_back(xn);
4.83 + return xn;
4.84 + } else {
4.85 + return id_handler->addId(impl);
4.86 + }
4.87 + }
4.88 +
4.89 + void eraseId(int xn) {
4.90 + if (id_handler == 0) {
4.91 + int fn = impl.index[xn];
4.92 + impl.index[xn] = impl.first_free;
4.93 + impl.first_free = xn;
4.94 + for(int i = fn + 1; i < int(impl.cross.size()); ++i) {
4.95 + impl.cross[i - 1] = impl.cross[i];
4.96 + impl.index[impl.cross[i]]--;
4.97 + }
4.98 + impl.cross.pop_back();
4.99 + } else {
4.100 + id_handler->eraseId(impl, xn);
4.101 + }
4.102 + }
4.103 +
4.104 + void firstFloating(int& fn) const {
4.105 + fn = impl.first_index;
4.106 + if (fn == int(impl.cross.size())) fn = -1;
4.107 + }
4.108 +
4.109 + void nextFloating(int& fn) const {
4.110 + ++fn;
4.111 + if (fn == int(impl.cross.size())) fn = -1;
4.112 + }
4.113 +
4.114 + void firstFix(int& xn) const {
4.115 + int fn;
4.116 + firstFloating(fn);
4.117 + xn = fn != -1 ? fixId(fn) : -1;
4.118 + }
4.119 +
4.120 + void nextFix(int& xn) const {
4.121 + int fn = floatingId(xn);
4.122 + nextFloating(fn);
4.123 + xn = fn != -1 ? fixId(fn) : -1;
4.124 + }
4.125 +
4.126 + protected:
4.127 + LpIdImpl impl;
4.128 + IdHandler *id_handler;
4.129 + };
4.130 +
4.131 + class RelocateIdHandler : public LpId::IdHandler {
4.132 + public:
4.133 +
4.134 + virtual int addId(LpIdImpl& impl) {
4.135 + int xn, fn = impl.cross.size();
4.136 + if (impl.first_free == -1) {
4.137 + xn = impl.index.size();
4.138 + impl.index.push_back(fn);
4.139 + } else {
4.140 + xn = impl.first_free;
4.141 + impl.first_free = impl.index[impl.first_free];
4.142 + impl.index[xn] = fn;
4.143 + }
4.144 + impl.cross.push_back(xn);
4.145 + return xn;
4.146 + }
4.147 +
4.148 + virtual void eraseId(LpIdImpl& impl, int xn) {
4.149 + int fn = impl.index[xn];
4.150 + impl.index[xn] = impl.first_free;
4.151 + impl.first_free = xn;
4.152 + impl.cross[fn] = impl.cross.back();
4.153 + impl.index[impl.cross.back()] = fn;
4.154 + impl.cross.pop_back();
4.155 + }
4.156 + };
4.157 + }
4.158 +}
4.159 +
4.160 +#endif
5.1 --- a/lemon/config.h.in Mon Jan 12 12:22:11 2009 +0000
5.2 +++ b/lemon/config.h.in Tue Dec 02 21:40:33 2008 +0100
5.3 @@ -9,3 +9,6 @@
5.4
5.5 /* Define to 1 if you have GLPK. */
5.6 #undef HAVE_GLPK
5.7 +
5.8 +/* Define to 1 if you have SOPLEX */
5.9 +#undef HAVE_SOPLEX
5.10 \ No newline at end of file
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/lemon/lp.h Tue Dec 02 21:40:33 2008 +0100
6.3 @@ -0,0 +1,90 @@
6.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
6.5 + *
6.6 + * This file is a part of LEMON, a generic C++ optimization library.
6.7 + *
6.8 + * Copyright (C) 2003-2008
6.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
6.11 + *
6.12 + * Permission to use, modify and distribute this software is granted
6.13 + * provided that this copyright notice appears in all copies. For
6.14 + * precise terms see the accompanying LICENSE file.
6.15 + *
6.16 + * This software is provided "AS IS" with no warranty of any kind,
6.17 + * express or implied, and with no claim as to its suitability for any
6.18 + * purpose.
6.19 + *
6.20 + */
6.21 +
6.22 +#ifndef LEMON_LP_H
6.23 +#define LEMON_LP_H
6.24 +
6.25 +#include<lemon/config.h>
6.26 +
6.27 +
6.28 +#ifdef HAVE_GLPK
6.29 +#include <lemon/lp_glpk.h>
6.30 +#include <lemon/mip_glpk.h>
6.31 +#elif HAVE_CPLEX
6.32 +#include <lemon/lp_cplex.h>
6.33 +#include <lemon/mip_cplex.h>
6.34 +#elif HAVE_SOPLEX
6.35 +#include <lemon/lp_soplex.h>
6.36 +#endif
6.37 +
6.38 +///\file
6.39 +///\brief Defines a default LP solver
6.40 +///\ingroup lp_group
6.41 +namespace lemon {
6.42 +
6.43 +#ifdef DOXYGEN
6.44 + ///The default LP solver identifier
6.45 +
6.46 + ///The default LP solver identifier.
6.47 + ///\ingroup lp_group
6.48 + ///
6.49 + ///Currently, the possible values are \c GLPK or \c CPLEX
6.50 +#define DEFAULT_LP SOLVER
6.51 + ///The default LP solver
6.52 +
6.53 + ///The default LP solver.
6.54 + ///\ingroup lp_group
6.55 + ///
6.56 + ///Currently, it is either \c LpGlpk or \c LpCplex
6.57 + typedef LpGlpk Lp;
6.58 + ///The default LP solver identifier string
6.59 +
6.60 + ///The default LP solver identifier string.
6.61 + ///\ingroup lp_group
6.62 + ///
6.63 + ///Currently, the possible values are "GLPK" or "CPLEX"
6.64 + const char default_solver_name[]="SOLVER";
6.65 +
6.66 + ///The default ILP solver.
6.67 +
6.68 + ///The default ILP solver.
6.69 + ///\ingroup lp_group
6.70 + ///
6.71 + ///Currently, it is either \c LpGlpk or \c LpCplex
6.72 + typedef MipGlpk Mip;
6.73 +#else
6.74 +#ifdef HAVE_GLPK
6.75 +#define DEFAULT_LP GLPK
6.76 + typedef LpGlpk Lp;
6.77 + typedef MipGlpk Mip;
6.78 + const char default_solver_name[]="GLPK";
6.79 +#elif HAVE_CPLEX
6.80 +#define DEFAULT_LP CPLEX
6.81 + typedef LpCplex Lp;
6.82 + typedef MipCplex Mip;
6.83 + const char default_solver_name[]="CPLEX";
6.84 +#elif HAVE_SOPLEX
6.85 +#define DEFAULT_LP SOPLEX
6.86 + typedef LpSoplex Lp;
6.87 + const char default_solver_name[]="SOPLEX";
6.88 +#endif
6.89 +#endif
6.90 +
6.91 +} //namespace lemon
6.92 +
6.93 +#endif //LEMON_LP_H
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/lemon/lp_base.cc Tue Dec 02 21:40:33 2008 +0100
7.3 @@ -0,0 +1,35 @@
7.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
7.5 + *
7.6 + * This file is a part of LEMON, a generic C++ optimization library.
7.7 + *
7.8 + * Copyright (C) 2003-2008
7.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
7.11 + *
7.12 + * Permission to use, modify and distribute this software is granted
7.13 + * provided that this copyright notice appears in all copies. For
7.14 + * precise terms see the accompanying LICENSE file.
7.15 + *
7.16 + * This software is provided "AS IS" with no warranty of any kind,
7.17 + * express or implied, and with no claim as to its suitability for any
7.18 + * purpose.
7.19 + *
7.20 + */
7.21 +
7.22 +///\file
7.23 +///\brief The implementation of the LP solver interface.
7.24 +
7.25 +#include <lemon/lp_base.h>
7.26 +namespace lemon {
7.27 +
7.28 + const LpSolverBase::Value
7.29 + LpSolverBase::INF = std::numeric_limits<Value>::infinity();
7.30 + const LpSolverBase::Value
7.31 + LpSolverBase::NaN = std::numeric_limits<Value>::quiet_NaN();
7.32 +
7.33 +// const LpSolverBase::Constr::Value
7.34 +// LpSolverBase::Constr::INF = std::numeric_limits<Value>::infinity();
7.35 +// const LpSolverBase::Constr::Value
7.36 +// LpSolverBase::Constr::NaN = std::numeric_limits<Value>::quiet_NaN();
7.37 +
7.38 +} //namespace lemon
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/lemon/lp_base.h Tue Dec 02 21:40:33 2008 +0100
8.3 @@ -0,0 +1,1705 @@
8.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
8.5 + *
8.6 + * This file is a part of LEMON, a generic C++ optimization library.
8.7 + *
8.8 + * Copyright (C) 2003-2008
8.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
8.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
8.11 + *
8.12 + * Permission to use, modify and distribute this software is granted
8.13 + * provided that this copyright notice appears in all copies. For
8.14 + * precise terms see the accompanying LICENSE file.
8.15 + *
8.16 + * This software is provided "AS IS" with no warranty of any kind,
8.17 + * express or implied, and with no claim as to its suitability for any
8.18 + * purpose.
8.19 + *
8.20 + */
8.21 +
8.22 +#ifndef LEMON_LP_BASE_H
8.23 +#define LEMON_LP_BASE_H
8.24 +
8.25 +#include<iostream>
8.26 +#include<vector>
8.27 +#include<map>
8.28 +#include<limits>
8.29 +#include<lemon/math.h>
8.30 +
8.31 +#include<lemon/core.h>
8.32 +#include<lemon/bits/lp_id.h>
8.33 +
8.34 +///\file
8.35 +///\brief The interface of the LP solver interface.
8.36 +///\ingroup lp_group
8.37 +namespace lemon {
8.38 +
8.39 + /// Function to decide whether a floating point value is finite or not.
8.40 +
8.41 + /// Retruns true if the argument is not infinity, minus infinity or NaN.
8.42 + /// It does the same as the isfinite() function defined by C99.
8.43 + template <typename T>
8.44 + bool isFinite(T value)
8.45 + {
8.46 + typedef std::numeric_limits<T> Lim;
8.47 + if ((Lim::has_infinity && (value == Lim::infinity() || value ==
8.48 + -Lim::infinity())) ||
8.49 + ((Lim::has_quiet_NaN || Lim::has_signaling_NaN) && value != value))
8.50 + {
8.51 + return false;
8.52 + }
8.53 + return true;
8.54 + }
8.55 +
8.56 + ///Common base class for LP solvers
8.57 +
8.58 + ///\todo Much more docs
8.59 + ///\ingroup lp_group
8.60 + class LpSolverBase {
8.61 +
8.62 + protected:
8.63 +
8.64 + _lp_bits::LpId rows;
8.65 + _lp_bits::LpId cols;
8.66 +
8.67 + public:
8.68 +
8.69 + ///Possible outcomes of an LP solving procedure
8.70 + enum SolveExitStatus {
8.71 + ///This means that the problem has been successfully solved: either
8.72 + ///an optimal solution has been found or infeasibility/unboundedness
8.73 + ///has been proved.
8.74 + SOLVED = 0,
8.75 + ///Any other case (including the case when some user specified
8.76 + ///limit has been exceeded)
8.77 + UNSOLVED = 1
8.78 + };
8.79 +
8.80 + ///\e
8.81 + enum SolutionStatus {
8.82 + ///Feasible solution hasn't been found (but may exist).
8.83 +
8.84 + ///\todo NOTFOUND might be a better name.
8.85 + ///
8.86 + UNDEFINED = 0,
8.87 + ///The problem has no feasible solution
8.88 + INFEASIBLE = 1,
8.89 + ///Feasible solution found
8.90 + FEASIBLE = 2,
8.91 + ///Optimal solution exists and found
8.92 + OPTIMAL = 3,
8.93 + ///The cost function is unbounded
8.94 +
8.95 + ///\todo Give a feasible solution and an infinite ray (and the
8.96 + ///corresponding bases)
8.97 + INFINITE = 4
8.98 + };
8.99 +
8.100 + ///\e The type of the investigated LP problem
8.101 + enum ProblemTypes {
8.102 + ///Primal-dual feasible
8.103 + PRIMAL_DUAL_FEASIBLE = 0,
8.104 + ///Primal feasible dual infeasible
8.105 + PRIMAL_FEASIBLE_DUAL_INFEASIBLE = 1,
8.106 + ///Primal infeasible dual feasible
8.107 + PRIMAL_INFEASIBLE_DUAL_FEASIBLE = 2,
8.108 + ///Primal-dual infeasible
8.109 + PRIMAL_DUAL_INFEASIBLE = 3,
8.110 + ///Could not determine so far
8.111 + UNKNOWN = 4
8.112 + };
8.113 +
8.114 + ///The floating point type used by the solver
8.115 + typedef double Value;
8.116 + ///The infinity constant
8.117 + static const Value INF;
8.118 + ///The not a number constant
8.119 + static const Value NaN;
8.120 +
8.121 + static inline bool isNaN(const Value& v) { return v!=v; }
8.122 +
8.123 + friend class Col;
8.124 + friend class ColIt;
8.125 + friend class Row;
8.126 +
8.127 + ///Refer to a column of the LP.
8.128 +
8.129 + ///This type is used to refer to a column of the LP.
8.130 + ///
8.131 + ///Its value remains valid and correct even after the addition or erase of
8.132 + ///other columns.
8.133 + ///
8.134 + ///\todo Document what can one do with a Col (INVALID, comparing,
8.135 + ///it is similar to Node/Edge)
8.136 + class Col {
8.137 + protected:
8.138 + int id;
8.139 + friend class LpSolverBase;
8.140 + friend class MipSolverBase;
8.141 + explicit Col(int _id) : id(_id) {}
8.142 + public:
8.143 + typedef Value ExprValue;
8.144 + typedef True LpSolverCol;
8.145 + Col() {}
8.146 + Col(const Invalid&) : id(-1) {}
8.147 + bool operator< (Col c) const {return id< c.id;}
8.148 + bool operator> (Col c) const {return id> c.id;}
8.149 + bool operator==(Col c) const {return id==c.id;}
8.150 + bool operator!=(Col c) const {return id!=c.id;}
8.151 + };
8.152 +
8.153 + class ColIt : public Col {
8.154 + const LpSolverBase *_lp;
8.155 + public:
8.156 + ColIt() {}
8.157 + ColIt(const LpSolverBase &lp) : _lp(&lp)
8.158 + {
8.159 + _lp->cols.firstFix(id);
8.160 + }
8.161 + ColIt(const Invalid&) : Col(INVALID) {}
8.162 + ColIt &operator++()
8.163 + {
8.164 + _lp->cols.nextFix(id);
8.165 + return *this;
8.166 + }
8.167 + };
8.168 +
8.169 + static int id(const Col& col) { return col.id; }
8.170 +
8.171 +
8.172 + ///Refer to a row of the LP.
8.173 +
8.174 + ///This type is used to refer to a row of the LP.
8.175 + ///
8.176 + ///Its value remains valid and correct even after the addition or erase of
8.177 + ///other rows.
8.178 + ///
8.179 + ///\todo Document what can one do with a Row (INVALID, comparing,
8.180 + ///it is similar to Node/Edge)
8.181 + class Row {
8.182 + protected:
8.183 + int id;
8.184 + friend class LpSolverBase;
8.185 + explicit Row(int _id) : id(_id) {}
8.186 + public:
8.187 + typedef Value ExprValue;
8.188 + typedef True LpSolverRow;
8.189 + Row() {}
8.190 + Row(const Invalid&) : id(-1) {}
8.191 +
8.192 + bool operator< (Row c) const {return id< c.id;}
8.193 + bool operator> (Row c) const {return id> c.id;}
8.194 + bool operator==(Row c) const {return id==c.id;}
8.195 + bool operator!=(Row c) const {return id!=c.id;}
8.196 + };
8.197 +
8.198 + class RowIt : public Row {
8.199 + const LpSolverBase *_lp;
8.200 + public:
8.201 + RowIt() {}
8.202 + RowIt(const LpSolverBase &lp) : _lp(&lp)
8.203 + {
8.204 + _lp->rows.firstFix(id);
8.205 + }
8.206 + RowIt(const Invalid&) : Row(INVALID) {}
8.207 + RowIt &operator++()
8.208 + {
8.209 + _lp->rows.nextFix(id);
8.210 + return *this;
8.211 + }
8.212 + };
8.213 +
8.214 + static int id(const Row& row) { return row.id; }
8.215 +
8.216 + protected:
8.217 +
8.218 + int _lpId(const Col& c) const {
8.219 + return cols.floatingId(id(c));
8.220 + }
8.221 +
8.222 + int _lpId(const Row& r) const {
8.223 + return rows.floatingId(id(r));
8.224 + }
8.225 +
8.226 + Col _item(int i, Col) const {
8.227 + return Col(cols.fixId(i));
8.228 + }
8.229 +
8.230 + Row _item(int i, Row) const {
8.231 + return Row(rows.fixId(i));
8.232 + }
8.233 +
8.234 +
8.235 + public:
8.236 +
8.237 + ///Linear expression of variables and a constant component
8.238 +
8.239 + ///This data structure stores a linear expression of the variables
8.240 + ///(\ref Col "Col"s) and also has a constant component.
8.241 + ///
8.242 + ///There are several ways to access and modify the contents of this
8.243 + ///container.
8.244 + ///- Its it fully compatible with \c std::map<Col,double>, so for expamle
8.245 + ///if \c e is an Expr and \c v and \c w are of type \ref Col, then you can
8.246 + ///read and modify the coefficients like
8.247 + ///these.
8.248 + ///\code
8.249 + ///e[v]=5;
8.250 + ///e[v]+=12;
8.251 + ///e.erase(v);
8.252 + ///\endcode
8.253 + ///or you can also iterate through its elements.
8.254 + ///\code
8.255 + ///double s=0;
8.256 + ///for(LpSolverBase::Expr::iterator i=e.begin();i!=e.end();++i)
8.257 + /// s+=i->second;
8.258 + ///\endcode
8.259 + ///(This code computes the sum of all coefficients).
8.260 + ///- Numbers (<tt>double</tt>'s)
8.261 + ///and variables (\ref Col "Col"s) directly convert to an
8.262 + ///\ref Expr and the usual linear operations are defined, so
8.263 + ///\code
8.264 + ///v+w
8.265 + ///2*v-3.12*(v-w/2)+2
8.266 + ///v*2.1+(3*v+(v*12+w+6)*3)/2
8.267 + ///\endcode
8.268 + ///are valid \ref Expr "Expr"essions.
8.269 + ///The usual assignment operations are also defined.
8.270 + ///\code
8.271 + ///e=v+w;
8.272 + ///e+=2*v-3.12*(v-w/2)+2;
8.273 + ///e*=3.4;
8.274 + ///e/=5;
8.275 + ///\endcode
8.276 + ///- The constant member can be set and read by \ref constComp()
8.277 + ///\code
8.278 + ///e.constComp()=12;
8.279 + ///double c=e.constComp();
8.280 + ///\endcode
8.281 + ///
8.282 + ///\note \ref clear() not only sets all coefficients to 0 but also
8.283 + ///clears the constant components.
8.284 + ///
8.285 + ///\sa Constr
8.286 + ///
8.287 + class Expr : public std::map<Col,Value>
8.288 + {
8.289 + public:
8.290 + typedef LpSolverBase::Col Key;
8.291 + typedef LpSolverBase::Value Value;
8.292 +
8.293 + protected:
8.294 + typedef std::map<Col,Value> Base;
8.295 +
8.296 + Value const_comp;
8.297 + public:
8.298 + typedef True IsLinExpression;
8.299 + ///\e
8.300 + Expr() : Base(), const_comp(0) { }
8.301 + ///\e
8.302 + Expr(const Key &v) : const_comp(0) {
8.303 + Base::insert(std::make_pair(v, 1));
8.304 + }
8.305 + ///\e
8.306 + Expr(const Value &v) : const_comp(v) {}
8.307 + ///\e
8.308 + void set(const Key &v,const Value &c) {
8.309 + Base::insert(std::make_pair(v, c));
8.310 + }
8.311 + ///\e
8.312 + Value &constComp() { return const_comp; }
8.313 + ///\e
8.314 + const Value &constComp() const { return const_comp; }
8.315 +
8.316 + ///Removes the components with zero coefficient.
8.317 + void simplify() {
8.318 + for (Base::iterator i=Base::begin(); i!=Base::end();) {
8.319 + Base::iterator j=i;
8.320 + ++j;
8.321 + if ((*i).second==0) Base::erase(i);
8.322 + i=j;
8.323 + }
8.324 + }
8.325 +
8.326 + void simplify() const {
8.327 + const_cast<Expr*>(this)->simplify();
8.328 + }
8.329 +
8.330 + ///Removes the coefficients closer to zero than \c tolerance.
8.331 + void simplify(double &tolerance) {
8.332 + for (Base::iterator i=Base::begin(); i!=Base::end();) {
8.333 + Base::iterator j=i;
8.334 + ++j;
8.335 + if (std::fabs((*i).second)<tolerance) Base::erase(i);
8.336 + i=j;
8.337 + }
8.338 + }
8.339 +
8.340 + ///Sets all coefficients and the constant component to 0.
8.341 + void clear() {
8.342 + Base::clear();
8.343 + const_comp=0;
8.344 + }
8.345 +
8.346 + ///\e
8.347 + Expr &operator+=(const Expr &e) {
8.348 + for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
8.349 + (*this)[j->first]+=j->second;
8.350 + const_comp+=e.const_comp;
8.351 + return *this;
8.352 + }
8.353 + ///\e
8.354 + Expr &operator-=(const Expr &e) {
8.355 + for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
8.356 + (*this)[j->first]-=j->second;
8.357 + const_comp-=e.const_comp;
8.358 + return *this;
8.359 + }
8.360 + ///\e
8.361 + Expr &operator*=(const Value &c) {
8.362 + for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
8.363 + j->second*=c;
8.364 + const_comp*=c;
8.365 + return *this;
8.366 + }
8.367 + ///\e
8.368 + Expr &operator/=(const Value &c) {
8.369 + for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
8.370 + j->second/=c;
8.371 + const_comp/=c;
8.372 + return *this;
8.373 + }
8.374 +
8.375 + };
8.376 +
8.377 + ///Linear constraint
8.378 +
8.379 + ///This data stucture represents a linear constraint in the LP.
8.380 + ///Basically it is a linear expression with a lower or an upper bound
8.381 + ///(or both). These parts of the constraint can be obtained by the member
8.382 + ///functions \ref expr(), \ref lowerBound() and \ref upperBound(),
8.383 + ///respectively.
8.384 + ///There are two ways to construct a constraint.
8.385 + ///- You can set the linear expression and the bounds directly
8.386 + /// by the functions above.
8.387 + ///- The operators <tt>\<=</tt>, <tt>==</tt> and <tt>\>=</tt>
8.388 + /// are defined between expressions, or even between constraints whenever
8.389 + /// it makes sense. Therefore if \c e and \c f are linear expressions and
8.390 + /// \c s and \c t are numbers, then the followings are valid expressions
8.391 + /// and thus they can be used directly e.g. in \ref addRow() whenever
8.392 + /// it makes sense.
8.393 + ///\code
8.394 + /// e<=s
8.395 + /// e<=f
8.396 + /// e==f
8.397 + /// s<=e<=t
8.398 + /// e>=t
8.399 + ///\endcode
8.400 + ///\warning The validity of a constraint is checked only at run time, so
8.401 + ///e.g. \ref addRow(<tt>x[1]\<=x[2]<=5</tt>) will compile, but will throw
8.402 + ///an assertion.
8.403 + class Constr
8.404 + {
8.405 + public:
8.406 + typedef LpSolverBase::Expr Expr;
8.407 + typedef Expr::Key Key;
8.408 + typedef Expr::Value Value;
8.409 +
8.410 + protected:
8.411 + Expr _expr;
8.412 + Value _lb,_ub;
8.413 + public:
8.414 + ///\e
8.415 + Constr() : _expr(), _lb(NaN), _ub(NaN) {}
8.416 + ///\e
8.417 + Constr(Value lb,const Expr &e,Value ub) :
8.418 + _expr(e), _lb(lb), _ub(ub) {}
8.419 + ///\e
8.420 + Constr(const Expr &e,Value ub) :
8.421 + _expr(e), _lb(NaN), _ub(ub) {}
8.422 + ///\e
8.423 + Constr(Value lb,const Expr &e) :
8.424 + _expr(e), _lb(lb), _ub(NaN) {}
8.425 + ///\e
8.426 + Constr(const Expr &e) :
8.427 + _expr(e), _lb(NaN), _ub(NaN) {}
8.428 + ///\e
8.429 + void clear()
8.430 + {
8.431 + _expr.clear();
8.432 + _lb=_ub=NaN;
8.433 + }
8.434 +
8.435 + ///Reference to the linear expression
8.436 + Expr &expr() { return _expr; }
8.437 + ///Cont reference to the linear expression
8.438 + const Expr &expr() const { return _expr; }
8.439 + ///Reference to the lower bound.
8.440 +
8.441 + ///\return
8.442 + ///- \ref INF "INF": the constraint is lower unbounded.
8.443 + ///- \ref NaN "NaN": lower bound has not been set.
8.444 + ///- finite number: the lower bound
8.445 + Value &lowerBound() { return _lb; }
8.446 + ///The const version of \ref lowerBound()
8.447 + const Value &lowerBound() const { return _lb; }
8.448 + ///Reference to the upper bound.
8.449 +
8.450 + ///\return
8.451 + ///- \ref INF "INF": the constraint is upper unbounded.
8.452 + ///- \ref NaN "NaN": upper bound has not been set.
8.453 + ///- finite number: the upper bound
8.454 + Value &upperBound() { return _ub; }
8.455 + ///The const version of \ref upperBound()
8.456 + const Value &upperBound() const { return _ub; }
8.457 + ///Is the constraint lower bounded?
8.458 + bool lowerBounded() const {
8.459 + return isFinite(_lb);
8.460 + }
8.461 + ///Is the constraint upper bounded?
8.462 + bool upperBounded() const {
8.463 + return isFinite(_ub);
8.464 + }
8.465 +
8.466 + };
8.467 +
8.468 + ///Linear expression of rows
8.469 +
8.470 + ///This data structure represents a column of the matrix,
8.471 + ///thas is it strores a linear expression of the dual variables
8.472 + ///(\ref Row "Row"s).
8.473 + ///
8.474 + ///There are several ways to access and modify the contents of this
8.475 + ///container.
8.476 + ///- Its it fully compatible with \c std::map<Row,double>, so for expamle
8.477 + ///if \c e is an DualExpr and \c v
8.478 + ///and \c w are of type \ref Row, then you can
8.479 + ///read and modify the coefficients like
8.480 + ///these.
8.481 + ///\code
8.482 + ///e[v]=5;
8.483 + ///e[v]+=12;
8.484 + ///e.erase(v);
8.485 + ///\endcode
8.486 + ///or you can also iterate through its elements.
8.487 + ///\code
8.488 + ///double s=0;
8.489 + ///for(LpSolverBase::DualExpr::iterator i=e.begin();i!=e.end();++i)
8.490 + /// s+=i->second;
8.491 + ///\endcode
8.492 + ///(This code computes the sum of all coefficients).
8.493 + ///- Numbers (<tt>double</tt>'s)
8.494 + ///and variables (\ref Row "Row"s) directly convert to an
8.495 + ///\ref DualExpr and the usual linear operations are defined, so
8.496 + ///\code
8.497 + ///v+w
8.498 + ///2*v-3.12*(v-w/2)
8.499 + ///v*2.1+(3*v+(v*12+w)*3)/2
8.500 + ///\endcode
8.501 + ///are valid \ref DualExpr "DualExpr"essions.
8.502 + ///The usual assignment operations are also defined.
8.503 + ///\code
8.504 + ///e=v+w;
8.505 + ///e+=2*v-3.12*(v-w/2);
8.506 + ///e*=3.4;
8.507 + ///e/=5;
8.508 + ///\endcode
8.509 + ///
8.510 + ///\sa Expr
8.511 + ///
8.512 + class DualExpr : public std::map<Row,Value>
8.513 + {
8.514 + public:
8.515 + typedef LpSolverBase::Row Key;
8.516 + typedef LpSolverBase::Value Value;
8.517 +
8.518 + protected:
8.519 + typedef std::map<Row,Value> Base;
8.520 +
8.521 + public:
8.522 + typedef True IsLinExpression;
8.523 + ///\e
8.524 + DualExpr() : Base() { }
8.525 + ///\e
8.526 + DualExpr(const Key &v) {
8.527 + Base::insert(std::make_pair(v, 1));
8.528 + }
8.529 + ///\e
8.530 + void set(const Key &v,const Value &c) {
8.531 + Base::insert(std::make_pair(v, c));
8.532 + }
8.533 +
8.534 + ///Removes the components with zero coefficient.
8.535 + void simplify() {
8.536 + for (Base::iterator i=Base::begin(); i!=Base::end();) {
8.537 + Base::iterator j=i;
8.538 + ++j;
8.539 + if ((*i).second==0) Base::erase(i);
8.540 + i=j;
8.541 + }
8.542 + }
8.543 +
8.544 + void simplify() const {
8.545 + const_cast<DualExpr*>(this)->simplify();
8.546 + }
8.547 +
8.548 + ///Removes the coefficients closer to zero than \c tolerance.
8.549 + void simplify(double &tolerance) {
8.550 + for (Base::iterator i=Base::begin(); i!=Base::end();) {
8.551 + Base::iterator j=i;
8.552 + ++j;
8.553 + if (std::fabs((*i).second)<tolerance) Base::erase(i);
8.554 + i=j;
8.555 + }
8.556 + }
8.557 +
8.558 + ///Sets all coefficients to 0.
8.559 + void clear() {
8.560 + Base::clear();
8.561 + }
8.562 +
8.563 + ///\e
8.564 + DualExpr &operator+=(const DualExpr &e) {
8.565 + for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
8.566 + (*this)[j->first]+=j->second;
8.567 + return *this;
8.568 + }
8.569 + ///\e
8.570 + DualExpr &operator-=(const DualExpr &e) {
8.571 + for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
8.572 + (*this)[j->first]-=j->second;
8.573 + return *this;
8.574 + }
8.575 + ///\e
8.576 + DualExpr &operator*=(const Value &c) {
8.577 + for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
8.578 + j->second*=c;
8.579 + return *this;
8.580 + }
8.581 + ///\e
8.582 + DualExpr &operator/=(const Value &c) {
8.583 + for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
8.584 + j->second/=c;
8.585 + return *this;
8.586 + }
8.587 + };
8.588 +
8.589 +
8.590 + private:
8.591 +
8.592 + template <typename _Expr>
8.593 + class MappedOutputIterator {
8.594 + public:
8.595 +
8.596 + typedef std::insert_iterator<_Expr> Base;
8.597 +
8.598 + typedef std::output_iterator_tag iterator_category;
8.599 + typedef void difference_type;
8.600 + typedef void value_type;
8.601 + typedef void reference;
8.602 + typedef void pointer;
8.603 +
8.604 + MappedOutputIterator(const Base& _base, const LpSolverBase& _lp)
8.605 + : base(_base), lp(_lp) {}
8.606 +
8.607 + MappedOutputIterator& operator*() {
8.608 + return *this;
8.609 + }
8.610 +
8.611 + MappedOutputIterator& operator=(const std::pair<int, Value>& value) {
8.612 + *base = std::make_pair(lp._item(value.first, typename _Expr::Key()),
8.613 + value.second);
8.614 + return *this;
8.615 + }
8.616 +
8.617 + MappedOutputIterator& operator++() {
8.618 + ++base;
8.619 + return *this;
8.620 + }
8.621 +
8.622 + MappedOutputIterator operator++(int) {
8.623 + MappedOutputIterator tmp(*this);
8.624 + ++base;
8.625 + return tmp;
8.626 + }
8.627 +
8.628 + bool operator==(const MappedOutputIterator& it) const {
8.629 + return base == it.base;
8.630 + }
8.631 +
8.632 + bool operator!=(const MappedOutputIterator& it) const {
8.633 + return base != it.base;
8.634 + }
8.635 +
8.636 + private:
8.637 + Base base;
8.638 + const LpSolverBase& lp;
8.639 + };
8.640 +
8.641 + template <typename Expr>
8.642 + class MappedInputIterator {
8.643 + public:
8.644 +
8.645 + typedef typename Expr::const_iterator Base;
8.646 +
8.647 + typedef typename Base::iterator_category iterator_category;
8.648 + typedef typename Base::difference_type difference_type;
8.649 + typedef const std::pair<int, Value> value_type;
8.650 + typedef value_type reference;
8.651 + class pointer {
8.652 + public:
8.653 + pointer(value_type& _value) : value(_value) {}
8.654 + value_type* operator->() { return &value; }
8.655 + private:
8.656 + value_type value;
8.657 + };
8.658 +
8.659 + MappedInputIterator(const Base& _base, const LpSolverBase& _lp)
8.660 + : base(_base), lp(_lp) {}
8.661 +
8.662 + reference operator*() {
8.663 + return std::make_pair(lp._lpId(base->first), base->second);
8.664 + }
8.665 +
8.666 + pointer operator->() {
8.667 + return pointer(operator*());
8.668 + }
8.669 +
8.670 + MappedInputIterator& operator++() {
8.671 + ++base;
8.672 + return *this;
8.673 + }
8.674 +
8.675 + MappedInputIterator operator++(int) {
8.676 + MappedInputIterator tmp(*this);
8.677 + ++base;
8.678 + return tmp;
8.679 + }
8.680 +
8.681 + bool operator==(const MappedInputIterator& it) const {
8.682 + return base == it.base;
8.683 + }
8.684 +
8.685 + bool operator!=(const MappedInputIterator& it) const {
8.686 + return base != it.base;
8.687 + }
8.688 +
8.689 + private:
8.690 + Base base;
8.691 + const LpSolverBase& lp;
8.692 + };
8.693 +
8.694 + protected:
8.695 +
8.696 + /// STL compatible iterator for lp col
8.697 + typedef MappedInputIterator<Expr> ConstRowIterator;
8.698 + /// STL compatible iterator for lp row
8.699 + typedef MappedInputIterator<DualExpr> ConstColIterator;
8.700 +
8.701 + /// STL compatible iterator for lp col
8.702 + typedef MappedOutputIterator<Expr> RowIterator;
8.703 + /// STL compatible iterator for lp row
8.704 + typedef MappedOutputIterator<DualExpr> ColIterator;
8.705 +
8.706 + //Abstract virtual functions
8.707 + virtual LpSolverBase* _newLp() = 0;
8.708 + virtual LpSolverBase* _copyLp(){
8.709 + LpSolverBase* newlp = _newLp();
8.710 +
8.711 + std::map<Col, Col> ref;
8.712 + for (LpSolverBase::ColIt it(*this); it != INVALID; ++it) {
8.713 + Col ccol = newlp->addCol();
8.714 + ref[it] = ccol;
8.715 + newlp->colName(ccol, colName(it));
8.716 + newlp->colLowerBound(ccol, colLowerBound(it));
8.717 + newlp->colUpperBound(ccol, colUpperBound(it));
8.718 + }
8.719 +
8.720 + for (LpSolverBase::RowIt it(*this); it != INVALID; ++it) {
8.721 + Expr e = row(it), ce;
8.722 + for (Expr::iterator jt = e.begin(); jt != e.end(); ++jt) {
8.723 + ce[ref[jt->first]] = jt->second;
8.724 + }
8.725 + ce += e.constComp();
8.726 + Row r = newlp->addRow(ce);
8.727 +
8.728 + double lower, upper;
8.729 + getRowBounds(it, lower, upper);
8.730 + newlp->rowBounds(r, lower, upper);
8.731 + }
8.732 +
8.733 + return newlp;
8.734 + };
8.735 +
8.736 + virtual int _addCol() = 0;
8.737 + virtual int _addRow() = 0;
8.738 +
8.739 + virtual void _eraseCol(int col) = 0;
8.740 + virtual void _eraseRow(int row) = 0;
8.741 +
8.742 + virtual void _getColName(int col, std::string & name) const = 0;
8.743 + virtual void _setColName(int col, const std::string & name) = 0;
8.744 + virtual int _colByName(const std::string& name) const = 0;
8.745 +
8.746 + virtual void _setRowCoeffs(int i, ConstRowIterator b,
8.747 + ConstRowIterator e) = 0;
8.748 + virtual void _getRowCoeffs(int i, RowIterator b) const = 0;
8.749 + virtual void _setColCoeffs(int i, ConstColIterator b,
8.750 + ConstColIterator e) = 0;
8.751 + virtual void _getColCoeffs(int i, ColIterator b) const = 0;
8.752 + virtual void _setCoeff(int row, int col, Value value) = 0;
8.753 + virtual Value _getCoeff(int row, int col) const = 0;
8.754 + virtual void _setColLowerBound(int i, Value value) = 0;
8.755 + virtual Value _getColLowerBound(int i) const = 0;
8.756 + virtual void _setColUpperBound(int i, Value value) = 0;
8.757 + virtual Value _getColUpperBound(int i) const = 0;
8.758 + virtual void _setRowBounds(int i, Value lower, Value upper) = 0;
8.759 + virtual void _getRowBounds(int i, Value &lower, Value &upper) const = 0;
8.760 +
8.761 + virtual void _setObjCoeff(int i, Value obj_coef) = 0;
8.762 + virtual Value _getObjCoeff(int i) const = 0;
8.763 + virtual void _clearObj()=0;
8.764 +
8.765 + virtual SolveExitStatus _solve() = 0;
8.766 + virtual Value _getPrimal(int i) const = 0;
8.767 + virtual Value _getDual(int i) const = 0;
8.768 + virtual Value _getPrimalValue() const = 0;
8.769 + virtual bool _isBasicCol(int i) const = 0;
8.770 + virtual SolutionStatus _getPrimalStatus() const = 0;
8.771 + virtual SolutionStatus _getDualStatus() const = 0;
8.772 + virtual ProblemTypes _getProblemType() const = 0;
8.773 +
8.774 + virtual void _setMax() = 0;
8.775 + virtual void _setMin() = 0;
8.776 +
8.777 +
8.778 + virtual bool _isMax() const = 0;
8.779 +
8.780 + //Own protected stuff
8.781 +
8.782 + //Constant component of the objective function
8.783 + Value obj_const_comp;
8.784 +
8.785 + public:
8.786 +
8.787 + ///\e
8.788 + LpSolverBase() : obj_const_comp(0) {}
8.789 +
8.790 + ///\e
8.791 + virtual ~LpSolverBase() {}
8.792 +
8.793 + ///Creates a new LP problem
8.794 + LpSolverBase* newLp() {return _newLp();}
8.795 + ///Makes a copy of the LP problem
8.796 + LpSolverBase* copyLp() {return _copyLp();}
8.797 +
8.798 + ///\name Build up and modify the LP
8.799 +
8.800 + ///@{
8.801 +
8.802 + ///Add a new empty column (i.e a new variable) to the LP
8.803 + Col addCol() { Col c; _addCol(); c.id = cols.addId(); return c;}
8.804 +
8.805 + ///\brief Adds several new columns
8.806 + ///(i.e a variables) at once
8.807 + ///
8.808 + ///This magic function takes a container as its argument
8.809 + ///and fills its elements
8.810 + ///with new columns (i.e. variables)
8.811 + ///\param t can be
8.812 + ///- a standard STL compatible iterable container with
8.813 + ///\ref Col as its \c values_type
8.814 + ///like
8.815 + ///\code
8.816 + ///std::vector<LpSolverBase::Col>
8.817 + ///std::list<LpSolverBase::Col>
8.818 + ///\endcode
8.819 + ///- a standard STL compatible iterable container with
8.820 + ///\ref Col as its \c mapped_type
8.821 + ///like
8.822 + ///\code
8.823 + ///std::map<AnyType,LpSolverBase::Col>
8.824 + ///\endcode
8.825 + ///- an iterable lemon \ref concepts::WriteMap "write map" like
8.826 + ///\code
8.827 + ///ListGraph::NodeMap<LpSolverBase::Col>
8.828 + ///ListGraph::EdgeMap<LpSolverBase::Col>
8.829 + ///\endcode
8.830 + ///\return The number of the created column.
8.831 +#ifdef DOXYGEN
8.832 + template<class T>
8.833 + int addColSet(T &t) { return 0;}
8.834 +#else
8.835 + template<class T>
8.836 + typename enable_if<typename T::value_type::LpSolverCol,int>::type
8.837 + addColSet(T &t,dummy<0> = 0) {
8.838 + int s=0;
8.839 + for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
8.840 + return s;
8.841 + }
8.842 + template<class T>
8.843 + typename enable_if<typename T::value_type::second_type::LpSolverCol,
8.844 + int>::type
8.845 + addColSet(T &t,dummy<1> = 1) {
8.846 + int s=0;
8.847 + for(typename T::iterator i=t.begin();i!=t.end();++i) {
8.848 + i->second=addCol();
8.849 + s++;
8.850 + }
8.851 + return s;
8.852 + }
8.853 + template<class T>
8.854 + typename enable_if<typename T::MapIt::Value::LpSolverCol,
8.855 + int>::type
8.856 + addColSet(T &t,dummy<2> = 2) {
8.857 + int s=0;
8.858 + for(typename T::MapIt i(t); i!=INVALID; ++i)
8.859 + {
8.860 + i.set(addCol());
8.861 + s++;
8.862 + }
8.863 + return s;
8.864 + }
8.865 +#endif
8.866 +
8.867 + ///Set a column (i.e a dual constraint) of the LP
8.868 +
8.869 + ///\param c is the column to be modified
8.870 + ///\param e is a dual linear expression (see \ref DualExpr)
8.871 + ///a better one.
8.872 + void col(Col c,const DualExpr &e) {
8.873 + e.simplify();
8.874 + _setColCoeffs(_lpId(c), ConstColIterator(e.begin(), *this),
8.875 + ConstColIterator(e.end(), *this));
8.876 + }
8.877 +
8.878 + ///Get a column (i.e a dual constraint) of the LP
8.879 +
8.880 + ///\param r is the column to get
8.881 + ///\return the dual expression associated to the column
8.882 + DualExpr col(Col c) const {
8.883 + DualExpr e;
8.884 + _getColCoeffs(_lpId(c), ColIterator(std::inserter(e, e.end()), *this));
8.885 + return e;
8.886 + }
8.887 +
8.888 + ///Add a new column to the LP
8.889 +
8.890 + ///\param e is a dual linear expression (see \ref DualExpr)
8.891 + ///\param obj is the corresponding component of the objective
8.892 + ///function. It is 0 by default.
8.893 + ///\return The created column.
8.894 + Col addCol(const DualExpr &e, Value o = 0) {
8.895 + Col c=addCol();
8.896 + col(c,e);
8.897 + objCoeff(c,o);
8.898 + return c;
8.899 + }
8.900 +
8.901 + ///Add a new empty row (i.e a new constraint) to the LP
8.902 +
8.903 + ///This function adds a new empty row (i.e a new constraint) to the LP.
8.904 + ///\return The created row
8.905 + Row addRow() { Row r; _addRow(); r.id = rows.addId(); return r;}
8.906 +
8.907 + ///\brief Add several new rows
8.908 + ///(i.e a constraints) at once
8.909 + ///
8.910 + ///This magic function takes a container as its argument
8.911 + ///and fills its elements
8.912 + ///with new row (i.e. variables)
8.913 + ///\param t can be
8.914 + ///- a standard STL compatible iterable container with
8.915 + ///\ref Row as its \c values_type
8.916 + ///like
8.917 + ///\code
8.918 + ///std::vector<LpSolverBase::Row>
8.919 + ///std::list<LpSolverBase::Row>
8.920 + ///\endcode
8.921 + ///- a standard STL compatible iterable container with
8.922 + ///\ref Row as its \c mapped_type
8.923 + ///like
8.924 + ///\code
8.925 + ///std::map<AnyType,LpSolverBase::Row>
8.926 + ///\endcode
8.927 + ///- an iterable lemon \ref concepts::WriteMap "write map" like
8.928 + ///\code
8.929 + ///ListGraph::NodeMap<LpSolverBase::Row>
8.930 + ///ListGraph::EdgeMap<LpSolverBase::Row>
8.931 + ///\endcode
8.932 + ///\return The number of rows created.
8.933 +#ifdef DOXYGEN
8.934 + template<class T>
8.935 + int addRowSet(T &t) { return 0;}
8.936 +#else
8.937 + template<class T>
8.938 + typename enable_if<typename T::value_type::LpSolverRow,int>::type
8.939 + addRowSet(T &t,dummy<0> = 0) {
8.940 + int s=0;
8.941 + for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addRow();s++;}
8.942 + return s;
8.943 + }
8.944 + template<class T>
8.945 + typename enable_if<typename T::value_type::second_type::LpSolverRow,
8.946 + int>::type
8.947 + addRowSet(T &t,dummy<1> = 1) {
8.948 + int s=0;
8.949 + for(typename T::iterator i=t.begin();i!=t.end();++i) {
8.950 + i->second=addRow();
8.951 + s++;
8.952 + }
8.953 + return s;
8.954 + }
8.955 + template<class T>
8.956 + typename enable_if<typename T::MapIt::Value::LpSolverRow,
8.957 + int>::type
8.958 + addRowSet(T &t,dummy<2> = 2) {
8.959 + int s=0;
8.960 + for(typename T::MapIt i(t); i!=INVALID; ++i)
8.961 + {
8.962 + i.set(addRow());
8.963 + s++;
8.964 + }
8.965 + return s;
8.966 + }
8.967 +#endif
8.968 +
8.969 + ///Set a row (i.e a constraint) of the LP
8.970 +
8.971 + ///\param r is the row to be modified
8.972 + ///\param l is lower bound (-\ref INF means no bound)
8.973 + ///\param e is a linear expression (see \ref Expr)
8.974 + ///\param u is the upper bound (\ref INF means no bound)
8.975 + ///\bug This is a temporary function. The interface will change to
8.976 + ///a better one.
8.977 + ///\todo Option to control whether a constraint with a single variable is
8.978 + ///added or not.
8.979 + void row(Row r, Value l, const Expr &e, Value u) {
8.980 + e.simplify();
8.981 + _setRowCoeffs(_lpId(r), ConstRowIterator(e.begin(), *this),
8.982 + ConstRowIterator(e.end(), *this));
8.983 + _setRowBounds(_lpId(r),l-e.constComp(),u-e.constComp());
8.984 + }
8.985 +
8.986 + ///Set a row (i.e a constraint) of the LP
8.987 +
8.988 + ///\param r is the row to be modified
8.989 + ///\param c is a linear expression (see \ref Constr)
8.990 + void row(Row r, const Constr &c) {
8.991 + row(r, c.lowerBounded()?c.lowerBound():-INF,
8.992 + c.expr(), c.upperBounded()?c.upperBound():INF);
8.993 + }
8.994 +
8.995 +
8.996 + ///Get a row (i.e a constraint) of the LP
8.997 +
8.998 + ///\param r is the row to get
8.999 + ///\return the expression associated to the row
8.1000 + Expr row(Row r) const {
8.1001 + Expr e;
8.1002 + _getRowCoeffs(_lpId(r), RowIterator(std::inserter(e, e.end()), *this));
8.1003 + return e;
8.1004 + }
8.1005 +
8.1006 + ///Add a new row (i.e a new constraint) to the LP
8.1007 +
8.1008 + ///\param l is the lower bound (-\ref INF means no bound)
8.1009 + ///\param e is a linear expression (see \ref Expr)
8.1010 + ///\param u is the upper bound (\ref INF means no bound)
8.1011 + ///\return The created row.
8.1012 + ///\bug This is a temporary function. The interface will change to
8.1013 + ///a better one.
8.1014 + Row addRow(Value l,const Expr &e, Value u) {
8.1015 + Row r=addRow();
8.1016 + row(r,l,e,u);
8.1017 + return r;
8.1018 + }
8.1019 +
8.1020 + ///Add a new row (i.e a new constraint) to the LP
8.1021 +
8.1022 + ///\param c is a linear expression (see \ref Constr)
8.1023 + ///\return The created row.
8.1024 + Row addRow(const Constr &c) {
8.1025 + Row r=addRow();
8.1026 + row(r,c);
8.1027 + return r;
8.1028 + }
8.1029 + ///Erase a coloumn (i.e a variable) from the LP
8.1030 +
8.1031 + ///\param c is the coloumn to be deleted
8.1032 + ///\todo Please check this
8.1033 + void eraseCol(Col c) {
8.1034 + _eraseCol(_lpId(c));
8.1035 + cols.eraseId(c.id);
8.1036 + }
8.1037 + ///Erase a row (i.e a constraint) from the LP
8.1038 +
8.1039 + ///\param r is the row to be deleted
8.1040 + ///\todo Please check this
8.1041 + void eraseRow(Row r) {
8.1042 + _eraseRow(_lpId(r));
8.1043 + rows.eraseId(r.id);
8.1044 + }
8.1045 +
8.1046 + /// Get the name of a column
8.1047 +
8.1048 + ///\param c is the coresponding coloumn
8.1049 + ///\return The name of the colunm
8.1050 + std::string colName(Col c) const {
8.1051 + std::string name;
8.1052 + _getColName(_lpId(c), name);
8.1053 + return name;
8.1054 + }
8.1055 +
8.1056 + /// Set the name of a column
8.1057 +
8.1058 + ///\param c is the coresponding coloumn
8.1059 + ///\param name The name to be given
8.1060 + void colName(Col c, const std::string& name) {
8.1061 + _setColName(_lpId(c), name);
8.1062 + }
8.1063 +
8.1064 + /// Get the column by its name
8.1065 +
8.1066 + ///\param name The name of the column
8.1067 + ///\return the proper column or \c INVALID
8.1068 + Col colByName(const std::string& name) const {
8.1069 + int k = _colByName(name);
8.1070 + return k != -1 ? Col(cols.fixId(k)) : Col(INVALID);
8.1071 + }
8.1072 +
8.1073 + /// Set an element of the coefficient matrix of the LP
8.1074 +
8.1075 + ///\param r is the row of the element to be modified
8.1076 + ///\param c is the coloumn of the element to be modified
8.1077 + ///\param val is the new value of the coefficient
8.1078 +
8.1079 + void coeff(Row r, Col c, Value val) {
8.1080 + _setCoeff(_lpId(r),_lpId(c), val);
8.1081 + }
8.1082 +
8.1083 + /// Get an element of the coefficient matrix of the LP
8.1084 +
8.1085 + ///\param r is the row of the element in question
8.1086 + ///\param c is the coloumn of the element in question
8.1087 + ///\return the corresponding coefficient
8.1088 +
8.1089 + Value coeff(Row r, Col c) const {
8.1090 + return _getCoeff(_lpId(r),_lpId(c));
8.1091 + }
8.1092 +
8.1093 + /// Set the lower bound of a column (i.e a variable)
8.1094 +
8.1095 + /// The lower bound of a variable (column) has to be given by an
8.1096 + /// extended number of type Value, i.e. a finite number of type
8.1097 + /// Value or -\ref INF.
8.1098 + void colLowerBound(Col c, Value value) {
8.1099 + _setColLowerBound(_lpId(c),value);
8.1100 + }
8.1101 +
8.1102 + /// Get the lower bound of a column (i.e a variable)
8.1103 +
8.1104 + /// This function returns the lower bound for column (variable) \t c
8.1105 + /// (this might be -\ref INF as well).
8.1106 + ///\return The lower bound for coloumn \t c
8.1107 + Value colLowerBound(Col c) const {
8.1108 + return _getColLowerBound(_lpId(c));
8.1109 + }
8.1110 +
8.1111 + ///\brief Set the lower bound of several columns
8.1112 + ///(i.e a variables) at once
8.1113 + ///
8.1114 + ///This magic function takes a container as its argument
8.1115 + ///and applies the function on all of its elements.
8.1116 + /// The lower bound of a variable (column) has to be given by an
8.1117 + /// extended number of type Value, i.e. a finite number of type
8.1118 + /// Value or -\ref INF.
8.1119 +#ifdef DOXYGEN
8.1120 + template<class T>
8.1121 + void colLowerBound(T &t, Value value) { return 0;}
8.1122 +#else
8.1123 + template<class T>
8.1124 + typename enable_if<typename T::value_type::LpSolverCol,void>::type
8.1125 + colLowerBound(T &t, Value value,dummy<0> = 0) {
8.1126 + for(typename T::iterator i=t.begin();i!=t.end();++i) {
8.1127 + colLowerBound(*i, value);
8.1128 + }
8.1129 + }
8.1130 + template<class T>
8.1131 + typename enable_if<typename T::value_type::second_type::LpSolverCol,
8.1132 + void>::type
8.1133 + colLowerBound(T &t, Value value,dummy<1> = 1) {
8.1134 + for(typename T::iterator i=t.begin();i!=t.end();++i) {
8.1135 + colLowerBound(i->second, value);
8.1136 + }
8.1137 + }
8.1138 + template<class T>
8.1139 + typename enable_if<typename T::MapIt::Value::LpSolverCol,
8.1140 + void>::type
8.1141 + colLowerBound(T &t, Value value,dummy<2> = 2) {
8.1142 + for(typename T::MapIt i(t); i!=INVALID; ++i){
8.1143 + colLowerBound(*i, value);
8.1144 + }
8.1145 + }
8.1146 +#endif
8.1147 +
8.1148 + /// Set the upper bound of a column (i.e a variable)
8.1149 +
8.1150 + /// The upper bound of a variable (column) has to be given by an
8.1151 + /// extended number of type Value, i.e. a finite number of type
8.1152 + /// Value or \ref INF.
8.1153 + void colUpperBound(Col c, Value value) {
8.1154 + _setColUpperBound(_lpId(c),value);
8.1155 + };
8.1156 +
8.1157 + /// Get the upper bound of a column (i.e a variable)
8.1158 +
8.1159 + /// This function returns the upper bound for column (variable) \t c
8.1160 + /// (this might be \ref INF as well).
8.1161 + ///\return The upper bound for coloumn \t c
8.1162 + Value colUpperBound(Col c) const {
8.1163 + return _getColUpperBound(_lpId(c));
8.1164 + }
8.1165 +
8.1166 + ///\brief Set the upper bound of several columns
8.1167 + ///(i.e a variables) at once
8.1168 + ///
8.1169 + ///This magic function takes a container as its argument
8.1170 + ///and applies the function on all of its elements.
8.1171 + /// The upper bound of a variable (column) has to be given by an
8.1172 + /// extended number of type Value, i.e. a finite number of type
8.1173 + /// Value or \ref INF.
8.1174 +#ifdef DOXYGEN
8.1175 + template<class T>
8.1176 + void colUpperBound(T &t, Value value) { return 0;}
8.1177 +#else
8.1178 + template<class T>
8.1179 + typename enable_if<typename T::value_type::LpSolverCol,void>::type
8.1180 + colUpperBound(T &t, Value value,dummy<0> = 0) {
8.1181 + for(typename T::iterator i=t.begin();i!=t.end();++i) {
8.1182 + colUpperBound(*i, value);
8.1183 + }
8.1184 + }
8.1185 + template<class T>
8.1186 + typename enable_if<typename T::value_type::second_type::LpSolverCol,
8.1187 + void>::type
8.1188 + colUpperBound(T &t, Value value,dummy<1> = 1) {
8.1189 + for(typename T::iterator i=t.begin();i!=t.end();++i) {
8.1190 + colUpperBound(i->second, value);
8.1191 + }
8.1192 + }
8.1193 + template<class T>
8.1194 + typename enable_if<typename T::MapIt::Value::LpSolverCol,
8.1195 + void>::type
8.1196 + colUpperBound(T &t, Value value,dummy<2> = 2) {
8.1197 + for(typename T::MapIt i(t); i!=INVALID; ++i){
8.1198 + colUpperBound(*i, value);
8.1199 + }
8.1200 + }
8.1201 +#endif
8.1202 +
8.1203 + /// Set the lower and the upper bounds of a column (i.e a variable)
8.1204 +
8.1205 + /// The lower and the upper bounds of
8.1206 + /// a variable (column) have to be given by an
8.1207 + /// extended number of type Value, i.e. a finite number of type
8.1208 + /// Value, -\ref INF or \ref INF.
8.1209 + void colBounds(Col c, Value lower, Value upper) {
8.1210 + _setColLowerBound(_lpId(c),lower);
8.1211 + _setColUpperBound(_lpId(c),upper);
8.1212 + }
8.1213 +
8.1214 + ///\brief Set the lower and the upper bound of several columns
8.1215 + ///(i.e a variables) at once
8.1216 + ///
8.1217 + ///This magic function takes a container as its argument
8.1218 + ///and applies the function on all of its elements.
8.1219 + /// The lower and the upper bounds of
8.1220 + /// a variable (column) have to be given by an
8.1221 + /// extended number of type Value, i.e. a finite number of type
8.1222 + /// Value, -\ref INF or \ref INF.
8.1223 +#ifdef DOXYGEN
8.1224 + template<class T>
8.1225 + void colBounds(T &t, Value lower, Value upper) { return 0;}
8.1226 +#else
8.1227 + template<class T>
8.1228 + typename enable_if<typename T::value_type::LpSolverCol,void>::type
8.1229 + colBounds(T &t, Value lower, Value upper,dummy<0> = 0) {
8.1230 + for(typename T::iterator i=t.begin();i!=t.end();++i) {
8.1231 + colBounds(*i, lower, upper);
8.1232 + }
8.1233 + }
8.1234 + template<class T>
8.1235 + typename enable_if<typename T::value_type::second_type::LpSolverCol,
8.1236 + void>::type
8.1237 + colBounds(T &t, Value lower, Value upper,dummy<1> = 1) {
8.1238 + for(typename T::iterator i=t.begin();i!=t.end();++i) {
8.1239 + colBounds(i->second, lower, upper);
8.1240 + }
8.1241 + }
8.1242 + template<class T>
8.1243 + typename enable_if<typename T::MapIt::Value::LpSolverCol,
8.1244 + void>::type
8.1245 + colBounds(T &t, Value lower, Value upper,dummy<2> = 2) {
8.1246 + for(typename T::MapIt i(t); i!=INVALID; ++i){
8.1247 + colBounds(*i, lower, upper);
8.1248 + }
8.1249 + }
8.1250 +#endif
8.1251 +
8.1252 +
8.1253 + /// Set the lower and the upper bounds of a row (i.e a constraint)
8.1254 +
8.1255 + /// The lower and the upper bound of a constraint (row) have to be
8.1256 + /// given by an extended number of type Value, i.e. a finite
8.1257 + /// number of type Value, -\ref INF or \ref INF. There is no
8.1258 + /// separate function for the lower and the upper bound because
8.1259 + /// that would have been hard to implement for CPLEX.
8.1260 + void rowBounds(Row c, Value lower, Value upper) {
8.1261 + _setRowBounds(_lpId(c),lower, upper);
8.1262 + }
8.1263 +
8.1264 + /// Get the lower and the upper bounds of a row (i.e a constraint)
8.1265 +
8.1266 + /// The lower and the upper bound of
8.1267 + /// a constraint (row) are
8.1268 + /// extended numbers of type Value, i.e. finite numbers of type
8.1269 + /// Value, -\ref INF or \ref INF.
8.1270 + /// \todo There is no separate function for the
8.1271 + /// lower and the upper bound because we had problems with the
8.1272 + /// implementation of the setting functions for CPLEX:
8.1273 + /// check out whether this can be done for these functions.
8.1274 + void getRowBounds(Row c, Value &lower, Value &upper) const {
8.1275 + _getRowBounds(_lpId(c),lower, upper);
8.1276 + }
8.1277 +
8.1278 + ///Set an element of the objective function
8.1279 + void objCoeff(Col c, Value v) {_setObjCoeff(_lpId(c),v); };
8.1280 +
8.1281 + ///Get an element of the objective function
8.1282 + Value objCoeff(Col c) const { return _getObjCoeff(_lpId(c)); };
8.1283 +
8.1284 + ///Set the objective function
8.1285 +
8.1286 + ///\param e is a linear expression of type \ref Expr.
8.1287 + void obj(Expr e) {
8.1288 + _clearObj();
8.1289 + for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
8.1290 + objCoeff((*i).first,(*i).second);
8.1291 + obj_const_comp=e.constComp();
8.1292 + }
8.1293 +
8.1294 + ///Get the objective function
8.1295 +
8.1296 + ///\return the objective function as a linear expression of type \ref Expr.
8.1297 + Expr obj() const {
8.1298 + Expr e;
8.1299 + for (ColIt it(*this); it != INVALID; ++it) {
8.1300 + double c = objCoeff(it);
8.1301 + if (c != 0.0) {
8.1302 + e.insert(std::make_pair(it, c));
8.1303 + }
8.1304 + }
8.1305 + return e;
8.1306 + }
8.1307 +
8.1308 +
8.1309 + ///Maximize
8.1310 + void max() { _setMax(); }
8.1311 + ///Minimize
8.1312 + void min() { _setMin(); }
8.1313 +
8.1314 + ///Query function: is this a maximization problem?
8.1315 + bool isMax() const {return _isMax(); }
8.1316 +
8.1317 + ///Query function: is this a minimization problem?
8.1318 + bool isMin() const {return !isMax(); }
8.1319 +
8.1320 + ///@}
8.1321 +
8.1322 +
8.1323 + ///\name Solve the LP
8.1324 +
8.1325 + ///@{
8.1326 +
8.1327 + ///\e Solve the LP problem at hand
8.1328 + ///
8.1329 + ///\return The result of the optimization procedure. Possible
8.1330 + ///values and their meanings can be found in the documentation of
8.1331 + ///\ref SolveExitStatus.
8.1332 + ///
8.1333 + ///\todo Which method is used to solve the problem
8.1334 + SolveExitStatus solve() { return _solve(); }
8.1335 +
8.1336 + ///@}
8.1337 +
8.1338 + ///\name Obtain the solution
8.1339 +
8.1340 + ///@{
8.1341 +
8.1342 + /// The status of the primal problem (the original LP problem)
8.1343 + SolutionStatus primalStatus() const {
8.1344 + return _getPrimalStatus();
8.1345 + }
8.1346 +
8.1347 + /// The status of the dual (of the original LP) problem
8.1348 + SolutionStatus dualStatus() const {
8.1349 + return _getDualStatus();
8.1350 + }
8.1351 +
8.1352 + ///The type of the original LP problem
8.1353 + ProblemTypes problemType() const {
8.1354 + return _getProblemType();
8.1355 + }
8.1356 +
8.1357 + ///\e
8.1358 + Value primal(Col c) const { return _getPrimal(_lpId(c)); }
8.1359 + ///\e
8.1360 + Value primal(const Expr& e) const {
8.1361 + double res = e.constComp();
8.1362 + for (std::map<Col, double>::const_iterator it = e.begin();
8.1363 + it != e.end(); ++it) {
8.1364 + res += _getPrimal(_lpId(it->first)) * it->second;
8.1365 + }
8.1366 + return res;
8.1367 + }
8.1368 +
8.1369 + ///\e
8.1370 + Value dual(Row r) const { return _getDual(_lpId(r)); }
8.1371 + ///\e
8.1372 + Value dual(const DualExpr& e) const {
8.1373 + double res = 0.0;
8.1374 + for (std::map<Row, double>::const_iterator it = e.begin();
8.1375 + it != e.end(); ++it) {
8.1376 + res += _getPrimal(_lpId(it->first)) * it->second;
8.1377 + }
8.1378 + return res;
8.1379 + }
8.1380 +
8.1381 + ///\e
8.1382 + bool isBasicCol(Col c) const { return _isBasicCol(_lpId(c)); }
8.1383 +
8.1384 + ///\e
8.1385 +
8.1386 + ///\return
8.1387 + ///- \ref INF or -\ref INF means either infeasibility or unboundedness
8.1388 + /// of the primal problem, depending on whether we minimize or maximize.
8.1389 + ///- \ref NaN if no primal solution is found.
8.1390 + ///- The (finite) objective value if an optimal solution is found.
8.1391 + Value primalValue() const { return _getPrimalValue()+obj_const_comp;}
8.1392 + ///@}
8.1393 +
8.1394 + };
8.1395 +
8.1396 +
8.1397 + /// \ingroup lp_group
8.1398 + ///
8.1399 + /// \brief Common base class for MIP solvers
8.1400 + /// \todo Much more docs
8.1401 + class MipSolverBase : virtual public LpSolverBase{
8.1402 + public:
8.1403 +
8.1404 + ///Possible variable (coloumn) types (e.g. real, integer, binary etc.)
8.1405 + enum ColTypes {
8.1406 + ///Continuous variable
8.1407 + REAL = 0,
8.1408 + ///Integer variable
8.1409 +
8.1410 + ///Unfortunately, cplex 7.5 somewhere writes something like
8.1411 + ///#define INTEGER 'I'
8.1412 + INT = 1
8.1413 + ///\todo No support for other types yet.
8.1414 + };
8.1415 +
8.1416 + ///Sets the type of the given coloumn to the given type
8.1417 + ///
8.1418 + ///Sets the type of the given coloumn to the given type.
8.1419 + void colType(Col c, ColTypes col_type) {
8.1420 + _colType(_lpId(c),col_type);
8.1421 + }
8.1422 +
8.1423 + ///Gives back the type of the column.
8.1424 + ///
8.1425 + ///Gives back the type of the column.
8.1426 + ColTypes colType(Col c) const {
8.1427 + return _colType(_lpId(c));
8.1428 + }
8.1429 +
8.1430 + ///Sets the type of the given Col to integer or remove that property.
8.1431 + ///
8.1432 + ///Sets the type of the given Col to integer or remove that property.
8.1433 + void integer(Col c, bool enable) {
8.1434 + if (enable)
8.1435 + colType(c,INT);
8.1436 + else
8.1437 + colType(c,REAL);
8.1438 + }
8.1439 +
8.1440 + ///Gives back whether the type of the column is integer or not.
8.1441 + ///
8.1442 + ///Gives back the type of the column.
8.1443 + ///\return true if the column has integer type and false if not.
8.1444 + bool integer(Col c) const {
8.1445 + return (colType(c)==INT);
8.1446 + }
8.1447 +
8.1448 + /// The status of the MIP problem
8.1449 + SolutionStatus mipStatus() const {
8.1450 + return _getMipStatus();
8.1451 + }
8.1452 +
8.1453 + protected:
8.1454 +
8.1455 + virtual ColTypes _colType(int col) const = 0;
8.1456 + virtual void _colType(int col, ColTypes col_type) = 0;
8.1457 + virtual SolutionStatus _getMipStatus() const = 0;
8.1458 +
8.1459 + };
8.1460 +
8.1461 + ///\relates LpSolverBase::Expr
8.1462 + ///
8.1463 + inline LpSolverBase::Expr operator+(const LpSolverBase::Expr &a,
8.1464 + const LpSolverBase::Expr &b)
8.1465 + {
8.1466 + LpSolverBase::Expr tmp(a);
8.1467 + tmp+=b;
8.1468 + return tmp;
8.1469 + }
8.1470 + ///\e
8.1471 +
8.1472 + ///\relates LpSolverBase::Expr
8.1473 + ///
8.1474 + inline LpSolverBase::Expr operator-(const LpSolverBase::Expr &a,
8.1475 + const LpSolverBase::Expr &b)
8.1476 + {
8.1477 + LpSolverBase::Expr tmp(a);
8.1478 + tmp-=b;
8.1479 + return tmp;
8.1480 + }
8.1481 + ///\e
8.1482 +
8.1483 + ///\relates LpSolverBase::Expr
8.1484 + ///
8.1485 + inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
8.1486 + const LpSolverBase::Value &b)
8.1487 + {
8.1488 + LpSolverBase::Expr tmp(a);
8.1489 + tmp*=b;
8.1490 + return tmp;
8.1491 + }
8.1492 +
8.1493 + ///\e
8.1494 +
8.1495 + ///\relates LpSolverBase::Expr
8.1496 + ///
8.1497 + inline LpSolverBase::Expr operator*(const LpSolverBase::Value &a,
8.1498 + const LpSolverBase::Expr &b)
8.1499 + {
8.1500 + LpSolverBase::Expr tmp(b);
8.1501 + tmp*=a;
8.1502 + return tmp;
8.1503 + }
8.1504 + ///\e
8.1505 +
8.1506 + ///\relates LpSolverBase::Expr
8.1507 + ///
8.1508 + inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
8.1509 + const LpSolverBase::Value &b)
8.1510 + {
8.1511 + LpSolverBase::Expr tmp(a);
8.1512 + tmp/=b;
8.1513 + return tmp;
8.1514 + }
8.1515 +
8.1516 + ///\e
8.1517 +
8.1518 + ///\relates LpSolverBase::Constr
8.1519 + ///
8.1520 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
8.1521 + const LpSolverBase::Expr &f)
8.1522 + {
8.1523 + return LpSolverBase::Constr(-LpSolverBase::INF,e-f,0);
8.1524 + }
8.1525 +
8.1526 + ///\e
8.1527 +
8.1528 + ///\relates LpSolverBase::Constr
8.1529 + ///
8.1530 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &e,
8.1531 + const LpSolverBase::Expr &f)
8.1532 + {
8.1533 + return LpSolverBase::Constr(e,f);
8.1534 + }
8.1535 +
8.1536 + ///\e
8.1537 +
8.1538 + ///\relates LpSolverBase::Constr
8.1539 + ///
8.1540 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
8.1541 + const LpSolverBase::Value &f)
8.1542 + {
8.1543 + return LpSolverBase::Constr(-LpSolverBase::INF,e,f);
8.1544 + }
8.1545 +
8.1546 + ///\e
8.1547 +
8.1548 + ///\relates LpSolverBase::Constr
8.1549 + ///
8.1550 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
8.1551 + const LpSolverBase::Expr &f)
8.1552 + {
8.1553 + return LpSolverBase::Constr(-LpSolverBase::INF,f-e,0);
8.1554 + }
8.1555 +
8.1556 +
8.1557 + ///\e
8.1558 +
8.1559 + ///\relates LpSolverBase::Constr
8.1560 + ///
8.1561 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &e,
8.1562 + const LpSolverBase::Expr &f)
8.1563 + {
8.1564 + return LpSolverBase::Constr(f,e);
8.1565 + }
8.1566 +
8.1567 +
8.1568 + ///\e
8.1569 +
8.1570 + ///\relates LpSolverBase::Constr
8.1571 + ///
8.1572 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
8.1573 + const LpSolverBase::Value &f)
8.1574 + {
8.1575 + return LpSolverBase::Constr(f,e,LpSolverBase::INF);
8.1576 + }
8.1577 +
8.1578 + ///\e
8.1579 +
8.1580 + ///\relates LpSolverBase::Constr
8.1581 + ///
8.1582 + inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
8.1583 + const LpSolverBase::Value &f)
8.1584 + {
8.1585 + return LpSolverBase::Constr(f,e,f);
8.1586 + }
8.1587 +
8.1588 + ///\e
8.1589 +
8.1590 + ///\relates LpSolverBase::Constr
8.1591 + ///
8.1592 + inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
8.1593 + const LpSolverBase::Expr &f)
8.1594 + {
8.1595 + return LpSolverBase::Constr(0,e-f,0);
8.1596 + }
8.1597 +
8.1598 + ///\e
8.1599 +
8.1600 + ///\relates LpSolverBase::Constr
8.1601 + ///
8.1602 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &n,
8.1603 + const LpSolverBase::Constr&c)
8.1604 + {
8.1605 + LpSolverBase::Constr tmp(c);
8.1606 + LEMON_ASSERT(LpSolverBase::isNaN(tmp.lowerBound()), "Wrong LP constraint");
8.1607 + tmp.lowerBound()=n;
8.1608 + return tmp;
8.1609 + }
8.1610 + ///\e
8.1611 +
8.1612 + ///\relates LpSolverBase::Constr
8.1613 + ///
8.1614 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
8.1615 + const LpSolverBase::Value &n)
8.1616 + {
8.1617 + LpSolverBase::Constr tmp(c);
8.1618 + LEMON_ASSERT(LpSolverBase::isNaN(tmp.upperBound()), "Wrong LP constraint");
8.1619 + tmp.upperBound()=n;
8.1620 + return tmp;
8.1621 + }
8.1622 +
8.1623 + ///\e
8.1624 +
8.1625 + ///\relates LpSolverBase::Constr
8.1626 + ///
8.1627 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &n,
8.1628 + const LpSolverBase::Constr&c)
8.1629 + {
8.1630 + LpSolverBase::Constr tmp(c);
8.1631 + LEMON_ASSERT(LpSolverBase::isNaN(tmp.upperBound()), "Wrong LP constraint");
8.1632 + tmp.upperBound()=n;
8.1633 + return tmp;
8.1634 + }
8.1635 + ///\e
8.1636 +
8.1637 + ///\relates LpSolverBase::Constr
8.1638 + ///
8.1639 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
8.1640 + const LpSolverBase::Value &n)
8.1641 + {
8.1642 + LpSolverBase::Constr tmp(c);
8.1643 + LEMON_ASSERT(LpSolverBase::isNaN(tmp.lowerBound()), "Wrong LP constraint");
8.1644 + tmp.lowerBound()=n;
8.1645 + return tmp;
8.1646 + }
8.1647 +
8.1648 + ///\e
8.1649 +
8.1650 + ///\relates LpSolverBase::DualExpr
8.1651 + ///
8.1652 + inline LpSolverBase::DualExpr operator+(const LpSolverBase::DualExpr &a,
8.1653 + const LpSolverBase::DualExpr &b)
8.1654 + {
8.1655 + LpSolverBase::DualExpr tmp(a);
8.1656 + tmp+=b;
8.1657 + return tmp;
8.1658 + }
8.1659 + ///\e
8.1660 +
8.1661 + ///\relates LpSolverBase::DualExpr
8.1662 + ///
8.1663 + inline LpSolverBase::DualExpr operator-(const LpSolverBase::DualExpr &a,
8.1664 + const LpSolverBase::DualExpr &b)
8.1665 + {
8.1666 + LpSolverBase::DualExpr tmp(a);
8.1667 + tmp-=b;
8.1668 + return tmp;
8.1669 + }
8.1670 + ///\e
8.1671 +
8.1672 + ///\relates LpSolverBase::DualExpr
8.1673 + ///
8.1674 + inline LpSolverBase::DualExpr operator*(const LpSolverBase::DualExpr &a,
8.1675 + const LpSolverBase::Value &b)
8.1676 + {
8.1677 + LpSolverBase::DualExpr tmp(a);
8.1678 + tmp*=b;
8.1679 + return tmp;
8.1680 + }
8.1681 +
8.1682 + ///\e
8.1683 +
8.1684 + ///\relates LpSolverBase::DualExpr
8.1685 + ///
8.1686 + inline LpSolverBase::DualExpr operator*(const LpSolverBase::Value &a,
8.1687 + const LpSolverBase::DualExpr &b)
8.1688 + {
8.1689 + LpSolverBase::DualExpr tmp(b);
8.1690 + tmp*=a;
8.1691 + return tmp;
8.1692 + }
8.1693 + ///\e
8.1694 +
8.1695 + ///\relates LpSolverBase::DualExpr
8.1696 + ///
8.1697 + inline LpSolverBase::DualExpr operator/(const LpSolverBase::DualExpr &a,
8.1698 + const LpSolverBase::Value &b)
8.1699 + {
8.1700 + LpSolverBase::DualExpr tmp(a);
8.1701 + tmp/=b;
8.1702 + return tmp;
8.1703 + }
8.1704 +
8.1705 +
8.1706 +} //namespace lemon
8.1707 +
8.1708 +#endif //LEMON_LP_BASE_H
9.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
9.2 +++ b/lemon/lp_cplex.cc Tue Dec 02 21:40:33 2008 +0100
9.3 @@ -0,0 +1,699 @@
9.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
9.5 + *
9.6 + * This file is a part of LEMON, a generic C++ optimization library.
9.7 + *
9.8 + * Copyright (C) 2003-2008
9.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
9.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
9.11 + *
9.12 + * Permission to use, modify and distribute this software is granted
9.13 + * provided that this copyright notice appears in all copies. For
9.14 + * precise terms see the accompanying LICENSE file.
9.15 + *
9.16 + * This software is provided "AS IS" with no warranty of any kind,
9.17 + * express or implied, and with no claim as to its suitability for any
9.18 + * purpose.
9.19 + *
9.20 + */
9.21 +
9.22 +#include <iostream>
9.23 +#include <vector>
9.24 +#include <lemon/lp_cplex.h>
9.25 +
9.26 +extern "C" {
9.27 +#include <ilcplex/cplex.h>
9.28 +}
9.29 +
9.30 +
9.31 +///\file
9.32 +///\brief Implementation of the LEMON-CPLEX lp solver interface.
9.33 +namespace lemon {
9.34 +
9.35 + LpCplex::LpCplex() {
9.36 + // env = CPXopenCPLEXdevelop(&status);
9.37 + env = CPXopenCPLEX(&status);
9.38 + lp = CPXcreateprob(env, &status, "LP problem");
9.39 + }
9.40 +
9.41 + LpCplex::LpCplex(const LpCplex& cplex) : LpSolverBase() {
9.42 + env = CPXopenCPLEX(&status);
9.43 + lp = CPXcloneprob(env, cplex.lp, &status);
9.44 + rows = cplex.rows;
9.45 + cols = cplex.cols;
9.46 + }
9.47 +
9.48 + LpCplex::~LpCplex() {
9.49 + CPXfreeprob(env,&lp);
9.50 + CPXcloseCPLEX(&env);
9.51 + }
9.52 +
9.53 + LpSolverBase* LpCplex::_newLp()
9.54 + {
9.55 + //The first approach opens a new environment
9.56 + return new LpCplex();
9.57 + }
9.58 +
9.59 + LpSolverBase* LpCplex::_copyLp() {
9.60 + return new LpCplex(*this);
9.61 + }
9.62 +
9.63 + int LpCplex::_addCol()
9.64 + {
9.65 + int i = CPXgetnumcols(env, lp);
9.66 + Value lb[1],ub[1];
9.67 + lb[0]=-INF;
9.68 + ub[0]=INF;
9.69 + status = CPXnewcols(env, lp, 1, NULL, lb, ub, NULL, NULL);
9.70 + return i;
9.71 + }
9.72 +
9.73 +
9.74 + int LpCplex::_addRow()
9.75 + {
9.76 + //We want a row that is not constrained
9.77 + char sense[1];
9.78 + sense[0]='L';//<= constraint
9.79 + Value rhs[1];
9.80 + rhs[0]=INF;
9.81 + int i = CPXgetnumrows(env, lp);
9.82 + status = CPXnewrows(env, lp, 1, rhs, sense, NULL, NULL);
9.83 + return i;
9.84 + }
9.85 +
9.86 +
9.87 + void LpCplex::_eraseCol(int i) {
9.88 + CPXdelcols(env, lp, i, i);
9.89 + }
9.90 +
9.91 + void LpCplex::_eraseRow(int i) {
9.92 + CPXdelrows(env, lp, i, i);
9.93 + }
9.94 +
9.95 + void LpCplex::_getColName(int col, std::string &name) const
9.96 + {
9.97 + ///\bug Untested
9.98 + int storespace;
9.99 + CPXgetcolname(env, lp, 0, 0, 0, &storespace, col, col);
9.100 + if (storespace == 0) {
9.101 + name.clear();
9.102 + return;
9.103 + }
9.104 +
9.105 + storespace *= -1;
9.106 + std::vector<char> buf(storespace);
9.107 + char *names[1];
9.108 + int dontcare;
9.109 + ///\bug return code unchecked for error
9.110 + CPXgetcolname(env, lp, names, &*buf.begin(), storespace,
9.111 + &dontcare, col, col);
9.112 + name = names[0];
9.113 + }
9.114 +
9.115 + void LpCplex::_setColName(int col, const std::string &name)
9.116 + {
9.117 + ///\bug Untested
9.118 + char *names[1];
9.119 + names[0] = const_cast<char*>(name.c_str());
9.120 + ///\bug return code unchecked for error
9.121 + CPXchgcolname(env, lp, 1, &col, names);
9.122 + }
9.123 +
9.124 + int LpCplex::_colByName(const std::string& name) const
9.125 + {
9.126 + int index;
9.127 + if (CPXgetcolindex(env, lp,
9.128 + const_cast<char*>(name.c_str()), &index) == 0) {
9.129 + return index;
9.130 + }
9.131 + return -1;
9.132 + }
9.133 +
9.134 + ///\warning Data at index 0 is ignored in the arrays.
9.135 + void LpCplex::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e)
9.136 + {
9.137 + std::vector<int> indices;
9.138 + std::vector<int> rowlist;
9.139 + std::vector<Value> values;
9.140 +
9.141 + for(ConstRowIterator it=b; it!=e; ++it) {
9.142 + indices.push_back(it->first);
9.143 + values.push_back(it->second);
9.144 + rowlist.push_back(i);
9.145 + }
9.146 +
9.147 + status = CPXchgcoeflist(env, lp, values.size(),
9.148 + &rowlist[0], &indices[0], &values[0]);
9.149 + }
9.150 +
9.151 + void LpCplex::_getRowCoeffs(int i, RowIterator b) const {
9.152 + int tmp1, tmp2, tmp3, length;
9.153 + CPXgetrows(env, lp, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
9.154 +
9.155 + length = -length;
9.156 + std::vector<int> indices(length);
9.157 + std::vector<double> values(length);
9.158 +
9.159 + CPXgetrows(env, lp, &tmp1, &tmp2, &indices[0], &values[0],
9.160 + length, &tmp3, i, i);
9.161 +
9.162 + for (int i = 0; i < length; ++i) {
9.163 + *b = std::make_pair(indices[i], values[i]);
9.164 + ++b;
9.165 + }
9.166 +
9.167 + /// \todo implement
9.168 + }
9.169 +
9.170 + void LpCplex::_setColCoeffs(int i, ConstColIterator b, ConstColIterator e)
9.171 + {
9.172 + std::vector<int> indices;
9.173 + std::vector<int> collist;
9.174 + std::vector<Value> values;
9.175 +
9.176 + for(ConstColIterator it=b; it!=e; ++it) {
9.177 + indices.push_back(it->first);
9.178 + values.push_back(it->second);
9.179 + collist.push_back(i);
9.180 + }
9.181 +
9.182 + status = CPXchgcoeflist(env, lp, values.size(),
9.183 + &indices[0], &collist[0], &values[0]);
9.184 + }
9.185 +
9.186 + void LpCplex::_getColCoeffs(int i, ColIterator b) const {
9.187 +
9.188 + int tmp1, tmp2, tmp3, length;
9.189 + CPXgetcols(env, lp, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
9.190 +
9.191 + length = -length;
9.192 + std::vector<int> indices(length);
9.193 + std::vector<double> values(length);
9.194 +
9.195 + CPXgetcols(env, lp, &tmp1, &tmp2, &indices[0], &values[0],
9.196 + length, &tmp3, i, i);
9.197 +
9.198 + for (int i = 0; i < length; ++i) {
9.199 + *b = std::make_pair(indices[i], values[i]);
9.200 + ++b;
9.201 + }
9.202 +
9.203 + }
9.204 +
9.205 + void LpCplex::_setCoeff(int row, int col, Value value)
9.206 + {
9.207 + CPXchgcoef(env, lp, row, col, value);
9.208 + }
9.209 +
9.210 + LpCplex::Value LpCplex::_getCoeff(int row, int col) const
9.211 + {
9.212 + LpCplex::Value value;
9.213 + CPXgetcoef(env, lp, row, col, &value);
9.214 + return value;
9.215 + }
9.216 +
9.217 + void LpCplex::_setColLowerBound(int i, Value value)
9.218 + {
9.219 + int indices[1];
9.220 + indices[0]=i;
9.221 + char lu[1];
9.222 + lu[0]='L';
9.223 + Value bd[1];
9.224 + bd[0]=value;
9.225 + status = CPXchgbds(env, lp, 1, indices, lu, bd);
9.226 +
9.227 + }
9.228 +
9.229 + LpCplex::Value LpCplex::_getColLowerBound(int i) const
9.230 + {
9.231 + LpCplex::Value x;
9.232 + CPXgetlb (env, lp, &x, i, i);
9.233 + if (x <= -CPX_INFBOUND) x = -INF;
9.234 + return x;
9.235 + }
9.236 +
9.237 + void LpCplex::_setColUpperBound(int i, Value value)
9.238 + {
9.239 + int indices[1];
9.240 + indices[0]=i;
9.241 + char lu[1];
9.242 + lu[0]='U';
9.243 + Value bd[1];
9.244 + bd[0]=value;
9.245 + status = CPXchgbds(env, lp, 1, indices, lu, bd);
9.246 + }
9.247 +
9.248 + LpCplex::Value LpCplex::_getColUpperBound(int i) const
9.249 + {
9.250 + LpCplex::Value x;
9.251 + CPXgetub (env, lp, &x, i, i);
9.252 + if (x >= CPX_INFBOUND) x = INF;
9.253 + return x;
9.254 + }
9.255 +
9.256 + //This will be easier to implement
9.257 + void LpCplex::_setRowBounds(int i, Value lb, Value ub)
9.258 + {
9.259 + //Bad parameter
9.260 + if (lb==INF || ub==-INF) {
9.261 + //FIXME error
9.262 + }
9.263 +
9.264 + int cnt=1;
9.265 + int indices[1];
9.266 + indices[0]=i;
9.267 + char sense[1];
9.268 +
9.269 + if (lb==-INF){
9.270 + sense[0]='L';
9.271 + CPXchgsense(env, lp, cnt, indices, sense);
9.272 + CPXchgcoef(env, lp, i, -1, ub);
9.273 +
9.274 + }
9.275 + else{
9.276 + if (ub==INF){
9.277 + sense[0]='G';
9.278 + CPXchgsense(env, lp, cnt, indices, sense);
9.279 + CPXchgcoef(env, lp, i, -1, lb);
9.280 + }
9.281 + else{
9.282 + if (lb == ub){
9.283 + sense[0]='E';
9.284 + CPXchgsense(env, lp, cnt, indices, sense);
9.285 + CPXchgcoef(env, lp, i, -1, lb);
9.286 + }
9.287 + else{
9.288 + sense[0]='R';
9.289 + CPXchgsense(env, lp, cnt, indices, sense);
9.290 + CPXchgcoef(env, lp, i, -1, lb);
9.291 + CPXchgcoef(env, lp, i, -2, ub-lb);
9.292 + }
9.293 + }
9.294 + }
9.295 + }
9.296 +
9.297 +// void LpCplex::_setRowLowerBound(int i, Value value)
9.298 +// {
9.299 +// //Not implemented, obsolete
9.300 +// }
9.301 +
9.302 +// void LpCplex::_setRowUpperBound(int i, Value value)
9.303 +// {
9.304 +// //Not implemented, obsolete
9.305 +// // //TODO Ezt kell meg megirni
9.306 +// // //type of the problem
9.307 +// // char sense[1];
9.308 +// // status = CPXgetsense(env, lp, sense, i, i);
9.309 +// // Value rhs[1];
9.310 +// // status = CPXgetrhs(env, lp, rhs, i, i);
9.311 +
9.312 +// // switch (sense[0]) {
9.313 +// // case 'L'://<= constraint
9.314 +// // break;
9.315 +// // case 'E'://= constraint
9.316 +// // break;
9.317 +// // case 'G'://>= constraint
9.318 +// // break;
9.319 +// // case 'R'://ranged constraint
9.320 +// // break;
9.321 +// // default: ;
9.322 +// // //FIXME error
9.323 +// // }
9.324 +
9.325 +// // status = CPXchgcoef(env, lp, i, -2, value_rng);
9.326 +// }
9.327 +
9.328 + void LpCplex::_getRowBounds(int i, Value &lb, Value &ub) const
9.329 + {
9.330 + char sense;
9.331 + CPXgetsense(env, lp, &sense,i,i);
9.332 + lb=-INF;
9.333 + ub=INF;
9.334 + switch (sense)
9.335 + {
9.336 + case 'L':
9.337 + CPXgetcoef(env, lp, i, -1, &ub);
9.338 + break;
9.339 + case 'G':
9.340 + CPXgetcoef(env, lp, i, -1, &lb);
9.341 + break;
9.342 + case 'E':
9.343 + CPXgetcoef(env, lp, i, -1, &lb);
9.344 + ub=lb;
9.345 + break;
9.346 + case 'R':
9.347 + CPXgetcoef(env, lp, i, -1, &lb);
9.348 + Value x;
9.349 + CPXgetcoef(env, lp, i, -2, &x);
9.350 + ub=lb+x;
9.351 + break;
9.352 + }
9.353 + }
9.354 +
9.355 + void LpCplex::_setObjCoeff(int i, Value obj_coef)
9.356 + {
9.357 + CPXchgcoef(env, lp, -1, i, obj_coef);
9.358 + }
9.359 +
9.360 + LpCplex::Value LpCplex::_getObjCoeff(int i) const
9.361 + {
9.362 + Value x;
9.363 + CPXgetcoef(env, lp, -1, i, &x);
9.364 + return x;
9.365 + }
9.366 +
9.367 + void LpCplex::_clearObj()
9.368 + {
9.369 + for (int i=0;i< CPXgetnumcols(env, lp);++i){
9.370 + CPXchgcoef(env, lp, -1, i, 0);
9.371 + }
9.372 +
9.373 + }
9.374 + // The routine returns zero unless an error occurred during the
9.375 + // optimization. Examples of errors include exhausting available
9.376 + // memory (CPXERR_NO_MEMORY) or encountering invalid data in the
9.377 + // CPLEX problem object (CPXERR_NO_PROBLEM). Exceeding a
9.378 + // user-specified CPLEX limit, or proving the model infeasible or
9.379 + // unbounded, are not considered errors. Note that a zero return
9.380 + // value does not necessarily mean that a solution exists. Use query
9.381 + // routines CPXsolninfo, CPXgetstat, and CPXsolution to obtain
9.382 + // further information about the status of the optimization.
9.383 + LpCplex::SolveExitStatus LpCplex::_solve()
9.384 + {
9.385 + //CPX_PARAM_LPMETHOD
9.386 + status = CPXlpopt(env, lp);
9.387 + //status = CPXprimopt(env, lp);
9.388 +#if CPX_VERSION >= 800
9.389 + if (status)
9.390 + {
9.391 + return UNSOLVED;
9.392 + }
9.393 + else
9.394 + {
9.395 + switch (CPXgetstat(env, lp))
9.396 + {
9.397 + case CPX_STAT_OPTIMAL:
9.398 + case CPX_STAT_INFEASIBLE:
9.399 + case CPX_STAT_UNBOUNDED:
9.400 + return SOLVED;
9.401 + default:
9.402 + return UNSOLVED;
9.403 + }
9.404 + }
9.405 +#else
9.406 + if (status == 0){
9.407 + //We want to exclude some cases
9.408 + switch (CPXgetstat(env, lp)){
9.409 + case CPX_OBJ_LIM:
9.410 + case CPX_IT_LIM_FEAS:
9.411 + case CPX_IT_LIM_INFEAS:
9.412 + case CPX_TIME_LIM_FEAS:
9.413 + case CPX_TIME_LIM_INFEAS:
9.414 + return UNSOLVED;
9.415 + default:
9.416 + return SOLVED;
9.417 + }
9.418 + }
9.419 + else{
9.420 + return UNSOLVED;
9.421 + }
9.422 +#endif
9.423 + }
9.424 +
9.425 + LpCplex::Value LpCplex::_getPrimal(int i) const
9.426 + {
9.427 + Value x;
9.428 + CPXgetx(env, lp, &x, i, i);
9.429 + return x;
9.430 + }
9.431 +
9.432 + LpCplex::Value LpCplex::_getDual(int i) const
9.433 + {
9.434 + Value y;
9.435 + CPXgetpi(env, lp, &y, i, i);
9.436 + return y;
9.437 + }
9.438 +
9.439 + LpCplex::Value LpCplex::_getPrimalValue() const
9.440 + {
9.441 + Value objval;
9.442 + //method = CPXgetmethod (env, lp);
9.443 + //printf("CPXgetprobtype %d \n",CPXgetprobtype(env,lp));
9.444 + CPXgetobjval(env, lp, &objval);
9.445 + //printf("Objective value: %g \n",objval);
9.446 + return objval;
9.447 + }
9.448 + bool LpCplex::_isBasicCol(int i) const
9.449 + {
9.450 + std::vector<int> cstat(CPXgetnumcols(env, lp));
9.451 + CPXgetbase(env, lp, &*cstat.begin(), NULL);
9.452 + return (cstat[i]==CPX_BASIC);
9.453 + }
9.454 +
9.455 +//7.5-os cplex statusai (Vigyazat: a 9.0-asei masok!)
9.456 +// This table lists the statuses, returned by the CPXgetstat()
9.457 +// routine, for solutions to LP problems or mixed integer problems. If
9.458 +// no solution exists, the return value is zero.
9.459 +
9.460 +// For Simplex, Barrier
9.461 +// 1 CPX_OPTIMAL
9.462 +// Optimal solution found
9.463 +// 2 CPX_INFEASIBLE
9.464 +// Problem infeasible
9.465 +// 3 CPX_UNBOUNDED
9.466 +// Problem unbounded
9.467 +// 4 CPX_OBJ_LIM
9.468 +// Objective limit exceeded in Phase II
9.469 +// 5 CPX_IT_LIM_FEAS
9.470 +// Iteration limit exceeded in Phase II
9.471 +// 6 CPX_IT_LIM_INFEAS
9.472 +// Iteration limit exceeded in Phase I
9.473 +// 7 CPX_TIME_LIM_FEAS
9.474 +// Time limit exceeded in Phase II
9.475 +// 8 CPX_TIME_LIM_INFEAS
9.476 +// Time limit exceeded in Phase I
9.477 +// 9 CPX_NUM_BEST_FEAS
9.478 +// Problem non-optimal, singularities in Phase II
9.479 +// 10 CPX_NUM_BEST_INFEAS
9.480 +// Problem non-optimal, singularities in Phase I
9.481 +// 11 CPX_OPTIMAL_INFEAS
9.482 +// Optimal solution found, unscaled infeasibilities
9.483 +// 12 CPX_ABORT_FEAS
9.484 +// Aborted in Phase II
9.485 +// 13 CPX_ABORT_INFEAS
9.486 +// Aborted in Phase I
9.487 +// 14 CPX_ABORT_DUAL_INFEAS
9.488 +// Aborted in barrier, dual infeasible
9.489 +// 15 CPX_ABORT_PRIM_INFEAS
9.490 +// Aborted in barrier, primal infeasible
9.491 +// 16 CPX_ABORT_PRIM_DUAL_INFEAS
9.492 +// Aborted in barrier, primal and dual infeasible
9.493 +// 17 CPX_ABORT_PRIM_DUAL_FEAS
9.494 +// Aborted in barrier, primal and dual feasible
9.495 +// 18 CPX_ABORT_CROSSOVER
9.496 +// Aborted in crossover
9.497 +// 19 CPX_INForUNBD
9.498 +// Infeasible or unbounded
9.499 +// 20 CPX_PIVOT
9.500 +// User pivot used
9.501 +//
9.502 +// Ezeket hova tegyem:
9.503 +// ??case CPX_ABORT_DUAL_INFEAS
9.504 +// ??case CPX_ABORT_CROSSOVER
9.505 +// ??case CPX_INForUNBD
9.506 +// ??case CPX_PIVOT
9.507 +
9.508 +//Some more interesting stuff:
9.509 +
9.510 +// CPX_PARAM_LPMETHOD 1062 int LPMETHOD
9.511 +// 0 Automatic
9.512 +// 1 Primal Simplex
9.513 +// 2 Dual Simplex
9.514 +// 3 Network Simplex
9.515 +// 4 Standard Barrier
9.516 +// Default: 0
9.517 +// Description: Method for linear optimization.
9.518 +// Determines which algorithm is used when CPXlpopt() (or "optimize"
9.519 +// in the Interactive Optimizer) is called. Currently the behavior of
9.520 +// the "Automatic" setting is that CPLEX simply invokes the dual
9.521 +// simplex method, but this capability may be expanded in the future
9.522 +// so that CPLEX chooses the method based on problem characteristics
9.523 +#if CPX_VERSION < 900
9.524 + void statusSwitch(CPXENVptr env,int& stat){
9.525 + int lpmethod;
9.526 + CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);
9.527 + if (lpmethod==2){
9.528 + if (stat==CPX_UNBOUNDED){
9.529 + stat=CPX_INFEASIBLE;
9.530 + }
9.531 + else{
9.532 + if (stat==CPX_INFEASIBLE)
9.533 + stat=CPX_UNBOUNDED;
9.534 + }
9.535 + }
9.536 + }
9.537 +#else
9.538 + void statusSwitch(CPXENVptr,int&){}
9.539 +#endif
9.540 +
9.541 + LpCplex::SolutionStatus LpCplex::_getPrimalStatus() const
9.542 + {
9.543 + //Unboundedness not treated well: the following is from cplex 9.0 doc
9.544 + // About Unboundedness
9.545 +
9.546 + // The treatment of models that are unbounded involves a few
9.547 + // subtleties. Specifically, a declaration of unboundedness means that
9.548 + // ILOG CPLEX has determined that the model has an unbounded
9.549 + // ray. Given any feasible solution x with objective z, a multiple of
9.550 + // the unbounded ray can be added to x to give a feasible solution
9.551 + // with objective z-1 (or z+1 for maximization models). Thus, if a
9.552 + // feasible solution exists, then the optimal objective is
9.553 + // unbounded. Note that ILOG CPLEX has not necessarily concluded that
9.554 + // a feasible solution exists. Users can call the routine CPXsolninfo
9.555 + // to determine whether ILOG CPLEX has also concluded that the model
9.556 + // has a feasible solution.
9.557 +
9.558 + int stat = CPXgetstat(env, lp);
9.559 +#if CPX_VERSION >= 800
9.560 + switch (stat)
9.561 + {
9.562 + case CPX_STAT_OPTIMAL:
9.563 + return OPTIMAL;
9.564 + case CPX_STAT_UNBOUNDED:
9.565 + return INFINITE;
9.566 + case CPX_STAT_INFEASIBLE:
9.567 + return INFEASIBLE;
9.568 + default:
9.569 + return UNDEFINED;
9.570 + }
9.571 +#else
9.572 + statusSwitch(env,stat);
9.573 + //CPXgetstat(env, lp);
9.574 + //printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL);
9.575 + switch (stat) {
9.576 + case 0:
9.577 + return UNDEFINED; //Undefined
9.578 + case CPX_OPTIMAL://Optimal
9.579 + return OPTIMAL;
9.580 + case CPX_UNBOUNDED://Unbounded
9.581 + return INFEASIBLE;//In case of dual simplex
9.582 + //return INFINITE;
9.583 + case CPX_INFEASIBLE://Infeasible
9.584 + // case CPX_IT_LIM_INFEAS:
9.585 +// case CPX_TIME_LIM_INFEAS:
9.586 +// case CPX_NUM_BEST_INFEAS:
9.587 +// case CPX_OPTIMAL_INFEAS:
9.588 +// case CPX_ABORT_INFEAS:
9.589 +// case CPX_ABORT_PRIM_INFEAS:
9.590 +// case CPX_ABORT_PRIM_DUAL_INFEAS:
9.591 + return INFINITE;//In case of dual simplex
9.592 + //return INFEASIBLE;
9.593 +// case CPX_OBJ_LIM:
9.594 +// case CPX_IT_LIM_FEAS:
9.595 +// case CPX_TIME_LIM_FEAS:
9.596 +// case CPX_NUM_BEST_FEAS:
9.597 +// case CPX_ABORT_FEAS:
9.598 +// case CPX_ABORT_PRIM_DUAL_FEAS:
9.599 +// return FEASIBLE;
9.600 + default:
9.601 + return UNDEFINED; //Everything else comes here
9.602 + //FIXME error
9.603 + }
9.604 +#endif
9.605 + }
9.606 +
9.607 +//9.0-as cplex verzio statusai
9.608 +// CPX_STAT_ABORT_DUAL_OBJ_LIM
9.609 +// CPX_STAT_ABORT_IT_LIM
9.610 +// CPX_STAT_ABORT_OBJ_LIM
9.611 +// CPX_STAT_ABORT_PRIM_OBJ_LIM
9.612 +// CPX_STAT_ABORT_TIME_LIM
9.613 +// CPX_STAT_ABORT_USER
9.614 +// CPX_STAT_FEASIBLE_RELAXED
9.615 +// CPX_STAT_INFEASIBLE
9.616 +// CPX_STAT_INForUNBD
9.617 +// CPX_STAT_NUM_BEST
9.618 +// CPX_STAT_OPTIMAL
9.619 +// CPX_STAT_OPTIMAL_FACE_UNBOUNDED
9.620 +// CPX_STAT_OPTIMAL_INFEAS
9.621 +// CPX_STAT_OPTIMAL_RELAXED
9.622 +// CPX_STAT_UNBOUNDED
9.623 +
9.624 + LpCplex::SolutionStatus LpCplex::_getDualStatus() const
9.625 + {
9.626 + int stat = CPXgetstat(env, lp);
9.627 +#if CPX_VERSION >= 800
9.628 + switch (stat)
9.629 + {
9.630 + case CPX_STAT_OPTIMAL:
9.631 + return OPTIMAL;
9.632 + case CPX_STAT_UNBOUNDED:
9.633 + return INFEASIBLE;
9.634 + default:
9.635 + return UNDEFINED;
9.636 + }
9.637 +#else
9.638 + statusSwitch(env,stat);
9.639 + switch (stat) {
9.640 + case 0:
9.641 + return UNDEFINED; //Undefined
9.642 + case CPX_OPTIMAL://Optimal
9.643 + return OPTIMAL;
9.644 + case CPX_UNBOUNDED:
9.645 + return INFEASIBLE;
9.646 + default:
9.647 + return UNDEFINED; //Everything else comes here
9.648 + //FIXME error
9.649 + }
9.650 +#endif
9.651 + }
9.652 +
9.653 + LpCplex::ProblemTypes LpCplex::_getProblemType() const
9.654 + {
9.655 + int stat = CPXgetstat(env, lp);
9.656 +#if CPX_VERSION >= 800
9.657 + switch (stat)
9.658 + {
9.659 + case CPX_STAT_OPTIMAL:
9.660 + return PRIMAL_DUAL_FEASIBLE;
9.661 + case CPX_STAT_UNBOUNDED:
9.662 + return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
9.663 + default:
9.664 + return UNKNOWN;
9.665 + }
9.666 +#else
9.667 + switch (stat) {
9.668 + case CPX_OPTIMAL://Optimal
9.669 + return PRIMAL_DUAL_FEASIBLE;
9.670 + case CPX_UNBOUNDED:
9.671 + return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
9.672 +// return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
9.673 +// return PRIMAL_DUAL_INFEASIBLE;
9.674 +
9.675 +//Seems to be that this is all we can say for sure
9.676 + default:
9.677 + //In all other cases
9.678 + return UNKNOWN;
9.679 + //FIXME error
9.680 + }
9.681 +#endif
9.682 + }
9.683 +
9.684 + void LpCplex::_setMax()
9.685 + {
9.686 + CPXchgobjsen(env, lp, CPX_MAX);
9.687 + }
9.688 + void LpCplex::_setMin()
9.689 + {
9.690 + CPXchgobjsen(env, lp, CPX_MIN);
9.691 + }
9.692 +
9.693 + bool LpCplex::_isMax() const
9.694 + {
9.695 + if (CPXgetobjsen(env, lp)==CPX_MAX)
9.696 + return true;
9.697 + else
9.698 + return false;
9.699 + }
9.700 +
9.701 +} //namespace lemon
9.702 +
10.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
10.2 +++ b/lemon/lp_cplex.h Tue Dec 02 21:40:33 2008 +0100
10.3 @@ -0,0 +1,113 @@
10.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
10.5 + *
10.6 + * This file is a part of LEMON, a generic C++ optimization library.
10.7 + *
10.8 + * Copyright (C) 2003-2008
10.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
10.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
10.11 + *
10.12 + * Permission to use, modify and distribute this software is granted
10.13 + * provided that this copyright notice appears in all copies. For
10.14 + * precise terms see the accompanying LICENSE file.
10.15 + *
10.16 + * This software is provided "AS IS" with no warranty of any kind,
10.17 + * express or implied, and with no claim as to its suitability for any
10.18 + * purpose.
10.19 + *
10.20 + */
10.21 +
10.22 +#ifndef LEMON_LP_CPLEX_H
10.23 +#define LEMON_LP_CPLEX_H
10.24 +
10.25 +///\file
10.26 +///\brief Header of the LEMON-CPLEX lp solver interface.
10.27 +
10.28 +#include <lemon/lp_base.h>
10.29 +
10.30 +struct cpxenv;
10.31 +struct cpxlp;
10.32 +
10.33 +namespace lemon {
10.34 +
10.35 +
10.36 + /// \brief Interface for the CPLEX solver
10.37 + ///
10.38 + /// This class implements an interface for the CPLEX LP solver.
10.39 + class LpCplex :virtual public LpSolverBase {
10.40 +
10.41 + public:
10.42 +
10.43 + typedef LpSolverBase Parent;
10.44 +
10.45 + /// \e
10.46 + int status;
10.47 + cpxenv* env;
10.48 + cpxlp* lp;
10.49 +
10.50 +
10.51 + /// \e
10.52 + LpCplex();
10.53 + /// \e
10.54 + LpCplex(const LpCplex&);
10.55 + /// \e
10.56 + ~LpCplex();
10.57 +
10.58 + protected:
10.59 + virtual LpSolverBase* _newLp();
10.60 + virtual LpSolverBase* _copyLp();
10.61 +
10.62 +
10.63 + virtual int _addCol();
10.64 + virtual int _addRow();
10.65 + virtual void _eraseCol(int i);
10.66 + virtual void _eraseRow(int i);
10.67 + virtual void _getColName(int col, std::string & name) const;
10.68 + virtual void _setColName(int col, const std::string & name);
10.69 + virtual int _colByName(const std::string& name) const;
10.70 + virtual void _setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e);
10.71 + virtual void _getRowCoeffs(int i, RowIterator b) const;
10.72 + virtual void _setColCoeffs(int i, ConstColIterator b, ConstColIterator e);
10.73 + virtual void _getColCoeffs(int i, ColIterator b) const;
10.74 + virtual void _setCoeff(int row, int col, Value value);
10.75 + virtual Value _getCoeff(int row, int col) const;
10.76 +
10.77 + virtual void _setColLowerBound(int i, Value value);
10.78 + virtual Value _getColLowerBound(int i) const;
10.79 + virtual void _setColUpperBound(int i, Value value);
10.80 + virtual Value _getColUpperBound(int i) const;
10.81 +
10.82 +// virtual void _setRowLowerBound(int i, Value value);
10.83 +// virtual void _setRowUpperBound(int i, Value value);
10.84 + virtual void _setRowBounds(int i, Value lower, Value upper);
10.85 + virtual void _getRowBounds(int i, Value &lb, Value &ub) const;
10.86 + virtual void _setObjCoeff(int i, Value obj_coef);
10.87 + virtual Value _getObjCoeff(int i) const;
10.88 + virtual void _clearObj();
10.89 +
10.90 +
10.91 + virtual SolveExitStatus _solve();
10.92 + virtual Value _getPrimal(int i) const;
10.93 + virtual Value _getDual(int i) const;
10.94 + virtual Value _getPrimalValue() const;
10.95 + virtual bool _isBasicCol(int i) const;
10.96 +
10.97 + virtual SolutionStatus _getPrimalStatus() const;
10.98 + virtual SolutionStatus _getDualStatus() const;
10.99 + virtual ProblemTypes _getProblemType() const;
10.100 +
10.101 +
10.102 + virtual void _setMax();
10.103 + virtual void _setMin();
10.104 +
10.105 + virtual bool _isMax() const;
10.106 +
10.107 + public:
10.108 +
10.109 + cpxenv* cplexEnv() { return env; }
10.110 + cpxlp* cplexLp() { return lp; }
10.111 +
10.112 + };
10.113 +} //END OF NAMESPACE LEMON
10.114 +
10.115 +#endif //LEMON_LP_CPLEX_H
10.116 +
11.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
11.2 +++ b/lemon/lp_glpk.cc Tue Dec 02 21:40:33 2008 +0100
11.3 @@ -0,0 +1,644 @@
11.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
11.5 + *
11.6 + * This file is a part of LEMON, a generic C++ optimization library.
11.7 + *
11.8 + * Copyright (C) 2003-2008
11.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
11.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
11.11 + *
11.12 + * Permission to use, modify and distribute this software is granted
11.13 + * provided that this copyright notice appears in all copies. For
11.14 + * precise terms see the accompanying LICENSE file.
11.15 + *
11.16 + * This software is provided "AS IS" with no warranty of any kind,
11.17 + * express or implied, and with no claim as to its suitability for any
11.18 + * purpose.
11.19 + *
11.20 + */
11.21 +
11.22 +///\file
11.23 +///\brief Implementation of the LEMON-GLPK lp solver interface.
11.24 +
11.25 +#include <lemon/lp_glpk.h>
11.26 +//#include <iostream>
11.27 +
11.28 +extern "C" {
11.29 +#include <glpk.h>
11.30 +}
11.31 +
11.32 +#if GLP_MAJOR_VERSION > 4 || (GLP_MAJOR_VERSION == 4 && GLP_MINOR_VERSION > 15)
11.33 +#define LEMON_glp(func) (glp_##func)
11.34 +#define LEMON_lpx(func) (lpx_##func)
11.35 +
11.36 +#define LEMON_GLP(def) (GLP_##def)
11.37 +#define LEMON_LPX(def) (LPX_##def)
11.38 +
11.39 +#else
11.40 +
11.41 +#define LEMON_glp(func) (lpx_##func)
11.42 +#define LEMON_lpx(func) (lpx_##func)
11.43 +
11.44 +#define LEMON_GLP(def) (LPX_##def)
11.45 +#define LEMON_LPX(def) (LPX_##def)
11.46 +
11.47 +#endif
11.48 +
11.49 +namespace lemon {
11.50 +
11.51 + LpGlpk::LpGlpk() : Parent() {
11.52 + solved = false;
11.53 + rows = _lp_bits::LpId(1);
11.54 + cols = _lp_bits::LpId(1);
11.55 + lp = LEMON_glp(create_prob)();
11.56 + LEMON_glp(create_index)(lp);
11.57 + messageLevel(0);
11.58 + }
11.59 +
11.60 + LpGlpk::LpGlpk(const LpGlpk &glp) : Parent() {
11.61 + solved = false;
11.62 + rows = _lp_bits::LpId(1);
11.63 + cols = _lp_bits::LpId(1);
11.64 + lp = LEMON_glp(create_prob)();
11.65 + LEMON_glp(create_index)(lp);
11.66 + messageLevel(0);
11.67 + //Coefficient matrix, row bounds
11.68 + LEMON_glp(add_rows)(lp, LEMON_glp(get_num_rows)(glp.lp));
11.69 + LEMON_glp(add_cols)(lp, LEMON_glp(get_num_cols)(glp.lp));
11.70 + int len;
11.71 + std::vector<int> ind(1+LEMON_glp(get_num_cols)(glp.lp));
11.72 + std::vector<Value> val(1+LEMON_glp(get_num_cols)(glp.lp));
11.73 + for (int i=1;i<=LEMON_glp(get_num_rows)(glp.lp);++i)
11.74 + {
11.75 + len=LEMON_glp(get_mat_row)(glp.lp,i,&*ind.begin(),&*val.begin());
11.76 + LEMON_glp(set_mat_row)(lp, i,len,&*ind.begin(),&*val.begin());
11.77 + LEMON_glp(set_row_bnds)(lp,i,
11.78 + LEMON_glp(get_row_type)(glp.lp,i),
11.79 + LEMON_glp(get_row_lb)(glp.lp,i),
11.80 + LEMON_glp(get_row_ub)(glp.lp,i));
11.81 + }
11.82 +
11.83 + //Objective function, coloumn bounds
11.84 + LEMON_glp(set_obj_dir)(lp, LEMON_glp(get_obj_dir)(glp.lp));
11.85 + //Objectif function's constant term treated separately
11.86 + LEMON_glp(set_obj_coef)(lp,0,LEMON_glp(get_obj_coef)(glp.lp,0));
11.87 + for (int i=1;i<=LEMON_glp(get_num_cols)(glp.lp);++i)
11.88 + {
11.89 + LEMON_glp(set_obj_coef)(lp,i,
11.90 + LEMON_glp(get_obj_coef)(glp.lp,i));
11.91 + LEMON_glp(set_col_bnds)(lp,i,
11.92 + LEMON_glp(get_col_type)(glp.lp,i),
11.93 + LEMON_glp(get_col_lb)(glp.lp,i),
11.94 + LEMON_glp(get_col_ub)(glp.lp,i));
11.95 + }
11.96 + rows = glp.rows;
11.97 + cols = glp.cols;
11.98 + }
11.99 +
11.100 + LpGlpk::~LpGlpk() {
11.101 + LEMON_glp(delete_prob)(lp);
11.102 + }
11.103 +
11.104 + int LpGlpk::_addCol() {
11.105 + int i=LEMON_glp(add_cols)(lp, 1);
11.106 + LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(FR), 0.0, 0.0);
11.107 + solved = false;
11.108 + return i;
11.109 + }
11.110 +
11.111 + ///\e
11.112 +
11.113 +
11.114 + LpSolverBase* LpGlpk::_newLp()
11.115 + {
11.116 + LpGlpk* newlp = new LpGlpk;
11.117 + return newlp;
11.118 + }
11.119 +
11.120 + ///\e
11.121 +
11.122 + LpSolverBase* LpGlpk::_copyLp()
11.123 + {
11.124 + LpGlpk *newlp = new LpGlpk(*this);
11.125 + return newlp;
11.126 + }
11.127 +
11.128 + int LpGlpk::_addRow() {
11.129 + int i=LEMON_glp(add_rows)(lp, 1);
11.130 + solved = false;
11.131 + return i;
11.132 + }
11.133 +
11.134 +
11.135 + void LpGlpk::_eraseCol(int i) {
11.136 + int ca[2];
11.137 + ca[1]=i;
11.138 + LEMON_glp(del_cols)(lp, 1, ca);
11.139 + solved = false;
11.140 + }
11.141 +
11.142 + void LpGlpk::_eraseRow(int i) {
11.143 + int ra[2];
11.144 + ra[1]=i;
11.145 + LEMON_glp(del_rows)(lp, 1, ra);
11.146 + solved = false;
11.147 + }
11.148 +
11.149 + void LpGlpk::_getColName(int c, std::string & name) const
11.150 + {
11.151 +
11.152 + const char *n = LEMON_glp(get_col_name)(lp,c);
11.153 + name = n?n:"";
11.154 + }
11.155 +
11.156 +
11.157 + void LpGlpk::_setColName(int c, const std::string & name)
11.158 + {
11.159 + LEMON_glp(set_col_name)(lp,c,const_cast<char*>(name.c_str()));
11.160 +
11.161 + }
11.162 +
11.163 + int LpGlpk::_colByName(const std::string& name) const
11.164 + {
11.165 + int k = LEMON_glp(find_col)(lp, const_cast<char*>(name.c_str()));
11.166 + return k > 0 ? k : -1;
11.167 + }
11.168 +
11.169 +
11.170 + void LpGlpk::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e)
11.171 + {
11.172 + std::vector<int> indices;
11.173 + std::vector<Value> values;
11.174 +
11.175 + indices.push_back(0);
11.176 + values.push_back(0);
11.177 +
11.178 + for(ConstRowIterator it=b; it!=e; ++it) {
11.179 + indices.push_back(it->first);
11.180 + values.push_back(it->second);
11.181 + }
11.182 +
11.183 + LEMON_glp(set_mat_row)(lp, i, values.size() - 1,
11.184 + &indices[0], &values[0]);
11.185 +
11.186 + solved = false;
11.187 + }
11.188 +
11.189 + void LpGlpk::_getRowCoeffs(int ix, RowIterator b) const
11.190 + {
11.191 + int length = LEMON_glp(get_mat_row)(lp, ix, 0, 0);
11.192 +
11.193 + std::vector<int> indices(length + 1);
11.194 + std::vector<Value> values(length + 1);
11.195 +
11.196 + LEMON_glp(get_mat_row)(lp, ix, &indices[0], &values[0]);
11.197 +
11.198 + for (int i = 1; i <= length; ++i) {
11.199 + *b = std::make_pair(indices[i], values[i]);
11.200 + ++b;
11.201 + }
11.202 + }
11.203 +
11.204 + void LpGlpk::_setColCoeffs(int ix, ConstColIterator b, ConstColIterator e) {
11.205 +
11.206 + std::vector<int> indices;
11.207 + std::vector<Value> values;
11.208 +
11.209 + indices.push_back(0);
11.210 + values.push_back(0);
11.211 +
11.212 + for(ConstColIterator it=b; it!=e; ++it) {
11.213 + indices.push_back(it->first);
11.214 + values.push_back(it->second);
11.215 + }
11.216 +
11.217 + LEMON_glp(set_mat_col)(lp, ix, values.size() - 1,
11.218 + &indices[0], &values[0]);
11.219 +
11.220 + solved = false;
11.221 + }
11.222 +
11.223 + void LpGlpk::_getColCoeffs(int ix, ColIterator b) const
11.224 + {
11.225 + int length = LEMON_glp(get_mat_col)(lp, ix, 0, 0);
11.226 +
11.227 + std::vector<int> indices(length + 1);
11.228 + std::vector<Value> values(length + 1);
11.229 +
11.230 + LEMON_glp(get_mat_col)(lp, ix, &indices[0], &values[0]);
11.231 +
11.232 + for (int i = 1; i <= length; ++i) {
11.233 + *b = std::make_pair(indices[i], values[i]);
11.234 + ++b;
11.235 + }
11.236 + }
11.237 +
11.238 + void LpGlpk::_setCoeff(int ix, int jx, Value value)
11.239 + {
11.240 +
11.241 + if (LEMON_glp(get_num_cols)(lp) < LEMON_glp(get_num_rows)(lp)) {
11.242 +
11.243 + int length=LEMON_glp(get_mat_row)(lp, ix, 0, 0);
11.244 +
11.245 + std::vector<int> indices(length + 2);
11.246 + std::vector<Value> values(length + 2);
11.247 +
11.248 + LEMON_glp(get_mat_row)(lp, ix, &indices[0], &values[0]);
11.249 +
11.250 + //The following code does not suppose that the elements of the
11.251 + //array indices are sorted
11.252 + bool found=false;
11.253 + for (int i = 1; i <= length; ++i) {
11.254 + if (indices[i]==jx){
11.255 + found=true;
11.256 + values[i]=value;
11.257 + break;
11.258 + }
11.259 + }
11.260 + if (!found){
11.261 + ++length;
11.262 + indices[length]=jx;
11.263 + values[length]=value;
11.264 + }
11.265 +
11.266 + LEMON_glp(set_mat_row)(lp, ix, length, &indices[0], &values[0]);
11.267 +
11.268 + } else {
11.269 +
11.270 + int length=LEMON_glp(get_mat_col)(lp, jx, 0, 0);
11.271 +
11.272 + std::vector<int> indices(length + 2);
11.273 + std::vector<Value> values(length + 2);
11.274 +
11.275 + LEMON_glp(get_mat_col)(lp, jx, &indices[0], &values[0]);
11.276 +
11.277 + //The following code does not suppose that the elements of the
11.278 + //array indices are sorted
11.279 + bool found=false;
11.280 + for (int i = 1; i <= length; ++i) {
11.281 + if (indices[i]==ix){
11.282 + found=true;
11.283 + values[i]=value;
11.284 + break;
11.285 + }
11.286 + }
11.287 + if (!found){
11.288 + ++length;
11.289 + indices[length]=ix;
11.290 + values[length]=value;
11.291 + }
11.292 +
11.293 + LEMON_glp(set_mat_col)(lp, jx, length, &indices[0], &values[0]);
11.294 + }
11.295 +
11.296 + solved = false;
11.297 + }
11.298 +
11.299 + LpGlpk::Value LpGlpk::_getCoeff(int ix, int jx) const
11.300 + {
11.301 +
11.302 + int length=LEMON_glp(get_mat_row)(lp, ix, 0, 0);
11.303 +
11.304 + std::vector<int> indices(length + 1);
11.305 + std::vector<Value> values(length + 1);
11.306 +
11.307 + LEMON_glp(get_mat_row)(lp, ix, &indices[0], &values[0]);
11.308 +
11.309 + //The following code does not suppose that the elements of the
11.310 + //array indices are sorted
11.311 + for (int i = 1; i <= length; ++i) {
11.312 + if (indices[i]==jx){
11.313 + return values[i];
11.314 + }
11.315 + }
11.316 + return 0;
11.317 +
11.318 + }
11.319 +
11.320 +
11.321 + void LpGlpk::_setColLowerBound(int i, Value lo)
11.322 + {
11.323 + if (lo==INF) {
11.324 + //FIXME error
11.325 + }
11.326 + int b=LEMON_glp(get_col_type)(lp, i);
11.327 + double up=LEMON_glp(get_col_ub)(lp, i);
11.328 + if (lo==-INF) {
11.329 + switch (b) {
11.330 + case LEMON_GLP(FR):
11.331 + case LEMON_GLP(LO):
11.332 + LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(FR), lo, up);
11.333 + break;
11.334 + case LEMON_GLP(UP):
11.335 + break;
11.336 + case LEMON_GLP(DB):
11.337 + case LEMON_GLP(FX):
11.338 + LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(UP), lo, up);
11.339 + break;
11.340 + default: ;
11.341 + //FIXME error
11.342 + }
11.343 + } else {
11.344 + switch (b) {
11.345 + case LEMON_GLP(FR):
11.346 + case LEMON_GLP(LO):
11.347 + LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(LO), lo, up);
11.348 + break;
11.349 + case LEMON_GLP(UP):
11.350 + case LEMON_GLP(DB):
11.351 + case LEMON_GLP(FX):
11.352 + if (lo==up)
11.353 + LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(FX), lo, up);
11.354 + else
11.355 + LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(DB), lo, up);
11.356 + break;
11.357 + default: ;
11.358 + //FIXME error
11.359 + }
11.360 + }
11.361 +
11.362 + solved = false;
11.363 + }
11.364 +
11.365 + LpGlpk::Value LpGlpk::_getColLowerBound(int i) const
11.366 + {
11.367 + int b=LEMON_glp(get_col_type)(lp, i);
11.368 + switch (b) {
11.369 + case LEMON_GLP(LO):
11.370 + case LEMON_GLP(DB):
11.371 + case LEMON_GLP(FX):
11.372 + return LEMON_glp(get_col_lb)(lp, i);
11.373 + default: ;
11.374 + return -INF;
11.375 + }
11.376 + }
11.377 +
11.378 + void LpGlpk::_setColUpperBound(int i, Value up)
11.379 + {
11.380 + if (up==-INF) {
11.381 + //FIXME error
11.382 + }
11.383 + int b=LEMON_glp(get_col_type)(lp, i);
11.384 + double lo=LEMON_glp(get_col_lb)(lp, i);
11.385 + if (up==INF) {
11.386 + switch (b) {
11.387 + case LEMON_GLP(FR):
11.388 + case LEMON_GLP(LO):
11.389 + break;
11.390 + case LEMON_GLP(UP):
11.391 + LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(FR), lo, up);
11.392 + break;
11.393 + case LEMON_GLP(DB):
11.394 + case LEMON_GLP(FX):
11.395 + LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(LO), lo, up);
11.396 + break;
11.397 + default: ;
11.398 + //FIXME error
11.399 + }
11.400 + } else {
11.401 + switch (b) {
11.402 + case LEMON_GLP(FR):
11.403 + LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(UP), lo, up);
11.404 + break;
11.405 + case LEMON_GLP(UP):
11.406 + LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(UP), lo, up);
11.407 + break;
11.408 + case LEMON_GLP(LO):
11.409 + case LEMON_GLP(DB):
11.410 + case LEMON_GLP(FX):
11.411 + if (lo==up)
11.412 + LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(FX), lo, up);
11.413 + else
11.414 + LEMON_glp(set_col_bnds)(lp, i, LEMON_GLP(DB), lo, up);
11.415 + break;
11.416 + default: ;
11.417 + //FIXME error
11.418 + }
11.419 + }
11.420 +
11.421 + solved = false;
11.422 + }
11.423 +
11.424 + LpGlpk::Value LpGlpk::_getColUpperBound(int i) const
11.425 + {
11.426 + int b=LEMON_glp(get_col_type)(lp, i);
11.427 + switch (b) {
11.428 + case LEMON_GLP(UP):
11.429 + case LEMON_GLP(DB):
11.430 + case LEMON_GLP(FX):
11.431 + return LEMON_glp(get_col_ub)(lp, i);
11.432 + default: ;
11.433 + return INF;
11.434 + }
11.435 + }
11.436 +
11.437 + void LpGlpk::_setRowBounds(int i, Value lb, Value ub)
11.438 + {
11.439 + //Bad parameter
11.440 + if (lb==INF || ub==-INF) {
11.441 + //FIXME error
11.442 + }
11.443 +
11.444 + if (lb == -INF){
11.445 + if (ub == INF){
11.446 + LEMON_glp(set_row_bnds)(lp, i, LEMON_GLP(FR), lb, ub);
11.447 + }
11.448 + else{
11.449 + LEMON_glp(set_row_bnds)(lp, i, LEMON_GLP(UP), lb, ub);
11.450 + }
11.451 + }
11.452 + else{
11.453 + if (ub==INF){
11.454 + LEMON_glp(set_row_bnds)(lp, i, LEMON_GLP(LO), lb, ub);
11.455 +
11.456 + }
11.457 + else{
11.458 + if (lb == ub){
11.459 + LEMON_glp(set_row_bnds)(lp, i, LEMON_GLP(FX), lb, ub);
11.460 + }
11.461 + else{
11.462 + LEMON_glp(set_row_bnds)(lp, i, LEMON_GLP(DB), lb, ub);
11.463 + }
11.464 + }
11.465 + }
11.466 +
11.467 + solved = false;
11.468 + }
11.469 +
11.470 + void LpGlpk::_getRowBounds(int i, Value &lb, Value &ub) const
11.471 + {
11.472 +
11.473 + int b=LEMON_glp(get_row_type)(lp, i);
11.474 + switch (b) {
11.475 + case LEMON_GLP(FR):
11.476 + case LEMON_GLP(UP):
11.477 + lb = -INF;
11.478 + break;
11.479 + default:
11.480 + lb=LEMON_glp(get_row_lb)(lp, i);
11.481 + }
11.482 +
11.483 + switch (b) {
11.484 + case LEMON_GLP(FR):
11.485 + case LEMON_GLP(LO):
11.486 + ub = INF;
11.487 + break;
11.488 + default:
11.489 + ub=LEMON_glp(get_row_ub)(lp, i);
11.490 + }
11.491 +
11.492 + }
11.493 +
11.494 + void LpGlpk::_setObjCoeff(int i, Value obj_coef)
11.495 + {
11.496 + //i=0 means the constant term (shift)
11.497 + LEMON_glp(set_obj_coef)(lp, i, obj_coef);
11.498 +
11.499 + solved = false;
11.500 + }
11.501 +
11.502 + LpGlpk::Value LpGlpk::_getObjCoeff(int i) const {
11.503 + //i=0 means the constant term (shift)
11.504 + return LEMON_glp(get_obj_coef)(lp, i);
11.505 + }
11.506 +
11.507 + void LpGlpk::_clearObj()
11.508 + {
11.509 + for (int i=0;i<=LEMON_glp(get_num_cols)(lp);++i){
11.510 + LEMON_glp(set_obj_coef)(lp, i, 0);
11.511 + }
11.512 +
11.513 + solved = false;
11.514 + }
11.515 +
11.516 + LpGlpk::SolveExitStatus LpGlpk::_solve()
11.517 + {
11.518 + // A way to check the problem to be solved
11.519 + //LEMON_glp(write_cpxlp(lp,"naittvan.cpx");
11.520 +
11.521 + LEMON_lpx(std_basis)(lp);
11.522 + int i = LEMON_lpx(simplex)(lp);
11.523 +
11.524 + switch (i) {
11.525 + case LEMON_LPX(E_OK):
11.526 + solved = true;
11.527 + return SOLVED;
11.528 + default:
11.529 + return UNSOLVED;
11.530 + }
11.531 + }
11.532 +
11.533 + LpGlpk::Value LpGlpk::_getPrimal(int i) const
11.534 + {
11.535 + return LEMON_glp(get_col_prim)(lp,i);
11.536 + }
11.537 +
11.538 + LpGlpk::Value LpGlpk::_getDual(int i) const
11.539 + {
11.540 + return LEMON_glp(get_row_dual)(lp,i);
11.541 + }
11.542 +
11.543 + LpGlpk::Value LpGlpk::_getPrimalValue() const
11.544 + {
11.545 + return LEMON_glp(get_obj_val)(lp);
11.546 + }
11.547 + bool LpGlpk::_isBasicCol(int i) const
11.548 + {
11.549 + return (LEMON_glp(get_col_stat)(lp, i)==LEMON_GLP(BS));
11.550 + }
11.551 +
11.552 +
11.553 + LpGlpk::SolutionStatus LpGlpk::_getPrimalStatus() const
11.554 + {
11.555 + if (!solved) return UNDEFINED;
11.556 + int stat= LEMON_lpx(get_status)(lp);
11.557 + switch (stat) {
11.558 + case LEMON_LPX(UNDEF)://Undefined (no solve has been run yet)
11.559 + return UNDEFINED;
11.560 + case LEMON_LPX(NOFEAS)://There is no feasible solution (primal, I guess)
11.561 + case LEMON_LPX(INFEAS)://Infeasible
11.562 + return INFEASIBLE;
11.563 + case LEMON_LPX(UNBND)://Unbounded
11.564 + return INFINITE;
11.565 + case LEMON_LPX(FEAS)://Feasible
11.566 + return FEASIBLE;
11.567 + case LEMON_LPX(OPT)://Feasible
11.568 + return OPTIMAL;
11.569 + default:
11.570 + return UNDEFINED; //to avoid gcc warning
11.571 + //FIXME error
11.572 + }
11.573 + }
11.574 +
11.575 + LpGlpk::SolutionStatus LpGlpk::_getDualStatus() const
11.576 + {
11.577 + if (!solved) return UNDEFINED;
11.578 + switch (LEMON_lpx(get_dual_stat)(lp)) {
11.579 + case LEMON_LPX(D_UNDEF)://Undefined (no solve has been run yet)
11.580 + return UNDEFINED;
11.581 + case LEMON_LPX(D_NOFEAS)://There is no dual feasible solution
11.582 +// case LEMON_LPX(D_INFEAS://Infeasible
11.583 + return INFEASIBLE;
11.584 + case LEMON_LPX(D_FEAS)://Feasible
11.585 + switch (LEMON_lpx(get_status)(lp)) {
11.586 + case LEMON_LPX(NOFEAS):
11.587 + return INFINITE;
11.588 + case LEMON_LPX(OPT):
11.589 + return OPTIMAL;
11.590 + default:
11.591 + return FEASIBLE;
11.592 + }
11.593 + default:
11.594 + return UNDEFINED; //to avoid gcc warning
11.595 + //FIXME error
11.596 + }
11.597 + }
11.598 +
11.599 + LpGlpk::ProblemTypes LpGlpk::_getProblemType() const
11.600 + {
11.601 + if (!solved) return UNKNOWN;
11.602 + //int stat= LEMON_glp(get_status(lp);
11.603 + int statp= LEMON_lpx(get_prim_stat)(lp);
11.604 + int statd= LEMON_lpx(get_dual_stat)(lp);
11.605 + if (statp==LEMON_LPX(P_FEAS) && statd==LEMON_LPX(D_FEAS))
11.606 + return PRIMAL_DUAL_FEASIBLE;
11.607 + if (statp==LEMON_LPX(P_FEAS) && statd==LEMON_LPX(D_NOFEAS))
11.608 + return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
11.609 + if (statp==LEMON_LPX(P_NOFEAS) && statd==LEMON_LPX(D_FEAS))
11.610 + return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
11.611 + if (statp==LEMON_LPX(P_NOFEAS) && statd==LEMON_LPX(D_NOFEAS))
11.612 + return PRIMAL_DUAL_INFEASIBLE;
11.613 + //In all other cases
11.614 + return UNKNOWN;
11.615 + }
11.616 +
11.617 + void LpGlpk::_setMax()
11.618 + {
11.619 + solved = false;
11.620 + LEMON_glp(set_obj_dir)(lp, LEMON_GLP(MAX));
11.621 + }
11.622 +
11.623 + void LpGlpk::_setMin()
11.624 + {
11.625 + solved = false;
11.626 + LEMON_glp(set_obj_dir)(lp, LEMON_GLP(MIN));
11.627 + }
11.628 +
11.629 + bool LpGlpk::_isMax() const
11.630 + {
11.631 + return (LEMON_glp(get_obj_dir)(lp)==LEMON_GLP(MAX));
11.632 + }
11.633 +
11.634 +
11.635 +
11.636 + void LpGlpk::messageLevel(int m)
11.637 + {
11.638 + LEMON_lpx(set_int_parm)(lp, LEMON_LPX(K_MSGLEV), m);
11.639 + }
11.640 +
11.641 + void LpGlpk::presolver(bool b)
11.642 + {
11.643 + LEMON_lpx(set_int_parm)(lp, LEMON_LPX(K_PRESOL), b);
11.644 + }
11.645 +
11.646 +
11.647 +} //END OF NAMESPACE LEMON
12.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
12.2 +++ b/lemon/lp_glpk.h Tue Dec 02 21:40:33 2008 +0100
12.3 @@ -0,0 +1,139 @@
12.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
12.5 + *
12.6 + * This file is a part of LEMON, a generic C++ optimization library.
12.7 + *
12.8 + * Copyright (C) 2003-2008
12.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
12.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
12.11 + *
12.12 + * Permission to use, modify and distribute this software is granted
12.13 + * provided that this copyright notice appears in all copies. For
12.14 + * precise terms see the accompanying LICENSE file.
12.15 + *
12.16 + * This software is provided "AS IS" with no warranty of any kind,
12.17 + * express or implied, and with no claim as to its suitability for any
12.18 + * purpose.
12.19 + *
12.20 + */
12.21 +
12.22 +#ifndef LEMON_LP_GLPK_H
12.23 +#define LEMON_LP_GLPK_H
12.24 +
12.25 +///\file
12.26 +///\brief Header of the LEMON-GLPK lp solver interface.
12.27 +///\ingroup lp_group
12.28 +
12.29 +#include <lemon/lp_base.h>
12.30 +
12.31 +// forward declaration
12.32 +#ifndef _GLP_PROB
12.33 +#define _GLP_PROB
12.34 +typedef struct { double _prob; } glp_prob;
12.35 +/* LP/MIP problem object */
12.36 +#endif
12.37 +
12.38 +namespace lemon {
12.39 +
12.40 +
12.41 + /// \brief Interface for the GLPK LP solver
12.42 + ///
12.43 + /// This class implements an interface for the GLPK LP solver.
12.44 + ///\ingroup lp_group
12.45 + class LpGlpk : virtual public LpSolverBase {
12.46 + protected:
12.47 +
12.48 + typedef glp_prob LPX;
12.49 + glp_prob* lp;
12.50 + bool solved;
12.51 +
12.52 + public:
12.53 +
12.54 + typedef LpSolverBase Parent;
12.55 +
12.56 + LpGlpk();
12.57 + LpGlpk(const LpGlpk &);
12.58 + ~LpGlpk();
12.59 +
12.60 + protected:
12.61 + virtual LpSolverBase* _newLp();
12.62 + virtual LpSolverBase* _copyLp();
12.63 +
12.64 + virtual int _addCol();
12.65 + virtual int _addRow();
12.66 + virtual void _eraseCol(int i);
12.67 + virtual void _eraseRow(int i);
12.68 + virtual void _getColName(int col, std::string & name) const;
12.69 + virtual void _setColName(int col, const std::string & name);
12.70 + virtual int _colByName(const std::string& name) const;
12.71 + virtual void _setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e);
12.72 + virtual void _getRowCoeffs(int i, RowIterator b) const;
12.73 + virtual void _setColCoeffs(int i, ConstColIterator b, ConstColIterator e);
12.74 + virtual void _getColCoeffs(int i, ColIterator b) const;
12.75 + virtual void _setCoeff(int row, int col, Value value);
12.76 + virtual Value _getCoeff(int row, int col) const;
12.77 +
12.78 + virtual void _setColLowerBound(int i, Value value);
12.79 + virtual Value _getColLowerBound(int i) const;
12.80 + virtual void _setColUpperBound(int i, Value value);
12.81 + virtual Value _getColUpperBound(int i) const;
12.82 +
12.83 + virtual void _setRowBounds(int i, Value lower, Value upper);
12.84 + virtual void _getRowBounds(int i, Value &lb, Value &ub) const;
12.85 + virtual void _setObjCoeff(int i, Value obj_coef);
12.86 + virtual Value _getObjCoeff(int i) const;
12.87 + virtual void _clearObj();
12.88 +
12.89 + ///\e
12.90 +
12.91 + ///\todo It should be clarified
12.92 + ///
12.93 + virtual SolveExitStatus _solve();
12.94 + virtual Value _getPrimal(int i) const;
12.95 + virtual Value _getDual(int i) const;
12.96 + virtual Value _getPrimalValue() const;
12.97 + virtual bool _isBasicCol(int i) const;
12.98 + ///\e
12.99 +
12.100 + ///\todo It should be clarified
12.101 + ///
12.102 + virtual SolutionStatus _getPrimalStatus() const;
12.103 + virtual SolutionStatus _getDualStatus() const;
12.104 + virtual ProblemTypes _getProblemType() const;
12.105 +
12.106 + virtual void _setMax();
12.107 + virtual void _setMin();
12.108 +
12.109 + virtual bool _isMax() const;
12.110 +
12.111 + public:
12.112 + ///Set the verbosity of the messages
12.113 +
12.114 + ///Set the verbosity of the messages
12.115 + ///
12.116 + ///\param m is the level of the messages output by the solver routines.
12.117 + ///The possible values are:
12.118 + ///- 0 --- no output (default value)
12.119 + ///- 1 --- error messages only
12.120 + ///- 2 --- normal output
12.121 + ///- 3 --- full output (includes informational messages)
12.122 + void messageLevel(int m);
12.123 + ///Turns on or off the presolver
12.124 +
12.125 + ///Turns on (\c b is \c true) or off (\c b is \c false) the presolver
12.126 + ///
12.127 + ///The presolver is off by default.
12.128 + void presolver(bool b);
12.129 +
12.130 + ///Pointer to the underlying GLPK data structure.
12.131 + LPX *lpx() {return lp;}
12.132 +
12.133 + ///Returns the constraint identifier understood by GLPK.
12.134 + int lpxRow(Row r) { return _lpId(r); }
12.135 +
12.136 + ///Returns the variable identifier understood by GLPK.
12.137 + int lpxCol(Col c) { return _lpId(c); }
12.138 + };
12.139 +} //END OF NAMESPACE LEMON
12.140 +
12.141 +#endif //LEMON_LP_GLPK_H
12.142 +
13.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
13.2 +++ b/lemon/lp_skeleton.cc Tue Dec 02 21:40:33 2008 +0100
13.3 @@ -0,0 +1,187 @@
13.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
13.5 + *
13.6 + * This file is a part of LEMON, a generic C++ optimization library.
13.7 + *
13.8 + * Copyright (C) 2003-2008
13.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
13.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
13.11 + *
13.12 + * Permission to use, modify and distribute this software is granted
13.13 + * provided that this copyright notice appears in all copies. For
13.14 + * precise terms see the accompanying LICENSE file.
13.15 + *
13.16 + * This software is provided "AS IS" with no warranty of any kind,
13.17 + * express or implied, and with no claim as to its suitability for any
13.18 + * purpose.
13.19 + *
13.20 + */
13.21 +
13.22 +#include <lemon/lp_skeleton.h>
13.23 +
13.24 +///\file
13.25 +///\brief A skeleton file to implement LP solver interfaces
13.26 +namespace lemon {
13.27 +
13.28 + LpSolverBase* LpSkeleton::_newLp()
13.29 + {
13.30 + LpSolverBase *tmp=0;
13.31 + return tmp;
13.32 + }
13.33 +
13.34 + LpSolverBase* LpSkeleton::_copyLp()
13.35 + {
13.36 + LpSolverBase *tmp=0;
13.37 + return tmp;
13.38 + }
13.39 +
13.40 + int LpSkeleton::_addCol()
13.41 + {
13.42 + return ++col_num;
13.43 + }
13.44 +
13.45 + int LpSkeleton::_addRow()
13.46 + {
13.47 + return ++row_num;
13.48 + }
13.49 +
13.50 + void LpSkeleton::_eraseCol(int ) {
13.51 + }
13.52 +
13.53 + void LpSkeleton::_eraseRow(int) {
13.54 + }
13.55 +
13.56 + void LpSkeleton::_getColName(int, std::string &) const {
13.57 + }
13.58 +
13.59 +
13.60 + void LpSkeleton::_setColName(int, const std::string &) {
13.61 + }
13.62 +
13.63 + int LpSkeleton::_colByName(const std::string&) const { return -1; }
13.64 +
13.65 +
13.66 + void LpSkeleton::_setRowCoeffs(int, ConstRowIterator, ConstRowIterator) {
13.67 + }
13.68 +
13.69 + void LpSkeleton::_getRowCoeffs(int, RowIterator) const {
13.70 + }
13.71 +
13.72 + void LpSkeleton::_setColCoeffs(int, ConstColIterator, ConstColIterator) {
13.73 + }
13.74 +
13.75 + void LpSkeleton::_getColCoeffs(int, ColIterator) const {
13.76 + }
13.77 +
13.78 + void LpSkeleton::_setCoeff(int, int, Value )
13.79 + {
13.80 + }
13.81 +
13.82 + LpSkeleton::Value LpSkeleton::_getCoeff(int, int) const
13.83 + {
13.84 + return 0;
13.85 + }
13.86 +
13.87 +
13.88 + void LpSkeleton::_setColLowerBound(int, Value)
13.89 + {
13.90 + }
13.91 +
13.92 + LpSkeleton::Value LpSkeleton::_getColLowerBound(int) const
13.93 + {
13.94 + return 0;
13.95 + }
13.96 +
13.97 + void LpSkeleton::_setColUpperBound(int, Value)
13.98 + {
13.99 + }
13.100 +
13.101 + LpSkeleton::Value LpSkeleton::_getColUpperBound(int) const
13.102 + {
13.103 + return 0;
13.104 + }
13.105 +
13.106 +// void LpSkeleton::_setRowLowerBound(int, Value)
13.107 +// {
13.108 +// }
13.109 +
13.110 +// void LpSkeleton::_setRowUpperBound(int, Value)
13.111 +// {
13.112 +// }
13.113 +
13.114 + void LpSkeleton::_setRowBounds(int, Value, Value)
13.115 + {
13.116 + }
13.117 +
13.118 + void LpSkeleton::_getRowBounds(int, Value&, Value&) const
13.119 + {
13.120 + }
13.121 +
13.122 + void LpSkeleton::_setObjCoeff(int, Value)
13.123 + {
13.124 + }
13.125 +
13.126 + LpSkeleton::Value LpSkeleton::_getObjCoeff(int) const
13.127 + {
13.128 + return 0;
13.129 + }
13.130 +
13.131 + void LpSkeleton::_setMax()
13.132 + {
13.133 + }
13.134 +
13.135 + void LpSkeleton::_setMin()
13.136 + {
13.137 + }
13.138 +
13.139 + bool LpSkeleton::_isMax() const
13.140 + {
13.141 + return true;
13.142 + }
13.143 +
13.144 +
13.145 + void LpSkeleton::_clearObj()
13.146 + {
13.147 + }
13.148 +
13.149 + LpSkeleton::SolveExitStatus LpSkeleton::_solve()
13.150 + {
13.151 + return SOLVED;
13.152 + }
13.153 +
13.154 + LpSkeleton::Value LpSkeleton::_getPrimal(int) const
13.155 + {
13.156 + return 0;
13.157 + }
13.158 +
13.159 + LpSkeleton::Value LpSkeleton::_getDual(int) const
13.160 + {
13.161 + return 0;
13.162 + }
13.163 +
13.164 + LpSkeleton::Value LpSkeleton::_getPrimalValue() const
13.165 + {
13.166 + return 0;
13.167 + }
13.168 +
13.169 + LpSkeleton::SolutionStatus LpSkeleton::_getPrimalStatus() const
13.170 + {
13.171 + return UNDEFINED;
13.172 + }
13.173 +
13.174 + LpSkeleton::SolutionStatus LpSkeleton::_getDualStatus() const
13.175 + {
13.176 + return UNDEFINED;
13.177 + }
13.178 +
13.179 + LpSkeleton::ProblemTypes LpSkeleton::_getProblemType() const
13.180 + {
13.181 + return UNKNOWN;
13.182 + }
13.183 +
13.184 + bool LpSkeleton::_isBasicCol(int) const
13.185 + {
13.186 + return true;
13.187 + }
13.188 +
13.189 +} //namespace lemon
13.190 +
14.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
14.2 +++ b/lemon/lp_skeleton.h Tue Dec 02 21:40:33 2008 +0100
14.3 @@ -0,0 +1,183 @@
14.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
14.5 + *
14.6 + * This file is a part of LEMON, a generic C++ optimization library.
14.7 + *
14.8 + * Copyright (C) 2003-2008
14.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
14.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
14.11 + *
14.12 + * Permission to use, modify and distribute this software is granted
14.13 + * provided that this copyright notice appears in all copies. For
14.14 + * precise terms see the accompanying LICENSE file.
14.15 + *
14.16 + * This software is provided "AS IS" with no warranty of any kind,
14.17 + * express or implied, and with no claim as to its suitability for any
14.18 + * purpose.
14.19 + *
14.20 + */
14.21 +
14.22 +#ifndef LEMON_LP_SKELETON
14.23 +#define LEMON_LP_SKELETON
14.24 +
14.25 +#include <lemon/lp_base.h>
14.26 +
14.27 +///\file
14.28 +///\brief A skeleton file to implement LP solver interfaces
14.29 +namespace lemon {
14.30 +
14.31 + ///A skeleton class to implement LP solver interfaces
14.32 + class LpSkeleton :public LpSolverBase {
14.33 + int col_num,row_num;
14.34 +
14.35 + protected:
14.36 +
14.37 + ///\e
14.38 + virtual LpSolverBase* _newLp();
14.39 + ///\e
14.40 + virtual LpSolverBase* _copyLp();
14.41 + /// \e
14.42 + virtual int _addCol();
14.43 + /// \e
14.44 + virtual int _addRow();
14.45 + /// \e
14.46 + virtual void _eraseCol(int i);
14.47 + /// \e
14.48 + virtual void _eraseRow(int i);
14.49 + /// \e
14.50 + virtual void _getColName(int col, std::string & name) const;
14.51 + /// \e
14.52 + virtual void _setColName(int col, const std::string & name);
14.53 + /// \e
14.54 + virtual int _colByName(const std::string& name) const;
14.55 +
14.56 + /// \e
14.57 + virtual void _setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e);
14.58 + /// \e
14.59 + virtual void _getRowCoeffs(int i, RowIterator b) const;
14.60 + /// \e
14.61 + virtual void _setColCoeffs(int i, ConstColIterator b, ConstColIterator e);
14.62 + /// \e
14.63 + virtual void _getColCoeffs(int i, ColIterator b) const;
14.64 +
14.65 + /// Set one element of the coefficient matrix
14.66 + virtual void _setCoeff(int row, int col, Value value);
14.67 +
14.68 + /// Get one element of the coefficient matrix
14.69 + virtual Value _getCoeff(int row, int col) const;
14.70 +
14.71 + /// The lower bound of a variable (column) have to be given by an
14.72 + /// extended number of type Value, i.e. a finite number of type
14.73 + /// Value or -\ref INF.
14.74 + virtual void _setColLowerBound(int i, Value value);
14.75 + /// \e
14.76 +
14.77 + /// The lower bound of a variable (column) is an
14.78 + /// extended number of type Value, i.e. a finite number of type
14.79 + /// Value or -\ref INF.
14.80 + virtual Value _getColLowerBound(int i) const;
14.81 +
14.82 + /// The upper bound of a variable (column) have to be given by an
14.83 + /// extended number of type Value, i.e. a finite number of type
14.84 + /// Value or \ref INF.
14.85 + virtual void _setColUpperBound(int i, Value value);
14.86 + /// \e
14.87 +
14.88 + /// The upper bound of a variable (column) is an
14.89 + /// extended number of type Value, i.e. a finite number of type
14.90 + /// Value or \ref INF.
14.91 + virtual Value _getColUpperBound(int i) const;
14.92 +
14.93 +// /// The lower bound of a linear expression (row) have to be given by an
14.94 +// /// extended number of type Value, i.e. a finite number of type
14.95 +// /// Value or -\ref INF.
14.96 +// virtual void _setRowLowerBound(int i, Value value);
14.97 +// /// \e
14.98 +
14.99 +// /// The upper bound of a linear expression (row) have to be given by an
14.100 +// /// extended number of type Value, i.e. a finite number of type
14.101 +// /// Value or \ref INF.
14.102 +// virtual void _setRowUpperBound(int i, Value value);
14.103 +
14.104 + /// The lower and upper bound of a linear expression (row) have to be
14.105 + /// given by an
14.106 + /// extended number of type Value, i.e. a finite number of type
14.107 + /// Value or +/-\ref INF.
14.108 + virtual void _setRowBounds(int i, Value lb, Value ub);
14.109 + /// \e
14.110 +
14.111 +
14.112 + /// The lower and the upper bound of
14.113 + /// a constraint (row) are
14.114 + /// extended numbers of type Value, i.e. finite numbers of type
14.115 + /// Value, -\ref INF or \ref INF.
14.116 + virtual void _getRowBounds(int i, Value &lb, Value &ub) const;
14.117 + /// \e
14.118 +
14.119 +
14.120 + /// \e
14.121 + virtual void _clearObj();
14.122 + /// \e
14.123 + virtual void _setObjCoeff(int i, Value obj_coef);
14.124 +
14.125 + /// \e
14.126 + virtual Value _getObjCoeff(int i) const;
14.127 +
14.128 + ///\e
14.129 +
14.130 + ///\bug Wrong interface
14.131 + ///
14.132 + virtual SolveExitStatus _solve();
14.133 +
14.134 + ///\e
14.135 +
14.136 + ///\bug Wrong interface
14.137 + ///
14.138 + virtual Value _getPrimal(int i) const;
14.139 +
14.140 + ///\e
14.141 +
14.142 + ///\bug Wrong interface
14.143 + ///
14.144 + virtual Value _getDual(int i) const;
14.145 +
14.146 + ///\e
14.147 +
14.148 + ///\bug Wrong interface
14.149 + ///
14.150 + virtual Value _getPrimalValue() const;
14.151 +
14.152 + ///\e
14.153 +
14.154 + ///\bug Wrong interface
14.155 + ///
14.156 + virtual SolutionStatus _getPrimalStatus() const;
14.157 +
14.158 + ////e
14.159 + virtual SolutionStatus _getDualStatus() const;
14.160 +
14.161 +
14.162 + ///\e
14.163 + virtual ProblemTypes _getProblemType() const;
14.164 +
14.165 + ///\e
14.166 + virtual void _setMax();
14.167 + ///\e
14.168 + virtual void _setMin();
14.169 +
14.170 + ///\e
14.171 + virtual bool _isMax() const;
14.172 +
14.173 +
14.174 +
14.175 + ///\e
14.176 + virtual bool _isBasicCol(int i) const;
14.177 +
14.178 +
14.179 +
14.180 + public:
14.181 + LpSkeleton() : LpSolverBase(), col_num(0), row_num(0) {}
14.182 + };
14.183 +
14.184 +} //namespace lemon
14.185 +
14.186 +#endif // LEMON_LP_SKELETON
15.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
15.2 +++ b/lemon/lp_soplex.cc Tue Dec 02 21:40:33 2008 +0100
15.3 @@ -0,0 +1,316 @@
15.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
15.5 + *
15.6 + * This file is a part of LEMON, a generic C++ optimization library.
15.7 + *
15.8 + * Copyright (C) 2003-2008
15.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
15.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
15.11 + *
15.12 + * Permission to use, modify and distribute this software is granted
15.13 + * provided that this copyright notice appears in all copies. For
15.14 + * precise terms see the accompanying LICENSE file.
15.15 + *
15.16 + * This software is provided "AS IS" with no warranty of any kind,
15.17 + * express or implied, and with no claim as to its suitability for any
15.18 + * purpose.
15.19 + *
15.20 + */
15.21 +
15.22 +#include<iostream>
15.23 +#include<lemon/lp_soplex.h>
15.24 +
15.25 +#include <soplex/soplex.h>
15.26 +
15.27 +
15.28 +///\file
15.29 +///\brief Implementation of the LEMON-SOPLEX lp solver interface.
15.30 +namespace lemon {
15.31 +
15.32 + LpSoplex::LpSoplex() : LpSolverBase() {
15.33 + rows.setIdHandler(relocateIdHandler);
15.34 + cols.setIdHandler(relocateIdHandler);
15.35 + soplex = new soplex::SoPlex;
15.36 + solved = false;
15.37 + }
15.38 +
15.39 + LpSoplex::~LpSoplex() {
15.40 + delete soplex;
15.41 + }
15.42 +
15.43 + LpSoplex::LpSoplex(const LpSoplex& lp) : LpSolverBase() {
15.44 + rows = lp.rows;
15.45 + rows.setIdHandler(relocateIdHandler);
15.46 +
15.47 + cols = lp.cols;
15.48 + cols.setIdHandler(relocateIdHandler);
15.49 +
15.50 + soplex = new soplex::SoPlex;
15.51 + (*static_cast<soplex::SPxLP*>(soplex)) = *(lp.soplex);
15.52 +
15.53 + colNames = lp.colNames;
15.54 + invColNames = lp.invColNames;
15.55 +
15.56 + primal_value = lp.primal_value;
15.57 + dual_value = lp.dual_value;
15.58 +
15.59 + }
15.60 +
15.61 + LpSolverBase* LpSoplex::_newLp() {
15.62 + LpSoplex* newlp = new LpSoplex();
15.63 + return newlp;
15.64 + }
15.65 +
15.66 + LpSolverBase* LpSoplex::_copyLp() {
15.67 + LpSoplex* newlp = new LpSoplex(*this);
15.68 + return newlp;
15.69 + }
15.70 +
15.71 + int LpSoplex::_addCol() {
15.72 + soplex::LPCol c;
15.73 + c.setLower(-soplex::infinity);
15.74 + c.setUpper(soplex::infinity);
15.75 + soplex->addCol(c);
15.76 +
15.77 + colNames.push_back(std::string());
15.78 + primal_value.push_back(0.0);
15.79 + solved = false;
15.80 +
15.81 + return soplex->nCols() - 1;
15.82 + }
15.83 +
15.84 + int LpSoplex::_addRow() {
15.85 + soplex::LPRow r;
15.86 + r.setLhs(-soplex::infinity);
15.87 + r.setRhs(soplex::infinity);
15.88 + soplex->addRow(r);
15.89 +
15.90 + dual_value.push_back(0.0);
15.91 + solved = false;
15.92 +
15.93 + return soplex->nRows() - 1;
15.94 + }
15.95 +
15.96 +
15.97 + void LpSoplex::_eraseCol(int i) {
15.98 + soplex->removeCol(i);
15.99 + invColNames.erase(colNames[i]);
15.100 + colNames[i] = colNames.back();
15.101 + invColNames[colNames.back()] = i;
15.102 + colNames.pop_back();
15.103 + primal_value[i] = primal_value.back();
15.104 + primal_value.pop_back();
15.105 + solved = false;
15.106 + }
15.107 +
15.108 + void LpSoplex::_eraseRow(int i) {
15.109 + soplex->removeRow(i);
15.110 + dual_value[i] = dual_value.back();
15.111 + dual_value.pop_back();
15.112 + solved = false;
15.113 + }
15.114 +
15.115 + void LpSoplex::_getColName(int c, std::string &name) const {
15.116 + name = colNames[c];
15.117 + }
15.118 +
15.119 + void LpSoplex::_setColName(int c, const std::string &name) {
15.120 + invColNames.erase(colNames[c]);
15.121 + colNames[c] = name;
15.122 + if (!name.empty()) {
15.123 + invColNames.insert(std::make_pair(name, c));
15.124 + }
15.125 + }
15.126 +
15.127 + int LpSoplex::_colByName(const std::string& name) const {
15.128 + std::map<std::string, int>::const_iterator it =
15.129 + invColNames.find(name);
15.130 + if (it != invColNames.end()) {
15.131 + return it->second;
15.132 + } else {
15.133 + return -1;
15.134 + }
15.135 + }
15.136 +
15.137 +
15.138 + void LpSoplex::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e) {
15.139 + for (int j = 0; j < soplex->nCols(); ++j) {
15.140 + soplex->changeElement(i, j, 0.0);
15.141 + }
15.142 + for(ConstRowIterator it = b; it != e; ++it) {
15.143 + soplex->changeElement(i, it->first, it->second);
15.144 + }
15.145 + solved = false;
15.146 + }
15.147 +
15.148 + void LpSoplex::_getRowCoeffs(int i, RowIterator b) const {
15.149 + const soplex::SVector& vec = soplex->rowVector(i);
15.150 + for (int k = 0; k < vec.size(); ++k) {
15.151 + *b = std::make_pair(vec.index(k), vec.value(k));
15.152 + ++b;
15.153 + }
15.154 + }
15.155 +
15.156 + void LpSoplex::_setColCoeffs(int j, ConstColIterator b, ConstColIterator e) {
15.157 + for (int i = 0; i < soplex->nRows(); ++i) {
15.158 + soplex->changeElement(i, j, 0.0);
15.159 + }
15.160 + for(ConstColIterator it = b; it != e; ++it) {
15.161 + soplex->changeElement(it->first, j, it->second);
15.162 + }
15.163 + solved = false;
15.164 + }
15.165 +
15.166 + void LpSoplex::_getColCoeffs(int i, ColIterator b) const {
15.167 + const soplex::SVector& vec = soplex->colVector(i);
15.168 + for (int k = 0; k < vec.size(); ++k) {
15.169 + *b = std::make_pair(vec.index(k), vec.value(k));
15.170 + ++b;
15.171 + }
15.172 + }
15.173 +
15.174 + void LpSoplex::_setCoeff(int i, int j, Value value) {
15.175 + soplex->changeElement(i, j, value);
15.176 + solved = false;
15.177 + }
15.178 +
15.179 + LpSoplex::Value LpSoplex::_getCoeff(int i, int j) const {
15.180 + return soplex->rowVector(i)[j];
15.181 + }
15.182 +
15.183 + void LpSoplex::_setColLowerBound(int i, Value value) {
15.184 + soplex->changeLower(i, value != -INF ? value : -soplex::infinity);
15.185 + solved = false;
15.186 + }
15.187 +
15.188 + LpSoplex::Value LpSoplex::_getColLowerBound(int i) const {
15.189 + double value = soplex->lower(i);
15.190 + return value != -soplex::infinity ? value : -INF;
15.191 + }
15.192 +
15.193 + void LpSoplex::_setColUpperBound(int i, Value value) {
15.194 + soplex->changeUpper(i, value != INF ? value : soplex::infinity);
15.195 + solved = false;
15.196 + }
15.197 +
15.198 + LpSoplex::Value LpSoplex::_getColUpperBound(int i) const {
15.199 + double value = soplex->upper(i);
15.200 + return value != soplex::infinity ? value : INF;
15.201 + }
15.202 +
15.203 + void LpSoplex::_setRowBounds(int i, Value lb, Value ub) {
15.204 + soplex->changeRange(i, lb != -INF ? lb : -soplex::infinity,
15.205 + ub != INF ? ub : soplex::infinity);
15.206 + solved = false;
15.207 + }
15.208 + void LpSoplex::_getRowBounds(int i, Value &lower, Value &upper) const {
15.209 + lower = soplex->lhs(i);
15.210 + if (lower == -soplex::infinity) lower = -INF;
15.211 + upper = soplex->rhs(i);
15.212 + if (upper == -soplex::infinity) upper = INF;
15.213 + }
15.214 +
15.215 + void LpSoplex::_setObjCoeff(int i, Value obj_coef) {
15.216 + soplex->changeObj(i, obj_coef);
15.217 + solved = false;
15.218 + }
15.219 +
15.220 + LpSoplex::Value LpSoplex::_getObjCoeff(int i) const {
15.221 + return soplex->obj(i);
15.222 + }
15.223 +
15.224 + void LpSoplex::_clearObj() {
15.225 + for (int i = 0; i < soplex->nCols(); ++i) {
15.226 + soplex->changeObj(i, 0.0);
15.227 + }
15.228 + solved = false;
15.229 + }
15.230 +
15.231 + LpSoplex::SolveExitStatus LpSoplex::_solve() {
15.232 + soplex::SPxSolver::Status status = soplex->solve();
15.233 +
15.234 + soplex::Vector pv(primal_value.size(), &primal_value[0]);
15.235 + soplex->getPrimal(pv);
15.236 +
15.237 + soplex::Vector dv(dual_value.size(), &dual_value[0]);
15.238 + soplex->getDual(dv);
15.239 +
15.240 + switch (status) {
15.241 + case soplex::SPxSolver::OPTIMAL:
15.242 + case soplex::SPxSolver::INFEASIBLE:
15.243 + case soplex::SPxSolver::UNBOUNDED:
15.244 + solved = true;
15.245 + return SOLVED;
15.246 + default:
15.247 + return UNSOLVED;
15.248 + }
15.249 + }
15.250 +
15.251 + LpSoplex::Value LpSoplex::_getPrimal(int i) const {
15.252 + return primal_value[i];
15.253 + }
15.254 +
15.255 + LpSoplex::Value LpSoplex::_getDual(int i) const {
15.256 + return dual_value[i];
15.257 + }
15.258 +
15.259 + LpSoplex::Value LpSoplex::_getPrimalValue() const {
15.260 + return soplex->objValue();
15.261 + }
15.262 +
15.263 + bool LpSoplex::_isBasicCol(int i) const {
15.264 + return soplex->getBasisColStatus(i) == soplex::SPxSolver::BASIC;
15.265 + }
15.266 +
15.267 + LpSoplex::SolutionStatus LpSoplex::_getPrimalStatus() const {
15.268 + if (!solved) return UNDEFINED;
15.269 + switch (soplex->status()) {
15.270 + case soplex::SPxSolver::OPTIMAL:
15.271 + return OPTIMAL;
15.272 + case soplex::SPxSolver::UNBOUNDED:
15.273 + return INFINITE;
15.274 + case soplex::SPxSolver::INFEASIBLE:
15.275 + return INFEASIBLE;
15.276 + default:
15.277 + return UNDEFINED;
15.278 + }
15.279 + }
15.280 +
15.281 + LpSoplex::SolutionStatus LpSoplex::_getDualStatus() const {
15.282 + if (!solved) return UNDEFINED;
15.283 + switch (soplex->status()) {
15.284 + case soplex::SPxSolver::OPTIMAL:
15.285 + return OPTIMAL;
15.286 + case soplex::SPxSolver::UNBOUNDED:
15.287 + return INFEASIBLE;
15.288 + default:
15.289 + return UNDEFINED;
15.290 + }
15.291 + }
15.292 +
15.293 + LpSoplex::ProblemTypes LpSoplex::_getProblemType() const {
15.294 + if (!solved) return UNKNOWN;
15.295 + switch (soplex->status()) {
15.296 + case soplex::SPxSolver::OPTIMAL:
15.297 + return PRIMAL_DUAL_FEASIBLE;
15.298 + case soplex::SPxSolver::UNBOUNDED:
15.299 + return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
15.300 + default:
15.301 + return UNKNOWN;
15.302 + }
15.303 + }
15.304 +
15.305 + void LpSoplex::_setMax() {
15.306 + soplex->changeSense(soplex::SPxSolver::MAXIMIZE);
15.307 + solved = false;
15.308 + }
15.309 + void LpSoplex::_setMin() {
15.310 + soplex->changeSense(soplex::SPxSolver::MINIMIZE);
15.311 + solved = false;
15.312 + }
15.313 + bool LpSoplex::_isMax() const {
15.314 + return soplex->spxSense() == soplex::SPxSolver::MAXIMIZE;
15.315 + }
15.316 +
15.317 +
15.318 +} //namespace lemon
15.319 +
16.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
16.2 +++ b/lemon/lp_soplex.h Tue Dec 02 21:40:33 2008 +0100
16.3 @@ -0,0 +1,120 @@
16.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
16.5 + *
16.6 + * This file is a part of LEMON, a generic C++ optimization library.
16.7 + *
16.8 + * Copyright (C) 2003-2008
16.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
16.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
16.11 + *
16.12 + * Permission to use, modify and distribute this software is granted
16.13 + * provided that this copyright notice appears in all copies. For
16.14 + * precise terms see the accompanying LICENSE file.
16.15 + *
16.16 + * This software is provided "AS IS" with no warranty of any kind,
16.17 + * express or implied, and with no claim as to its suitability for any
16.18 + * purpose.
16.19 + *
16.20 + */
16.21 +
16.22 +#ifndef LEMON_LP_SOPLEX_H
16.23 +#define LEMON_LP_SOPLEX_H
16.24 +
16.25 +///\file
16.26 +///\brief Header of the LEMON-SOPLEX lp solver interface.
16.27 +
16.28 +#include <vector>
16.29 +#include <string>
16.30 +
16.31 +#include <lemon/lp_base.h>
16.32 +
16.33 +// Forward declaration
16.34 +namespace soplex {
16.35 + class SoPlex;
16.36 +}
16.37 +
16.38 +namespace lemon {
16.39 +
16.40 + /// \ingroup lp_group
16.41 + ///
16.42 + /// \brief Interface for the SOPLEX solver
16.43 + ///
16.44 + /// This class implements an interface for the SoPlex LP solver.
16.45 + /// The SoPlex library is an object oriented lp solver library
16.46 + /// developed at the Konrad-Zuse-Zentrum für Informationstechnik
16.47 + /// Berlin (ZIB). You can find detailed information about it at the
16.48 + /// <tt>http://soplex.zib.de</tt> address.
16.49 + class LpSoplex :virtual public LpSolverBase {
16.50 + protected:
16.51 +
16.52 + _lp_bits::RelocateIdHandler relocateIdHandler;
16.53 +
16.54 + soplex::SoPlex* soplex;
16.55 + bool solved;
16.56 +
16.57 + std::vector<std::string> colNames;
16.58 + std::map<std::string, int> invColNames;
16.59 +
16.60 + std::vector<Value> primal_value;
16.61 + std::vector<Value> dual_value;
16.62 +
16.63 +
16.64 + public:
16.65 +
16.66 + typedef LpSolverBase Parent;
16.67 +
16.68 +
16.69 + /// \e
16.70 + LpSoplex();
16.71 + /// \e
16.72 + LpSoplex(const LpSoplex&);
16.73 + /// \e
16.74 + ~LpSoplex();
16.75 +
16.76 + protected:
16.77 +
16.78 + virtual LpSolverBase* _newLp();
16.79 + virtual LpSolverBase* _copyLp();
16.80 +
16.81 + virtual int _addCol();
16.82 + virtual int _addRow();
16.83 + virtual void _eraseCol(int i);
16.84 + virtual void _eraseRow(int i);
16.85 + virtual void _getColName(int col, std::string & name) const;
16.86 + virtual void _setColName(int col, const std::string & name);
16.87 + virtual int _colByName(const std::string& name) const;
16.88 + virtual void _setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e);
16.89 + virtual void _getRowCoeffs(int i, RowIterator b) const;
16.90 + virtual void _setColCoeffs(int i, ConstColIterator b, ConstColIterator e);
16.91 + virtual void _getColCoeffs(int i, ColIterator b) const;
16.92 + virtual void _setCoeff(int row, int col, Value value);
16.93 + virtual Value _getCoeff(int row, int col) const;
16.94 + virtual void _setColLowerBound(int i, Value value);
16.95 + virtual Value _getColLowerBound(int i) const;
16.96 + virtual void _setColUpperBound(int i, Value value);
16.97 + virtual Value _getColUpperBound(int i) const;
16.98 + virtual void _setRowBounds(int i, Value lower, Value upper);
16.99 + virtual void _getRowBounds(int i, Value &lower, Value &upper) const;
16.100 + virtual void _setObjCoeff(int i, Value obj_coef);
16.101 + virtual Value _getObjCoeff(int i) const;
16.102 + virtual void _clearObj();
16.103 +
16.104 + virtual SolveExitStatus _solve();
16.105 + virtual Value _getPrimal(int i) const;
16.106 + virtual Value _getDual(int i) const;
16.107 + virtual Value _getPrimalValue() const;
16.108 + virtual bool _isBasicCol(int i) const;
16.109 +
16.110 + virtual SolutionStatus _getPrimalStatus() const;
16.111 + virtual SolutionStatus _getDualStatus() const;
16.112 + virtual ProblemTypes _getProblemType() const;
16.113 +
16.114 +
16.115 + virtual void _setMax();
16.116 + virtual void _setMin();
16.117 + virtual bool _isMax() const;
16.118 +
16.119 + };
16.120 +} //END OF NAMESPACE LEMON
16.121 +
16.122 +#endif //LEMON_LP_SOPLEX_H
16.123 +
17.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
17.2 +++ b/lemon/mip_cplex.cc Tue Dec 02 21:40:33 2008 +0100
17.3 @@ -0,0 +1,141 @@
17.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
17.5 + *
17.6 + * This file is a part of LEMON, a generic C++ optimization library.
17.7 + *
17.8 + * Copyright (C) 2003-2008
17.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
17.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
17.11 + *
17.12 + * Permission to use, modify and distribute this software is granted
17.13 + * provided that this copyright notice appears in all copies. For
17.14 + * precise terms see the accompanying LICENSE file.
17.15 + *
17.16 + * This software is provided "AS IS" with no warranty of any kind,
17.17 + * express or implied, and with no claim as to its suitability for any
17.18 + * purpose.
17.19 + *
17.20 + */
17.21 +
17.22 +///\file
17.23 +///\brief Implementation of the LEMON-CPLEX mip solver interface.
17.24 +
17.25 +#include <lemon/mip_cplex.h>
17.26 +
17.27 +extern "C" {
17.28 +#include <ilcplex/cplex.h>
17.29 +}
17.30 +
17.31 +namespace lemon {
17.32 +
17.33 + MipCplex::MipCplex() {
17.34 + //This is unnecessary: setting integrality constraints on
17.35 + //variables will set this, too
17.36 +
17.37 + ///\todo The constant CPXPROB_MIP is
17.38 + ///called CPXPROB_MILP in later versions
17.39 +#if CPX_VERSION < 800
17.40 + CPXchgprobtype( env, lp, CPXPROB_MIP);
17.41 +#else
17.42 + CPXchgprobtype( env, lp, CPXPROB_MILP);
17.43 +#endif
17.44 +
17.45 + }
17.46 +
17.47 + void MipCplex::_colType(int i, MipCplex::ColTypes col_type){
17.48 +
17.49 + // Note If a variable is to be changed to binary, a call to CPXchgbds
17.50 + // should also be made to change the bounds to 0 and 1.
17.51 +
17.52 + int indices[1];
17.53 + indices[0]=i;
17.54 + char ctype[1];
17.55 + switch (col_type){
17.56 + case INT:
17.57 + ctype[0]=CPX_INTEGER;//'I'
17.58 + break;
17.59 + case REAL:
17.60 + ctype[0]=CPX_CONTINUOUS ;//'C'
17.61 + break;
17.62 + default:;
17.63 + //FIXME problem
17.64 + }
17.65 + CPXchgctype (env, lp, 1, indices, ctype);
17.66 + }
17.67 +
17.68 + MipCplex::ColTypes MipCplex::_colType(int i) const {
17.69 +
17.70 + char ctype[1];
17.71 + CPXgetctype (env, lp, ctype, i, i);
17.72 + switch (ctype[0]){
17.73 +
17.74 + case CPX_INTEGER:
17.75 + return INT;
17.76 + case CPX_CONTINUOUS:
17.77 + return REAL;
17.78 + default:
17.79 + return REAL;//Error!
17.80 + }
17.81 +
17.82 + }
17.83 +
17.84 + LpCplex::SolveExitStatus MipCplex::_solve(){
17.85 +
17.86 + status = CPXmipopt (env, lp);
17.87 + if (status==0)
17.88 + return SOLVED;
17.89 + else
17.90 + return UNSOLVED;
17.91 +
17.92 + }
17.93 +
17.94 +
17.95 + LpCplex::SolutionStatus MipCplex::_getMipStatus() const {
17.96 +
17.97 + int stat = CPXgetstat(env, lp);
17.98 +
17.99 + //Fortunately, MIP statuses did not change for cplex 8.0
17.100 + switch (stat)
17.101 + {
17.102 + case CPXMIP_OPTIMAL:
17.103 + // Optimal integer solution has been found.
17.104 + case CPXMIP_OPTIMAL_TOL:
17.105 + // Optimal soluton with the tolerance defined by epgap or epagap has
17.106 + // been found.
17.107 + return OPTIMAL;
17.108 + //This also exists in later issues
17.109 + // case CPXMIP_UNBOUNDED:
17.110 + //return INFINITE;
17.111 + case CPXMIP_INFEASIBLE:
17.112 + return INFEASIBLE;
17.113 + default:
17.114 + return UNDEFINED;
17.115 + }
17.116 + //Unboundedness not treated well: the following is from cplex 9.0 doc
17.117 + // About Unboundedness
17.118 +
17.119 + // The treatment of models that are unbounded involves a few
17.120 + // subtleties. Specifically, a declaration of unboundedness means that
17.121 + // ILOG CPLEX has determined that the model has an unbounded
17.122 + // ray. Given any feasible solution x with objective z, a multiple of
17.123 + // the unbounded ray can be added to x to give a feasible solution
17.124 + // with objective z-1 (or z+1 for maximization models). Thus, if a
17.125 + // feasible solution exists, then the optimal objective is
17.126 + // unbounded. Note that ILOG CPLEX has not necessarily concluded that
17.127 + // a feasible solution exists. Users can call the routine CPXsolninfo
17.128 + // to determine whether ILOG CPLEX has also concluded that the model
17.129 + // has a feasible solution.
17.130 +
17.131 + }
17.132 +
17.133 + MipCplex::Value MipCplex::_getPrimal(int i) const {
17.134 + Value x;
17.135 + CPXgetmipx(env, lp, &x, i, i);
17.136 + return x;
17.137 + }
17.138 +
17.139 + MipCplex::Value MipCplex::_getPrimalValue() const {
17.140 + Value objval;
17.141 + CPXgetmipobjval(env, lp, &objval);
17.142 + return objval;
17.143 + }
17.144 +} //END OF NAMESPACE LEMON
18.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
18.2 +++ b/lemon/mip_cplex.h Tue Dec 02 21:40:33 2008 +0100
18.3 @@ -0,0 +1,61 @@
18.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
18.5 + *
18.6 + * This file is a part of LEMON, a generic C++ optimization library.
18.7 + *
18.8 + * Copyright (C) 2003-2008
18.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
18.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
18.11 + *
18.12 + * Permission to use, modify and distribute this software is granted
18.13 + * provided that this copyright notice appears in all copies. For
18.14 + * precise terms see the accompanying LICENSE file.
18.15 + *
18.16 + * This software is provided "AS IS" with no warranty of any kind,
18.17 + * express or implied, and with no claim as to its suitability for any
18.18 + * purpose.
18.19 + *
18.20 + */
18.21 +
18.22 +#ifndef LEMON_MIP_CPLEX_H
18.23 +#define LEMON_MIP_CPLEX_H
18.24 +
18.25 +///\file
18.26 +///\brief Header of the LEMON-CPLEX mip solver interface.
18.27 +///\ingroup lp_group
18.28 +
18.29 +
18.30 +#include <lemon/lp_cplex.h>
18.31 +
18.32 +namespace lemon {
18.33 +
18.34 + /// \brief Interface for the CPLEX MIP solver
18.35 + ///
18.36 + /// This class implements an interface for the CPLEX MIP solver.
18.37 + ///\ingroup lp_group
18.38 + class MipCplex : public MipSolverBase, public LpCplex{
18.39 +
18.40 + public:
18.41 +
18.42 + typedef MipSolverBase ParentMip;
18.43 + typedef LpCplex ParentLp;
18.44 +
18.45 + MipCplex();
18.46 + //~MipCplex();
18.47 +
18.48 +
18.49 +
18.50 +
18.51 + protected:
18.52 +
18.53 + virtual ColTypes _colType(int col) const;
18.54 + virtual void _colType(int col, ColTypes col_type);
18.55 +
18.56 + virtual LpCplex::SolveExitStatus _solve();
18.57 + virtual LpCplex::SolutionStatus _getMipStatus() const;
18.58 + virtual ParentLp::Value _getPrimal(int i) const;
18.59 + virtual ParentLp::Value _getPrimalValue() const;
18.60 + };
18.61 +
18.62 +} //END OF NAMESPACE LEMON
18.63 +
18.64 +#endif // END OF LEMON_MIP_CPLEX_H
19.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
19.2 +++ b/lemon/mip_glpk.cc Tue Dec 02 21:40:33 2008 +0100
19.3 @@ -0,0 +1,154 @@
19.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
19.5 + *
19.6 + * This file is a part of LEMON, a generic C++ optimization library.
19.7 + *
19.8 + * Copyright (C) 2003-2008
19.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
19.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
19.11 + *
19.12 + * Permission to use, modify and distribute this software is granted
19.13 + * provided that this copyright notice appears in all copies. For
19.14 + * precise terms see the accompanying LICENSE file.
19.15 + *
19.16 + * This software is provided "AS IS" with no warranty of any kind,
19.17 + * express or implied, and with no claim as to its suitability for any
19.18 + * purpose.
19.19 + *
19.20 + */
19.21 +
19.22 +///\file
19.23 +///\brief Implementation of the LEMON-GLPK mip solver interface.
19.24 +
19.25 +#include <lemon/mip_glpk.h>
19.26 +
19.27 +extern "C" {
19.28 +#include <glpk.h>
19.29 +}
19.30 +
19.31 +#if GLP_MAJOR_VERSION > 4 || (GLP_MAJOR_VERSION == 4 && GLP_MINOR_VERSION > 15)
19.32 +#define LEMON_glp(func) (glp_##func)
19.33 +#define LEMON_lpx(func) (lpx_##func)
19.34 +
19.35 +#define LEMON_GLP(def) (GLP_##def)
19.36 +#define LEMON_LPX(def) (LPX_##def)
19.37 +
19.38 +#else
19.39 +
19.40 +#define LEMON_glp(func) (lpx_##func)
19.41 +#define LEMON_lpx(func) (lpx_##func)
19.42 +
19.43 +#define LEMON_GLP(def) (LPX_##def)
19.44 +#define LEMON_LPX(def) (LPX_##def)
19.45 +
19.46 +#endif
19.47 +
19.48 +namespace lemon {
19.49 +
19.50 + MipGlpk::MipGlpk() {
19.51 +#if !(GLP_MAJOR_VERSION > 4 || \
19.52 + (GLP_MAJOR_VERSION == 4 && GLP_MINOR_VERSION > 15))
19.53 + LEMON_lpx(set_class)(lp,LEMON_GLP(MIP));
19.54 +#endif
19.55 + }
19.56 +
19.57 + void MipGlpk::_colType(int i, MipGlpk::ColTypes col_type){
19.58 + switch (col_type){
19.59 + case INT:
19.60 + LEMON_glp(set_col_kind)(lp,i,LEMON_GLP(IV));
19.61 + break;
19.62 + case REAL:
19.63 + LEMON_glp(set_col_kind)(lp,i,LEMON_GLP(CV));
19.64 + break;
19.65 + default:;
19.66 + //FIXME problem
19.67 + }
19.68 + }
19.69 +
19.70 + MipGlpk::ColTypes MipGlpk::_colType(int i) const {
19.71 + switch (LEMON_glp(get_col_kind)(lp,i)){
19.72 + case LEMON_GLP(IV):
19.73 + return INT;//Or binary
19.74 + case LEMON_GLP(CV):
19.75 + return REAL;
19.76 + default:
19.77 + return REAL;//Error!
19.78 + }
19.79 +
19.80 + }
19.81 +
19.82 + LpGlpk::SolveExitStatus MipGlpk::_solve() {
19.83 + int result = LEMON_lpx(simplex)(lp);
19.84 +
19.85 + // hack: mip does not contain integer variable
19.86 +#if GLP_MAJOR_VERSION == 4 && GLP_MINOR_VERSION == 16
19.87 + int tmp = -1;
19.88 + if (LEMON_glp(get_num_int(lp)) == 0) {
19.89 + tmp = LEMON_lpx(add_cols)(lp, 1);
19.90 + LEMON_glp(set_col_bnds)(lp, tmp, LEMON_GLP(FX), 0.0, 0.0);
19.91 + LEMON_glp(set_col_kind)(lp, tmp, LEMON_GLP(IV));
19.92 + }
19.93 +#endif
19.94 +
19.95 + if (LEMON_lpx(get_status)(lp)==LEMON_LPX(OPT)) {
19.96 + //Maybe we could try the routine lpx_intopt(lp), a revised
19.97 + //version of lpx_integer
19.98 +
19.99 + result = LEMON_lpx(integer)(lp);
19.100 + switch (result){
19.101 + case LEMON_LPX(E_OK):
19.102 + solved = true;
19.103 + break;
19.104 + default:
19.105 + solved = false;
19.106 + }
19.107 + } else {
19.108 + solved = false;
19.109 + }
19.110 +#if GLP_MAJOR_VERSION == 4 && GLP_MINOR_VERSION == 16
19.111 + if (tmp != -1) {
19.112 + int tmpa[2];
19.113 + tmpa[1] = tmp;
19.114 + LEMON_lpx(del_cols)(lp, 1, tmpa);
19.115 + }
19.116 +#endif
19.117 + return solved ? SOLVED : UNSOLVED;
19.118 + }
19.119 +
19.120 +
19.121 + LpGlpk::SolutionStatus MipGlpk::_getMipStatus() const {
19.122 +
19.123 + if (LEMON_lpx(get_status)(lp)==LEMON_LPX(OPT)){
19.124 + //Meg kell nezni: ha az LP is infinite, akkor ez is, ha az is
19.125 + //infeasible, akkor ez is, de ez lehet maskepp is infeasible.
19.126 + int stat= LEMON_lpx(mip_status)(lp);
19.127 +
19.128 + switch (stat) {
19.129 + case LEMON_LPX(I_UNDEF)://Undefined (no solve has been run yet)
19.130 + return UNDEFINED;
19.131 + case LEMON_LPX(I_NOFEAS)://There is no feasible integral solution
19.132 + return INFEASIBLE;
19.133 + // case LEMON_LPX(UNBND)://Unbounded
19.134 + // return INFINITE;
19.135 + case LEMON_LPX(I_FEAS)://Feasible
19.136 + return FEASIBLE;
19.137 + case LEMON_LPX(I_OPT)://Feasible
19.138 + return OPTIMAL;
19.139 + default:
19.140 + return UNDEFINED; //to avoid gcc warning
19.141 + //FIXME error
19.142 + }
19.143 + }
19.144 + else
19.145 + return UNDEFINED; //Maybe we could refine this: what does the LP
19.146 + //relaxation look like
19.147 +
19.148 + }
19.149 +
19.150 + MipGlpk::Value MipGlpk::_getPrimal(int i) const {
19.151 + return LEMON_glp(mip_col_val)(lp,i);
19.152 + }
19.153 +
19.154 + MipGlpk::Value MipGlpk::_getPrimalValue() const {
19.155 + return LEMON_glp(mip_obj_val)(lp);
19.156 + }
19.157 +} //END OF NAMESPACE LEMON
20.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
20.2 +++ b/lemon/mip_glpk.h Tue Dec 02 21:40:33 2008 +0100
20.3 @@ -0,0 +1,59 @@
20.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
20.5 + *
20.6 + * This file is a part of LEMON, a generic C++ optimization library.
20.7 + *
20.8 + * Copyright (C) 2003-2008
20.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
20.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
20.11 + *
20.12 + * Permission to use, modify and distribute this software is granted
20.13 + * provided that this copyright notice appears in all copies. For
20.14 + * precise terms see the accompanying LICENSE file.
20.15 + *
20.16 + * This software is provided "AS IS" with no warranty of any kind,
20.17 + * express or implied, and with no claim as to its suitability for any
20.18 + * purpose.
20.19 + *
20.20 + */
20.21 +
20.22 +#ifndef LEMON_MIP_GLPK_H
20.23 +#define LEMON_MIP_GLPK_H
20.24 +
20.25 +///\file
20.26 +///\brief Header of the LEMON-GLPK mip solver interface.
20.27 +///\ingroup lp_group
20.28 +
20.29 +
20.30 +#include <lemon/lp_glpk.h>
20.31 +
20.32 +namespace lemon {
20.33 + /// \brief Interface for the GLPK MIP solver
20.34 + ///
20.35 + /// This class implements an interface for the GLPK MIP solver.
20.36 + ///\ingroup lp_group
20.37 + class MipGlpk : public MipSolverBase, public LpGlpk{
20.38 +
20.39 + public:
20.40 +
20.41 + typedef MipSolverBase ParentMip;
20.42 + typedef LpGlpk ParentLp;
20.43 +
20.44 + MipGlpk();
20.45 + //~MipGlpk();
20.46 +
20.47 +
20.48 +
20.49 + protected:
20.50 +
20.51 + virtual ColTypes _colType(int col) const;
20.52 + virtual void _colType(int col, ColTypes col_type);
20.53 +
20.54 + virtual LpGlpk::SolveExitStatus _solve();
20.55 + virtual LpGlpk::SolutionStatus _getMipStatus() const;
20.56 + virtual ParentLp::Value _getPrimal(int i) const;
20.57 + virtual ParentLp::Value _getPrimalValue() const;
20.58 + };
20.59 +
20.60 +} //END OF NAMESPACE LEMON
20.61 +
20.62 +#endif // END OF LEMON_MIP_GLPK_H
21.1 --- a/test/CMakeLists.txt Mon Jan 12 12:22:11 2009 +0000
21.2 +++ b/test/CMakeLists.txt Tue Dec 02 21:40:33 2008 +0100
21.3 @@ -18,6 +18,8 @@
21.4 hao_orlin_test
21.5 heap_test
21.6 kruskal_test
21.7 + lp_test
21.8 + mip_test
21.9 maps_test
21.10 max_matching_test
21.11 radix_sort_test
22.1 --- a/test/Makefile.am Mon Jan 12 12:22:11 2009 +0000
22.2 +++ b/test/Makefile.am Tue Dec 02 21:40:33 2008 +0100
22.3 @@ -33,6 +33,13 @@
22.4 test/time_measure_test \
22.5 test/unionfind_test
22.6
22.7 +if HAVE_LP
22.8 +check_PROGRAMS += test/lp_test
22.9 +endif HAVE_LP
22.10 +if HAVE_MIP
22.11 +check_PROGRAMS += test/mip_test
22.12 +endif HAVE_MIP
22.13 +
22.14 TESTS += $(check_PROGRAMS)
22.15 XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
22.16
22.17 @@ -51,7 +58,9 @@
22.18 test_heap_test_SOURCES = test/heap_test.cc
22.19 test_kruskal_test_SOURCES = test/kruskal_test.cc
22.20 test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
22.21 +test_lp_test_SOURCES = test/lp_test.cc
22.22 test_maps_test_SOURCES = test/maps_test.cc
22.23 +test_mip_test_SOURCES = test/mip_test.cc
22.24 test_max_matching_test_SOURCES = test/max_matching_test.cc
22.25 test_path_test_SOURCES = test/path_test.cc
22.26 test_preflow_test_SOURCES = test/preflow_test.cc
23.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
23.2 +++ b/test/lp_test.cc Tue Dec 02 21:40:33 2008 +0100
23.3 @@ -0,0 +1,423 @@
23.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
23.5 + *
23.6 + * This file is a part of LEMON, a generic C++ optimization library.
23.7 + *
23.8 + * Copyright (C) 2003-2008
23.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
23.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
23.11 + *
23.12 + * Permission to use, modify and distribute this software is granted
23.13 + * provided that this copyright notice appears in all copies. For
23.14 + * precise terms see the accompanying LICENSE file.
23.15 + *
23.16 + * This software is provided "AS IS" with no warranty of any kind,
23.17 + * express or implied, and with no claim as to its suitability for any
23.18 + * purpose.
23.19 + *
23.20 + */
23.21 +
23.22 +#include <sstream>
23.23 +#include <lemon/lp_skeleton.h>
23.24 +#include "test_tools.h"
23.25 +#include <lemon/tolerance.h>
23.26 +
23.27 +#ifdef HAVE_CONFIG_H
23.28 +#include <lemon/config.h>
23.29 +#endif
23.30 +
23.31 +#ifdef HAVE_GLPK
23.32 +#include <lemon/lp_glpk.h>
23.33 +#endif
23.34 +
23.35 +#ifdef HAVE_CPLEX
23.36 +#include <lemon/lp_cplex.h>
23.37 +#endif
23.38 +
23.39 +#ifdef HAVE_SOPLEX
23.40 +#include <lemon/lp_soplex.h>
23.41 +#endif
23.42 +
23.43 +using namespace lemon;
23.44 +
23.45 +void lpTest(LpSolverBase & lp)
23.46 +{
23.47 +
23.48 +
23.49 +
23.50 + typedef LpSolverBase LP;
23.51 +
23.52 + std::vector<LP::Col> x(10);
23.53 + // for(int i=0;i<10;i++) x.push_back(lp.addCol());
23.54 + lp.addColSet(x);
23.55 + lp.colLowerBound(x,1);
23.56 + lp.colUpperBound(x,1);
23.57 + lp.colBounds(x,1,2);
23.58 +#ifndef GYORSITAS
23.59 +
23.60 + std::vector<LP::Col> y(10);
23.61 + lp.addColSet(y);
23.62 +
23.63 + lp.colLowerBound(y,1);
23.64 + lp.colUpperBound(y,1);
23.65 + lp.colBounds(y,1,2);
23.66 +
23.67 + std::map<int,LP::Col> z;
23.68 +
23.69 + z.insert(std::make_pair(12,INVALID));
23.70 + z.insert(std::make_pair(2,INVALID));
23.71 + z.insert(std::make_pair(7,INVALID));
23.72 + z.insert(std::make_pair(5,INVALID));
23.73 +
23.74 + lp.addColSet(z);
23.75 +
23.76 + lp.colLowerBound(z,1);
23.77 + lp.colUpperBound(z,1);
23.78 + lp.colBounds(z,1,2);
23.79 +
23.80 + {
23.81 + LP::Expr e,f,g;
23.82 + LP::Col p1,p2,p3,p4,p5;
23.83 + LP::Constr c;
23.84 +
23.85 + p1=lp.addCol();
23.86 + p2=lp.addCol();
23.87 + p3=lp.addCol();
23.88 + p4=lp.addCol();
23.89 + p5=lp.addCol();
23.90 +
23.91 + e[p1]=2;
23.92 + e.constComp()=12;
23.93 + e[p1]+=2;
23.94 + e.constComp()+=12;
23.95 + e[p1]-=2;
23.96 + e.constComp()-=12;
23.97 +
23.98 + e=2;
23.99 + e=2.2;
23.100 + e=p1;
23.101 + e=f;
23.102 +
23.103 + e+=2;
23.104 + e+=2.2;
23.105 + e+=p1;
23.106 + e+=f;
23.107 +
23.108 + e-=2;
23.109 + e-=2.2;
23.110 + e-=p1;
23.111 + e-=f;
23.112 +
23.113 + e*=2;
23.114 + e*=2.2;
23.115 + e/=2;
23.116 + e/=2.2;
23.117 +
23.118 + e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+
23.119 + (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+
23.120 + (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+
23.121 + 2.2*f+f*2.2+f/2.2+
23.122 + 2*f+f*2+f/2+
23.123 + 2.2*p1+p1*2.2+p1/2.2+
23.124 + 2*p1+p1*2+p1/2
23.125 + );
23.126 +
23.127 +
23.128 + c = (e <= f );
23.129 + c = (e <= 2.2);
23.130 + c = (e <= 2 );
23.131 + c = (e <= p1 );
23.132 + c = (2.2<= f );
23.133 + c = (2 <= f );
23.134 + c = (p1 <= f );
23.135 + c = (p1 <= p2 );
23.136 + c = (p1 <= 2.2);
23.137 + c = (p1 <= 2 );
23.138 + c = (2.2<= p2 );
23.139 + c = (2 <= p2 );
23.140 +
23.141 + c = (e >= f );
23.142 + c = (e >= 2.2);
23.143 + c = (e >= 2 );
23.144 + c = (e >= p1 );
23.145 + c = (2.2>= f );
23.146 + c = (2 >= f );
23.147 + c = (p1 >= f );
23.148 + c = (p1 >= p2 );
23.149 + c = (p1 >= 2.2);
23.150 + c = (p1 >= 2 );
23.151 + c = (2.2>= p2 );
23.152 + c = (2 >= p2 );
23.153 +
23.154 + c = (e == f );
23.155 + c = (e == 2.2);
23.156 + c = (e == 2 );
23.157 + c = (e == p1 );
23.158 + c = (2.2== f );
23.159 + c = (2 == f );
23.160 + c = (p1 == f );
23.161 + //c = (p1 == p2 );
23.162 + c = (p1 == 2.2);
23.163 + c = (p1 == 2 );
23.164 + c = (2.2== p2 );
23.165 + c = (2 == p2 );
23.166 +
23.167 + c = (2 <= e <= 3);
23.168 + c = (2 <= p1<= 3);
23.169 +
23.170 + c = (2 >= e >= 3);
23.171 + c = (2 >= p1>= 3);
23.172 +
23.173 + e[x[3]]=2;
23.174 + e[x[3]]=4;
23.175 + e[x[3]]=1;
23.176 + e.constComp()=12;
23.177 +
23.178 + lp.addRow(LP::INF,e,23);
23.179 + lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
23.180 + lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
23.181 +
23.182 + lp.addRow(x[1]+x[3]<=x[5]-3);
23.183 + lp.addRow(-7<=x[1]+x[3]-12<=3);
23.184 + lp.addRow(x[1]<=x[5]);
23.185 +
23.186 + std::ostringstream buf;
23.187 +
23.188 +
23.189 + //Checking the simplify function
23.190 +
23.191 +// //How to check the simplify function? A map gives no information
23.192 +// //on the question whether a given key is or is not stored in it, or
23.193 +// //it does?
23.194 +// Yes, it does, using the find() function.
23.195 + e=((p1+p2)+(p1-p2));
23.196 + e.simplify();
23.197 + buf << "Coeff. of p2 should be 0";
23.198 + // std::cout<<e[p1]<<e[p2]<<e[p3]<<std::endl;
23.199 + check(e.find(p2)==e.end(), buf.str());
23.200 +
23.201 +
23.202 +
23.203 +
23.204 + e=((p1+p2)+(p1-0.99*p2));
23.205 + //e.prettyPrint(std::cout);
23.206 + //(e<=2).prettyPrint(std::cout);
23.207 + double tolerance=0.001;
23.208 + e.simplify(tolerance);
23.209 + buf << "Coeff. of p2 should be 0.01";
23.210 + check(e[p2]>0, buf.str());
23.211 +
23.212 + tolerance=0.02;
23.213 + e.simplify(tolerance);
23.214 + buf << "Coeff. of p2 should be 0";
23.215 + check(e.find(p2)==e.end(), buf.str());
23.216 +
23.217 +
23.218 + }
23.219 +
23.220 + {
23.221 + LP::DualExpr e,f,g;
23.222 + LP::Row p1 = INVALID, p2 = INVALID, p3 = INVALID,
23.223 + p4 = INVALID, p5 = INVALID;
23.224 +
23.225 + e[p1]=2;
23.226 + e[p1]+=2;
23.227 + e[p1]-=2;
23.228 +
23.229 + e=p1;
23.230 + e=f;
23.231 +
23.232 + e+=p1;
23.233 + e+=f;
23.234 +
23.235 + e-=p1;
23.236 + e-=f;
23.237 +
23.238 + e*=2;
23.239 + e*=2.2;
23.240 + e/=2;
23.241 + e/=2.2;
23.242 +
23.243 + e=((p1+p2)+(p1-p2)+
23.244 + (p1+f)+(f+p1)+(f+g)+
23.245 + (p1-f)+(f-p1)+(f-g)+
23.246 + 2.2*f+f*2.2+f/2.2+
23.247 + 2*f+f*2+f/2+
23.248 + 2.2*p1+p1*2.2+p1/2.2+
23.249 + 2*p1+p1*2+p1/2
23.250 + );
23.251 + }
23.252 +
23.253 +#endif
23.254 +}
23.255 +
23.256 +void solveAndCheck(LpSolverBase& lp, LpSolverBase::SolutionStatus stat,
23.257 + double exp_opt) {
23.258 + using std::string;
23.259 + lp.solve();
23.260 + //int decimal,sign;
23.261 + std::ostringstream buf;
23.262 + buf << "Primalstatus should be: " << int(stat);
23.263 +
23.264 + // itoa(stat,buf1, 10);
23.265 + check(lp.primalStatus()==stat, buf.str());
23.266 +
23.267 + if (stat == LpSolverBase::OPTIMAL) {
23.268 + std::ostringstream sbuf;
23.269 + sbuf << "Wrong optimal value: the right optimum is " << exp_opt;
23.270 + check(std::abs(lp.primalValue()-exp_opt) < 1e-3, sbuf.str());
23.271 + //+ecvt(exp_opt,2)
23.272 + }
23.273 +}
23.274 +
23.275 +void aTest(LpSolverBase & lp)
23.276 +{
23.277 + typedef LpSolverBase LP;
23.278 +
23.279 + //The following example is very simple
23.280 +
23.281 + typedef LpSolverBase::Row Row;
23.282 + typedef LpSolverBase::Col Col;
23.283 +
23.284 +
23.285 + Col x1 = lp.addCol();
23.286 + Col x2 = lp.addCol();
23.287 +
23.288 +
23.289 + //Constraints
23.290 + Row upright=lp.addRow(x1+x2 <=1);
23.291 + lp.addRow(x1+x2 >=-1);
23.292 + lp.addRow(x1-x2 <=1);
23.293 + lp.addRow(x1-x2 >=-1);
23.294 + //Nonnegativity of the variables
23.295 + lp.colLowerBound(x1, 0);
23.296 + lp.colLowerBound(x2, 0);
23.297 + //Objective function
23.298 + lp.obj(x1+x2);
23.299 +
23.300 + lp.max();
23.301 +
23.302 + //Testing the problem retrieving routines
23.303 + check(lp.objCoeff(x1)==1,"First term should be 1 in the obj function!");
23.304 + check(lp.isMax(),"This is a maximization!");
23.305 + check(lp.coeff(upright,x1)==1,"The coefficient in question is 1!");
23.306 + // std::cout<<lp.colLowerBound(x1)<<std::endl;
23.307 + check( lp.colLowerBound(x1)==0,
23.308 + "The lower bound for variable x1 should be 0.");
23.309 + check( lp.colUpperBound(x1)==LpSolverBase::INF,
23.310 + "The upper bound for variable x1 should be infty.");
23.311 + LpSolverBase::Value lb,ub;
23.312 + lp.getRowBounds(upright,lb,ub);
23.313 + check( lb==-LpSolverBase::INF,
23.314 + "The lower bound for the first row should be -infty.");
23.315 + check( ub==1,"The upper bound for the first row should be 1.");
23.316 + LpSolverBase::Expr e = lp.row(upright);
23.317 + check( e.size() == 2, "The row retrieval gives back wrong expression.");
23.318 + check( e[x1] == 1, "The first coefficient should 1.");
23.319 + check( e[x2] == 1, "The second coefficient should 1.");
23.320 +
23.321 + LpSolverBase::DualExpr de = lp.col(x1);
23.322 + check( de.size() == 4, "The col retrieval gives back wrong expression.");
23.323 + check( de[upright] == 1, "The first coefficient should 1.");
23.324 +
23.325 + LpSolverBase* clp = lp.copyLp();
23.326 +
23.327 + //Testing the problem retrieving routines
23.328 + check(clp->objCoeff(x1)==1,"First term should be 1 in the obj function!");
23.329 + check(clp->isMax(),"This is a maximization!");
23.330 + check(clp->coeff(upright,x1)==1,"The coefficient in question is 1!");
23.331 + // std::cout<<lp.colLowerBound(x1)<<std::endl;
23.332 + check( clp->colLowerBound(x1)==0,
23.333 + "The lower bound for variable x1 should be 0.");
23.334 + check( clp->colUpperBound(x1)==LpSolverBase::INF,
23.335 + "The upper bound for variable x1 should be infty.");
23.336 +
23.337 + clp->getRowBounds(upright,lb,ub);
23.338 + check( lb==-LpSolverBase::INF,
23.339 + "The lower bound for the first row should be -infty.");
23.340 + check( ub==1,"The upper bound for the first row should be 1.");
23.341 + e = clp->row(upright);
23.342 + check( e.size() == 2, "The row retrieval gives back wrong expression.");
23.343 + check( e[x1] == 1, "The first coefficient should 1.");
23.344 + check( e[x2] == 1, "The second coefficient should 1.");
23.345 +
23.346 + de = clp->col(x1);
23.347 + check( de.size() == 4, "The col retrieval gives back wrong expression.");
23.348 + check( de[upright] == 1, "The first coefficient should 1.");
23.349 +
23.350 + delete clp;
23.351 +
23.352 + //Maximization of x1+x2
23.353 + //over the triangle with vertices (0,0) (0,1) (1,0)
23.354 + double expected_opt=1;
23.355 + solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
23.356 +
23.357 + //Minimization
23.358 + lp.min();
23.359 + expected_opt=0;
23.360 + solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
23.361 +
23.362 + //Vertex (-1,0) instead of (0,0)
23.363 + lp.colLowerBound(x1, -LpSolverBase::INF);
23.364 + expected_opt=-1;
23.365 + solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt);
23.366 +
23.367 + //Erase one constraint and return to maximization
23.368 + lp.eraseRow(upright);
23.369 + lp.max();
23.370 + expected_opt=LpSolverBase::INF;
23.371 + solveAndCheck(lp, LpSolverBase::INFINITE, expected_opt);
23.372 +
23.373 + //Infeasibilty
23.374 + lp.addRow(x1+x2 <=-2);
23.375 + solveAndCheck(lp, LpSolverBase::INFEASIBLE, expected_opt);
23.376 +
23.377 + //Change problem and forget to solve
23.378 + lp.min();
23.379 + check(lp.primalStatus()==LpSolverBase::UNDEFINED,
23.380 + "Primalstatus should be UNDEFINED");
23.381 +
23.382 +
23.383 +// lp.solve();
23.384 +// if (lp.primalStatus()==LpSolverBase::OPTIMAL){
23.385 +// std::cout<< "Z = "<<lp.primalValue()
23.386 +// << " (error = " << lp.primalValue()-expected_opt
23.387 +// << "); x1 = "<<lp.primal(x1)
23.388 +// << "; x2 = "<<lp.primal(x2)
23.389 +// <<std::endl;
23.390 +
23.391 +// }
23.392 +// else{
23.393 +// std::cout<<lp.primalStatus()<<std::endl;
23.394 +// std::cout<<"Optimal solution not found!"<<std::endl;
23.395 +// }
23.396 +
23.397 +
23.398 +
23.399 +}
23.400 +
23.401 +
23.402 +int main()
23.403 +{
23.404 + LpSkeleton lp_skel;
23.405 + lpTest(lp_skel);
23.406 +
23.407 +#ifdef HAVE_GLPK
23.408 + LpGlpk lp_glpk1,lp_glpk2;
23.409 + lpTest(lp_glpk1);
23.410 + aTest(lp_glpk2);
23.411 +#endif
23.412 +
23.413 +#ifdef HAVE_CPLEX
23.414 + LpCplex lp_cplex1,lp_cplex2;
23.415 + lpTest(lp_cplex1);
23.416 + aTest(lp_cplex2);
23.417 +#endif
23.418 +
23.419 +#ifdef HAVE_SOPLEX
23.420 + LpSoplex lp_soplex1,lp_soplex2;
23.421 + lpTest(lp_soplex1);
23.422 + aTest(lp_soplex2);
23.423 +#endif
23.424 +
23.425 + return 0;
23.426 +}
24.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
24.2 +++ b/test/mip_test.cc Tue Dec 02 21:40:33 2008 +0100
24.3 @@ -0,0 +1,126 @@
24.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
24.5 + *
24.6 + * This file is a part of LEMON, a generic C++ optimization library.
24.7 + *
24.8 + * Copyright (C) 2003-2008
24.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
24.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
24.11 + *
24.12 + * Permission to use, modify and distribute this software is granted
24.13 + * provided that this copyright notice appears in all copies. For
24.14 + * precise terms see the accompanying LICENSE file.
24.15 + *
24.16 + * This software is provided "AS IS" with no warranty of any kind,
24.17 + * express or implied, and with no claim as to its suitability for any
24.18 + * purpose.
24.19 + *
24.20 + */
24.21 +
24.22 +#include "test_tools.h"
24.23 +
24.24 +
24.25 +#ifdef HAVE_CONFIG_H
24.26 +#include <lemon/config.h>
24.27 +#endif
24.28 +
24.29 +#ifdef HAVE_CPLEX
24.30 +#include <lemon/mip_cplex.h>
24.31 +#endif
24.32 +
24.33 +#ifdef HAVE_GLPK
24.34 +#include <lemon/mip_glpk.h>
24.35 +#endif
24.36 +
24.37 +
24.38 +using namespace lemon;
24.39 +
24.40 +void solveAndCheck(MipSolverBase& lp, MipSolverBase::SolutionStatus stat,
24.41 + double exp_opt) {
24.42 + using std::string;
24.43 +
24.44 + lp.solve();
24.45 + //int decimal,sign;
24.46 + std::ostringstream buf;
24.47 + buf << "Primalstatus should be: " << int(stat)
24.48 + <<" and it is "<<int(lp.mipStatus());
24.49 +
24.50 +
24.51 + // itoa(stat,buf1, 10);
24.52 + check(lp.mipStatus()==stat, buf.str());
24.53 +
24.54 + if (stat == MipSolverBase::OPTIMAL) {
24.55 + std::ostringstream sbuf;
24.56 + buf << "Wrong optimal value: the right optimum is " << exp_opt;
24.57 + check(std::abs(lp.primalValue()-exp_opt) < 1e-3, sbuf.str());
24.58 + //+ecvt(exp_opt,2)
24.59 + }
24.60 +}
24.61 +
24.62 +void aTest(MipSolverBase& mip)
24.63 +{
24.64 + //The following example is very simple
24.65 +
24.66 +
24.67 + typedef MipSolverBase::Row Row;
24.68 + typedef MipSolverBase::Col Col;
24.69 +
24.70 +
24.71 +
24.72 + Col x1 = mip.addCol();
24.73 + Col x2 = mip.addCol();
24.74 +
24.75 +
24.76 + //Objective function
24.77 + mip.obj(x1);
24.78 +
24.79 + mip.max();
24.80 +
24.81 +
24.82 + //Unconstrained optimization
24.83 + mip.solve();
24.84 + //Check it out!
24.85 +
24.86 + //Constraints
24.87 + mip.addRow(2*x1+x2 <=2);
24.88 + mip.addRow(x1-2*x2 <=0);
24.89 +
24.90 + //Nonnegativity of the variable x1
24.91 + mip.colLowerBound(x1, 0);
24.92 +
24.93 + //Maximization of x1
24.94 + //over the triangle with vertices (0,0),(4/5,2/5),(0,2)
24.95 + double expected_opt=4.0/5.0;
24.96 + solveAndCheck(mip, MipSolverBase::OPTIMAL, expected_opt);
24.97 +
24.98 + //Restrict x2 to integer
24.99 + mip.colType(x2,MipSolverBase::INT);
24.100 + expected_opt=1.0/2.0;
24.101 + solveAndCheck(mip, MipSolverBase::OPTIMAL, expected_opt);
24.102 +
24.103 +
24.104 + //Restrict both to integer
24.105 + mip.colType(x1,MipSolverBase::INT);
24.106 + expected_opt=0;
24.107 + solveAndCheck(mip, MipSolverBase::OPTIMAL, expected_opt);
24.108 +
24.109 +
24.110 +
24.111 +}
24.112 +
24.113 +
24.114 +int main()
24.115 +{
24.116 +
24.117 +#ifdef HAVE_GLPK
24.118 + MipGlpk mip1;
24.119 + aTest(mip1);
24.120 +#endif
24.121 +
24.122 +#ifdef HAVE_CPLEX
24.123 + MipCplex mip2;
24.124 + aTest(mip2);
24.125 +#endif
24.126 +
24.127 + return 0;
24.128 +
24.129 +}