Instructions for Obtaining Random Numbers

For each problem $(1)$ or its part where random numbers are needed, obtain them from the consecutive random digits from

Random Number Table as follows. Start from a seed location. Assume for this HW the seed location is first column & first

row of the table $($i$.$e$.,$ seed at $(1,1)).$ Now read the five$-$digits of from the seed location and form a random numbers by placing

a decimal point in front. From seed $(1,1)$ the first random number is $0\mathrm{.}13962,$ and the second random number is $0\mathrm{.}70992.$

Once you reach the end of the first row, start from the first column of the next row. Always restart the generation of random

numbers for each new problem $($or any sub$-$problem$).$ For this HW the seed is $(1,1).$ If any random number that you

use results in infeasibility, then discard it and move to the next random number. An example for Problem$-1$ is given below.

Extended Neighbors For generating an extended neighbor, you need two random variables $R_1$ and $R_2,$ such that $0$

$R_{1}1$ and $0R_{2}1.$ Use first random variable $(R_1)$ to identify the position or variable to update from the

current solution. Use second random variable $(R_2)$ to get the value of the selected element. To select the variable

or position to update, use the following formula:

position $=1+{|}_{{?}_{?}}{R}_1**M_{{?}_{?}}|$

where $M$ is the total number of variables, $\backslash$lfloor$\backslash$rfloor is the floor function. If the position is infeasible, then repeat the above

position calculation with the next random number until we get a feasible position. To get the value of the selected

position, use the following formula.

value $=$ old value $+{|}_{{?}_{?}}(R_2-0\mathrm{.}5)**(U-L{)}_{{?}_{?}}|$

where 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 star$-$

ting 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 neighbor$-$

hood, 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.$