max.cc

#ifndef SCIL_MAX_CC
#define SCIL_MAX_CC

#include<scil/scil.h>
#include <scil/variable.h>
#include<scil/constraints/max.h>
#include <map>
#include <list>
#include <queue>

#include<iostream>
#include<cstdarg>

#define LEPS 1e-4

//FIXME
//#define NO_MAX_SEPARATION

using namespace SCIL;
using std::cout;
using std::cerr;
using std::endl;
using std::pair;

/* (reverse-)Comparator for std::pair<double,var>. 
   Comparation is given by:  (x1,x2) < (y1,y2) iff x1 < y1 */
struct paircomp {
  bool operator() (const pair<double,var>& p1, const pair<double,var>& p2) const
  {
    return p1.first > p2.first;
  }
};

namespace SCIL {
MAX::MAX(var v_, var_map<int>& VM_, std::map<var, double>& CF_, int n_, bool geq_)
   : v(v_), VM(VM_), CF(CF_), n(n_), geq(geq_){
      priority_queue< std::pair<double,var>, vector<std::pair<double,var> >, paircomp> QQ;
      
      for( int i = 0; i < n; i++ ) {
         QQ.push(pair<double,var>(CF[VM[i]], VM[i]));
      }

      for( int i = 0; i < n; i++ ) {
         VM[i] = QQ.top().second;
         QQ.pop();
      }

      mc = CF[VM[n - 1]];

   };
}


void MAX::init(subproblem& S) {
   if(S.configuration("MAX_Debug_Out")=="true")
      cerr << "MAX::init\n";

#ifndef NO_MAX_SEPARATION
    /* trivial facets (largest entry always one)*/
   for( int i = 0; i < n - 1; i++ ) {
      row r;
      r += VM[i] * CF[VM[i]];
      r += VM[n-1] * (CF[VM[n-1]] - CF[VM[i]]);
      r -= v;
      S.add_basic_constraint(r<=0., Static);
   }
   row r;
   r += VM[n-1] * CF[VM[n-1]];
   r -= v;
   S.add_basic_constraint(r<=0., Static);
   return;
#else
#if 0
   for( int i = 0; i < n; i++ ) {
      row r;
      r += VM[i] * CF[VM[i]];
      r -= v;
      S.add_basic_constraint(r<=0., Static);
   }
#endif
   return;
#endif
};


MAX::status MAX::feasible(solution& S) {
   if(S.originating_subproblem()->configuration("MAX_Debug_Out")=="true")
      cerr << "MAX::feasible\n";

   //FIXME
   //return feasible_solution;

   double m = CF[VM[0]] * S.value(VM[0]);
   double t;
   for( int i = 1; i < n; i++ ) {
      t = CF[VM[i]] * S.value(VM[i]);
      if( t >= m )
         m = t;
   }

   bool feas = false;

   if( geq && (m < S.value(v) + LEPS) ) {
      feas = true;
   }
   else if( !geq && (fabs(m - S.value(v)) < LEPS) )
      feas = true;


   return feas ? feasible_solution : infeasible_solution;
}

MAX::status MAX::standard_separation(subproblem& S) {
   if(S.configuration("MAX_Debug_Out")=="true")
      cerr << "MAX::standard_separation\n";

#ifdef NO_MAX_SEPARATION
   return no_constraint_found;
#endif//NO_MAX_SEPARATION

   std::list< pair<double, int> > lQ;
   for( int i = 0; i < n; i++ ) {
      lQ.push_back( pair<double, int> (S.value(VM[i]), i));
   }

   lQ.sort();

   int st = -1;
   double s = 0.;
   double m = 0.;
   double l = 0.;
   row r;
   do {
      if( (lQ.back()).second < st ) {
         lQ.pop_back();
         continue;
      }
      st = lQ.back().second;
      lQ.pop_back();

      //FIXME
      s = CF[VM[st]] - m;
      /*
      if( mc - m < s ) {
         s = mc - m;
      }
      */

      r += VM[st] * s;
      l += S.value(VM[st]) * s;
      m += s;
   } while( !lQ.empty() );
   //} while( st != n - 1 );
  // } while( st != n - 1 && m + LEPS < mc );

   if( l > S.value(v) + LEPS ) {
      r -= v;
      S.add_basic_constraint(r <= 0.);
      if(S.configuration("MAX_Debug_Out")=="true")
         cerr << "MAX::standard_separation: constraint added\n";
      return constraint_found;
   }
   return no_constraint_found;
}

void MAX::info() {
   cout<<"Configurations:\n";
   cout<<"MAX_Debug_Out [true|false]\n";
}
#endif

---