12
$\begingroup$

I was trying to solve a moderate scheduling model using an open-source solver. I did two different ways.

A) using pure branch and bound algorithm (disable all options).

B) using the default setting of the solver option (activating pre-solving, separating and heuristics).

While I'm using (A) the results are better than using (B).

Is it possible that the performance of a pure branch and bound algorithm be better than branch-cut-heuristic?

$\endgroup$
11
$\begingroup$

If your outcome is confirmed by 10 runs with different random seeds (or 10 permutations of the input) on different instances of your problem, then you are facing a (rare) case where the default cuts and heuristics are not needed and actually slow-down the solver (of course this can happen, as the default setting is not perfect in all cases).

| improve this answer | |
$\endgroup$
5
$\begingroup$

If all of the unknown variables are required to be integers, then the problem is called an integer programming (IP) problem, if only some of the unknown variables are required to be integers, then the problem is called a mixed integer programming (MIP) problem.

A cutting-plane method is an optimization that iteratively refines a feasible set and is commonly used to find integer solutions to mixed integer linear programming (MILP) problems.

Branch and cut is a method of combinatorial optimization for solving integer linear programs (ILPs), where some or all the unknowns are restricted to integer values. Branch and cut involves running a branch and bound algorithm and using cutting planes to tighten the linear programming relaxations.

The branch-and-bound algorithm is used to find a value $x$ that maximizes or minimizes the value of a real-valued function $f(x)$.

Often a problem can be split into a master problem and the subproblem, that is called column generation. Branch-and-price is a hybrid of branch and bound and column generation methods.

The branch-and-bound was first described by John Little in: "An Algorithm for the Traveling Salesman Problem", (Dec 1 1963):

"A “branch and bound” algorithm is presented for solving the traveling salesman problem. The set of all tours (feasible solutions) is broken up into increasingly small subsets by a procedure called branching. For each subset a lower bound on the length of the tours therein is calculated. Eventually, a subset is found that contains a single tour whose length is less than or equal to some lower bound for every tour.".

Egon Balas described branch-and-bound in his paper "Branch-and-bound Methods for the Travelling Salesman Problem" as follows:

Enumerative (branch and bound, implicit enumeration) methods solve a discrete optimization problem by breaking up its feasible set into successively smaller subsets, calculating bounds on the objective function value over each subset, and using them to discard certain subsets from further consideration. The bounds are obtained by replacing the problem over a given subset with an easier (relaxed) problem, such that the solution value of the latter bounds that of the former. The procedure ends when each subset has either produced a feasible solution, or was shown to contain no better solution than the one already in hand. The best solution found during the procedure is a global optimum.

Branch-and-cut on the other hand is a means to divide the problem (as is branch-and-price) so branch-and-bound can be called upon it.

If the problem is simple enough BnB can look at the whole problem at once and provide an optimal solution, if the problem is enormous (as practical problems, opposed to simple ones, usually are) then solving pieces involves later recombining them and reiterating over them; that can lead to small errors, or pieces that were useful in the final solution having been trimmed.

Heuristics are an estimation and not an exact method, they enable a significant speedup at the cost of accuracy. Ideally they can be used to obtain an estimate from which to start rather than being relied upon as partial answers incorporated into the solution.

| improve this answer | |
$\endgroup$
3
$\begingroup$

Note that a different solver might yield a different result. The quality differences between solver, especially between open-source and commercial solvers, are huge.

That said, there are problems where cuts, pre-solving, primal heuristics and other features don't help all that much. In some rare cases, as pointed out by Matteo Fischetti, they even hurt enough so that on average the slow down the solver more than they help.

It might also be possible that only one of the deactivated features hurts and the others are performance neutral or even slightly helpful, really hard to say anything without a lot of experimentation.

Also note that in a reasonably advance solver, doing "just branch-and-bound" might be very far from what is described in textbooks. Solvers might do node-presolve, probing in nodes, restarts and all kinds of other advanced features that might be hard to turn off or there even might be no option to do that.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.