Question

solve the following LP by hand using Branch-and-Bound. Can use any solver for the LPs.

minimize tal que -7:01 - 2.02 -21 +2:02 < 4 5x1 + x2 < 20 -2.21 - 222 < -7 X1, X2 E ZI

Answer 1

Step1

• I have setup the objective function and constraints and setup bound as (0,0)
• I have taken sumproduct for objective and constratint vs decision variable and
• also applied the constraints limits as given in the problem.
• Then I have just setup a min objective for decision variables and with decision variables >= bound values , as a Simplex LP.

A B с D E F 1 2 3 -2 2 4. 5 x1 -7 -1 5 -2 0 Objective Constraint 1 Constraint 2 Constraint 3 Bound Decision variable =SUMPRODUCT(B3:C3, SBS8:SC$8) 0 0 0 0 4 20 -7 6 2 0 7 8

Solver Parameters X Set Objective: $D$3 To: Max Min Value of: 0 By Changing Variable Cells: $B$8:$C$8 Subject to the Constraints: $B$8:$C$8 >= >= $B$7:$C$7 $D$4:$D$6 <= $F$4:$F$6 Add Change Delete Reset All Load/Save Make Unconstrained variables Non-Negative Select a Solving Method: Simplex LP Options Solving Method Select the GRG Nonlinear engine for Solver Problems that are smooth nonlinear. Select the LP Simplex engine for linear Solver Problems, and select the Evolutionary engine for Solver problems that are non-smooth. Help Solve Close

A B C D E F G 1 نيا -2 2 =SUMPRODUCT(B3:C3, $B$8:SC88) -28.25 -3.083333333 xl -7 -1 5 -2 0 1 2 Objective 4 Constraint 1 5 Constraint 2 6 Constraint 3 Bound Decision variable 20 4 20 -7 -7 2 0 7 8 3.9167 0.41667

• As you can see from step 1 both the decision variables are non-integers so we need to check boundary conditions and branch out.
• The condition I am taking in Step 2 is considering x1 >= 4 and x2 <=3 and solve again

Step 2

As the decision variables are not integers, need to branch out

Case 1 – x1 >=4 , just add one more constraint in the same solver above that x1 >=4 and solve

Solver Parameters X Set Objective: $D$3 To: Max Min Value of: 0 By Changing Variable Cells: $B$8:$C$8 Subject to the Constraints: $B$8 >= 4 $B$8:$C$8 >= $B$7:$C$7 $D$4:$D$6 <= $F$4:$F$6 Add Change Delete Reset All Load/Save Make Unconstrained variables Non-Negative Select a Solving Method: Simplex LP Options Solving Method Select the GRG Nonlinear engine for Solver Problems that are smooth nonlinear. Select the LP Simplex engine for linear Solver Problems, and select the Evolutionary engine for Solver problems that are non-smooth. Help Solve Close

Case 2 x1 <=3

Change the solver constraint to x1 <=3 and solve again , solver doesn't give any solution for x1 <=3 as you can below as well that constraint 3 is violated.

B с A D E F G H Solver Parameters I Х T 1 2 Set Objective: $D$3] 1 ترا -2 xl -7 -1 5 -2 2 =SUMPRODUCT(B3:C3, $B$8:$C$8) -21 -3 15 -6 4 To: O Max O Min O Value of: Objective Constraint 1 Constraint 2 Constraint 3 Bound Decision variable л 1 20 -7 2 By Changing Variable Cells: $B$8:$C$8 7 0 0 1 3 0 8 Subject to the Constraints: $B$8 <= 3 $D$4:$D$6 <= $F$4:$F$6 9. Add Change Delete No need to branch further (x1 >=4) (-28) (4,0) Reset All Load/Save Make Unconstrained variables Non-Negative 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 60 Select a Solving Method: Simplex LP Options (-28.25) (3.9167,0.4166) Solving Method Select the GRG Nonlinear engine for Solver problems that are smooth nonlinear. Select the LP Simplex engine for linear Solver Problems, and select the Evolutionary engine for Solver problems that are non-smooth. (xl<=3) No optimal solution for this branch , as constraint 3 fails so no further branch Help Solve Close

• Under the scenario, we got optimal branched solution for x1<=4 as objective function = -28, decision variables as 4,0 which is the optimal bounded solution.
• The final answer is the branch shown in orange above and mentioned as well.

No need to branch further (x1 >=4) (-28) (4,0) (-28.25) (3.9167,0.4166) (xl<=3) No optimal solution for this branch , as constraint 3 fails so no further branch

If you liked my answer, thumbs up pls.