Content deleted Content added
m →Branch and bound for exact solutions: whitespace |
→Branch and bound for exact solutions: more explicit about subproblem variables |
||
Line 43:
# If the current subproblem's relaxed solution is worse than the best integer solution found so far, backtrack from this branch of the recursive search.
# If the relaxed solution has all variables set to 0 or 1, test it against the best integer solution found so far and keep whichever of the two solutions is best.
# Otherwise, let ''x<sub>j</sub>'' be any variable that is set to a fractional value in the relaxed solution. Form two subproblems, one in which ''x<sub>j</sub>'' is set to 0 and the other in which ''x<sub>j</sub>'' is set to 1; in both subproblems,
Although it is difficult to prove theoretical bounds on the performance of algorithms of this type, they can be very effective in practice.
| |||