Using CbcModel::branchAndBound inside heuristic instead of CbcHeuristic::smallBranchAndBound

[IlyaShaternik]

Hi.
So I have a model that I need to solve using CBC. In order to do so and also to figure out some inner workings of CBC I decided to implement Local Branching Heuristic. Despite it actually working quite well for my model, I did it in a really naive way so I would appreciate if someone would be able to answer some of my questions.

solution method implementation.

int LocalBranching::solution(double &objectiveValue, double *newSolution)
{
    if(!mutex.try_lock()) // I don't want heuristic to run in all threads.
        return 0;
        
    // Execute Local Branching if new feasible solution have been found.
    if(model_->getSolutionCount() > known_solutions_number_)
    {
        known_solutions_number_ = model_->getSolutionCount();
    }
    else
    {
        mutex.unlock();
        return 0;
    }

    // Add local branching cut.
    int ones_sum = 0;
    CoinPackedVector local_branching_cut;
    std::span<double> best_solution(model_->bestSolution(), model_->getNumCols());
    std::span<const int> integers_indices(model_->integerVariable(), model_->numberIntegers());

    for(auto int_idx : integers_indices)
    {
        auto int_val = best_solution[int_idx];

        if(std::abs(int_val - 1) <= model_->getIntegerTolerance())
        {
            ++ones_sum;
            local_branching_cut.insert(int_idx, -1.0);
        }
        else if(std::abs(int_val) <= model_->getIntegerTolerance())
        {
            local_branching_cut.insert(int_idx, 1.0);
        }
    }

    std::shared_ptr<OsiSolverInterface> newSolver(model_->solver()->clone());
    // k_ - neighbourhood size.
    newSolver->addRow(local_branching_cut, -COIN_DBL_MAX, k_ - ones_sum, "LocalBranchingCut"); 

    CbcModel model(*newSolver);

    // Changing settings and adding heuristics.
    model.setCutoffAsConstraint(true);
    model.setCutoff(objectiveValue);
    model.setPreferredWay(1);
    model.setMaximumNodes(150);
    model.addHeuristic(&vnd_);
    model.addHeuristic(&rens_);
    model.addHeuristic(&fpump_);
    model.addHeuristic(&rounding_);

    model.branchAndBound();

    // Copy and return new solution.
    if(model.getObjValue() < objectiveValue)
    {
        objectiveValue = model.getObjValue();
        
        std::span<double> source(model.bestSolution(), model.getNumCols());
        std::span<double> destination(newSolution, model.getNumCols());
        std::copy(source.begin(), source.end(), destination.begin());
        std::cout << "* In LocalBranching, returning new solution. Objective: " << objectiveValue  << std::endl;

        mutex.unlock();
        return 1;
    }
    mutex.unlock();
    return 0;
}

So here are my questions:

1. So as you can see instead off using CbcHeuristic::smallBranchAndBound, I create new instance of CbcModel. The reason for it is
   that I want to add some heuristics to be used inside Local Branching's branch and bound method. Is there a better way to do it? As far as I understand with smallBranchAndBound you can configure Feasibility Pump, but not much more.
2. Is there a way to avoid creating new CbcModel object each time? I've tried to have CbcModel object as class member and use resetModel method, but it doesn't seem to work.
3. This is probably the most important question to me. So, I'm actually considering implementing this not as heuristic inside CBC, but rather as procedure in its own thread, that would be communicating with main CbcModel object by event handler. But If the main CbcModel is multi-threaded I'm not sure how to implement threads synchronization when fetching new feasible solution or sending new found solution back to main CbcModel object. Is code inside CbcEvenHandler::event thread safe?

[jjhforrest]

Thanks - impressive coding.  Here are some answers.

On 11/06/2022 21:03, IlyaShaternik wrote: Hi. So I have a model that I need to solve using CBC. In order to do so and also to figure out some inner workings of CBC I decided to implement Local Branching Heuristic. Despite it actually working quite well for my model, I did it in a really naive way so I would appreciate if someone would be able to answer some of my questions. solution method implementation. |int LocalBranching::solution(double &objectiveValue, double *newSolution) { if(!mutex.try_lock()) // I don't want heuristic to run in all threads. return 0; // Execute Local Branching if new feasible solution have been found. if(model_->getSolutionCount() > known_solutions_number_) { known_solutions_number_ = model_->getSolutionCount(); } else { mutex.unlock(); return 0; } // Add local branching cut. int ones_sum = 0; CoinPackedVector local_branching_cut; std::span<double> best_solution(model_->bestSolution(), model_->getNumCols()); std::span<const int> integers_indices(model_->integerVariable(), model_->numberIntegers()); for(auto int_idx : integers_indices) { auto int_val = best_solution[int_idx]; if(std::abs(int_val - 1) <= model_->getIntegerTolerance()) { ++ones_sum; local_branching_cut.insert(int_idx, -1.0); } else if(std::abs(int_val) <= model_->getIntegerTolerance()) { local_branching_cut.insert(int_idx, 1.0); } } std::shared_ptr<OsiSolverInterface> newSolver(model_->solver()->clone()); // k_ - neighbourhood size. newSolver->addRow(local_branching_cut, -COIN_DBL_MAX, k_ - ones_sum, "LocalBranchingCut"); CbcModel model(*newSolver); // Changing settings and adding heuristics. model.setCutoffAsConstraint(true); model.setCutoff(objectiveValue); model.setPreferredWay(1); model.setMaximumNodes(150); model.addHeuristic(&vnd_); model.addHeuristic(&rens_); model.addHeuristic(&fpump_); model.addHeuristic(&rounding_); model.branchAndBound(); // Copy and return new solution. if(model.getObjValue() < objectiveValue) { objectiveValue = model.getObjValue(); std::span<double> source(model.bestSolution(), model.getNumCols()); std::span<double> destination(newSolution, model.getNumCols()); std::copy(source.begin(), source.end(), destination.begin()); std::cout << "* In LocalBranching, returning new solution. Objective: " << objectiveValue << std::endl; mutex.unlock(); return 1; } mutex.unlock(); return 0; } | So here are my questions: 1. So as you can see instead off using |CbcHeuristic::smallBranchAndBound|, I create new instance of |CbcModel|. The reason for it is that I want to add some heuristics to be used inside Local Branching's branch and bound method. Is there a better way to do it? As far as I understand with |smallBranchAndBound| you can configure Feasibility Pump, but not much more. 2. Is there a way to avoid creating new |CbcModel| object each time? I've tried to have |CbcModel| object as class member and use |resetModel| method, but it doesn't seem to work.

Creating a new model is probably the simplest way to do it and has no real overhead.  As for 1. what you are doing is probably a good way - see below.

1. This is probably the most important question to me. So, I'm actually considering implementing this not as heuristic inside CBC, but rather as procedure in its own thread, that would be communicating with main |CbcModel| object by event handler. But If the main |CbcModel| is multi-threaded I'm not sure how to implement threads synchronization when fetching new feasible solution or sending new found solution back to main |CbcModel| object. Is code inside |CbcEvenHandler::event| thread safe?

I coded a user example, but it ran into trouble when CbcModel was multi-threaded - and it was totally inelegant.  I think a minor modification to what you are doing will work well.  Just add the CbcHeuristicUser which inherits from CbcHeuristic to heuristics. Only the heuristic in one thread is primed to do heuristic.  This means that if the heuristic is run, that thread will do fewer nodes and spend time in the heuristic.  I can't see anything wrong with that  - it should balance out and avoids any problems with mutexes.. I hope to put up a user example soon.  I have a bit more investigation to do before putting up a new example userParallelHeuristic.cpp.

[IlyaShaternik]

Thank you, I will be looking forward for the new example.

[jjhforrest]

I have put up two examples - userParallelHeuristic.cpp and ..2.cpp. The second one uses the event handler which feels a cleaner way. I ran into trouble when the model wanted to restart having reduced the size of the problem. This was because the models in the threads are updated slightly after the main model. You can turn off the restart option, but I fixed the problem, but am not totally happy with method.

Feel free to criticise and alter.