The optimal relaxed solution for an ILP has X₁ = 3.6 and X₂ = 2.9. If we branch on X₁, what constraints must be added to the two resulting LP problems? A) X₁ ≥ 3, X₁ ≥ 4 B) X₁ = 4 C) 3 ≤ X₁, X₁ ≤ 4 D) X₁ ≤ 3, X₁ ≥ 4

Question

Quizplus · Accepted Answer

When branching on a variable in integer linear programming (ILP), the solution space is divided into two: one where the variable is less than or equal to the floor of its value in the relaxed solution, and another where it is greater than or equal to the ceiling of that value. Since the relaxed solution value for X₁ is 3.6, the two new constraints are X₁ ≤ 3 and X₁ ≥ 4.

The Optimal Relaxed Solution for an ILP Has X1 =

The Optimal Relaxed Solution for an ILP Has X₁ =