---

search_node.cc

Go to the documentation of this file.

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

// 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 <search_node.h>
#include <infeasible_delta.h>

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
  {
    std::cerr << "ERROR: Cannot unapply delta <" << _d <<
        "> which was not previously applied to work node <" << _tmp.get_id() <<
        ">!";
      throw "Programming error: work_node -";
  }
  else
  {
    std::list<delta_id>::iterator __g, __e(_tmp.deltas.end());
    for(__g = _tmp.deltas.begin(); __g != __e; ++__g)
      if(*__g == _d)
        break;
    if(__g != __e)
      _tmp.deltas.erase(__g);
  }
  if(!(*__f).second.unapply(_tmp))
    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
  {
    std::cerr << "ERROR: Cannot unapply delta <" << _d <<
        "> which was not previously applied to work node <" << _w.get_id() <<
        ">!" << std::endl;
    throw "Programming error: work_node -=";
  }
  else
  {
    std::list<delta_id>::iterator __g, __e(_w.deltas.end());
    for(__g = _w.deltas.begin(); __g != __e; ++__g)
      if(*__g == _d)
        break;
    if(__g != __e)
      _w.deltas.erase(__g);
  }
  if(!(*__f).second.unapply(_w))
    std::cerr << "Warning: Could not unapply delta <" <<
      _d << "> to work node <" << _w.get_id() << ">!" << std::endl;
  else
    _w.undeltas.erase(__f);
  return _w;
}

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) : 
  _Base(_i, _dui, __m, _gm, __d, __an, snr),
  deltas(__de),
  undeltas(),
  node_ranges(), 
  infeasible(false),
  gain_factor(1.),
  _tnum(0),
  proposed_splits(),
  n_bds(0), 
  n_lin(0),
  n_quad(0), 
  n_poly(0), 
  n_other(0)
{
  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 "Database inconsistency: Programming Error!";
    dtable_id = get_database_ptr()->get_tableid("deltas", get_dbuserid());
    dtable->add_col("delta",vdbl::typed_col<delta>(delta(infeasible_delta())),
                    vdbl::colflags());
    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));
  }
  make_node_ranges(false);
  init_cnumbers();
}

void work_node::init_cnumbers()
{
  model::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(-INFINITY,INFINITY));
  }
  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(-INFINITY,INFINITY);
  }
}

#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)
  {
    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 += log(help);
    }
    else
      lv += MAX_VOL_COMP;
  }
  return lv;
}

---