$Solve this problem using branch and bound algorithm.$

Question

$Solve this problem using branch and bound algorithm.$

Consider the following integer program
maximize z = 5x1 + 4x2
subject to x1 + x2 ≤ 5
10x1 + 6x2 ≤ 45
x1, x2 ≥ 0 integer
The optimal solution to the linear programming relaxation is x1 = 3.75, x2 = 1.25, and z = 23.75. Solve this problem using the branch-and-bound algorithm. Start by branching on x1.

Algebra Optimization

Fannypack

15

Report

Answer

The answer is accepted.

Join Matchmaticians Affiliate Marketing Program to earn up to a 50% commission on every question that your affiliated users ask or answer.

Answer 1

Answers can only be viewed under the following conditions:

The questioner was satisfied with and accepted the answer, or
The answer was evaluated as being 100% correct by the judge.

View the answer

First branch on $x_{1}$ by creating two new subproblems; one with the contraint $x_{1} \le 3$ , and another with $x_{1} \ge 4$. (Hence we've "branched" on x1, and "bounded" it to the nearest integer values 3 or 4). Solve the LP relaxation for each:

Subproblem 1
maximize $z=5x_{1}+4x_{2}$
subject to $x_{1}+x_{2}\le5$
$10x_1+6x_2 \le 45$
$x_1 \le 3$
LP Relaxation: {$x_1$,$x_2$} = {3,2}, z = 23

Subproblem 2
maximize $z=5x_{1}+4x_{2}$
subject to $x_{1}+x_{2}\le5$
$10x_1+6x_2 \le 45$
$x_1 \ge 4$
LP Relaxation: {$x_1$,$x_2$} = {4,5/6}, z = 23.333

Next, we branch the Subproblem 2 on x2, since x1 is an integer now. Bound $x_2$ to the closest integer values 0 or 1. Also keep the previous bounding constraint on $x_1$:

Subproblem 3
maximize $z=5x_{1}+4x_{2}$
subject to $x_{1}+x_{2}\le5$
$10x_1+6x_2 \le 45$
$x_1 \ge 4$
$x_2 \le 0$
LP Relaxation: {x1,x2} = {4.5,0}, z = 22.5

Subproblem 4
maximize $z=5x_{1}+4x_{2}$
subject to $x_{1}+x_{2}\le5$
$10x_1+6x_2 \le 45$
$x_1 \ge 4$
$x_2 \ge 1$
Infeasible

Of the four subproblems, the only feasible solution is Subproblem 1, and so the optimal solution is {$x_1$, $x_2$} = {3,2}, with an objective value of 23.

Stephenbarr

7

$Solve this problem using branch and bound algorithm.$

Answer

Related Questions

Search