subproblem.cc

#include<scil/global.h>
#include<scil/cons.h>
#include<scil/cons_obj.h>
#include<scil/var_obj.h>
#include<scil/subproblem.h>
#include<scil/aba_constraint.h>
#include<scil/aba_variable.h>
#include<scil/sym_constraint.h>
#include<scil/ilp_problem.h>
#include<scil/primal_heur.h>
#include<scil/row.h>
#include<scil/solution.h>
#include<scil/constraints/quadref.h>
//FIXME prio
#include<abacus/setbranchrule.h>

using namespace SCIL;

void subproblem::add_sym_constraint (sym_constraint * c)
{
  sym_constraints.push_back (c);
}

const
std::string subproblem::configuration(const std::string& s) const {
  return GM.configuration(s);
};

void subproblem::configuration(const std::string& s1, const std::string& s2) {
   GM.configuration(s1, s2);
   return;
};

cons
subproblem::add_basic_constraint (cons_obj * c, Activation a, Validity v)
{
  //check if the objective function is not linear and if sqk2 option is activated
  if(GM.monomialinstance != NULL && (GM.get_qr_on_separate() || master_->nLp() == 1)){
    cons_obj* cons = NULL;
    //check for reformulation (if no new variables have to be added -> reformulate)
    switch (c->get_qrStatus()){
         //TODO Column Generation
         /*case SQK2:
            cons = GM.qr->reformulate_SQK2(c, false);
            break;
         case SQK3:
            GM.qr->reformulate_SQK3(c, false);
            break;
         case SQK2_SQK3:
            cons = GM.qr->reformulate_SQK2(c, false);
            GM.qr->reformulate_SQK3(c, false);
            break;*/
         case CHECK:
            switch (GM.get_qrType()){
            case SQK2:
               cons = GM.qr->reformulate_SQK2(c, false);
               break;
            case SQK3:
               GM.qr->reformulate_SQK3(c, false);
               break;
            case SQK2_SQK3:
               cons = GM.qr->reformulate_SQK2(c, false);
               GM.qr->reformulate_SQK3(c, false);
               break;
            default:
               break;
            }
            break;
         default:
            break;
      }
    if(cons != NULL)
       _add_basic_constraint (cons, a, v);
  }
  return _add_basic_constraint (c, a, v);
};

cons
subproblem::_add_basic_constraint (cons_obj * c, Activation a, Validity v)
{
  c->init (*this, GM.number_of_constraints(), a, v);
  GM.nconss++;
  ABA_BUFFER< ABA_CONSTRAINT * > constraint (master_, 1);
  constraint.push(c->Acons());
  addCons(constraint);
  return c;
};

cons
subproblem::add_basic_constraint (cons_sense s, double rhs,
                                  Activation a, Validity v)
{
  cons_obj *
    c = new cons_obj (s, rhs);
  add_basic_constraint (c, a, v);
  return c;
};

var subproblem::add_binary_variable (double obj, Activation a)
{
   return add_variable(obj, 0, 1, Vartype_Binary, a);
};

var
subproblem::add_variable (double obj,
                          double lBound, double uBound,
                          Vartype t, Activation a)
{
   var v;

   if (initpricing == false)
   {
      v = new var_obj (obj, lBound, uBound, t);
      add_variable (v, a);
   }
   else
   {
      if (newvarbuffer->size () == newvarbuffer->number ())
         newvarbuffer->realloc (newvarbuffer->size () * 2);
      v = new var_obj (obj, lBound, uBound, t);
      v.var_pointer ()->init (*this, GM.nvars, a);
      newvarbuffer->push (v.Avar_pointer ());
      GM.nvars++;
   }
   return v;
};

void
subproblem::add_variable (var v, Activation a)
{
  v.var_pointer ()->init (*this, GM.nvars, a);
  if (v.var_pointer () != nil)
    {
      GM.nvars++;  // function machen und friend entfernen?
      ABA_BUFFER < ABA_VARIABLE * >p (master_, 1);
      p.push (v.Avar_pointer ());
      if (addVars (p) == 0)
         cout << "Variable not added\n";
    }
}

subproblem::subproblem (ABA_MASTER * master):ABA_SUB (master, 0, 0, 0),
GM (*(ILP_Problem *) master_)
{
  //FIXME prio
  prio = 0;
  initpricing = false;
  newvarbuffer= new ABA_BUFFER < ABA_VARIABLE * >(master_,8);
};

subproblem::subproblem (ABA_MASTER * master, ABA_SUB * father,
ABA_BRANCHRULE * branchRule):ABA_SUB (master, father, branchRule),
GM (*(ILP_Problem *) master_)
{
  //FIXME prio
  prio = 0;
  initpricing = false;
  newvarbuffer=new ABA_BUFFER < ABA_VARIABLE * >(master_,8);
};

bool
subproblem::feasible ()
{
  //cout << master_->nLp () << " LPs\n";
  if (master_->nLp () == 1)
    return false;

  //  if(!integerFeasible()) return false;
  solution S;
  S.save_solution(*this);
  for (int i = 0; i < nVar (); i++)
    if (get_var (i).Avar_pointer ()->varType () != ABA_VARTYPE::Continuous)
      {
        if (fabs (xVal (i) - floor (xVal (i) + 0.5)) > GM.machineEps())
          {
            return false;
          }
        S.round_to_integer(get_var(i));
      };
  //cout << "integer Feasible\n";

  update_indices ();
  if (!feasible (*this, S))
    return false;

  GM.updateBestSolution (S);

  return true;
}

bool
subproblem::feasible (subproblem & S, solution& Sol)
{

  std::list<sym_constraint*>::const_iterator s;
  foreach (s, sym_constraints)
  {
    if ((*s)->feasible (Sol) == sym_constraint::infeasible_solution)
      return false;
  }

  if (father () != 0)
    {
      if (!((subproblem *) father ())->feasible (S, Sol))
        return false;
    }

  return true;
};

void
subproblem::update_indices ()
{
  //if(updateLP==nLP()) return;

  //updateLP=nLp();

  for (int i = 0; i < nVar (); i++)
    {
      get_var (i).var_pointer ()->vi = i;
    }

  for (int i = 0; i < nCon (); i++)
    {
      ((ABA_Constraint *) constraint (i))->ii = i;
    }
};

int
subproblem::separate ()
{
  if (master_->nLp () == 1)
    {
      std::list<sym_constraint*>::iterator c;
      foreach (c, sym_constraints) (*c)->init (*this);

      add_basic_constraint((row) 0 <= 0);

      return 1;
    }

  update_indices ();
  return separate (*this);
};

int
subproblem::separate (subproblem & S)
{
  //int
  t = 0;

  sym_constraint_iterator s;
  sym_constraint::status rs;
  foreach (s, sym_constraints) if(t!=-1)
  {
    rs=(*s)->standard_separation(S);
    if (rs == sym_constraint::constraint_found) t++;
    if (rs == sym_constraint::fathom) t=-1;
  };

  int l;
  if ((father () != 0) && (t!=-1))
    {
      l = ((subproblem *) father ())->separate (S);
      if(l==-1) return -1; else t+=l;
    }

  if(t==-1) {
    t=1; add_basic_constraint((row) get_var(0) <= -1);
  };
  //cout<<t<<" Cosntraints\n";
  return t;
};

int
subproblem::pricing ()
{
  update_indices ();
  int
    i;
  if (lp ()->infeasible ())
    {
      i = mf_pricing (*this);
    }
  else
    {
      i = pricing (*this);
    }
  cout << i << " Vars added\n";
  return i;
};

int
subproblem::mf_pricing (subproblem & S)
{
  int
    counter = 0;

  sym_constraint_iterator p;
  foreach (p, sym_constraints)
  {
    if ((*p)->mf_pricing (S) == sym_constraint::variable_found)
      counter++;
  }

  if (father () != 0)
    {
      counter += ((subproblem *) father ())->mf_pricing (S);
    }
  //cout<<counter<<" Vars added"<<endl;
  return counter;
};

int
subproblem::pricing (subproblem & S)
{
  int
    counter = 0;

  sym_constraint_iterator p;
  foreach (p, sym_constraints)
  {
    if ((*p)->LP_pricing (S) == sym_constraint::variable_found)
      counter++;
  }

  if (father () != 0)
    {
      counter += ((subproblem *) father ())->pricing (S);
    }
  //cout<<counter<<" Vars added"<<endl;
  return counter;
};


void subproblem::remove_variable (var V)
{
  /*{\Mop removes a variable for the linear program of the 
    current node.} */
    removeVar (V.var_pointer ()->index ());
};


double subproblem::get_coeff (var v, cons i)
{
  return v.var_pointer ()->coeff (i.cons_pointer ()->Acons ()) +
    i.cons_pointer ()->coeff (v.var_pointer ());
    // This is unsymmetric, since set_coefficient is stored in both
}


void subproblem::set_coefficient (var v, cons i, double d)
{
  /*{\Mop sets the coefficient for variable $v$ and basic constraint $i$
    to $d$ in the LP-Matrix.} */
    v.var_pointer ()->set (i.cons_pointer (), d);
    i.cons_pointer ()->set (v.var_pointer (), d);
};



var subproblem::get_var (int i)
{
  /*{\Mop {\bf better give the possibility to iterate over the variables!}} */
  if(i>=nVar()) return nil;
  return var (((ABA_Variable *) ABA_SUB::variable (i))->SVar ());
};

int subproblem::nVar () const
{
  /*{\Mop returns the number of active variables in the current node.} */
  return ABA_SUB::nVar ();
};

cons subproblem::get_cons (int i)
{
  /*{\Mop {\bf better give the possibility to iterate over the basic
    constraints!}} */
  if(i>=nCon()) return nil;
  return cons (((ABA_Constraint *) ABA_SUB::constraint (i))->Scons ());
};

int subproblem::ncons ()
{
  /*{\Mop returns the number of active basic constraints in the current 
    node.} */
  return ABA_SUB::nCon ();
};


double subproblem::value (var v)
{
  /*{\Mop returns the value of |v| of the last solved LP.} */
  if(v==nil) return 1;
  return xVal (v.var_pointer ()->index ());
};

double subproblem::value(row& r) {
  row_entry::list_constiterator re;
  double d=0;
  foreach(re, r) d+=re->coeff*value(re->Var);
  return d;
  };

double subproblem::lower_bound (var v)
{
  /*{\Mop returns the lower bound of the variable in the current node.} */
  if (fsVarStat (v.var_pointer ()->index ())->status () !=
      ABA_FSVARSTAT::Free)
    {
      return myvalue (v.var_pointer ()->index ());
    }
  return lBound (v.var_pointer ()->index ());
}


double subproblem::upper_bound (var v)
{
  /*{\Mop returns the upper bound of the variable in the current node.} */
  if (fsVarStat (v.var_pointer ()->index ())->fixedOrSet ())
    {
      return myvalue (v.var_pointer ()->index ());
    }
  return uBound (v.var_pointer ()->index ());
}

double subproblem::value (cons i, as_what as) {
  /*{\Mop returns the value of |i| of the last solved LP.} */
  if (i.cons_pointer () == nil)
    {
      cout << "nil basic constraint\n"; return 0;}
  double d = yVal (i.cons_pointer ()->Acons ()->index ());
  if (as == as_is) return d;
  if ((as == as_max) && (GM.opt_sense () == Optsense_Max)) return d;
  if ((as == as_min) && (GM.opt_sense () == Optsense_Min)) return d;
  return -d;
}



//int subproblem::separate (subproblem &); 

void subproblem::activate (subproblem & S)
{
  sym_constraint_iterator s;
  
  foreach (s, sym_constraints) 
    {
      (*s)->open_subproblem (S);
    }
  
  if (father () != 0)
    {
      ((subproblem *) father ())->activate (S);
    }

}

void subproblem::activate ()
{
  activate (*this);
}; 


void subproblem::deactivate (subproblem & S)
{
  sym_constraint_iterator s; 
  foreach (s, sym_constraints)
    {
      (*s)->close_subproblem (S);
    }; 
  if (father () != 0)
    {
      ((subproblem *) father ())->deactivate (S);
    }
}; 


bool subproblem::save_solution(solution& s) {
  return GM.save_solution(s);
};

void subproblem::deactivate ()
{
  deactivate (*this);

  

  // TODO why is primal_heur not= 0 ???
  //cout<<&GM<<" "<<GM.primal_heur<<" master and heur\n";
  //if (GM.primal_heur != nil)
  //  GM.primal_heur->heuristic (*this);
}; 

double subproblem::myvalue (int i)
{
  if (fsVarStat (i)->status () == ABA_FSVARSTAT::FixedToLowerBound)
    return lBound (i);
  if (fsVarStat (i)->status () == ABA_FSVARSTAT::SetToLowerBound)
    return lBound (i);
  if (fsVarStat (i)->status () == ABA_FSVARSTAT::FixedToUpperBound)
    return uBound (i);
  if (fsVarStat (i)->status () == ABA_FSVARSTAT::SetToUpperBound)
    return uBound (i); 
  return fsVarStat (i)->value ();
}

//int subproblem::mf_pricing (subproblem &); 

Varstat subproblem::get_varstat(var v) {

     ABA_FSVARSTAT::STATUS st;
     //st = v.Avar_pointer()->fsVarStat()->status();
     st = fsVarStat(v.var_pointer()->index())->status();
     switch( st ) {
        case ABA_FSVARSTAT::Free:
           return Free;
        case ABA_FSVARSTAT::SetToUpperBound:
           return SetToUpperBound;
        case ABA_FSVARSTAT::SetToLowerBound:
           return SetToLowerBound;
        case ABA_FSVARSTAT::Set:
           return Set;
        case ABA_FSVARSTAT::FixedToUpperBound:
           return FixedToUpperBound;
        case ABA_FSVARSTAT::FixedToLowerBound:
           return FixedToLowerBound;
        case ABA_FSVARSTAT::Fixed:
           return Fixed;
     }
}



void subproblem::fixByLogImp(ABA_BUFFER<int>& variable,
      ABA_BUFFER< ABA_FSVARSTAT * > &  status ) {

   implicator *im = GM.implic;
   if(!im) return;

   std::list< std::pair<var, double> > fv;
   variable.clear();
   status.clear();
   im->implicate(*this, fv, true);
   if( !fv.empty() ) {
      std::list< pair<var,double> >::const_iterator tt;
      foreach(tt, fv) {
         variable.push(tt->first.var_pointer()->index());
         if( tt->second < .001 ) {
            status.push(new ABA_FSVARSTAT(master(), ABA_FSVARSTAT::FixedToLowerBound));
         }
         else if( tt->second > .999 ) {
            cerr << "fixing to 1" << endl;
            status.push(new ABA_FSVARSTAT(master(), ABA_FSVARSTAT::FixedToUpperBound));
         }
         else {
            cerr << "cannot fix to " << tt->second << endl;
            exit(Fatal);
         }
      }
   }
   return;
}

void subproblem::setByLogImp(ABA_BUFFER<int>& variable,
      ABA_BUFFER< ABA_FSVARSTAT * > &  status ) {

   implicator *im = GM.implic;
   if(!im) return;

   std::list< pair<var, double> > fv;
   variable.clear();
   status.clear();
   im->implicate(*this, fv, false);
   if( !fv.empty() ) {
      std::list< pair<var,double> >::const_iterator tt;
      foreach(tt, fv) {
         variable.push(tt->first.var_pointer()->index());
         if( tt->second < .001 ) {
            status.push(new ABA_FSVARSTAT(master(), ABA_FSVARSTAT::SetToLowerBound));
         }
         else if( tt->second > .999 ) {
            cerr << "setting to 1" << endl;
            status.push(new ABA_FSVARSTAT(master(), ABA_FSVARSTAT::SetToUpperBound));
         }
         else {
            cerr << "cannot set to " << tt->second << endl;
            exit(Fatal);
         }
      }
   }
   return;
}

int subproblem::improve (double &primalValue) {
  primal_heuristic *ph = GM.primal_heur;
  if(!ph) return 0;

  solution newSol;
  double pb = GM.primalBound();
  
  //apply heuristic and test symbolic and basic constraints
  if( ph->heuristic(*this, newSol) && feasible(*this, newSol) ) {
    for(int i=0; i<this->ncons(); i++) {
      cons_obj* cons = get_cons(i).cons_pointer();
      if (cons->violation(*this) > GM.eps()) return 0;
    }
    if( save_solution(newSol) ) {
       primalValue = GM.primalBound();
       return 1;
    }
  }
  return 0;
}

double* subproblem::MxVal ()
{
  return xVal_;
}; 

ABA_SUB * subproblem::generateSon (ABA_BRANCHRULE * rule)
{
   //FIXME prio
  subproblem* newsub = new subproblem (master_, this, rule);
  newsub->prio = prio;
  if( rule->branchOnSetVar() && ((ABA_SETBRANCHRULE*)rule)->setToUpperBound() )
     newsub->prio += 1;
  //newsub->prio = (variable(((ABA_SETBRANCHRULE*)rule)->variable()))->obj();

  return newsub;
};
/*{\op Diese Funktion erzeugt ein neues Unterproblem. } */

double subproblem::red_cost(var v) {
  /*{\Mop returns the value of |v| of the last solved LP.}*/
  return lp()->reco(v.var_pointer()->index());
};

//TODO remove
/*list_item subproblem::first_sym_constraint_item() const { 
  if(sym_constraints.size()==0) return nil;
  return GM.myroot->sym_constraints.first(); }

list_item subproblem::next_sym_constraint_item(list_item i) const {
  return GM.myroot->sym_constraints.succ(i);
};

sym_constraint* subproblem::get_sym_cons(list_item i) {
  if(i==nil) return nil;
  return GM.myroot->sym_constraints[i];
};*/

subproblem::~subproblem() {
  delete newvarbuffer;
};

---