1
$\begingroup$

Can branch and bound be defined as a method to search a non-convex solution space which uses linear programming models(and solving them) to guide the search?

$\endgroup$

1 Answer 1

3
$\begingroup$

Not quite branch and bound is a more general algorithm that also applies to non-linear models. The important thing is that you can calculate a "relaxation" which is guaranteed to be a bound on the objective. If one restricts oneself to MILP, then yes, your suggests describes branch and bound for MILP correctly. For non-linear models there exist different solutions to get lower bounds such as generic Interval Arithmetic or more other methods to find global minima of relaxations.

$\endgroup$
3
  • 1
    $\begingroup$ Branch-and-bound implies neither a model nor a relaxation, just branching and bounding $\endgroup$
    – fontanf
    Commented Feb 28, 2022 at 16:48
  • $\begingroup$ I am curious, how do you derive a bound without some kind of relaxation? Especially if one allows integer valued variables in the model. $\endgroup$ Commented Mar 1, 2022 at 12:30
  • 1
    $\begingroup$ For example, for the graph coloring problem, a bound can be obtained by computing a clique. It would be unusual to call the maximum clique problem a relaxation of the graph coloring problem $\endgroup$
    – fontanf
    Commented Mar 1, 2022 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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