The branch-and-bound algorithm starts by A) relaxing all the integrality conditions in an ILP and solving the resulting LP problem. B) relaxing all the RHS values in an ILP and solving the resulting LP problem. C) solving two LP problems in which X₁ is set at 0 and 1 respectively. D) determining the most likely RHS values and solving for them.

Question

Quizplus · Accepted Answer

The branch-and-bound algorithm tackles the integer programming problem by first relaxing all integer constraints (i.e., allowing variables to take on fractional values) and solving the resulting linear programming problem. The algorithm then proceeds to "branch" the problem into subproblems by adding binary constraints on a variable in each subproblem. The LP relaxation is solved recursively on each subproblem until an optimal integer solution is found. Therefore, choice A is the correct answer.

The Branch-And-Bound Algorithm Starts by