In the 0-1 programming problem, branch and bound with linear programming relaxations needs exponential nodes enumeration for odd n due to fractional variable branching.
In the context of the 0-1 programming problem, where the objective is to minimize subject to the constraint 2x₁ + 2x₂ + ..... + 2xₙ + Xₙ₊₁ = n
xj ∈ {0,1}, j = 1,..... ,n the branch and bound algorithm is employed for optimization.
This algorithm relies on linear programming relaxations to compute lower bounds and branches by assigning fractional values to variables, subsequently setting them to either 0 or 1.
When n is odd, the peculiar structure of the problem leads to challenges in the branch and bound process.
Linear programming relaxations may result in fractional values for variables, and when a fractional variable is chosen for branching, the algorithm must explore both branches—assigning the variable to 0 and 1.
This branching strategy inherently requires the enumeration of an exponential number of nodes, leading to an exponential time complexity.
The reason for this exponential growth lies in the combinatorial nature of the feasible solutions, especially when n is odd.
The algorithm must explore all possible combinations of variable assignments, leading to an exponentially increasing number of nodes in the search tree.
As a consequence, the computational effort required by the branch and bound algorithm becomes prohibitively large for odd values of n, emphasizing the inherent complexity of the problem.