1.1 --- a/src/work/athos/lp_old/magic_square.cc Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,99 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#include <iostream>
1.6 -#include <fstream>
1.7 -
1.8 -#include <lemon/time_measure.h>
1.9 -#include <lp_solver_glpk.h>
1.10 -
1.11 -using std::cout;
1.12 -using std::endl;
1.13 -using namespace lemon;
1.14 -
1.15 -/*
1.16 - On an 1537Mhz PC, the run times with
1.17 - glpk are the following.
1.18 - for n=3,4, some secondes
1.19 - for n=5, 25 hours
1.20 - */
1.21 -
1.22 -int main(int, char **) {
1.23 - const int n=3;
1.24 - const double row_sum=(1.0+n*n)*n/2;
1.25 - Timer ts;
1.26 - ts.reset();
1.27 - typedef LpGlpk LPSolver;
1.28 - typedef LPSolver::Col Col;
1.29 - LPSolver lp;
1.30 - typedef std::map<std::pair<int, int>, Col> Coords;
1.31 - Coords x;
1.32 - // we create a new variable for each entry
1.33 - // of the magic square
1.34 - for (int i=1; i<=n; ++i) {
1.35 - for (int j=1; j<=n; ++j) {
1.36 - Col col=lp.addCol();
1.37 - x[std::make_pair(i,j)]=col;
1.38 - lp.setColLowerBound(col, 1.0);
1.39 - lp.setColUpperBound(col, double(n*n));
1.40 - }
1.41 - }
1.42 - LPSolver::Expression expr3, expr4;
1.43 - for (int i=1; i<=n; ++i) {
1.44 - LPSolver::Expression expr1, expr2;
1.45 - for (int j=1; j<=n; ++j) {
1.46 - expr1+=x[std::make_pair(i, j)];
1.47 - expr2+=x[std::make_pair(j, i)];
1.48 - }
1.49 -
1.50 - // sum of rows and columns
1.51 - lp.addRow(expr1==row_sum);
1.52 - lp.addRow(expr2==row_sum);
1.53 - cout <<"Expr1: "<<expr1<<endl;
1.54 - cout <<"Expr2: "<<expr2<<endl;
1.55 -
1.56 - expr3+=x[std::make_pair(i, i)];
1.57 - expr4+=x[std::make_pair(i, (n+1)-i)];
1.58 - }
1.59 - cout <<"Expr3: "<<expr3<<endl;
1.60 - cout <<"Expr4: "<<expr4<<endl;
1.61 - // sum of the diagonal entries
1.62 - lp.addRow(expr3==row_sum);
1.63 - lp.addRow(expr4==row_sum);
1.64 - lp.solveSimplex();
1.65 - cout << "elapsed time: " << ts << endl;
1.66 - for (int i=1; i<=n; ++i) {
1.67 - for (int j=1; j<=n; ++j) {
1.68 - cout << "x("<<i<<","<<j<<")="<<lp.getPrimal(x[std::make_pair(i,j)])
1.69 - << endl;
1.70 - }
1.71 - }
1.72 -
1.73 -
1.74 -
1.75 -// // we make new binary variables for each pair of
1.76 -// // entries of the square to achieve that
1.77 -// // the values of different entries are different
1.78 -// lp.setMIP();
1.79 -// for (Coords::const_iterator it=x.begin(); it!=x.end(); ++it) {
1.80 -// Coords::const_iterator jt=it; ++jt;
1.81 -// for(; jt!=x.end(); ++jt) {
1.82 -// Col col1=(*it).second;
1.83 -// Col col2=(*jt).second;
1.84 -// Col col=lp.addCol();
1.85 -// lp.setColLowerBound(col, 0.0);
1.86 -// lp.setColUpperBound(col, 1.0);
1.87 -// lp.addRow(double(-n*n+1.0)<=1.0*col2-1.0*col1-double(n*n)*col<=-1.0);
1.88 -// lp.setColInt(col);
1.89 -// }
1.90 -// }
1.91 -// cout << "elapsed time: " << ts << endl;
1.92 -// lp.solveSimplex();
1.93 -// // let's solve the integer problem
1.94 -// lp.solveBandB();
1.95 -// cout << "elapsed time: " << ts << endl;
1.96 -// for (int i=1; i<=n; ++i) {
1.97 -// for (int j=1; j<=n; ++j) {
1.98 -// cout << "x("<<i<<","<<j<<")="<<lp.getMIPPrimal(x[std::make_pair(i,j)])
1.99 -// << endl;
1.100 -// }
1.101 -// }
1.102 -}