Operation research - Heuristic methods

[This sheet must be completed and attached to the last page of your homework]

ISE 421

Operations Research II

Term 161

Homework #3

Student Name ID# Signature

Homework Guidelines

To receive full credit, you should make sure you follow the following guidelines.

Homework Presentation:

• Every main problem should be answered on a different page.

• You should submit the solutions for the first two problems only.

• All pages of your homework should be in chronological order.

• Your name, and the homework number should be clearly indicated.

Modeling Questions:

• Clearly define all the variables in one group. Then clearly define all the parameters in another group. Then display the final model in the standard style (Objective, Constraints, Restriction on Domain).

• For GAMS software questions, you should give the GAMS model and the part of GAMS output that gives the solution (do not attach dozens of pages of GAMS output). Moreover, the solution of the model should be presented in the text. That is, write what are the optimal values of variables and objective in the paper. Make sure, you incorporate scaling of objective and/or constraints.

• For VBA code, give the VBA code file. In addition to that, the solution of the model should be presented in the text.

ISE-421 HW-3

Problem #1

Consider the following optimization problem:

min :

6∑ i=1

x2i − 4 6∑

i=1

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 (available in the course blackboard).

(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 (available in the course blackboard).

(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 ).

1

ISE-421 HW-3

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 value A 29 B 34 C 31 D 24

(b) Using the random numbers from the Random Number Table (available in the course black- board), 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.

2

ISE-421 HW-3

Problem #3 Practice Only

Consider the cover problem (Example-3) 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 Annea- ling (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.

3