ISE 421 Operations Research II Assignment
Problem 1 - Consider the following optimization problem:
min:
i=1∑6xi2 - 4i=1∑6 xi - 24 (1)
s.t.:
x1 - 2x2 - x3 = 0 (2)
x4 + x5 + x6 = 5 (3)
1 ≤ xi ≤ 9 ∀i = 1, . . . , 6 (4)
where the variables of the multivariable optimization problem are integers.
(a) Let [9, 4, 1, 1, 3, 1]T be the current solution. Ignore Constraints (2) & (3), and write all the possible feasible immediate neighbors of the current solution.
(b) Let [9, 4, 1, 1, 3, 1]T be the current solution. Ignore Constraints (2) & (3), and write 3 possible feasible extended neighbors of the current solution. Use Random Number Table (available in the course blackboard).
(c) Ignore Constraints (2) & (3), execute one full iteration of the greedy search with the immediate neighborhood. Use starting solution as [9, 4, 1, 1, 3, 1]T.
(d) Ignore Constraints (2) & (3), execute 3 full iterations of the random-walk search with the extended neighborhood. Use starting solution as [9, 4, 1, 1, 3, 1]T. Use Random Number Table.
(e) Ignore Constraints (2) & (3). Let initial temperature be 1000, and starting solution be [9, 4, 1, 1, 3, 1]T. Execute 6 iterations of the simulated annealing. After 3 iterations, reduce the temperature to 200, and continue with the remaining iterations. Use Random Number Table.
(f) Design an objective function to incorporate Constraints (2) & (3) in the greedy or random-walk heuristics.
(g) Consider constraint: x1 - 2x2 - x3 = 0. Use the constraint programming approach to update the bounds of x1, x2 and x3.
(h) Consider constraint: x4 + x5 + x6 = 5. Use the constraint programming approach to update the bounds of the related variables.
(i) Use the information from Part (f), Part (g) and Part (h), and re-write the formulation.
(j) Use the bound information from Part (i), and write all the possible immediate neighbors of the current solution ([9, 4, 1, 1, 3, 1]T).
Problem 2 - Consider the simulated annealing algorithm. The objective type is to minimize the given objective function.
(a) Let T = 20 be the current value of the temperature. Let the objective function value of the current solution be 30. Starting from the current solution, determine the probability of accepting each of the following neighbor as the current solution for the next iteration.
|
Neighbor
|
Objective function time
|
|
A
|
29
|
|
B
|
34
|
|
C
|
31
|
|
D
|
24
|
(b) Using the random numbers from the Random Number Table (available in the course blackboard), determine which of the neighbors from Part (a) would have been actually accepted as the current solution for the next iteration.
(c) If the value of temperature is cooled down to T = 2, then calculate the probabilities of Part (a). Assume the objective function value of the current solution is 30.
(d) Compare the probabilities for each neighbor from Part (a) and Part (c). What can you infer? Explain.
(e) Let the objective function value of the current solution be 10. Let the objective function value of a randomly generated neighbor be 400. What should be the minimum value of the temperature, for which the randomly generated neighbor will be accepted for sure as the current solution for the next iteration.
(f) Let the objective function value of the current solution be 10. Let the objective function value of a randomly generated neighbor be 400. What should be the minimum value of the temperature, for which the randomly generated neighbor will be accepted with 50% probability as the current solution for the next iteration.
(g) Let the current temperature be 10. If the cooling schedule is of the following type: Tnew = 0.9Told, then how many temperature updates are required for temperature to cool down to 0.2.
(h) Let the current temperature be 10. If the cooling schedule is of the following type: Tnew = 0.95Told, then how many temperature updates are required for temperature to cool down to 0.2.
(i) What can you infer from Part (g) and Part (h)? Explain.
(j) Let the minimum value of the objective function be -10, and the maximum value be 1000 units. What should be the minimum value of the initial temperature, so that the algorithm can easily explore all of the feasible space?
Problem 3: Practice Only
Consider the cover problem from the Integer Programming Slide.
(a) Solve the cover problem using Cplex solver.
(b) Incorporate the constraint in the objective function. Solve the problem using Greedy Heuristic with Immediate Neighbors (use VBA code). Select reasonable values for the scaling parameters.
(c) Incorporate the constraint in the objective function. Solve the problem using Random-Walk Heuristic (use VBA code). Select reasonable values for the scaling parameters.
(d) Incorporate the constraint in the objective function. Solve the problem using Simulated Annealing (use VBA code). Select reasonable values for the scaling parameters. Try different values of the initial temperature, and other parameters to find a good solution.
(e) Use the solution obtained from Part (d) as the initial solution of the greedy heuristic. Execute the greedy search using the VBA code.
(f) Compare the objective function value of all the above parts.