Commits

Leonardo de Moura  committed 0990a2e

using a consistent naming convention for naming tactic subfolders

Signed-off-by: Leonardo de Moura <leonardo@microsoft.com>

  • Participants
  • Parent commits 67f5ed4

Comments (0)

Files changed (278)

File scripts/mk_make.py

 add_lib('smt', ['bit_blaster', 'macros', 'normal_forms', 'cmd_context', 
                 'substitution', 'grobner', 'euclid', 'proof_checker', 'pattern', 'parser_util'])
 add_lib('user_plugin', ['smt'], 'smt/user_plugin')
-add_lib('core_tactics', ['tactic', 'normal_forms'], 'tactic/core_tactics')
-add_lib('sat_tactic', ['tactic', 'sat'], 'tactic/sat_tactic')
-add_lib('arith_tactics', ['core_tactics', 'sat'], 'tactic/arith_tactics')
-add_lib('nlsat_tactic', ['nlsat', 'sat_tactic', 'arith_tactics'], 'tactic/nlsat_tactic')
-add_lib('subpaving_tactic', ['core_tactics', 'subpaving'], 'tactic/subpaving_tactic')
-add_lib('bv_tactics', ['tactic', 'bit_blaster'], 'tactic/bv_tactics')
+add_lib('core_tactics', ['tactic', 'normal_forms'], 'tactic/core')
+add_lib('sat_tactic', ['tactic', 'sat'], 'tactic/sat')
+add_lib('arith_tactics', ['core_tactics', 'sat'], 'tactic/arith')
+add_lib('nlsat_tactic', ['nlsat', 'sat_tactic', 'arith_tactics'], 'tactic/nlsat')
+add_lib('subpaving_tactic', ['core_tactics', 'subpaving'], 'tactic/subpaving')
+add_lib('bv_tactics', ['tactic', 'bit_blaster'], 'tactic/bv')
 add_lib('fuzzing', ['ast'], 'test/fuzzing')
 add_lib('fpa', ['core_tactics', 'bv_tactics', 'sat_tactic'], 'tactic/fpa')
-add_lib('smt_tactic', ['smt'], 'tactic/smt_tactic')
+add_lib('smt_tactic', ['smt'], 'tactic/smt')
 add_lib('extra_cmds', ['cmd_context', 'subpaving_tactic', 'arith_tactics'], 'cmd_context/extra_cmds')
-add_lib('sls_tactic', ['tactic', 'normal_forms', 'core_tactics', 'bv_tactics'], 'tactic/sls_tactic')
+add_lib('sls_tactic', ['tactic', 'normal_forms', 'core_tactics', 'bv_tactics'], 'tactic/sls')
 add_lib('aig', ['tactic'], 'tactic/aig')
 # TODO: split muz_qe into muz, qe. Perhaps, we should also consider breaking muz into muz and pdr.
 add_lib('muz_qe', ['smt', 'sat', 'smt2parser'])
-add_lib('smtlogic_tactics', ['arith_tactics', 'bv_tactics', 'nlsat_tactic', 'smt_tactic', 'aig', 'muz_qe'], 'tactic/smtlogic_tactics')
-add_lib('ufbv_tactic', ['normal_forms', 'core_tactics', 'macros', 'smt_tactic', 'rewriter'], 'tactic/ufbv_tactic')
+add_lib('smtlogic_tactics', ['arith_tactics', 'bv_tactics', 'nlsat_tactic', 'smt_tactic', 'aig', 'muz_qe'], 'tactic/smtlogics')
+add_lib('ufbv_tactic', ['normal_forms', 'core_tactics', 'macros', 'smt_tactic', 'rewriter'], 'tactic/ufbv')
 add_lib('portfolio', ['smtlogic_tactics', 'ufbv_tactic', 'fpa', 'aig', 'muz_qe', 'sls_tactic', 'subpaving_tactic'], 'tactic/portfolio')
 # TODO: delete SMT 1.0 frontend
 add_lib('api', ['portfolio', 'user_plugin'])

File src/api/dll/dll.cpp

+#ifdef _WINDOWS
 
-#include "windows.h"
-
+#include<windows.h>
 
 #ifdef _MANAGED
 #pragma managed(push, off)
 #ifdef _MANAGED
 #pragma managed(pop)
 #endif
+
+#endif

File src/tactic/arith/add_bounds_tactic.cpp

+/*++
+Copyright (c) 2011 Microsoft Corporation
+
+Module Name:
+
+    add_bounds_tactic.h
+
+Abstract:
+
+    Tactic for bounding unbounded variables.
+
+Author:
+
+    Leonardo de Moura (leonardo) 2011-10-22.
+
+Revision History:
+
+--*/
+#include"tactical.h"
+#include"arith_decl_plugin.h"
+#include"ast_smt2_pp.h"
+#include"bound_manager.h"
+
+struct is_unbounded_proc {
+    struct found {};
+    arith_util      m_util;
+    bound_manager & m_bm;
+    
+    is_unbounded_proc(bound_manager & bm):m_util(bm.m()), m_bm(bm) {}
+
+    void operator()(app * t) {
+        if (is_uninterp_const(t) &&  (m_util.is_int(t) || m_util.is_real(t)) && (!m_bm.has_lower(t) || !m_bm.has_upper(t)))
+            throw found();
+    }
+    
+    void operator()(var *) {}
+    
+    void operator()(quantifier*) {}
+};
+
+bool is_unbounded(goal const & g) {
+    ast_manager & m = g.m();
+    bound_manager bm(m);
+    bm(g);
+    is_unbounded_proc proc(bm);
+    return test(g, proc);
+}
+
+class is_unbounded_probe : public probe {
+public:
+    virtual result operator()(goal const & g) {
+        return is_unbounded(g);
+    }
+};
+
+probe * mk_is_unbounded_probe() {
+    return alloc(is_unbounded_probe);
+}
+
+class add_bounds_tactic : public tactic {
+    struct imp {
+        ast_manager & m;
+        rational      m_lower;
+        rational      m_upper;
+        volatile bool m_cancel;
+        
+        imp(ast_manager & _m, params_ref const & p):
+            m(_m) {
+            updt_params(p);
+        }
+        
+        void updt_params(params_ref const & p) {
+            m_lower  = p.get_rat(":add-bound-lower", rational(-2));
+            m_upper  = p.get_rat(":add-bound-upper", rational(2));
+        }
+        
+        void set_cancel(bool f) {
+            m_cancel = f;
+        }
+        
+        struct add_bound_proc {
+            arith_util       m_util;
+            bound_manager &  m_bm;
+            goal &           m_goal;
+            rational const & m_lower;
+            rational const & m_upper;
+            unsigned         m_num_bounds;
+            
+            add_bound_proc(bound_manager & bm, goal & g, rational const & l, rational const & u):
+                m_util(bm.m()), 
+                m_bm(bm), 
+                m_goal(g),
+                m_lower(l),
+                m_upper(u) {
+                m_num_bounds = 0;
+            }
+            
+            void operator()(app * t) {
+                if (is_uninterp_const(t) &&  (m_util.is_int(t) || m_util.is_real(t))) {
+                    if (!m_bm.has_lower(t)) {
+                        m_goal.assert_expr(m_util.mk_le(t, m_util.mk_numeral(m_upper, m_util.is_int(t))));
+                        m_num_bounds++;
+                    }
+                    if (!m_bm.has_upper(t)) {
+                        m_goal.assert_expr(m_util.mk_ge(t, m_util.mk_numeral(m_lower, m_util.is_int(t))));
+                        m_num_bounds++;
+                    }
+                }
+            }
+            
+            void operator()(var *) {}
+            
+            void operator()(quantifier*) {}
+        };
+        
+        virtual void operator()(goal_ref const & g, 
+                                goal_ref_buffer & result, 
+                                model_converter_ref & mc, 
+                                proof_converter_ref & pc,
+                                expr_dependency_ref & core) {
+            mc = 0; pc = 0; core = 0;
+            tactic_report report("add-bounds", *g);
+            bound_manager bm(m);
+            expr_fast_mark1 visited;
+            add_bound_proc proc(bm, *(g.get()), m_lower, m_upper);
+            unsigned sz = g->size();
+            for (unsigned i = 0; i < sz; i++)
+                quick_for_each_expr(proc, visited, g->form(i));
+            visited.reset();
+            g->inc_depth();
+            result.push_back(g.get());
+            if (proc.m_num_bounds > 0) 
+                g->updt_prec(goal::UNDER);
+            report_tactic_progress(":added-bounds", proc.m_num_bounds);
+            TRACE("add_bounds", g->display(tout););
+        }
+    };
+
+    imp *      m_imp;
+    params_ref m_params;
+
+public:
+    add_bounds_tactic(ast_manager & m, params_ref const & p):
+        m_params(p) {
+        m_imp = alloc(imp, m, p);
+    }
+
+    virtual tactic * translate(ast_manager & m) {
+        return alloc(add_bounds_tactic, m, m_params);
+    }
+    
+    virtual ~add_bounds_tactic() {
+        dealloc(m_imp);
+    }
+    
+    virtual void updt_params(params_ref const & p) {
+        m_params = p;
+        m_imp->updt_params(p);
+    }
+
+    virtual void collect_param_descrs(param_descrs & r) { 
+        r.insert(":add-bound-lower", CPK_NUMERAL, "(default: -2) lower bound to be added to unbounded variables.");
+        r.insert(":add-bound-upper", CPK_NUMERAL, "(default: 2) upper bound to be added to unbounded variables.");
+    }
+    
+    virtual void operator()(goal_ref const & g, 
+                            goal_ref_buffer & result, 
+                            model_converter_ref & mc, 
+                            proof_converter_ref & pc,
+                            expr_dependency_ref & core) {
+        (*m_imp)(g, result, mc, pc, core);
+    }
+    
+    virtual void cleanup() {
+        ast_manager & m = m_imp->m;
+        imp * d = m_imp;
+        #pragma omp critical (tactic_cancel)
+        {
+            d = m_imp;
+        }
+        dealloc(d);
+        d = alloc(imp, m, m_params);
+        #pragma omp critical (tactic_cancel) 
+        {
+            m_imp = d;
+        }
+    }
+
+protected:
+    virtual void set_cancel(bool f) {
+        if (m_imp)
+            m_imp->set_cancel(f);
+    }
+};
+
+tactic * mk_add_bounds_tactic(ast_manager & m, params_ref const & p) {
+    return clean(alloc(add_bounds_tactic, m, p));
+}

File src/tactic/arith/add_bounds_tactic.h

+/*++
+Copyright (c) 2011 Microsoft Corporation
+
+Module Name:
+
+    add_bounds.h
+
+Abstract:
+
+    Tactic for bounding unbounded variables.
+
+Author:
+
+    Leonardo de Moura (leonardo) 2011-06-30.
+
+Revision History:
+
+--*/
+#ifndef _ADD_BOUNDS_H_
+#define _ADD_BOUNDS_H_
+
+#include"params.h"
+
+class ast_manager;
+class goal;
+class tactic;
+class probe;
+
+bool is_unbounded(goal const & g);
+probe * mk_is_unbounded_probe();
+
+tactic * mk_add_bounds_tactic(ast_manager & m, params_ref const & p = params_ref());
+
+#endif

File src/tactic/arith/bound_manager.cpp

+/*++
+Copyright (c) 2011 Microsoft Corporation
+
+Module Name:
+
+    bound_manager.cpp
+
+Abstract:
+
+    Collect bounds.
+
+Author:
+
+    Leonardo (leonardo) 2011-05-16
+
+Notes:
+
+--*/
+#include"bound_manager.h"
+#include"ast_smt2_pp.h"
+#include"goal.h"
+
+bound_manager::bound_manager(ast_manager & m):
+    m_util(m) {
+}
+
+bound_manager::~bound_manager() {
+    reset();
+}
+
+static decl_kind swap_decl(decl_kind k) {
+    switch (k) {
+    case OP_LE: return OP_GE;
+    case OP_LT: return OP_GT;
+    case OP_GE: return OP_LE;
+    case OP_GT: return OP_LT;
+    default:
+        UNREACHABLE();
+        return k;
+    }
+}
+
+decl_kind bound_manager::neg(decl_kind k) {
+    switch (k) {
+    case OP_LE: return OP_GT;
+    case OP_LT: return OP_GE;
+    case OP_GE: return OP_LT;
+    case OP_GT: return OP_LE;
+    default:
+        UNREACHABLE();
+        return k;
+    }
+}
+
+void bound_manager::norm(numeral & n, decl_kind & k) {
+    switch (k) {
+    case OP_LE: return;
+    case OP_GE: return;
+    case OP_LT: 
+        // x < n --> x <= n-1
+        n--;
+        k = OP_LE;
+        return;
+    case OP_GT:
+        // x > n --> x >= n+1
+        n++;
+        k = OP_GE;
+        return;
+    default:
+        return;
+    }
+}
+
+static bool is_lower(decl_kind k) {
+    return k == OP_GT || k == OP_GE;
+}
+
+static bool is_strict(decl_kind k) {
+    return k == OP_LT || k == OP_GT;
+} 
+
+void bound_manager::operator()(expr * f, expr_dependency * d) {
+    TRACE("bound_manager", tout << "processing:\n" << mk_ismt2_pp(f, m()) << "\n";);
+    expr * v;
+    numeral n;
+    if (is_disjunctive_bound(f, d))
+        return;
+    bool pos = true;    
+    while (m().is_not(f, f))
+        pos = !pos;
+    if (!is_app(f))
+        return;
+    app * t = to_app(f);
+    if (t->get_family_id() != m_util.get_family_id())
+        return;
+    decl_kind k = t->get_decl_kind();
+    if (k != OP_LE && k != OP_GE && k != OP_LT && k != OP_GT)
+        return;
+    expr * lhs = t->get_arg(0);
+    expr * rhs = t->get_arg(1);
+    bool is_int;
+    if (is_uninterp_const(lhs) && m_util.is_numeral(rhs, n, is_int)) {
+        v = lhs;
+    }
+    else if (is_uninterp_const(rhs) && m_util.is_numeral(lhs, n, is_int)) {
+        v = rhs;
+        k = swap_decl(k);
+    }
+    else {
+        return;
+    }
+    if (!pos)
+        k = neg(k);
+    if (is_int)
+        norm(n, k);
+    TRACE("bound_manager", tout << "found bound for:\n" << mk_ismt2_pp(v, m()) << "\n";);
+    bool strict = is_strict(k);
+    if (is_lower(k)) {
+        insert_lower(v, strict, n, d);
+    }
+    else {
+        insert_upper(v, strict, n, d);
+    }
+}
+
+void bound_manager::insert_upper(expr * v, bool strict, numeral const & n, expr_dependency * d) {
+    limit old;
+    if (m_uppers.find(v, old)) {
+        if (n < old.first || (n == old.first && strict && !old.second)) {
+            // improved bound
+            m_uppers.insert(v, limit(n, strict));
+            if (d)
+                m_upper_deps.insert(v, d);
+        }
+    }
+    else {
+        m_uppers.insert(v, limit(n, strict));
+        if (d)
+            m_upper_deps.insert(v, d);
+        if (!m_lowers.contains(v)) {
+            m_bounded_vars.push_back(v);
+            m().inc_ref(v);
+        }
+    }
+}
+
+void bound_manager::insert_lower(expr * v, bool strict, numeral const & n, expr_dependency * d) {
+    limit old;
+    if (m_lowers.find(v, old)) {
+        if (n > old.first || (n == old.first && strict && !old.second)) {
+            // improved bound
+            m_lowers.insert(v, limit(n, strict));
+            if (d)
+                m_lower_deps.insert(v, d);
+        }
+    }
+    else {
+        m_lowers.insert(v, limit(n, strict));
+        if (d)
+            m_lower_deps.insert(v, d);
+        if (!m_uppers.contains(v)) {
+            m_bounded_vars.push_back(v);
+            m().inc_ref(v);
+        }
+    }
+}
+
+bool bound_manager::is_disjunctive_bound(expr * f, expr_dependency * d) {
+    numeral lo, hi, n;
+    if (!m().is_or(f)) return false;
+    unsigned sz = to_app(f)->get_num_args();
+    if (sz == 0) return false;
+    expr * x, * y, * v = 0;
+    bool is_int;
+    for (unsigned i = 0; i < sz; ++i) {
+        expr * e = to_app(f)->get_arg(i);
+        if (!m().is_eq(e, x, y)) return false;
+        if (is_uninterp_const(x) && 
+            m_util.is_numeral(y, n, is_int) && is_int && 
+            (x == v || v == 0)) {
+            if (v == 0) { v = x; lo = hi = n; }
+            if (n < lo) lo = n;
+            if (n > hi) hi = n;
+        }
+        else if (is_uninterp_const(y) && 
+                 m_util.is_numeral(x, n, is_int) && is_int && 
+                 (y == v || v == 0)) {
+            if (v == 0) { v = y; lo = hi = n; }
+            if (n < lo) lo = n;
+            if (n > hi) hi = n;
+        }
+        else {
+            return false;
+        }
+    }
+    TRACE("bound_manager", tout << "bounds: " << lo << " " << hi << "\n";);
+    insert_lower(v, false, lo, d);
+    insert_upper(v, false, hi, d);
+    return true;
+}
+
+void bound_manager::operator()(goal const & g) {
+    unsigned sz = g.size();
+    for (unsigned i = 0; i < sz; i++) {
+        operator()(g.form(i), g.dep(i));
+    }
+}
+
+void bound_manager::reset() {
+    m().dec_array_ref(m_bounded_vars.size(), m_bounded_vars.c_ptr());
+    m_bounded_vars.finalize();
+    m_lowers.finalize();
+    m_uppers.finalize();
+    m_lower_deps.finalize();
+    m_upper_deps.finalize();
+}
+
+void bound_manager::display(std::ostream & out) const {
+    numeral n; bool strict;
+    for (iterator it = begin(); it != end(); ++it) {
+        expr * v = *it;
+        if (has_lower(v, n, strict))
+            out << n << " " << (strict ? "<" : "<=");
+        else
+            out << "-oo <";
+        out << " " << mk_ismt2_pp(v, m()) << " ";
+        if (has_upper(v, n, strict))
+            out << (strict ? "<" : "<=") << " " << n;
+        else
+            out << "< oo";
+        out << "\n";
+    }
+}

File src/tactic/arith/bound_manager.h

+/*++
+Copyright (c) 2011 Microsoft Corporation
+
+Module Name:
+
+    bound_manager.h
+
+Abstract:
+
+    Collect bounds.
+
+Author:
+
+    Leonardo (leonardo) 2011-05-16
+
+Notes:
+
+--*/
+#ifndef _BOUND_MANAGER_H_
+#define _BOUND_MANAGER_H_
+
+#include"ast.h"
+#include"arith_decl_plugin.h"
+
+class goal;
+
+class bound_manager {
+public:
+    typedef rational     numeral;
+private:
+    typedef std::pair<numeral, bool> limit;
+    arith_util           m_util;
+    obj_map<expr, limit> m_lowers;
+    obj_map<expr, limit> m_uppers;
+    obj_map<expr, expr_dependency*> m_lower_deps;
+    obj_map<expr, expr_dependency*> m_upper_deps;
+    ptr_vector<expr>     m_bounded_vars;
+    bool is_disjunctive_bound(expr * f, expr_dependency * d);
+    void insert_lower(expr * v, bool strict, numeral const & n, expr_dependency * d);
+    void insert_upper(expr * v, bool strict, numeral const & n, expr_dependency * d);
+public:
+    static decl_kind neg(decl_kind k);
+    static void norm(numeral & n, decl_kind & k);
+
+    bound_manager(ast_manager & m);
+    ~bound_manager();
+    
+    ast_manager & m() const { return m_util.get_manager(); }
+    
+    void operator()(goal const & g);
+    void operator()(expr * n, expr_dependency * d = 0);
+    
+    bool has_lower(expr * c, numeral & v, bool & strict) const {
+        limit l;
+        if (m_lowers.find(c, l)) {
+            v = l.first;
+            strict = l.second;
+            return true;
+        }
+        return false;
+    }
+
+    bool has_upper(expr * c, numeral & v, bool & strict) const {
+        limit l;
+        if (m_uppers.find(c, l)) {
+            v = l.first;
+            strict = l.second;
+            return true;
+        }
+        return false;
+    }
+
+    expr_dependency * lower_dep(expr * c) const {
+        expr_dependency * d;
+        if (m_lower_deps.find(c, d))
+            return d;
+        return 0;
+    }
+
+    expr_dependency * upper_dep(expr * c) const {
+        expr_dependency * d;
+        if (m_upper_deps.find(c, d))
+            return d;
+        return 0;
+    }
+    
+    bool has_lower(expr * c) const {
+        return m_lowers.contains(c);
+    }
+
+    bool has_upper(expr * c) const {
+        return m_uppers.contains(c);
+    }
+    
+    typedef ptr_vector<expr>::const_iterator iterator;
+    
+    /**
+       \brief Iterator for all bounded constants.
+    */
+    iterator begin() const { return m_bounded_vars.begin(); }
+    iterator end() const { return m_bounded_vars.end(); }
+    
+    void reset();
+
+    // for debugging purposes
+    void display(std::ostream & out) const;
+};
+
+#endif

File src/tactic/arith/bound_propagator.cpp

+/*++
+Copyright (c) 2011 Microsoft Corporation
+
+Module Name:
+
+    bound_propagator.cpp
+
+Abstract:
+
+    Bound propagators for arithmetic.
+    Support class for implementing strategies and search procedures
+
+Author:
+
+    Leonardo de Moura (leonardo) 2011-06-18.
+
+Revision History:
+
+--*/
+#include"bound_propagator.h"
+#include<cmath>
+
+// -------------------------------
+// Bound Relaxation configuration
+//
+// The idea is to minimize errors in floating point computations
+//
+// If RELAX_BOUNDS is undefined, then bound relaxation is disabled.
+// Otherwise, lower bounds l are relaxed using the formula
+//    PRECISION * floor(l * INV_PRECISION + TOLERANCE)
+// and upper bounds u as:
+//    PRECISION * ceil(u * INV_PRECISION - TOLERANCE)
+// In the LP literature, the suggested values are
+//  l :=  10^-5 * floor(l*10^5 + 10^-6)
+//  u :=  10^-5 * ceil(u*10^5 - 10^-6)
+// I'm using the following values because of strict bounds
+//  l :=  10^-6 * floor(l*10^6 + 10^-7)
+//  u :=  10^-6 * ceil(u*10^6 - 10^-7)
+#define RELAX_BOUNDS
+#define TOLERANCE 0.0000001
+#define PRECISION 0.000001
+#define INV_PRECISION 1000000.0
+// -------------------------------
+
+bound_propagator::bound::bound(numeral_manager & m,
+                               mpq const & k, 
+                               double approx_k,
+                               bool lower, 
+                               bool strict, 
+                               unsigned lvl, 
+                               unsigned ts, 
+                               bkind bk, 
+                               unsigned c_idx,
+                               assumption a, 
+                               bound * prev):
+    m_approx_k(approx_k),
+    m_lower(lower),
+    m_strict(strict),
+    m_kind(bk),
+    m_level(lvl),
+    m_timestamp(ts),
+    m_prev(prev) {
+    m.set(m_k, k);
+    if (bk == DERIVED)
+        m_constraint_idx = c_idx;
+    else
+        m_assumption = a;
+}
+
+bound_propagator::bound_propagator(numeral_manager & _m, allocator & a, params_ref const & p):
+    m(_m),
+    m_allocator(a), 
+    m_eq_manager(m, a) {
+    m_timestamp = 0;
+    m_qhead     = 0;
+    m_conflict  = null_var;
+    updt_params(p);
+    reset_statistics();
+}
+
+bound_propagator::~bound_propagator() {
+    m.del(m_tmp);
+    reset();
+}
+
+void bound_propagator::del_constraints_core() {
+    constraint_vector::iterator it  = m_constraints.begin();
+    constraint_vector::iterator end = m_constraints.end();
+    for (; it != end; ++it) {
+        del_constraint(*it);
+    }
+    m_constraints.reset();
+}
+
+void bound_propagator::del_constraints() {
+    SASSERT(scope_lvl() == 0);
+    if (m_constraints.empty())
+        return;
+    del_constraints_core();
+    m_constraints.finalize();
+    vector<wlist>::iterator it  = m_watches.begin();
+    vector<wlist>::iterator end = m_watches.end();
+    for (; it != end; ++it)
+        it->finalize();
+}
+
+void bound_propagator::del_constraint(constraint & c) {
+    switch (c.m_kind) {
+    case LINEAR:
+        m_eq_manager.del(c.m_eq);
+        break;
+    default:
+        UNREACHABLE();
+        break;
+    }
+}
+    
+void bound_propagator::updt_params(params_ref const & p) {
+    m_max_refinements = p.get_uint(":bound-max-refinements", 16);
+    m_threshold       = p.get_double(":bound-threshold", 0.05);
+    m_small_interval  = p.get_double(":bound-small-interval", 128);
+    m_strict2double   = p.get_double(":strict2double", 0.00001);
+}
+
+void bound_propagator::get_param_descrs(param_descrs & r) {
+    r.insert(":bound-max-refinements", CPK_UINT, "(default: 16) maximum number of bound refinements (per round) for unbounded variables.");
+    r.insert(":bound-threshold", CPK_DOUBLE, "(default: 0.05) bound propagation improvement threshold ratio.");
+}
+
+void bound_propagator::collect_statistics(statistics & st) const {
+    st.update("bound conflicts", m_conflicts);
+    st.update("bound propagations", m_propagations);
+    st.update("bound false alarms", m_false_alarms);
+}
+
+void bound_propagator::reset_statistics() {
+    m_conflicts = 0;
+    m_propagations = 0;
+    m_false_alarms = 0;
+}
+
+void bound_propagator::mk_var(var x, bool is_int) {
+    m_is_int.reserve(x+1, false);
+    m_dead.reserve(x+1, true);
+    m_lowers.reserve(x+1, 0);
+    m_uppers.reserve(x+1, 0);
+    m_lower_refinements.reserve(x+1, 0);
+    m_upper_refinements.reserve(x+1, 0);
+    m_watches.reserve(x+1);
+
+    SASSERT(m_dead[x]);
+
+    m_is_int[x] = is_int;
+    m_dead[x]   = false;
+    m_lowers[x] = 0;
+    m_uppers[x] = 0;
+    m_lower_refinements[x] = 0;
+    m_upper_refinements[x] = 0;
+    m_watches[x].reset();
+}
+
+void bound_propagator::del_var(var x) {
+    SASSERT(!m_dead[x]);
+    m_dead[x] = true;
+    // mark constraints containing x as dead.
+    wlist & wl = m_watches[x];
+    wlist::iterator it  = wl.begin();
+    wlist::iterator end = wl.end();
+    for (; it != end; ++it) {
+        m_constraints[*it].m_dead = true;
+    }
+}
+
+void bound_propagator::mk_eq(unsigned sz, mpq * as, var * xs) {
+    linear_equation * eq = m_eq_manager.mk(sz, as, xs);
+    init_eq(eq);
+}
+
+void bound_propagator::mk_eq(unsigned sz, mpz * as, var * xs) {
+    linear_equation * eq = m_eq_manager.mk(sz, as, xs);
+    init_eq(eq);
+}
+
+void bound_propagator::init_eq(linear_equation * eq) {
+    if (eq == 0)
+        return;
+    unsigned c_idx = m_constraints.size();
+    m_constraints.push_back(constraint());
+    constraint & new_c  = m_constraints.back();
+    new_c.m_kind        = LINEAR;
+    new_c.m_dead        = false;
+    new_c.m_timestamp   = 0;
+    new_c.m_act         = 0;
+    new_c.m_counter     = 0;
+    new_c.m_eq          = eq;
+    unsigned sz = eq->size();
+    for (unsigned i = 0; i < sz; i++) {
+        m_watches[eq->x(i)].push_back(c_idx);
+    }
+    if (propagate(c_idx) && scope_lvl() > 0)
+        m_reinit_stack.push_back(c_idx);
+}
+
+void bound_propagator::push() {
+    m_scopes.push_back(scope());
+    scope & s = m_scopes.back();
+    s.m_trail_limit        = m_trail.size();
+    s.m_qhead_old          = m_qhead;
+    s.m_reinit_stack_limit = m_reinit_stack.size();
+    s.m_timestamp_old      = m_timestamp;
+    s.m_in_conflict        = inconsistent();
+}
+
+void bound_propagator::undo_trail(unsigned old_sz) {
+    SASSERT(old_sz <= m_trail.size());
+    unsigned i = m_trail.size();
+    while (i > old_sz) {
+        --i;
+        trail_info & info = m_trail.back();
+        var x         = info.x();
+        bool is_lower = info.is_lower();
+        m_trail.pop_back();
+        bound * b;
+        if (is_lower) {
+            b = m_lowers[x];
+            m_lowers[x] = b->m_prev;
+        }
+        else {
+            b = m_uppers[x];
+            m_uppers[x] = b->m_prev;
+        }
+        m.del(b->m_k);
+        b->~bound();
+        m_allocator.deallocate(sizeof(bound), b);
+    }
+    SASSERT(m_trail.size() == old_sz);
+}
+
+void bound_propagator::pop(unsigned num_scopes) {
+    unsigned lvl     = scope_lvl();
+    SASSERT(num_scopes <= lvl);
+    unsigned new_lvl = lvl - num_scopes;
+    scope & s        = m_scopes[new_lvl];
+    undo_trail(s.m_trail_limit);
+    m_timestamp = s.m_timestamp_old;
+    m_qhead     = s.m_qhead_old;
+    if (!s.m_in_conflict)
+        m_conflict = null_var;
+    unsigned reinit_stack_sz = s.m_reinit_stack_limit;
+    m_scopes.shrink(new_lvl);
+
+    // reinitialize
+    unsigned i  = reinit_stack_sz;
+    unsigned j  = reinit_stack_sz;
+    unsigned sz = m_reinit_stack.size();
+    for (; i < sz; i++) {
+        unsigned c_idx = m_reinit_stack[i];
+        bool p = propagate(c_idx);
+        if (new_lvl > 0 && p) {
+            m_reinit_stack[j] = c_idx;
+            j++;
+        }
+    }
+    m_reinit_stack.shrink(j);
+}
+
+bool bound_propagator::assert_lower_core(var x, mpq & k, bool strict, bkind bk, unsigned c_idx, assumption a) {
+    if (is_int(x)) {
+        if (m.is_int(k)) {
+            if (strict)
+                m.inc(k);
+        }
+        else {
+            m.ceil(k, k);
+        }
+        SASSERT(m.is_int(k));
+        strict = false;
+    }
+    TRACE("bound_propagator_detail", tout << "new lower x" << x << " " << m.to_string(k) << " strict: " << strict << "\n";);
+
+    bound * old_lower = m_lowers[x];
+    if (old_lower) {
+        bool improves = m.gt(k, old_lower->m_k) || (!old_lower->m_strict && strict && m.eq(k, old_lower->m_k));
+        if (!improves) {
+            if (bk == DERIVED) {
+                TRACE("bound_propagator_detail", tout << "false alarm\n";);
+                m_false_alarms++;
+            }
+            return false;
+        }
+    }
+    
+    if (bk == DERIVED) {
+        TRACE("bound_propagator_derived", tout << "new lower x" << x << " " << m.to_string(k) << " strict: " << strict << "\n";);
+        m_propagations++;
+    }
+
+    if (scope_lvl() == 0 && bk == DERIVED)
+        bk = AXIOM; // don't need justification at level 0
+
+    double approx_k = m.get_double(k);
+    TRACE("new_bound", tout << "x" << x << " lower: " << m.to_string(k) << " approx: " << approx_k << "\n";);
+#ifdef RELAX_BOUNDS
+    approx_k = PRECISION*floor(approx_k*INV_PRECISION + TOLERANCE);
+    TRACE("new_bound", tout << "x" << x << " lower: " << m.to_string(k) << " relaxed approx: " << approx_k << "\n";);
+#endif
+    void  * mem = m_allocator.allocate(sizeof(bound));
+    bound * new_lower = new (mem) bound(m, k, approx_k, true, strict, scope_lvl(), m_timestamp, bk, c_idx, a, old_lower);
+    m_timestamp++;
+    m_lowers[x] = new_lower;
+    m_trail.push_back(trail_info(x, true));
+    m_lower_refinements[x]++;
+    check_feasibility(x);
+
+    return true;
+}
+
+bool bound_propagator::assert_upper_core(var x, mpq & k, bool strict, bkind bk, unsigned c_idx, assumption a) {
+    if (is_int(x)) {
+        if (m.is_int(k)) {
+            if (strict)
+                m.dec(k);
+        }
+        else {
+            m.floor(k, k);
+        }
+        SASSERT(m.is_int(k));
+        strict = false;
+    }
+
+    TRACE("bound_propagator_detail", tout << "new upper x" << x << " " << m.to_string(k) << " strict: " << strict << "\n";);
+
+    bound * old_upper = m_uppers[x];
+    if (old_upper) {
+        bool improves = m.lt(k, old_upper->m_k) || (!old_upper->m_strict && strict && m.eq(k, old_upper->m_k));
+        if (!improves) {
+            if (bk == DERIVED) {
+                TRACE("bound_propagator_detail", tout << "false alarm\n";);
+                m_false_alarms++;
+            }
+            return false;
+        }
+    }
+
+    if (bk == DERIVED) {
+        m_propagations++;
+        TRACE("bound_propagator_derived", tout << "new upper x" << x << " " << m.to_string(k) << " strict: " << strict << "\n";);
+    }
+
+    if (scope_lvl() == 0 && bk == DERIVED)
+        bk = AXIOM; // don't need justification at level 0
+
+    double approx_k = m.get_double(k);
+    TRACE("new_bound", tout << "x" << x << " upper: " << m.to_string(k) << " approx: " << approx_k << "\n";);
+#ifdef RELAX_BOUNDS
+    approx_k = PRECISION*ceil(approx_k*INV_PRECISION - TOLERANCE);
+    TRACE("new_bound", tout << "x" << x << " upper: " << m.to_string(k) << " relaxed approx: " << approx_k << "\n";);
+#endif
+    
+    void  * mem = m_allocator.allocate(sizeof(bound));
+    bound * new_upper = new (mem) bound(m, k, approx_k, false, strict, scope_lvl(), m_timestamp, bk, c_idx, a, m_uppers[x]);
+    m_timestamp++;
+    m_uppers[x] = new_upper;
+    m_trail.push_back(trail_info(x, false));
+    m_upper_refinements[x]++;
+    check_feasibility(x);
+    return true;
+}
+
+bool bound_propagator::get_interval_size(var x, double & r) const {
+    bound * l = m_lowers[x];
+    bound * u = m_uppers[x];
+    if (l && u) {
+        r = u->m_approx_k - l->m_approx_k;
+        return true;
+    }
+    return false;
+}
+
+template<bool LOWER>
+bool bound_propagator::relevant_bound(var x, double new_k) const {
+    TRACE("bound_propagator_detail", tout << "relevant_bound x" << x << " " << new_k << " LOWER: " << LOWER << "\n";
+          if (LOWER && has_lower(x)) tout << "old: " << m.to_string(m_lowers[x]->m_k) << " | " << m_lowers[x]->m_approx_k << "\n";
+          if (!LOWER && has_upper(x)) tout << "old: " << m.to_string(m_uppers[x]->m_k) << " | " << m_uppers[x]->m_approx_k << "\n";);
+    bound * b = LOWER ? m_lowers[x] : m_uppers[x];
+    if (b == 0)
+        return true; // variable did not have a bound
+    
+    double interval_size;
+    bool bounded = get_interval_size(x, interval_size);
+
+    if (!is_int(x)) {
+        // check if the improvement is significant
+        double improvement;
+        double abs_k = b->m_approx_k;
+        if (abs_k < 0.0) 
+            abs_k -= abs_k;
+        if (bounded)
+            improvement = m_threshold * std::max(std::min(interval_size, abs_k), 1.0);
+        else
+            improvement = m_threshold * std::max(abs_k, 1.0);
+        
+        if (LOWER) {
+            if (new_k <= b->m_approx_k + improvement) {
+                TRACE("bound_propagator", tout << "LOWER new: " << new_k << " old: " << b->m_approx_k << " improvement is too small\n";);
+                return false; // improvement is too small
+            }
+        }
+        else {
+            if (new_k >= b->m_approx_k - improvement) {
+                TRACE("bound_propagator", tout << "UPPER new: " << new_k << " old: " << b->m_approx_k << " improvement is too small\n";);
+                return false; // improvement is too small
+            }
+        }
+    }
+    else {
+        if (LOWER) {
+            if (new_k < b->m_approx_k + 1.0)
+                return false; // no improvement
+        }
+        else {
+            if (new_k > b->m_approx_k - 1.0)
+                return false; // no improvement
+        }
+    }
+    
+    if (bounded && interval_size <= m_small_interval)
+        return true;
+    
+    if (LOWER)
+        return m_lower_refinements[x] < m_max_refinements;
+    else
+        return m_upper_refinements[x] < m_max_refinements;
+}
+
+bool bound_propagator::relevant_lower(var x, double approx_k) const {
+    return relevant_bound<true>(x, approx_k);
+}
+
+bool bound_propagator::relevant_upper(var x, double approx_k) const {
+    return relevant_bound<false>(x, approx_k);
+}
+
+void bound_propagator::check_feasibility(var x) {
+    if (inconsistent())
+        return;
+    bound * l = m_lowers[x];
+    bound * u = m_uppers[x];
+    if (l && u) {
+        if (m.lt(l->m_k, u->m_k))
+            return;
+        if (!l->m_strict && !u->m_strict && m.eq(l->m_k, u->m_k))
+            return;
+        m_conflict = x;
+        m_conflicts++;
+        SASSERT(inconsistent());
+        TRACE("bound_propagator", tout << "inconsistency detected: x" << x << "\n"; display(tout););
+    }
+}
+
+void bound_propagator::propagate() {
+    m_to_reset_ts.reset();
+
+    while (m_qhead < m_trail.size()) {
+        if (inconsistent())
+            break;
+        trail_info & info = m_trail[m_qhead];
+        var x = info.x();
+        bool is_lower = info.is_lower();
+        bound * b   = is_lower ? m_lowers[x] : m_uppers[x];
+        SASSERT(b);
+        unsigned ts = b->m_timestamp; 
+        TRACE("bound_propagator_detail", tout << "propagating x" << x << "\n";);
+        m_qhead++;
+        wlist const & wl = m_watches[x];
+        wlist::const_iterator it  = wl.begin();
+        wlist::const_iterator end = wl.end();
+        for (; it != end; ++it) {
+            unsigned c_idx = *it;
+            constraint & c = m_constraints[c_idx];
+            // We don't need to visit c if it was already propagated using b.
+            // Whenever we visit c we store in c.m_timestamp the current timestamp
+            // So, we know that c was already propagated any bound using bounds with timestamp lower than c.m_timestamp.
+            if (ts >= c.m_timestamp) {
+                if (c.m_timestamp == 0)
+                    m_to_reset_ts.push_back(c_idx);
+                c.m_timestamp = m_timestamp; 
+                propagate(c_idx);
+            }
+        }
+    }
+
+    unsigned_vector::iterator it  =  m_to_reset_ts.begin();
+    unsigned_vector::iterator end =  m_to_reset_ts.end();
+    for (; it != end; ++it)
+        m_constraints[*it].m_timestamp = 0;
+}
+
+bool bound_propagator::propagate(unsigned c_idx) {
+    constraint const & c = m_constraints[c_idx];
+    if (c.m_dead)
+        return false;
+    if (c.m_kind == LINEAR)
+        return propagate_eq(c_idx);
+    return false;
+}
+
+bool bound_propagator::propagate_eq(unsigned c_idx) {
+    constraint const & c = m_constraints[c_idx];
+    linear_equation * eq = c.m_eq;
+
+#if 0
+    {
+        static unsigned counter = 0;
+        static unsigned visited = 0;
+        counter++;
+        visited += eq->size();
+        if (counter % 1000 == 0)
+            verbose_stream() << "[bound-propagator] :propagate-eq " << counter << " :visited-vars " << visited << std::endl;
+    }
+#endif
+
+    TRACE("bound_propagator_detail", tout << "propagating using eq: "; m_eq_manager.display(tout, *eq); tout << "\n";);
+    // ll = (Sum_{a_i < 0} -a_i*lower(x_i)) + (Sum_{a_i > 0} -a_i * upper(x_i)) 
+    // uu = (Sum_{a_i > 0} -a_i*lower(x_i)) + (Sum_{a_i < 0} -a_i * upper(x_i)) 
+    unsigned ll_i = UINT_MAX; // position of the variable that couldn't contribute to ll
+    unsigned uu_i = UINT_MAX; // position of the variable that coundn't contribute to uu
+    bool ll_failed = false;
+    bool uu_failed = false;
+    double ll = 0.0;
+    double uu = 0.0;
+    unsigned sz = eq->size();
+    for (unsigned i = 0; i < sz; i++) {
+        var x_i     = eq->x(i);
+        double a_i  = eq->approx_a(i);
+        bound * l_i = m_lowers[x_i];
+        bound * u_i = m_uppers[x_i];
+        if (a_i < 0.0) {
+            if (!ll_failed) {
+                if (l_i == 0) {
+                    if (ll_i == UINT_MAX)
+                        ll_i = i;
+                    else
+                        ll_failed = true;
+                }
+                else {
+                    ll -= a_i * l_i->m_approx_k;
+                }
+            }
+            
+            if (!uu_failed) {
+                if (u_i == 0) {
+                    if (uu_i == UINT_MAX)
+                        uu_i = i;
+                    else
+                        uu_failed = true;
+                }
+                else {
+                    uu -= a_i * u_i->m_approx_k;
+                }
+            }
+        }
+        else {
+            if (!ll_failed) {
+                if (u_i == 0) {
+                    if (ll_i == UINT_MAX)
+                        ll_i = i;
+                    else
+                        ll_failed = true;
+                }
+                else {
+                    ll -= a_i * u_i->m_approx_k;
+                }
+            }
+
+            if (!uu_failed) {
+                if (l_i == 0) {
+                    if (uu_i == UINT_MAX)
+                        uu_i = i;
+                    else
+                        uu_failed = true;
+                }
+                else {
+                    uu -= a_i * l_i->m_approx_k;
+                }
+            }
+        }
+        if (ll_failed && uu_failed)
+            return false; // nothing to propagate
+    }
+
+    bool propagated = false;
+
+    SASSERT(!ll_failed || !uu_failed);
+    if (ll_i == UINT_MAX || uu_i == UINT_MAX) {
+        for (unsigned i = 0; i < sz; i++) {
+            var x_i     = eq->x(i);
+            double a_i  = eq->approx_a(i);
+            bound * l_i = m_lowers[x_i];
+            bound * u_i = m_uppers[x_i];
+            // ll = (Sum_{a_i < 0} -a_i*lower(x_i)) + (Sum_{a_i > 0} -a_i * upper(x_i)) 
+            // uu = (Sum_{a_i > 0} -a_i*lower(x_i)) + (Sum_{a_i < 0} -a_i * upper(x_i)) 
+            if (ll_i == UINT_MAX) {
+                // can propagate a lower bound for a_i*x_i
+                if (a_i > 0.0) {
+                    // can propagate a lower bound for x_i
+                    double new_k = (ll + a_i * u_i->m_approx_k)/a_i;
+                    if (relevant_lower(x_i, new_k) && propagate_lower(c_idx, i))
+                        propagated = true;
+                }
+                else {
+                    // a_i < 0.0
+                    // can propagate a upper bound for x_i
+                    double new_k = (ll + a_i * l_i->m_approx_k)/a_i;
+                    if (relevant_upper(x_i, new_k) && propagate_upper(c_idx, i))
+                        propagated = true;
+                }
+            }
+            if (uu_i == UINT_MAX) {
+                // can propagate an upper bound for a_i*x_i
+                if (a_i > 0.0) {
+                    // can propagate a upper bound for x_i
+                    double new_k = (uu + a_i * l_i->m_approx_k)/a_i;
+                    if (relevant_upper(x_i, new_k) && propagate_upper(c_idx, i))
+                        propagated = true;
+                }
+                else {
+                    // a_i < 0.0
+                    // can propagate a lower bound for x_i
+                    double new_k = (uu + a_i * u_i->m_approx_k)/a_i;
+                    if (relevant_lower(x_i, new_k) && propagate_lower(c_idx, i))
+                        propagated = true;
+                }
+            }
+        }
+    }
+
+    if (!ll_failed && ll_i != UINT_MAX) {
+        // can propagate a lower bound for the monomial at position ll_i
+        var x_i      = eq->x(ll_i);
+        double a_i   = eq->approx_a(ll_i);
+        double new_k = ll/a_i;
+        if (a_i > 0.0) {
+            if (relevant_lower(x_i, new_k) && propagate_lower(c_idx, ll_i))
+                propagated = true;
+        }
+        else {
+            if (relevant_upper(x_i, new_k) && propagate_upper(c_idx, ll_i))
+                propagated = true;
+        }
+    }
+
+    if (!uu_failed && uu_i != UINT_MAX) {
+        // can propagate a upper bound for the monomial at position uu_i
+        var x_i      = eq->x(uu_i);
+        double a_i   = eq->approx_a(uu_i);
+        double new_k = uu/a_i;
+        if (a_i > 0.0) {
+            if (relevant_upper(x_i, new_k) && propagate_upper(c_idx, uu_i))
+                propagated = true;
+        }
+        else {
+            if (relevant_lower(x_i, new_k) && propagate_lower(c_idx, uu_i))
+                propagated = true;
+        }
+    }
+    
+    return propagated;
+}
+
+/**
+   \brief Try to propagate a lower bound for the variable stored at position i, using mpq's (rationals).
+   When this method is invoked, we know that all other variables have the "right" bounds, and
+   using doubles we improve the current known bound.
+*/
+bool bound_propagator::propagate_lower(unsigned c_idx, unsigned i) {
+    constraint const & c = m_constraints[c_idx];
+    linear_equation * eq = c.m_eq;
+    var x_i = eq->x(i);
+    mpz const & a_i = eq->a(i);
+    unsigned sz = eq->size();
+    mpq k;
+    bool strict = false;
+    bool neg_a_i = m.is_neg(a_i);
+    for (unsigned j = 0; j < sz; j++) {
+        if (i == j)
+            continue;
+        var x_j = eq->x(j);
+        mpz const & a_j = eq->a(j);
+        bound * b_j = (m.is_neg(a_j) == neg_a_i) ? m_uppers[x_j] : m_lowers[x_j];
+        TRACE("bound_propagator_step_detail", tout << "k: " << m.to_string(k) << " b_j->m_k: " << m.to_string(b_j->m_k) << 
+              " a_j: " << m.to_string(a_j) << "\n";);
+        SASSERT(b_j);
+        if (b_j->m_strict)
+            strict = true;
+        m.addmul(k, a_j, b_j->m_k, k);
+    }
+    TRACE("bound_propagator_step_detail", tout << "k: " << m.to_string(k) << "\n";);
+    m.neg(k);
+    m.div(k, a_i, k);
+    TRACE("bound_propagator_step", tout << "propagating lower x" << x_i << " " << m.to_string(k) << " strict: " << strict << " using\n";
+          m_eq_manager.display(tout, *eq); tout << "\n"; display_bounds_of(tout, *eq););
+    bool r = assert_lower_core(x_i, k, strict, DERIVED, c_idx, null_assumption);
+    m.del(k);
+    return r;
+}
+
+/**
+   \brief Try to propagate a upper bound for the variable stored at position i, using mpq's (rationals).
+   When this method is invoked, we know that all other variables have the "right" bounds, and
+   using doubles we improve the current known bound.
+*/
+bool bound_propagator::propagate_upper(unsigned c_idx, unsigned i) {
+    constraint const & c = m_constraints[c_idx];
+    linear_equation * eq = c.m_eq;
+    var x_i = eq->x(i);
+    mpz const & a_i = eq->a(i);
+    unsigned sz = eq->size();
+    mpq k;
+    bool strict = false;
+    bool neg_a_i = m.is_neg(a_i);
+    for (unsigned j = 0; j < sz; j++) {
+        if (i == j)
+            continue;
+        var x_j = eq->x(j);
+        mpz const & a_j = eq->a(j);
+        bound * b_j = (m.is_neg(a_j) == neg_a_i) ? m_lowers[x_j] : m_uppers[x_j];
+        SASSERT(b_j);
+        if (b_j->m_strict)
+            strict = true;
+        m.addmul(k, a_j, b_j->m_k, k);
+    }
+    m.neg(k);
+    m.div(k, a_i, k);
+    TRACE("bound_propagator_step", tout << "propagating upper x" << x_i << " " << m.to_string(k) << " strict: " << strict << " using\n";
+          m_eq_manager.display(tout, *eq); tout << "\n"; display_bounds_of(tout, *eq););
+    bool r = assert_upper_core(x_i, k, strict, DERIVED, c_idx, null_assumption);
+    m.del(k);
+    return r;
+}
+
+void bound_propagator::reset() {
+    undo_trail(0);
+    del_constraints_core();
+    m_constraints.finalize();
+    m_is_int.finalize();
+    m_dead.finalize();
+    m_lowers.finalize();
+    m_uppers.finalize();
+    m_watches.finalize();
+    m_trail.finalize();
+    m_qhead = 0;
+    m_reinit_stack.finalize();
+    m_lower_refinements.finalize();
+    m_upper_refinements.finalize();
+    m_timestamp = 0;
+    m_conflict = null_var;
+    m_scopes.finalize();
+}
+
+bool bound_propagator::lower(var x, mpq & k, bool & strict, unsigned & ts) const {
+    bound * b = m_lowers[x];
+    if (!b)
+        return false;
+    m.set(k, b->m_k);
+    strict = b->m_strict;
+    ts = b->m_timestamp;
+    return true;
+}
+
+bool bound_propagator::upper(var x, mpq & k, bool & strict, unsigned & ts) const {
+    bound * b = m_uppers[x];
+    if (!b)
+        return false;
+    m.set(k, b->m_k);
+    strict = b->m_strict;
+    ts = b->m_timestamp;
+    return true;
+}
+
+bound_propagator::bound * bound_propagator::bound::at(unsigned timestamp) {
+    bound * r = this;
+    while (r != 0 && r->m_timestamp >= timestamp) 
+        r = r->m_prev;
+    return r;
+}
+
+/**
+   \brief Return true if the coefficient of x in eq is positive
+*/
+bool bound_propagator::is_a_i_pos(linear_equation const & eq, var x) const {
+    unsigned i = eq.pos(x);
+    if (i == UINT_MAX)
+        return false;
+    return m.is_pos(eq.a(i));
+}
+
+void bound_propagator::explain(var x, bound * b, unsigned ts, assumption_vector & ex) const {
+    if (!b)
+        return;
+    b = b->at(ts);
+    if (!b)
+        return;
+    if (b->m_kind == AXIOM || b->m_kind == DECISION)
+        return;
+    if (b->m_kind == ASSUMPTION) {
+        ex.push_back(b->m_assumption);
+        return;
+    }
+    svector<var_bound> & todo = const_cast<bound_propagator*>(this)->m_todo;
+    todo.reset();
+    unsigned qhead = 0;
+    todo.push_back(var_bound(x, b));
+    b->m_mark = true;
+    while (qhead < todo.size()) {
+        var_bound & vb = todo[qhead];
+        qhead ++;
+        var x     = vb.first;
+        bound * b = vb.second;
+        SASSERT(b->kind() == ASSUMPTION || b->kind() == DERIVED);
+        if (b->kind() == ASSUMPTION) {
+            ex.push_back(b->m_assumption);
+            continue;
+        }
+        SASSERT(b->kind() == DERIVED);
+        constraint const & c = m_constraints[b->m_constraint_idx];
+        switch (c.m_kind) {
+        case LINEAR: {
+            linear_equation * eq = c.m_eq;
+            bool is_lower  = b->is_lower();
+            if (!is_a_i_pos(*eq, x))
+                is_lower = !is_lower;
+            unsigned sz = eq->size();
+            for (unsigned i = 0; i < sz; i++) {
+                var x_i = eq->x(i);
+                if (x_i == x)
+                    continue;
+                bound * b = (m.is_neg(eq->a(i)) == is_lower) ? m_lowers[x_i] : m_uppers[x_i];
+                SASSERT(b);
+                if (b->kind() == DERIVED || b->kind() == ASSUMPTION) {
+                    if (!b->m_mark) {
+                        b->m_mark = true;
+                        todo.push_back(var_bound(x_i, b));
+                    }
+                }
+            }
+            break;
+        }
+        default:
+            break;
+        }
+    }
+    unsigned sz = todo.size();
+    for (unsigned i = 0; i < sz; i++)
+        todo[i].second->m_mark = false;
+    todo.reset();
+}
+
+/**
+   \brief Compute lower (upper) bound for the linear polynomial as[0]*xs[0] + ... + as[sz-1]*xs[sz-1]
+   
+   Return false if the lower (upper) bound is -oo (oo)
+*/
+template<bool LOWER, typename Numeral>
+bool bound_propagator::get_bound(unsigned sz, Numeral const * as, var const * xs, mpq & r, bool & st) const {
+    st = false;
+    m.reset(r);
+    for (unsigned i = 0; i < sz; i++) {
+        var x_i = xs[i];
+        Numeral const & a_i = as[i];
+        if (m.is_zero(a_i))
+            continue;
+        bound * b = (m.is_neg(a_i) == LOWER) ? m_uppers[x_i] : m_lowers[x_i];
+        if (!b) {
+            m.reset(r);
+            return false;
+        }
+        if (b->m_strict)
+            st = true;
+        m.addmul(r, a_i, b->m_k, r); 
+    }
+    return true;
+}
+
+bool bound_propagator::lower(unsigned sz, mpq const * as, var const * xs, mpq & r, bool & st) const {
+    return get_bound<true, mpq>(sz, as, xs, r, st);
+}
+
+bool bound_propagator::upper(unsigned sz, mpq const * as, var const * xs, mpq & r, bool & st) const {
+    return get_bound<false, mpq>(sz, as, xs, r, st);
+}
+
+void bound_propagator::display_bounds_of(std::ostream & out, linear_equation const & eq) const {
+    for (unsigned i = 0; i < eq.size(); i++) {
+        display_var_bounds(out, eq.x(i));
+        out << "\n";
+    }
+}
+
+void bound_propagator::display_var_bounds(std::ostream & out, var x, bool approx, bool precise) const {
+    if (m_lowers[x]) {
+        if (precise)
+            out << m.to_string(m_lowers[x]->m_k);
+        if (precise && approx)
+            out << " | ";
+        if (approx)
+            out << m_lowers[x]->m_approx_k;
+        out << " " << (m_lowers[x]->m_strict ? "<" : "<=");
+    }
+    else {
+        out << "-oo <";
+    }
+    out << " x" << x << " ";
+    if (m_uppers[x]) {
+        out << (m_uppers[x]->m_strict ? "<" : "<=") << " ";
+        if (precise)
+            out << m.to_string(m_uppers[x]->m_k);
+        if (precise && approx)
+            out << " | ";
+        if (approx)
+            out << m_uppers[x]->m_approx_k;
+    }
+    else {
+        out << "< oo";
+    }
+}
+
+void bound_propagator::display_bounds(std::ostream & out, bool approx, bool precise) const {
+    unsigned num_vars = m_dead.size();
+    for (unsigned x = 0; x < num_vars; x++) {
+        if (!is_dead(x)) {
+            display_var_bounds(out, x, approx, precise);
+            out << "\n";
+        }
+    }
+}
+
+void bound_propagator::display_constraints(std::ostream & out) const {
+    constraint_vector::const_iterator it  = m_constraints.begin();
+    constraint_vector::const_iterator end = m_constraints.end();
+    for (; it != end; ++it) {
+        constraint const & c = *it;
+        if (c.m_kind == LINEAR) {
+            m_eq_manager.display(out, *(c.m_eq));
+            out << "\n";
+        }
+    }
+}
+
+void bound_propagator::display(std::ostream & out) const {
+    display_bounds(out);
+    display_constraints(out);
+}
+
+
+

File src/tactic/arith/bound_propagator.h

+/*++
+Copyright (c) 2011 Microsoft Corporation
+
+Module Name:
+
+    bound_propagator.h
+
+Abstract:
+
+    Bound propagators for arithmetic.
+    Support class for implementing strategies and search procedures
+
+Author:
+
+    Leonardo de Moura (leonardo) 2011-06-18.
+
+Revision History:
+
+--*/
+#ifndef _BOUND_PROPAGATOR_H_
+#define _BOUND_PROPAGATOR_H_
+
+#include"mpq.h"
+#include"vector.h"
+#include"params.h"
+#include"statistics.h"
+#include"numeral_buffer.h"
+#include"linear_equation.h"
+
+class bound_propagator {
+public:
+    typedef unsigned var;
+    typedef unsigned assumption;
+    typedef unsynch_mpq_manager numeral_manager;
+    typedef unsigned_vector assumption_vector;
+    typedef unsigned constraint_id;
+    typedef numeral_buffer<mpz, numeral_manager> mpz_buffer;
+    typedef svector<double> double_vector;
+    static const assumption null_assumption = UINT_MAX;
+    static const var null_var = UINT_MAX;
+    static const unsigned null_constraint_idx = UINT_MAX;
+    class trail_info {
+        unsigned m_x_lower;
+    public:
+        trail_info(var x, bool is_lower):m_x_lower((x << 1) + static_cast<unsigned>(is_lower)) {}
+        trail_info():m_x_lower(UINT_MAX) {}
+        var x() const { return m_x_lower >> 1; }
+        bool is_lower() const { return (m_x_lower & 1) != 0; }
+    };
+
+protected:
+
+    enum ckind { LINEAR  // only linear equalities so far.
+    };
+
+    /**
+       \brief Constraints don't need justification.
+    */
+    class constraint {
+        friend class bound_propagator;
+        unsigned     m_kind:2;
+        unsigned     m_dead:1;
+        unsigned     m_timestamp; // Constraint tried to propagate new bounds using bounds with timestamp < m_timestamp.