00001 #include<scil/constraints/submodular.h>
00002 #include<list>
00003
00004 using namespace SCIL;
00005
00006 submodular::status submodular::standard_separation(subproblem& S) {
00007 std::list< pair<double,int> > lQ;
00008 for( int i=0; i<n; i++ )
00009 lQ.push_back( make_pair<double,int>(S.value(VM[i]),i) );
00010
00011 lQ.sort();
00012
00013 int st;
00014 row r;
00015 double a;
00016 double lhs = 0.;
00017 double oldval = value();
00018 double val;
00019 for( int i=0; i<n; i++ ){
00020 st = (lQ.back()).second;
00021 lQ.pop_back();
00022 val = value(st);
00023 a = val - oldval;
00024 if( fabs(a) > feps ) {
00025 r += VM[st] * a;
00026 lhs += a * S.value(VM[st]);
00027 }
00028 oldval = val;
00029 }
00030 if( lhs > S.value(v) + .01 ) {
00031 r -= v;
00032 S.add_basic_constraint(r<=0.);
00033 return constraint_found;
00034 }
00035 return no_constraint_found;
00036 }
