search_node.cc

Go to the documentation of this file.

// Search Node implementation -*- C++ -*-

// $Id: search_node.cc 681 2008-07-14 14:29:16Z mihaly $
// Copyright (C) 2001-2003 Hermann Schichl, Evgueni Petrov, Brice Pajot
//
// This file is part of the COCONUT API.  This library
// is free software; you can redistribute it and/or modify it under the
// terms of the Library GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// Library GNU General Public License for more details.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the Library GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the Library GNU General Public License.

#include <coconut_config.h>
#include <search_node.h>
#include <infeasible_delta.h>
#include <graphorder.h>

namespace coco {

work_node operator-(const work_node& _w, const delta_id& _d)
{
  work_node _tmp(_w);
  std::map<delta_id,undelta>::iterator __f;
  
  __f = _tmp.undeltas.find(_d);
  if(__f == _tmp.undeltas.end()) // this is not a new delta
  {
    throw api_exception(apiee_internal,
        std::string("work_node -: Cannot unapply delta <")+convert_to_str(_d)+
        "> which was not previously applied to work node <"+
        convert_to_str(_tmp.get_id())+">!");
  }
  else
  {
    std::list<delta_id>::iterator __g, __e(_tmp.deltas.begin());
    bool found = false;
    for(__g = _tmp.deltas.end(); __g != __e;)
    {
      --__g;
      if(*__g == _d)
      {
        found = true;
        break;
      }
    }
    if(found)
    {
      if(__g == _tmp.deltanew_it)
        ++_tmp.deltanew_it;
      _tmp.deltas.erase(__g);
    }
  }
  if(!(*__f).second.unapply(_tmp, _d))
    std::cerr << "Warning: Could not unapply delta <" <<
      _d << "> to work node <" << _tmp.get_id() << ">!" << std::endl;
  else
    _tmp.undeltas.erase(__f);
  return _tmp;
}

work_node& operator-=(work_node& _w, const delta_id& _d)
{
  std::map<delta_id,undelta>::iterator __f;
  
  __f = _w.undeltas.find(_d);
  if(__f == _w.undeltas.end()) // this is not a new delta
  {
    throw api_exception(apiee_internal,
        std::string("work_node -=: Cannot unapply delta <")+convert_to_str(_d)+
        "> which was not previously applied to work node <"+
        convert_to_str(_w.get_id())+">!");
  }
  else
  {
    std::list<delta_id>::iterator __g, __e(_w.deltas.begin());
    bool found = false;
    for(__g = _w.deltas.end(); __g != __e;)
    {
      --__g;
      if(*__g == _d)
      {
        found = true;
        break;
      }
    }
    if(found)
    {
      if(__g == _w.deltanew_it)
        ++_w.deltanew_it;
      _w.deltas.erase(__g);
    }
  }
  if(!(*__f).second.unapply(_w, _d))
    std::cerr << "Warning: Could not unapply delta <" <<
      _d << "> to work node <" << _w.get_id() << ">!" << std::endl;
  else
    _w.undeltas.erase(__f);
  return _w;
}

void work_node::init_all()
{
  dtable = (vdbl::standard_table*)
              get_database_ptr()->get_table("deltas", get_dbuserid());
  if(dtable == NULL)
  {
    get_database_ptr()->create_table("deltas", get_dbuserid());
    dtable = (vdbl::standard_table*)
              get_database_ptr()->get_table("deltas", get_dbuserid());
    if(dtable == NULL)
      throw api_exception(apiee_internal,
          "work_node::work_node: Database inconsistency (deltas table)");
    dtable_id = get_database_ptr()->get_tableid("deltas", get_dbuserid());
    dtable->add_col("delta",vdbl::typed_col<delta>(delta(infeasible_delta())),
                    vdbl::colflags());
    dtable->add_col("certificate",
        vdbl::typed_col<certificate>(certificate(no_certificate())),
                    vdbl::colflags(true));
    vdbl::colid _c_id(dtable->get_col_id("delta"));
    dtable->add_col("action",
                    vdbl::method_col<delta_get_action>(delta_get_action(_c_id)),
                    vdbl::colflags(true));
  }
  gitable = (vdbl::standard_table*)
              get_database_ptr()->get_table("global info", get_dbuserid());
  if(gitable == NULL)
  {
    get_database_ptr()->create_table("global info", get_dbuserid());
    gitable = (vdbl::standard_table*)
              get_database_ptr()->get_table("global info", get_dbuserid());
    if(gitable == NULL)
      throw api_exception(apiee_internal,
          "work_node::work_node: Database inconsistency (global info table)");
    gitable_id = get_database_ptr()->get_tableid("global info", get_dbuserid());
  }
  wnc = new work_node_context(this);
  __vdb = new vdbl::viewdbase(*this->database()->get_local_copy(),
        this->get_dbuserid(), *wnc,
        std::vector<std::pair<vdbl::tableid,vdbl::rowid> >(
              this->get_annotations().begin(),
              this->get_annotations().end()));
  make_node_ranges(false);
  make_node_order();
  init_cnumbers();
}

work_node::work_node(const search_node_id& _i, const vdbl::userid& _dui,
                     gptr<model>& __m, gptr<vdbl::database>& __d,
                     const std::vector<annotation>& __an,
                     const std::list<delta_id>& __de, gptr<search_node>* _gm,
                     search_node_relation snr, vdbl::viewdbase* vdbf) : 
  _Base(_i, _dui, __m, _gm, __d, __an, snr),
  deltas(__de),

  deltanew_it(deltas.end()),

  parents_in_graph(),
  undeltas(),
  __vdbf(vdbf),
  node_ranges(), 
  node_order(), 
  infeasible(false),
  gain_factor(1.),
  globalinfo(),
  _tnum(0),
  proposed_splits(),
  split_delta_ids(),
  n_bds(0), 
  n_lin(0),
  n_quad(0), 
  n_poly(0), 
  n_other(0)
{
  init_all();
}

work_node::work_node(const full_node& _f, const std::list<delta_id>& __de,
                     vdbl::viewdbase* vdbf) : 
  _Base(_f),
  deltas(__de),

  deltanew_it(deltas.end()),

  parents_in_graph(),
  undeltas(),
  __vdbf(vdbf),
  node_ranges(), 
  node_order(), 
  infeasible(false),
  gain_factor(1.),
  globalinfo(),
  _tnum(0),
  proposed_splits(),
  split_delta_ids(),
  n_bds(0), 
  n_lin(0),
  n_quad(0), 
  n_poly(0), 
  n_other(0)
{
  init_all();
  set_rowid(_f.get_rowid());
}

void work_node::init_cnumbers()
{
  expression_walker _c;
  int h = (**_m).constraints.size();
  n_bds = n_lin = n_quad = n_poly = n_other = 0;
  for(int i = 0; i < h; ++i)
  {
    _c = (**_m).constraints[i];
    if(_c->is(ex_bound))
      n_bds++;
    else if(_c->is(ex_linear))
      n_lin++;
    else if(_c->is(ex_quadratic))
      n_quad++;
    else if(_c->is(ex_polynomial))
      n_poly++;
    else
      n_other++;
  }
  log_vol = compute_log_volume(node_ranges);
}

void work_node::make_node_ranges(bool keep_old_ranges)
{
  unsigned int n = (**_m).number_of_nodes();
  if(n > node_ranges.size())
  {
    node_ranges.reserve(n);
    node_ranges.insert(node_ranges.end(), n-node_ranges.size(),
        interval(-COCO_INF,COCO_INF));
  }
  for(unsigned int i = 0; i < n; ++i)
  {
    if((**_m).node(i) != (**_m).ground())
    {
      if(!keep_old_ranges || node_ranges[i].is_entire())
        node_ranges[i] = (**_m).node(i)->f_bounds;
    }
    else
      node_ranges[i] = interval(-COCO_INF,COCO_INF);
  }
}

void work_node::make_node_order()
{
  graphorder(**_m, node_order);
}

#define MAX_VOL_COMP    1.e12
#define MIN_VOL_WIDTH   DBL_MIN

double work_node::compute_log_volume(const std::vector<interval>& _r) const
{
  // this makes sure that the volume, which is for finite boxes
  // in the range [-710,710]*num_of_var, stays finite even for
  // thin and inifinite boxes.
  unsigned int n = (**_m).number_of_variables();
  double lv(0);
  double help;

  for(unsigned int i = 0; i < n; ++i)
  {
    if((**_m).var(i)->sem.kj_flag())
      continue;
    const interval& nds(_r[(**_m).var(i)->node_num]);
    if(nds.is_bounded())
    {
      help = nds.width();
      if(help < MIN_VOL_WIDTH)
        lv -= MAX_VOL_COMP;
      else
        lv += std::log(help);
    }
    else
      lv += MAX_VOL_COMP;
  }
  return lv;
}

void work_node::set_globalinfo()
{
  if(gitable == NULL)
    throw api_exception(apiee_internal,
      "work_node::work_node: Database inconsistency (global info table)");
  vdbl::table::row_const_iterator r0i(gitable->row_begin());
  if(r0i != gitable->row_end())
  {
    bool error(false);
    vdbl::table::col_const_iterator ci, ce(gitable->col_end());
    for(ci = gitable->col_begin(); ci != ce; ++ci)
    {
      basic_alltype *bat;
      error = !gitable->retrieve(*r0i, (*ci).second, wnc, bat);
      if(error)
        throw api_exception(apiee_internal,
          "work_node::work_node: Database inconsistency (global info table)/get col");
      error = !globalinfo.sinsert((*ci).first, *bat, true);
      if(error)
        throw api_exception(apiee_internal,
          "work_node::work_node: Database inconsistency (global info table)/update cache");
    }
  }
}


bool work_node::global_info(basic_alltype& b, const std::string& i) const
{
  b = globalinfo.sfind(i);
  if(b.empty())
    return globalinfo.defd(i);
  return true;
}

basic_alltype work_node::global_info(const std::string& i) const
{
  return globalinfo.sfind(i);
}

} // namespace coco

---