model.h

Go to the documentation of this file.

// Model implementation -*- C++ -*-

// $Id: model.h 544 2008-04-07 17:12:03Z mihaly $
// Copyright (C) 2001-2003 Hermann Schichl
//
// 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.

#ifndef _MODEL_H_
#define _MODEL_H_

#include <iostream>
#include <coconut_config.h>
#include <expression.h>
#include <database>
#include <annotation.h>
#include <api_debug.h>

using namespace vgtl;

namespace coco {

class model_gid;
class dag_delta;


class model: public dag<expression_node>
{
private:
  typedef dag<expression_node> _Base;

public:
  typedef dag<expression_node>::walker walker;
  typedef dag<expression_node>::const_walker const_walker;

  typedef std::vector<walker>::iterator ref_iterator;
  typedef std::vector<walker>::const_iterator const_ref_iterator;

private:
  std::vector<walker> node_ref;
  std::vector<walker> var_ref;
  std::vector<walker> ghost_ref;
  model_gid* gid;
  bool keep_gid;
  bool destroy_node_ref;

public:
  linalg::matrix<double> lin;
  std::vector<linalg::matrix<double> > matd;
  std::vector<linalg::matrix<interval> > mati;
  int ocoeff;
  walker objective;
  std::vector<walker> constraints;
  bool has_read_errors;
public:
  model(model_gid* __id = NULL, bool clone = false);
  model(model_gid* __id, const erased_part& _ep, bool clone = false);
  model(int __num_of_vars);
  model(const model& __m);
  model(model_gid* __id, const model& __m);
  model(std::istream& inp, bool do_simplify = true, vdbl::database* _db = NULL,
       vdbl::userid _uid = vdbl::userid(), std::vector<annotation>* _la = NULL,
       std::string mname = std::string(), bool continue_on_errors = false);
  model(const char* name, bool do_simplify = true, vdbl::database* _db = NULL,
       vdbl::userid _uid = vdbl::userid(), std::vector<annotation>* _la = NULL,
       bool continue_on_errors = false);

  ~model();

  int next_num();
  int next_variable_num();
  int next_constraint_num();

  unsigned int number_of_variables() const;
  unsigned int number_of_nodes() const;
  unsigned int number_of_constraints() const;
  unsigned int number_of_managed_nodes() const
         { return (unsigned int)node_ref.size(); }
  unsigned int number_of_managed_variables() const
         { return (unsigned int)var_ref.size(); }
  unsigned int number_of_managed_constraints() const
         { return (unsigned int)constraints.size(); }
  const walker& var(unsigned int i) const;
  const walker& node(unsigned int i) const;
  const walker& constraint(unsigned int i) const;
  model_gid* gid_data() const { return gid; }

  void detach_gid();

  void compress_numbers();
  void renumber_variables();
  void renumber_constraints();

private:
  struct __docompare_nodes;
  struct __docompare_variables;
  class sort_constraints;
  class simplify_visitor_0;
  class simplify_visitor_m;
  struct lincoeff_visitor_st;
  struct lincoeff_visitor_ret;
  class lincoeff_visitor;
  struct detect_0chain_visitor_st;
  class detect_0chain_visitor;
#if 0
  class simplify_visitor_thin;
#endif
  
  interval read_interval(char *& cp, int ln);

  template <typename _TT>
  void read_vector(std::vector<_TT>& hd, char *& cq, const char *format,
                   const char* message, int ln);

  void store_point_in_db(const std::vector<double>& pt, vdbl::database* _db,
                         vdbl::userid _uid, unsigned int point_class,
                         std::vector<annotation>* _la) const;

  void model_read(std::istream& inp, bool do_simplify, vdbl::database* _db,
                  vdbl::userid _uid, std::vector<annotation>* _la,
                  std::string mname = std::string(),
                  bool continue_on_errors = false);
  bool read(std::istream& __i, vdbl::database* _db, vdbl::userid _uid,
            std::vector<annotation>* _la, bool continue_on_errors = false);
  bool children_eq(walker __n1, walker __n2);
  
  void del_nodes_and_edges(const std::vector<unsigned int>& delnodes,
           const std::vector<std::pair<unsigned int,unsigned int> >& deledges,
           const std::vector<unsigned int>& delghosts);
  bool exchange_ghost(walker prnt, walker gh_old, unsigned int _nnum);
  void safe_ghost(walker prnt, unsigned int _nnum);
  
  bool basic_simplify_0();
  bool basic_simplify_1_merge(walker __s, std::list<walker>& _todo,
                           std::vector<int>& _combined, std::vector<bool>& _fld,
                           std::vector<int>& _sorted);
  void basic_simplify_1_flood(walker __s, std::vector<int>& _combined);
  bool basic_simplify_1_is_ready(walker __s, const std::vector<int>& _combined,
                                 bool all_finished);
  bool basic_simplify_1();
  bool basic_simplify_2(std::set<std::pair<unsigned int, unsigned int> >&
  trf_gh_set, std::map<unsigned int, unsigned int>& gh_new_map);

  void fill_arrays(walker __w, std::vector<walker>& __n,
                   std::vector<walker>& __v, std::vector<walker>& __g);
  void copy_contents(model_gid* gid, const model& __m);
  void prepare_after_read();

public:
  void prepare_kill() { keep_gid = destroy_node_ref = true; }
  bool micro_simplify();
  bool basic_simplify();
  void arrange_constraints();
  void detect_0chain();
  bool simplify_thin();
  void set_counters();
  void clr_sky_ground_link();

  void write(std::ostream& __o = std::cout) const;
#if MODEL_INLINE_DEBUG

  void dbg_write() const;
#endif

  void check_counters(bool reset) const;

public:
  ref_iterator ghost_begin() { return ghost_ref.begin(); }
  const_ref_iterator ghost_begin() const { return ghost_ref.begin(); }
  ref_iterator ghost_end() { return ghost_ref.end(); }
  const_ref_iterator ghost_end() const { return ghost_ref.end(); }

  walker store_node(const walker& _w);
  walker store_variable(const walker& _w);
  walker store_ghost(const walker& _w);
  walker store_constraint(const walker& _w);

  void free_node_num(unsigned int _nnum);
  void free_var_num(int _vnum);
  void free_const_num(const walker& _w, unsigned int _cnum);
  void free_all();
  void free_nodes_on_destroy();
  void keep_nodes_on_destroy();
  

  void remove_node(const walker& _w, unsigned int _nnum);
  void remove_node(const walker& _w);
  void remove_node(unsigned int __node_num);
  
  void new_variables(int _new_num_of_vars);

  walker ghost(unsigned int _nnum);
  
  walker constant(double _constant);
  walker constant(const std::vector<double>& _constant);

  walker variable(unsigned int _vnum);

  walker binary(const walker& _op1, const walker& _op2, int expr_type,
                double _coeff1 = 1.0, double _coeff2 = 1.0);
  walker binary(const walker& _op1, const walker& _op2, int expr_type,
                const basic_alltype& _params, double _coeff1 = 1.0,
                double _coeff2 = 1.0);
  
  walker unary(const walker& _op1, int expr_type, double _coeff = 1.0);
  walker unary(const walker& _op1, int expr_type, const basic_alltype& _params,
      double _coeff = 1.0);

  walker nary(const std::vector<walker>& _op, int expr_type,
              const std::vector<double>& _coeffs = std::vector<double>());
  walker nary(const std::vector<walker>& _op, int expr_type,
              const basic_alltype& _params,
              const std::vector<double>& _coeffs = std::vector<double>());

  walker vnary(int expr_type, ...);
  walker vxnary(const basic_alltype& _params, int expr_type, ...);

  bool is_empty(const walker& _w) const;
  walker empty_reference() const;

public:
  const std::string model_name() const;
  const std::string var_name(unsigned int n) const;
  const std::string const_name(unsigned int n) const;
  const std::string obj_name() const;
  double obj_adj() const;
  double obj_mult() const;
  size_t n_fixed_vars() const;
  std::pair<const std::string, double> fixed_var(unsigned int n) const;
  size_t n_unused_vars() const;
  const std::string& unused_var(unsigned int n) const;
  size_t n_unused_constrs() const;
  const std::string& unused_constr(unsigned int n) const;

  const std::map<int, std::vector<double> >& trace_points() const;
  const std::map<int, std::vector<double> >& optima() const;
  
  bool get_const_num(unsigned int node_num, unsigned int& const_num) const;

public:
  bool get_linear_coeffs(const const_walker& expr,
          linalg::sparse_vector<double>& coeffs, double& constant,
          const std::vector<interval>& _ranges);
  bool get_linear_coeffs(const const_walker& expr,
          linalg::sparse_vector<double>& coeffs, double& constant);

  friend class dag_delta;
  friend class dag_undelta;
};


class model_iddata
{
private:
  unsigned int node_num_max;
  unsigned int var_num_max;
  unsigned int const_num_max;
  std::vector<unsigned int> node_free;
  std::vector<unsigned int> var_free;
  std::vector<unsigned int> const_free;

  std::list<model_gid*> backref;

  std::vector<std::string> var_names;
  std::vector<std::pair<std::string, double> > fixed_vars;
  std::string obj_names;
  double obj_adjs;
  double obj_mults;

  std::vector<std::string> unused_vars;
  std::vector<std::string> unused_constrs;

  std::vector<std::string> const_names;

  std::map<int, std::vector<double> > trace_points;
  std::map<int, std::vector<double> > optima;

  std::string mod_name;

public:
  model_iddata(unsigned int n = 0) : node_num_max(0), var_num_max(n),
                                     const_num_max(0), node_free(), var_free(),
                                     const_free(), backref(),
                                     var_names(n, std::string()), fixed_vars(),
                                     obj_names(), obj_adjs(0), obj_mults(1),
                                     unused_vars(), unused_constrs(),
                                     const_names(), trace_points(), optima(),
                                     mod_name()
     {}

  ~model_iddata() {} 

  void new_ref(model_gid& __m) { backref.push_back(&__m); }
  bool delete_ref(model_gid& __m);

  unsigned int number_of_nodes() const { return node_num_max; }
  unsigned int number_of_variables() const { return var_num_max; }
  unsigned int number_of_constraints() const { return const_num_max; }
  void number_of_nodes(unsigned int _n);
  void number_of_variables(unsigned int _n);
  void number_of_constraints(unsigned int _n);

  unsigned int get_node_id();
  void remove_node_id(unsigned int n);
  unsigned int get_var_id();
  void remove_var_id(unsigned int n);
  unsigned int get_const_id();
  void remove_const_id(unsigned int n);

  void compress_numbers(bool renum_vars, bool renum_consts = false);

public:
  const std::string model_name() const;
  void model_name(const std::string& n);

  const std::string var_name(unsigned int n) const;
  void var_name(unsigned int n, const std::string& vn);

  const std::string const_name(unsigned int n) const;
  void const_name(unsigned int n, const std::string& cn);

  const std::string obj_name() const;
  void obj_name(const std::string& vn);
  double obj_adj() const;
  void obj_adj(double adj);
  double obj_mult() const;
  void obj_mult(double mult);

  size_t n_fixed_vars() const { return fixed_vars.size(); }
  std::pair<const std::string, double> fixed_var(unsigned int n) const;
  void fixed_var(const std::string& vn, double val);

  size_t n_unused_vars() const { return unused_vars.size(); }
  const std::string& unused_var(unsigned int n) const;
  void unused_var(const std::string& vn);
  
  size_t n_unused_constrs() const { return unused_constrs.size(); }
  const std::string& unused_constr(unsigned int n) const;
  void unused_constr(const std::string& vn);
  
  friend class model_gid;
};


class model_gid
{
private:
  model_iddata* _id;
  model& model_ref;
  std::vector<model::walker> glob_ref;
  std::vector<model::walker> gvar_ref;
  std::vector<model::walker> gconst_ref;
  std::map<unsigned int, unsigned int> const_back_ref; 

#if MODEL_INLINE_DEBUG_SIMPLIFY
// added by MM
public:
  void print_const_back_ref()
  {
    std::cout << "begin const_back_ref:" << std::endl;
    std::map<unsigned int, unsigned int>::const_iterator it;
    for (it=const_back_ref.begin(); it!=const_back_ref.end(); ++it)
      std::cout << it->first << " , " << it->second << std::endl;
    std::cout << "end const_back_ref:" << std::endl;
  }
#endif

private:
  void renumber_nodes(std::vector<std::pair<unsigned int,unsigned int> >& __v);
  void renumber_variables(std::vector<std::pair<unsigned int,unsigned int> >& __v);
  void renumber_constraints(
                std::vector<std::pair<unsigned int,unsigned int> >& __v);
  void upd_number_of_nodes(unsigned int _n);
  void upd_number_of_variables(unsigned int _n);
  void upd_number_of_constraints(unsigned int _n);

public:
  void remove_node_ref(unsigned int _n)
    { if(glob_ref.size() == _n) glob_ref.pop_back();
      else glob_ref[_n] = model_ref.ground(); }
  void remove_var_ref(unsigned int _n)
    { if(gvar_ref.size() == _n) gvar_ref.pop_back();
      else gvar_ref[_n] = model_ref.ground(); }
  void remove_const_ref(unsigned int _n);

  model_gid(model& __m, model_iddata* __i=NULL);
  model_gid(model& __m, unsigned int n, model_iddata* __i = NULL);

  model_gid(model& __mr, const model_gid& __m);

  ~model_gid() { if(_id->delete_ref(*this)) delete _id; }

  unsigned int number_of_nodes() const { return _id->number_of_nodes(); }
  unsigned int number_of_variables() const
        { return _id->number_of_variables(); }
  unsigned int number_of_constraints() const
        { return _id->number_of_constraints(); }
  void number_of_nodes(unsigned int _n) { _id->number_of_nodes(_n); }
  void number_of_variables(unsigned int _n) { _id->number_of_variables(_n); }
  void number_of_constraints(unsigned int _n) {_id->number_of_constraints(_n);}

  void mk_globref(unsigned int n, const model::walker& __w);
  void mk_gvarref(unsigned int n, const model::walker& __w);
  void mk_gconstref(unsigned int n, const model::walker& __w);

  void make_const_back_ref(unsigned int node, unsigned int cnum);
  
  unsigned int get_node_id() { return _id->get_node_id(); }
  void remove_node_id(unsigned int n) { _id->remove_node_id(n); }
  unsigned int get_var_id() { return _id->get_var_id(); }
  void remove_var_id(unsigned int n) { _id->remove_var_id(n); }
  unsigned int get_const_id() { return _id->get_const_id(); }
  void remove_const_id(unsigned int n) { _id->remove_const_id(n); }

  void compress_numbers(bool renumber_vars = false, bool renumber_const = false)
        { _id->compress_numbers(renumber_vars, renumber_const); }

  const model::walker& node(unsigned int i) const { return glob_ref[i]; }
  const model::walker& variable(unsigned int i) const { return gvar_ref[i]; }
  const model::walker& constraint(unsigned int i) const
                                                { return gconst_ref[i]; }

  bool empty(const model::walker& __x) const
        { return __x == model_ref.ground(); }
  bool its_me(const model& __m) const { return &__m == &model_ref; }
  model::walker empty_reference() const { return model_ref.ground(); }

  bool have_glob_ref(unsigned int _nnum) const
        { return _nnum < glob_ref.size(); }
  bool have_gvar_ref(unsigned int _vnum) const
        { return _vnum < gvar_ref.size(); }
  bool have_gconst_ref(unsigned int _cnum) const
        { return _cnum < gconst_ref.size(); }

public:
  const std::string model_name() const { return _id->model_name(); }
  void model_name(const std::string& n) { _id->model_name(n); }
  void model_name(const char* n) { _id->model_name(std::string(n)); }

  const std::string var_name(unsigned int n) const { return _id->var_name(n); }
  void var_name(unsigned int n, const std::string& vn) { _id->var_name(n, vn); }
  void var_name(unsigned int n, const char* vn)
        { _id->var_name(n, std::string(vn)); }

  const std::string const_name(unsigned int n) const
                                                { return _id->const_name(n); }
  void const_name(unsigned int n, const std::string& vn)
                                                { _id->const_name(n, vn); }
  void const_name(unsigned int n, const char* vn)
        { _id->const_name(n, std::string(vn)); }
  bool get_const_num(unsigned int node_num, unsigned int& const_num);

  const std::string obj_name() const { return _id->obj_name(); }
  void obj_name(const std::string& vn) { _id->obj_name(vn); }
  void obj_name(const char* vn) { _id->obj_name(std::string(vn)); }
  double obj_adj() const { return _id->obj_adj(); }
  void obj_adj(double adj) { _id->obj_adj(adj); }
  double obj_mult() const { return _id->obj_mult(); }
  void obj_mult(double mult) { _id->obj_mult(mult); }

  size_t n_fixed_vars() const { return _id->n_fixed_vars(); }
  std::pair<const std::string, double> fixed_var(unsigned int n) const
        { return _id->fixed_var(n); }
  void fixed_var(const std::string& vn, double val) { _id->fixed_var(vn, val); }
  void fixed_var(const char* vn, double val)
        { _id->fixed_var(std::string(vn), val); }
  
  size_t n_unused_vars() const { return _id->n_unused_vars(); }
  const std::string& unused_var(unsigned int n) const
        { return _id->unused_var(n); }
  void unused_var(const std::string& vn) { _id->unused_var(vn); }
  void unused_var(const char* vn) { _id->unused_var(std::string(vn)); }
  
  size_t n_unused_constrs() const { return _id->n_unused_constrs(); }
  const std::string& unused_constr(unsigned int n) const
        { return _id->unused_constr(n); }
  void unused_constr(const std::string& vn) { _id->unused_constr(vn); }
  void unused_constr(const char* vn) { _id->unused_constr(std::string(vn)); }

  const std::map<int, std::vector<double> >& trace_points() const;
  const std::map<int, std::vector<double> >& optima() const;
  void add_trace_point(int nr, const std::vector<double>& d)
        { _id->trace_points[nr] = d; }
  void add_optimum(int nr, const std::vector<double>& d)
        { _id->optima[nr] = d; }
  
  friend class model_iddata;
};

} // namespace coco

#include <model.hpp>

namespace coco {


typedef model::walker expression_walker;

typedef model::const_walker expression_const_walker;

} // namespace coco

#endif /* _MODEL_H_ */

---