BranchAndBoundCallback

This class can be used to create callbacks to run on idol’s branch-and-bound implementation.

Warning

BranchAndBoundCallback-s is an advanced feature.

Please, make sure that what you are trying do cannot be done with a solver-independent callback first, or with pre-existing callbacks, e.g., UserCutCallback or LazyCutCallback.

The advantage of using a BranchAndBoundCallback instead of a standard solver-independent Callback lies in the possibility to access specific information regarding the execution of the branch-and-bound algorithm. For instance, accessing a node’s information, or the current relaxation model being solved.

Example

Here is an example of callback which prints out the event triggering it and, when the event corresponds to NodeLoaded, prints the node’s model to be solved.

class MyCallback : public BranchAndBoundCallbackFactory<NodeInfo> {
public:
    class Strategy : public BranchAndBoundCallback<NodeInfo> {
    protected:
        void operator()(CallbackEvent t_event) override {

            std::cout << "MyCallback is called for " << t_event << std::endl;

            if (t_event != NodeLoaded) {
                return;
            }

            std::cout << "The problem being solve at node " << node().id() << std::endl;
            std::cout << relaxation() << std::endl;

        }
    };

    BranchAndBoundCallback<NodeInfo> *operator()() override {
        return new Strategy();
    }

    [[nodiscard]] BranchAndBoundCallbackFactory<NodeInfo> *clone() const override {
        return new MyCallback(*this);
    }
};

Then, this callback can be used as follows.

model.use(
    BranchAndBound()
        .with_node_optimizer(GLPK::ContinuousRelaxation())
        .with_branching_rule(MostInfeasible())
        .with_node_selection_rule(DepthFirst())
        .with_callback(MyCallback());
);

Hint

By default, most of the objects returned by BranchAndBoundCallback methods are const. If you wish to access non-const versions (e.g., if you want to perform non-standard updates to the relaxed model or want to change the node’s current information manually), you should use the advanced interface obtained by calling BranchAndBoundCallback::advanced_interface.

Doxygen

template<class NodeInfoT>
class BranchAndBoundCallback

Subclassed by idol::CallbackAsBranchAndBoundCallback< NodeInfoT >::Strategy, idol::Cuts::KnapsackCover< NodeInfoT >::Strategy, idol::Heuristics::IntegerMaster< NodeInfoT >::Strategy, idol::ReducedCostFixing< NodeInfoT >::Strategy, idol::Utils::ExportBranchAndBoundTreeToCSV< NodeInfoT >::Strategy

Public Functions

virtual ~BranchAndBoundCallback() = default

Protected Functions

inline virtual void initialize()

This method is called at the very beginning of the Branch-and-Bound algorithm

virtual void operator()(CallbackEvent t_event) = 0

This method is left for the user to write and consists in the main execution block of the callback.

Parameters:

t_event – The event triggering the callback

inline virtual void log_after_termination()

void add_user_cut(const TempCtr &t_cut)

Adds a user cut to the relaxation

Parameters:

t_cut – the cut to be added

void add_lazy_cut(const TempCtr &t_cut)

Adds a lazy cut to the relaxation

Parameters:

t_cut – the cut to be added

void add_local_variable_branching(const Var &t_var, CtrType t_type, double t_rhs)

const Node<NodeInfoT> &node() const

Returns the node which is currently explored

Returns:

the node which is currently explored

const Model &relaxation() const

Returns the current node’s model being solved

Returns:

the current node’s model being solved

const Model &original_model() const

Returns the original model from which the branch-and-bound algorithm started (i.e., the original non-relaxed model)

Returns:

the original model

void submit_heuristic_solution(NodeInfoT *t_info)

Submits a new solution to the branch-and-bound tree algorithm.

The solution is checked for validity according to the branch-and-bound tree branching rule and is set as incumbent if and only if it is valid and improves the current best objective.

Parameters:

t_info – a node information storing the solution

void submit_bound(double t_bound)

Submits a new proven bound.

The given bound is set as best bound if and only if it improves the current best bound.

Parameters:

t_bound – a proven bound

const SideEffectRegistry &side_effect_registry() const

Returns the side effect registry

Returns:

the side effect registry

const Timer &time() const

double best_bound() const

double best_obj() const

void terminate()