Problem #$1$

Consider the following IP problem.

maximize :

$3x_1+6*x_2+3*x_3+3*x_4+1x_5$

subject to :

$3**x_1+5**x_2+3**x_3+3**x_4+2**x_{5}7$

$x_{i}in\{0,1\},$AAi$=1,$dots,$5$

$($a$)$ Write the LP relaxation of the above model.

$($b$)$ Get the optimal objective function value of the LP relaxation from Table $1.$ Is it a lower or an upper bound? Explain.

$($c$)$ Is $x=[0,1,0,0,0{]}^T$ a feasible solution to the above problem. If yes, then obtain its objective function value from Table $1.$ Is it a lower or an upper bound? Explain.

Solve the above problem using branch & bound method, and build the enumeration tree using the following strategies. You can use the information from Table $1.$ Note: For every strategy that you pick, you will generate one tree, i$.$e$.,$ one tree for Part $($d$),$ one for Part $($e$)$ and one for Part $($f$).$

$($d$)$ Strategy$-1$:

Node Selection: Best First

Select the node with the best objective function value.

Variable Selection: Nearest to integer A fractional variable with fractional value nearest to an integer will be used for branching.

Branching Direction: Up

Select the branch of $$ side $($lower bound is increased.$)$

$($e$)$ Strategy$-2$:

Node Selection: Depth First the Best Back

Select the most recently created child node to solve. If no child exists, then backtrack to the best bound node available in the entire tree.

Variable Selection: Lowest fraction A fractional variable with lowest fraction will be used for branching.

Branching Direction: Down

Select the branch of $$ side $($upper bound is decreased.$)$

$($f$)$ Strategy$-3$:

Node Selection: Breadth First the Best Next

All nodes at one level of the search tree are processed before any node at a deeper level. In a given level, best node should be processed first.

Variable Selection: Highest fraction

A fractional variable with highest fraction will be used for branching.

Branching Direction: You are free to pick any rule.