COPING WITH THE LIMITATIONS OF THE ALGORITHM POWER

TRAVELING SALESMAN PROBLEM

BACKTRACKING

BRANCH-AND-BOUND

HAMILTONIAN CIRCUIT PROBLEM

STATE-SPACE TREE

PROMISSING

NONPROMISSING

N-QUEENS PROBLEM

SUBSET-SUM PROBLEM

GENERAL REMARKS

FEASIBLE SOLUTION

OPTIMAL SOLUTION

ASSIGNMENT PROBLEM

KNAPSACK PROBLEM

TRAVELING SALESMAN PROBLEM

BRANCH-AND-BOUND REQUIRES TWO ADDITIONAL ITEMS:

A WAY TO PROVIDE, FOR EVERY NODE OF A STATE-SPACE TREE, A BOUND ON THE BEST VALUE OF THE OBJECTIVE FUNCTION1 ON ANY SOLUTION THAT CAN BE OBTAINED BY ADDING FURTHER COMPONENTS TO THE PARTIALLY CONSTRUCTED SOLUTION REPRESENTED BY THE NODE

THE VALUE OF THE BEST SOLUTION SEEN SO FAR

IN GENERAL, WE TERMINATE A SEARCH PATH AT THE CURRENT NODE IN A STATE-SPACE TREE OF A BRANCH-AND-BOUND ALGORITHM FOR ANY ONE OF THE FOLLOWING THREE REASONS:

THE VALUE OF THE NODE’S BOUND IS NOT BETTER THAN THE VALUE OF THE BEST SOLUTION SEEN SO FAR.

THE NODE REPRESENTS NO FEASIBLE SOLUTIONS BECAUSE THE CONSTRAINTS OF THE PROBLEM ARE ALREADY VIOLATED.

THE SUBSET OF FEASIBLE SOLUTIONS REPRESENTED BY THE NODE CONSISTS OF A SINGLE POINT (AND HENCE NO FURTHER CHOICES CAN BE MADE)—IN THIS CASE, WE COMPARE THE VALUE OF THE OBJECTIVE FUNCTION FOR THIS FEASIBLE SOLUTION WITH THAT OF THE BEST SOLUTION SEEN SO FAR AND UPDATE THE LATTER WITH THE FORMER IF THE NEW SOLUTION IS BETTER.