Problem #$1$

Consider the following optimization problem:

min:

$,8x_1+12x_2+16x_3-20x_4-24x_5-28x_6$

$s.t.$ :

$,x_1+3x_2+3x_3=5$

$,x_4+x_5+x_{6}10$

$,0x_{i}9,$AAi$=1,$dots,$6$

where the variables of the multivariable optimization problem are integers. Use Extension$-2$ type approach, $($i$.$e$.,$ Treat the multiple variables together as one structure or as one vector$).$ Answer the following:

$($a$)$ Let $[4,5,3,1,1,1{]}^T$ be the current solution. Ignore Constraints $(2)$ & $(3),$ and write all the possible feasible immediate neighbors $($star neighbors or unit neighbors$)$ of the current solution.

$($b$)$ Let $[4,5,3,1,1,1{]}^T$ be the current solution. Ignore Constraints $(2)$ & $(3),$ and write $3$ possible feasible extended neighbors of the current solution.

$($c$)$ Execute one full iteration of the greedy search with the immediate$/$star neighborhood. Use starting solution as $[3,0,1,1,1,1{]}^T.$ Handle Constraint $(2)$&$(3)$ by creating a penalized objective function. Assume all the penalty coefficients are equal to $1000.$

$($d$)$ Execute $3$ full iterations of the random$-$walk search with the extended$/$expanded neighborhood. Use starting solution as $[3,0,1,1,1,1{]}^T.$ Handle Constraint $(2)$ & $(3)$ by creating a penalized objective function. Assume all the penalty coefficients are equal to $1000.$ Use random numbers from the random number table. See explanation at the end of this HW for generating random numbers.

$($e$)$ Execute $4$ iterations of the simulated annealing with following parameters: Initial temperature be $1000,$ and starting solution be $[3,0,1,1,1,1{]}^T.$ Neighborhood type $=$ Extended neighborhood, Move type $=$ Random walk, Pool size $=1,$ Max # tries $=4.$ Cooling mechanism $=$ After $2$ iterations $($irrespective of success or failure in the iteration$),$ reduce the temperature to $500,$ and continue with the remaining iterations. Handle Constraint$(2)$ & $(3)$ by creating a penalized objective function. Assume all the penalty coefficients are equal to $1000.$

$($f$)$ Execute one next iteration of the tabu search with following parameters: Current solution $=[3,0,1,1,1,1{]}^T.$ Neighborhood type $=$ Immediate neighborhood, Move type $=$ Greedy move, Tenure period $=6,$ and the current tabu list is: $\{[4,0,1,1,1,1{]}^T,[3,0,2,1,1,1{]}^T,[3,2,1,1,1,1{]}^T,[3,0,1,2,1,1{]}^T,[3,0,1,2,1,1{]}^T,[3,0,1,1,1,2{]}^T\}$ The Constraint$(2)$ & $(3)$ were handled by creating a penalized objective function, where all the penalty coefficients are equal to $1000.$