1.1 --- a/src/work/marci/lp/lp_solver_base.h	Wed Feb 16 21:40:16 2005 +0000
     1.2 +++ b/src/work/marci/lp/lp_solver_base.h	Thu Feb 17 15:14:13 2005 +0000
     1.3 @@ -619,6 +619,8 @@
     1.4      virtual void _setColCont(int i) = 0;
     1.5      /// \e
     1.6      virtual void _setColInt(int i) = 0;
     1.7 +    /// \e
     1.8 +    virtual _Value _getMIPPrimal(int i) = 0;
     1.9    public:
    1.10      /// \e
    1.11      void setColCont(Col col) {
    1.12 @@ -628,6 +630,10 @@
    1.13      void setColInt(Col col) {
    1.14        _setColInt(col_iter_map[col]);
    1.15      }
    1.16 +    /// \e
    1.17 +    _Value getMIPPrimal(Col col) {
    1.18 +      return _getMIPPrimal(col_iter_map[col]);
    1.19 +    }
    1.20      //@}
    1.21    };
    1.22    
    1.23 @@ -1096,9 +1102,11 @@
    1.24      void setMIP() { lpx_set_class(lp, LPX_MIP); }
    1.25    protected:
    1.26      /// \e
    1.27 -    void _setColCont(int i) {lpx_set_col_kind(lp, i, LPX_CV); }
    1.28 +    void _setColCont(int i) { lpx_set_col_kind(lp, i, LPX_CV); }
    1.29      /// \e
    1.30 -    void _setColInt(int i) {lpx_set_col_kind(lp, i, LPX_IV); }
    1.31 +    void _setColInt(int i) { lpx_set_col_kind(lp, i, LPX_IV); }
    1.32 +    /// \e
    1.33 +    double _getMIPPrimal(int i) { return lpx_mip_col_val(lp, i); }
    1.34    };
    1.35    
    1.36    /// @}

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/work/marci/lp/magic_square.cc	Thu Feb 17 15:14:13 2005 +0000
     2.3 @@ -0,0 +1,88 @@
     2.4 +// -*- c++ -*-
     2.5 +#include <iostream>
     2.6 +#include <fstream>
     2.7 +
     2.8 +#include <lemon/time_measure.h>
     2.9 +#include <lp_solver_base.h>
    2.10 +
    2.11 +using std::cout;
    2.12 +using std::endl;
    2.13 +using namespace lemon;
    2.14 +
    2.15 +/*
    2.16 +  for n=3,4 , the program is very fast
    2.17 +  for n=5, with glpk, the run takes hours
    2.18 + */
    2.19 +
    2.20 +int main(int, char **) {
    2.21 +  const int n=4;
    2.22 +  const double row_sum=(1.0+n*n)*n/2;
    2.23 +  Timer ts;
    2.24 +  ts.reset();
    2.25 +  typedef LPGLPK LPSolver;
    2.26 +  typedef LPSolver::Col Col;
    2.27 +  LPSolver lp;
    2.28 +  typedef std::map<std::pair<int, int>, Col> Coords;
    2.29 +  Coords x;
    2.30 +  // we create a new variable for each entry 
    2.31 +  // of the magic square
    2.32 +  for (int i=1; i<=n; ++i) {
    2.33 +    for (int j=1; j<=n; ++j) { 
    2.34 +      Col col=lp.addCol();
    2.35 +      x[std::make_pair(i,j)]=col;
    2.36 +      lp.setColLowerBound(col, 1.0);
    2.37 +      lp.setColUpperBound(col, double(n*n));
    2.38 +    }
    2.39 +  }
    2.40 +  LPSolver::Expression expr3, expr4;
    2.41 +  for (int i=1; i<=n; ++i) {
    2.42 +    LPSolver::Expression expr1, expr2;
    2.43 +    for (int j=1; j<=n; ++j) {
    2.44 +      expr1+=x[std::make_pair(i, j)];
    2.45 +      expr2+=x[std::make_pair(j, i)];
    2.46 +    }
    2.47 +    // sum of rows and columns
    2.48 +    lp.addRow(expr1==row_sum);
    2.49 +    lp.addRow(expr2==row_sum);
    2.50 +    expr3+=x[std::make_pair(i, i)];
    2.51 +    expr4+=x[std::make_pair(i, (n+1)-i)];
    2.52 +  }
    2.53 +  // sum of the diagonal entries
    2.54 +  lp.addRow(expr3==row_sum);
    2.55 +  lp.addRow(expr4==row_sum);
    2.56 +  lp.solveSimplex();
    2.57 +  cout << "elapsed time: " << ts << endl;
    2.58 +  for (int i=1; i<=n; ++i) {
    2.59 +    for (int j=1; j<=n; ++j) { 
    2.60 +      cout << "x("<<i<<","<<j<<")="<<lp.getPrimal(x[std::make_pair(i,j)]) 
    2.61 +	   << endl;
    2.62 +    }
    2.63 +  }
    2.64 +  // we make new binary variables for each pair of 
    2.65 +  // entries of the square to achieve that 
    2.66 +  // the values of different entries are different
    2.67 +  lp.setMIP();
    2.68 +  for (Coords::const_iterator it=x.begin(); it!=x.end(); ++it) {
    2.69 +    Coords::const_iterator jt=it; ++jt;
    2.70 +    for(; jt!=x.end(); ++jt) {
    2.71 +      Col col1=(*it).second;
    2.72 +      Col col2=(*jt).second;
    2.73 +      Col col=lp.addCol();
    2.74 +      lp.setColLowerBound(col, 0.0);
    2.75 +      lp.setColUpperBound(col, 1.0);
    2.76 +      lp.addRow(double(-n*n+1.0)<=1.0*col2-1.0*col1-double(n*n)*col<=-1.0);
    2.77 +      lp.setColInt(col);
    2.78 +    }
    2.79 +  }
    2.80 +  cout << "elapsed time: " << ts << endl;
    2.81 +  lp.solveSimplex();
    2.82 +  // let's solve the integer problem
    2.83 +  lp.solveBandB();
    2.84 +  cout << "elapsed time: " << ts << endl;
    2.85 +  for (int i=1; i<=n; ++i) {
    2.86 +    for (int j=1; j<=n; ++j) { 
    2.87 +      cout << "x("<<i<<","<<j<<")="<<lp.getMIPPrimal(x[std::make_pair(i,j)]) 
    2.88 +	   << endl;
    2.89 +    }
    2.90 +  }
    2.91 +}

     3.1 --- a/src/work/marci/lp/makefile	Wed Feb 16 21:40:16 2005 +0000
     3.2 +++ b/src/work/marci/lp/makefile	Thu Feb 17 15:14:13 2005 +0000
     3.3 @@ -5,7 +5,7 @@
     3.4  CXXFLAGS = -g -O2 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
     3.5  LDFLAGS  =  -lglpk#-lcplex -lm -lpthread -lilocplex -L/usr/local/cplex/cplex75/lib/i86_linux2_glibc2.2_gcc3.0/static_mt# -L$(GLPKROOT)/lib
     3.6  
     3.7 -BINARIES = max_flow_expression expression_test max_flow_by_lp# sample sample2 sample11 sample15
     3.8 +BINARIES = magic_square max_flow_expression expression_test max_flow_by_lp# sample sample2 sample11 sample15
     3.9  
    3.10  #include ../makefile
    3.11