BCP_lp_branch.hpp

Go to the documentation of this file.

// Copyright (C) 2000, International Business Machines
// Corporation and others.  All Rights Reserved.
#ifndef _BCP_LP_BRANCH_H
#define _BCP_LP_BRANCH_H

// This file is fully docified.

#include "BCP_math.hpp"
#include "BCP_enum_branch.hpp"
#include "BCP_vector.hpp"
#include "BCP_lp_result.hpp"
#include "BCP_USER.hpp"
#include "BCP_var.hpp"
#include "BCP_cut.hpp"
#include "BCP_matrix.hpp"

#include "OsiBranchingObject.hpp"

class OsiSolverInterface;

//#############################################################################

class BCP_lp_integer_branching_object : public OsiIntegerBranchingObject
{
public:
    BCP_lp_integer_branching_object(const OsiIntegerBranchingObject* o) :
        OsiIntegerBranchingObject(*o) {}
    ~BCP_lp_integer_branching_object() {}
    inline const double* childBounds(int i) const { return i==0 ? down_:up_; }
};

//-----------------------------------------------------------------------------

class BCP_lp_sos_branching_object : public OsiSOSBranchingObject
{
public:
    BCP_lp_sos_branching_object(const OsiSOSBranchingObject* o) :
        OsiSOSBranchingObject(*o) {}
    ~BCP_lp_sos_branching_object() {}
};

//#############################################################################
// ASSUMPTION
// ----------
// All a branching object does are:
// - add cuts and/or variables
// - change bounds on cuts and/or variables
//#############################################################################

// *THINK* : Maybe the methods should be hidden???

// *THINK* : Maybe we should just use vectors instead of pointers to vectors?
// *THINK* : It'd simplify things and would not be significant extra storage
// *THINK* : (maybe none at all, depending pon the system operator new...)

class BCP_lp_branching_object {
private:
    BCP_lp_branching_object(const BCP_lp_branching_object&);
    BCP_lp_branching_object& operator=(const BCP_lp_branching_object&);
public:
    int child_num;
    BCP_vec<BCP_var*>* vars_to_add;
    BCP_vec<BCP_cut*>* cuts_to_add;

    BCP_vec<int>* forced_var_pos;
    BCP_vec<int>* forced_cut_pos;
    BCP_vec<double>* forced_var_bd;
    BCP_vec<double>* forced_cut_bd;
    BCP_vec<int>* implied_var_pos;
    BCP_vec<int>* implied_cut_pos;
    BCP_vec<double>* implied_var_bd;
    BCP_vec<double>* implied_cut_bd;
    BCP_vec<double>* objval_;
    BCP_vec<int>* termcode_;

public:
    explicit BCP_lp_branching_object(const int children,
                                     BCP_vec<BCP_var*>* const new_vars,
                                     BCP_vec<BCP_cut*>* const new_cuts,
                                     const BCP_vec<int>* const fvp,
                                     const BCP_vec<int>* const fcp,
                                     const BCP_vec<double>* const fvb,
                                     const BCP_vec<double>* const fcb,
                                     const BCP_vec<int>* const ivp,
                                     const BCP_vec<int>* const icp,
                                     const BCP_vec<double>* const ivb,
                                     const BCP_vec<double>* const icb ) :
        child_num(children),
        vars_to_add(0), cuts_to_add(0),
        forced_var_pos(0), forced_cut_pos(0),
        forced_var_bd(0), forced_cut_bd(0),
        implied_var_pos(0), implied_cut_pos(0),
        implied_var_bd(0), implied_cut_bd(0),
        objval_(0), termcode_(0)
    {
        if ( ((fvp == 0) ^ (fvb == 0)) || ((fcp == 0) ^ (fcb == 0)) || 
             ((ivp == 0) ^ (ivb == 0)) || ((icp == 0) ^ (icb == 0)) )
            throw BCP_fatal_error("Bad args to BCP_lp_branching_object()\n");
        if ( (fvp && (2 * children* fvp->size() != fvb->size())) ||
             (fcp && (2 * children* fcp->size() != fcb->size())) ||
             (ivp && (2 * children* ivp->size() != ivb->size())) ||
             (icp && (2 * children* icp->size() != icb->size())) )
            throw BCP_fatal_error("Bad args to BCP_lp_branching_object()\n");

        if (new_vars) {
            vars_to_add = new BCP_vec<BCP_var*>(*new_vars);
            new_vars->clear();
        }
        if (new_cuts) {
            cuts_to_add = new BCP_vec<BCP_cut*>(*new_cuts);
            new_cuts->clear();
        }

        if (fvp) forced_var_pos = new BCP_vec<int>(*fvp);
        if (fcp) forced_cut_pos = new BCP_vec<int>(*fcp);
        if (fvb) forced_var_bd = new BCP_vec<double>(*fvb);
        if (fcb) forced_cut_bd = new BCP_vec<double>(*fcb);

        if (ivp) implied_var_pos = new BCP_vec<int>(*ivp);
        if (icp) implied_cut_pos = new BCP_vec<int>(*icp);
        if (ivb) implied_var_bd = new BCP_vec<double>(*ivb);
        if (icb) implied_cut_bd = new BCP_vec<double>(*icb);
    }
    BCP_lp_branching_object(const BCP_lp_integer_branching_object& o,
                            const int* order);
    BCP_lp_branching_object(const OsiSolverInterface* osi,
                            const BCP_lp_sos_branching_object& o,
                            const int* order);

    inline void set_presolve_result(const BCP_vec<double>& objval,
                                    const BCP_vec<int>& termcode) {
        objval_ = new BCP_vec<double>(objval);
        termcode_ = new BCP_vec<int>(termcode);
    }

    // NOTE: when the desctructor `delete's vars_to_add and cuts_to_add, it
    // will just delete the pointers in the BCP_lp_..._sets (see the
    // destructors of those classes). But this is intentional, because the
    // vars/cuts will be actually deleted only later, when the unnecessery
    // ones are deleted from the formulation.
    ~BCP_lp_branching_object() {
        delete vars_to_add;     delete cuts_to_add;
        delete forced_var_pos;  delete forced_cut_pos;
        delete forced_var_bd;   delete forced_cut_bd;
        delete implied_var_pos; delete implied_cut_pos;
        delete implied_var_bd;  delete implied_cut_bd;
        delete objval_;         delete termcode_;
    }
    inline int vars_affected() const {
        return
            (forced_var_bd ? forced_var_bd->size() / (2*child_num) : 0) +
            (implied_var_bd ? implied_var_bd->size() / (2*child_num) : 0);
    }
    inline int cuts_affected() const {
        return
            (forced_cut_bd ? forced_cut_bd->size() / (2*child_num) : 0) +
            (implied_cut_bd ? implied_cut_bd->size() / (2*child_num) : 0);
    }
    inline int vars_added() const {
        return vars_to_add ? vars_to_add->size() : 0;
    }
    inline int cuts_added() const {
        return cuts_to_add ? cuts_to_add->size() : 0;
    }
    inline
    BCP_vec<double>::const_iterator forced_var_bd_child(const int index)const {
        return forced_var_bd->entry(2 * forced_var_pos->size() * index);
    }
    inline
    BCP_vec<double>::const_iterator forced_cut_bd_child(const int index)const {
        return forced_cut_bd->entry(2 * forced_cut_pos->size() * index);
    }
    inline
    BCP_vec<double>::const_iterator implied_var_bd_child(const int index)const{
        return implied_var_bd->entry(2 * implied_var_pos->size() * index);
    }
    inline
    BCP_vec<double>::const_iterator implied_cut_bd_child(const int index)const{
        return implied_cut_bd->entry(2 * implied_cut_pos->size() * index);
    }
    // this routine reorders the positions/bounds as well so that the positions
    // are in increasing order (the vars/cuts are already added to the problem,
    // no need to reorder those, too)
    void init_pos_for_added(const int added_vars_start,
                            const int added_cuts_start);
    void apply_child_bd(OsiSolverInterface* lp, const int child_ind) const;
    void print_branching_info(const int orig_varnum,
                              const double* x, const double * obj) const;
};

//#############################################################################

class BCP_presolved_lp_brobj {
private:
    BCP_presolved_lp_brobj(const BCP_presolved_lp_brobj&);
    BCP_presolved_lp_brobj& operator=(const BCP_presolved_lp_brobj&);
private:
    BCP_lp_branching_object* _candidate;
    BCP_vec<BCP_lp_result*> _lpres;
    // what to do with each child
    BCP_vec<BCP_child_action> _child_action;
    BCP_vec<BCP_user_data*> _user_data;
    BCP_vec< BCP_vec<BCP_cut*> > _new_cuts;
    BCP_vec< BCP_vec<BCP_row*> > _new_rows;
public:
    explicit BCP_presolved_lp_brobj(BCP_lp_branching_object* candidate) :
        _candidate(candidate),
        _lpres(),
        _child_action(candidate->child_num, BCP_ReturnChild),
        _user_data(candidate->child_num, NULL)
    {
        _lpres.reserve(candidate->child_num);
        for (int i = candidate->child_num; i; --i) {
            _lpres.unchecked_push_back(new BCP_lp_result);
            _new_cuts.push_back(BCP_vec<BCP_cut*>());
            _new_rows.push_back(BCP_vec<BCP_row*>());
        }
    }
    ~BCP_presolved_lp_brobj() {
        purge_ptr_vector(_lpres);
        purge_ptr_vector(_user_data);
        for (int i = _new_cuts.size() - 1; i >= 0; --i) {
            purge_ptr_vector(_new_cuts[i]);
            purge_ptr_vector(_new_rows[i]);
        }
    }
    inline BCP_lp_branching_object* candidate() {
        return _candidate;
    }
    inline const BCP_lp_branching_object* candidate() const {
        return _candidate;
    }
    inline const BCP_lp_result& lpres(const int child_ind) const {
        return *(_lpres[child_ind]);
    }
    inline BCP_vec<BCP_child_action>& action() {
        return _child_action;
    }
    inline const BCP_vec<BCP_child_action>& action() const {
        return _child_action;
    }

    inline BCP_vec<BCP_user_data*>& user_data() {
        return _user_data;
    }
    inline const BCP_vec<BCP_user_data*>& user_data() const {
        return _user_data;
    }

    bool fathomable(const double objval_limit) const;
    bool had_numerical_problems() const; 
    inline void initialize_lower_bound(const double val) {
        for (int i = _candidate->child_num - 1; i >= 0; --i) {
            _lpres[i]->fake_objective_value(val);
        }
    }
    inline void keep_no_child() {
        for (int i = _child_action.size() - 1; i >= 0; --i) {
            _child_action[i] = BCP_ReturnChild;
        }
    }
    inline bool is_pruned() const {
        for (int i = _child_action.size() - 1; i >= 0; --i) {
            if (_child_action[i] != BCP_FathomChild)
                return false;
        }
        return true;
    }
    inline void get_lower_bounds(BCP_vec<double>& obj) {
        obj.clear();
        obj.reserve(_candidate->child_num);
        const int num_children = _lpres.size();
        for (int i = 0; i < num_children; ++i)
            obj.unchecked_push_back(_lpres[i]->objval());
    }
    inline void set_lower_bounds(const BCP_vec<double>& obj) {
        const int num_children = _lpres.size();
        for (int i = 0; i < num_children; ++i)
            _lpres[i]->fake_objective_value(obj[i]);
    }
    inline void get_results(OsiSolverInterface& lp, const int child_ind) {
        _lpres[child_ind]->get_results(lp);
    }
    void fake_objective_values(const double itlim_objval);

    void set_objective_values(const BCP_vec<double>& obj,
                              const BCP_vec<int>& termcode,
                              const double itlim_objval);

    void swap(BCP_presolved_lp_brobj& rhs) {
        std::swap(_candidate, rhs._candidate);
        _lpres.swap(rhs._lpres);
        _child_action.swap(rhs._child_action);
        _user_data.swap(rhs._user_data);
        _new_cuts.swap(rhs._new_cuts);
        _new_rows.swap(rhs._new_rows);
    }
    inline BCP_vec< BCP_vec<BCP_cut*> >& get_new_cuts() { return _new_cuts; }
    inline BCP_vec< BCP_vec<BCP_row*> >& get_new_rows() { return _new_rows; }
};

#endif