# 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 <lemon/lp_glpk.h>
+#include <lemon/mip_glpk.h>
#elif HAVE_CPLEX
#include <lemon/lp_cplex.h>
#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 <lemon/mip_glpk.h>
+
+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 <lemon/lp_glpk.h>
+
+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 <lemon/lp.h>
+//#include <lemon/ilp_glpk.h>
+
+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!"<<std::endl;
+ printf("optimum value = %g; x1 = %g; x2 = %g; x3 = %g\n",
+ ilp.primalValue(),
+ ilp.primal(x1), ilp.primal(x2), ilp.primal(x3));
+ }
+ else{
+ std::cout<<"Optimal solution not found!"<<std::endl;
+ }
+
+}