Optimal Solution of Branch and Bound for Integer Linear Programs

Hi,

I am using the Branch and Bound algorithm to find the optimal solution
of an integer linear program. I am just wondering does B&B guarantee
to return an optimal solution? As far as I know, genetic algorithms
and hill climbing algoritms do not guarantee to return an optimal
solution.

Many Thanks,
David

David wrote:
Hi,
>
I am using the Branch and Bound algorithm to find the optimal solution
of an integer linear program. I am just wondering does B&B guarantee
to return an optimal solution? As far as I know, genetic algorithms
and hill climbing algoritms do not guarantee to return an optimal
solution.
>
Many Thanks,
David

Yes, assuming that the problem is bounded. Assuming you run the
algorithm to its correct conclusion, b-&-b will exhaust the search tree
in a finite number of steps. The key is that "finite" and "small" (or
"reasonable", or "less than the number of particles in the known
universe") are not necessarily synonymous.

/Paul