subproblem.cc

#include<LEDA/list.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>

using namespace SCIL;
using namespace LEDA;

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

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

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

cons
subproblem::add_basic_constraint (cons_obj * c, Activation a)
{
  c->init (*this, GM.number_of_constraints(), a);
  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)
{
  cons_obj *
    c = new cons_obj (s, rhs);
  add_basic_constraint (c, a);
  return c;
};

var
subproblem::add_variable (double obj,
                          double lBound, double uBound,
                          Vartype t, Activation a)
{
  ABA_VARTYPE::TYPE type = ABA_VARTYPE::Continuous;
  if (t == Vartype_Integer)
    {
      if ((lBound == 0) && (uBound == 1))
        type = ABA_VARTYPE::Binary;
      else
        type = ABA_VARTYPE::Integer;
    }

  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_)
{
  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_)
{
  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)) > 0.001)
          {
            //cout << xVal (i) << "\n";
            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)
{

  sym_constraint * s;
  forall (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)
    {
      sym_constraint *
        c;
      forall (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 * s;
  sym_constraint::status rs;
  forall (s, sym_constraints) if(t!=-1)
  {
    rs=s->separate(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 *
    p;
  forall (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 *
    p;
  forall (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 re;
  double d=0;
  forall(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 * s; 
  
  forall (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 * s; 
  forall (s, sym_constraints)
    {
      s->close_subproblem (S);
    }; 
  if (father () != 0)
        {
          ((subproblem *) father ())->deactivate (S);
  }
}; 


void subproblem::save_solution(solution& s) {
  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 &); 

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

ABA_SUB * subproblem::generateSon (ABA_BRANCHRULE * rule)
{
  return new subproblem (master_, this, rule);
};
/*{\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());
};

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;
};

---