# HG changeset patch # User athos # Date 1153126821 0 # Node ID cd8897f67c2641b31234de88752a21235d73b335 # Parent 4b3191b4970bab937996707c4cbc744b85acffdb MIP support added (by Jano, the Great). diff -r 4b3191b4970b -r cd8897f67c26 lemon/Makefile.am --- a/lemon/Makefile.am Mon Jul 17 07:30:56 2006 +0000 +++ b/lemon/Makefile.am Mon Jul 17 09:00:21 2006 +0000 @@ -19,6 +19,7 @@ if HAVE_GLPK lemon_libemon_la_SOURCES += lemon/lp_glpk.cc +lemon_libemon_la_SOURCES += lemon/mip_glpk.cc endif if HAVE_CPLEX diff -r 4b3191b4970b -r cd8897f67c26 lemon/lp.h --- a/lemon/lp.h Mon Jul 17 07:30:56 2006 +0000 +++ b/lemon/lp.h Mon Jul 17 09:00:21 2006 +0000 @@ -23,6 +23,7 @@ #ifdef HAVE_GLPK #include +#include #elif HAVE_CPLEX #include #endif @@ -54,10 +55,19 @@ /// ///Currently, the possible values are "GLPK" or "CPLEX" const char default_solver_name[]="SOLVER"; + + ///The default ILP solver. + + ///The default ILP solver. + ///\ingroup gen_opt_group + /// + ///Currently, it is either \c LpGlpk or \c LpCplex + typedef MipGlpk Mip; #else #ifdef HAVE_GLPK #define DEFAULT_LP GLPK typedef LpGlpk Lp; + typedef MipGlpk Mip; const char default_solver_name[]="GLPK"; #elif HAVE_CPLEX #define DEFAULT_LP CPLEX diff -r 4b3191b4970b -r cd8897f67c26 lemon/lp_base.h --- a/lemon/lp_base.h Mon Jul 17 07:30:56 2006 +0000 +++ b/lemon/lp_base.h Mon Jul 17 09:00:21 2006 +0000 @@ -175,6 +175,7 @@ protected: int id; friend class LpSolverBase; + friend class MipSolverBase; public: typedef Value ExprValue; typedef True LpSolverCol; @@ -1156,7 +1157,33 @@ }; - ///\e + + ///Common base class for ILP solvers + ///\todo Much more docs + ///\ingroup gen_opt_group + class MipSolverBase : virtual public LpSolverBase{ + public: + + ///Set the type of the given Col to integer or remove that property. + /// + ///Set the type of the given Col to integer or remove that property. + void integer(Col c, bool enable) { + _integer(cols.floatingId(c.id),enable); + } + + ///Gives back the type of the column. + /// + ///Gives back the type of the column. + ///\return true if the column has integer type and false if not. + bool integer(Col c){ + return _integer(cols.floatingId(c.id)); + } + + protected: + + virtual bool _integer(int col) = 0; + virtual void _integer(int col, bool enable) = 0; + }; ///\relates LpSolverBase::Expr /// diff -r 4b3191b4970b -r cd8897f67c26 lemon/lp_glpk.h --- a/lemon/lp_glpk.h Mon Jul 17 07:30:56 2006 +0000 +++ b/lemon/lp_glpk.h Mon Jul 17 09:00:21 2006 +0000 @@ -35,7 +35,7 @@ /// /// This class implements an interface for the GLPK LP solver. ///\ingroup gen_opt_group - class LpGlpk : public LpSolverBase { + class LpGlpk : virtual public LpSolverBase { protected: LPX* lp; diff -r 4b3191b4970b -r cd8897f67c26 lemon/mip_glpk.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/mip_glpk.cc Mon Jul 17 09:00:21 2006 +0000 @@ -0,0 +1,72 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2006 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_ILP_GLPK_CC +#define LEMON_ILP_GLPK_CC + +///\file +///\brief Implementation of the LEMON-GLPK lp solver interface. + +#include + +namespace lemon { + + MipGlpk::MipGlpk() { + lpx_set_class(lp,LPX_MIP); + } + + void MipGlpk::_integer(int i, bool enable){ + if(enable){ + lpx_set_col_kind(lp,i,LPX_IV); + }else{ + lpx_set_col_kind(lp,i,LPX_CV); + } + } + + bool MipGlpk::_integer(int i){ + if(LPX_IV == lpx_get_col_kind(lp,i)){ + return true; + } + return false; + } + + LpGlpk::SolveExitStatus MipGlpk::_solve(){ + int result = lpx_simplex(lp); + result = lpx_integer(lp); + switch (result){ + case LPX_E_OBJLL: + case LPX_E_OBJUL: + case LPX_E_ITLIM: + case LPX_E_TMLIM: + case LPX_E_OK: + return SOLVED; + default: + return UNSOLVED; + } + } + + MipGlpk::Value MipGlpk::_getPrimal(int i){ + return lpx_mip_col_val(lp,i); + } + + MipGlpk::Value MipGlpk::_getPrimalValue(){ + return lpx_mip_obj_val(lp); + } +} //END OG NAMESPACE LEMON + +#endif diff -r 4b3191b4970b -r cd8897f67c26 lemon/mip_glpk.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/mip_glpk.h Mon Jul 17 09:00:21 2006 +0000 @@ -0,0 +1,58 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2006 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_ILP_GLPK_H +#define LEMON_ILP_GLPK_H + +///\file +///\brief Header of the LEMON-GLPK lp solver interface. +///\ingroup gen_opt_group + + +#include + +namespace lemon { + /// \brief Interface for the GLPK ILP solver + /// + /// This class implements an interface for the GLPK ILP solver. + ///\ingroup gen_opt_group + class MipGlpk : public MipSolverBase, public LpGlpk{ + + public: + + typedef MipSolverBase ParentMip; + typedef LpGlpk ParentLp; + + MipGlpk(); + //~MipGlpk(); + + + + protected: + + virtual void _integer(int c, bool enable); + virtual bool _integer(int c); + + virtual LpGlpk::SolveExitStatus _solve(); + virtual ParentLp::Value _getPrimal(int i); + virtual ParentLp::Value _getPrimalValue(); + }; + +} //END OF NAMESPACE LEMON + +#endif // END OF LEMON_ILP_GLPK_H diff -r 4b3191b4970b -r cd8897f67c26 test/Makefile.am --- a/test/Makefile.am Mon Jul 17 07:30:56 2006 +0000 +++ b/test/Makefile.am Mon Jul 17 09:00:21 2006 +0000 @@ -28,6 +28,7 @@ test/matrix_maps_test \ test/max_matching_test \ test/min_cost_flow_test \ + test/mip_test \ test/path_test \ test/polynomial_test \ test/preflow_test \ @@ -70,6 +71,7 @@ test_matrix_maps_test_SOURCES = test/matrix_maps_test.cc test_max_matching_test_SOURCES = test/max_matching_test.cc test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc +test_mip_test_SOURCES = test/mip_test.cc test_path_test_SOURCES = test/path_test.cc test_polynomial_test_SOURCES = test/polynomial_test.cc test_preflow_test_SOURCES = test/preflow_test.cc diff -r 4b3191b4970b -r cd8897f67c26 test/mip_test.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/mip_test.cc Mon Jul 17 09:00:21 2006 +0000 @@ -0,0 +1,50 @@ +#include +//#include + +using namespace lemon; + +int main(){ + + //MipGlpk ilp; + + Mip ilp; + + + typedef Mip::Row Row; + typedef Mip::Col Col; + + ilp.max(); + + Col x1 = ilp.addCol(); + Col x2 = ilp.addCol(); + Col x3 = ilp.addCol(); + + ilp.integer(x1,true); + ilp.integer(x2,true); + ilp.integer(x3,true); + + ilp.addRow(x1+x2+x3 <=100); + ilp.addRow(10*x1+4*x2+5*x3<=600); + ilp.addRow(2*x1+2*x2+6*x3<=300); + + ilp.colLowerBound(x1, 0); + ilp.colLowerBound(x2, 0); + ilp.colLowerBound(x3, 0); + //Objective function + ilp.setObj(10*x1+6*x2+4*x3); + + //Call the routine of the underlying LP solver + ilp.solve(); + + //Print results + if (ilp.primalStatus()==LpSolverBase::OPTIMAL){ + std::cout<<"Optimal solution found!"<