SIMULATED ANNEALING

FOR INTEGER LINEAR PROGRAMMING PROBLEMS

Swetha B

24-PMT-044

II PG Mathematics

Department of Mathematics

Loyola College, Chennai - 600034

PROCESS
STEP 1: Solve the ILP as an LPP and get the rounded solution, 𝑋 = 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 .

STEP 2: Fix the obtained rounded solution as the initial solution.

STEP 3: Set up the initial temperature 𝑇0 = 𝑟0 × 𝐿𝑃𝑃 𝑂𝑏𝑗𝑒𝑐𝑡𝑖𝑣𝑒 𝑣𝑎𝑙𝑢𝑒, where 𝑟0 is the reduction
ratio (0 < 𝑟 < 1).

STEP 4: Set up the temperature reduction ratio 𝑟.

STEP 5: Find 𝐼 ∗ , the minimum of infeasibility measures of the neighboring solutions*.

 If 𝐼 ∗ = 0, then the solution is feasible and accepted.
 If 𝐼 ∗ ≠ 0, then the solution is infeasible and we’re allowed to search for a feasible solution.
* If 𝑋 = 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 = 4, 0, 5, 6 and we target the variable 𝑥3 (chosen on a random basis), then the neighbouring
solutions will be 4, 0, 𝟒, 6 and 4, 0, 𝟔, 6 .
PROCESS

STEP 6: Find the objective value of the solution.

STEP 7: Compare this with the objective value of the last accepted solution. In accordance to maximization
of an ILP,
 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 𝑜𝑏𝑗𝑒𝑐𝑡𝑖𝑣𝑒 𝑣𝑎𝑙𝑢𝑒 ≥ 𝑙𝑎𝑠𝑡 𝑜𝑏𝑗𝑒𝑐𝑡𝑖𝑣𝑒 𝑣𝑎𝑙𝑢𝑒 ⟶ accept the solution.
 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 𝑜𝑏𝑗𝑒𝑐𝑡𝑖𝑣𝑒 𝑣𝑎𝑙𝑢𝑒 < 𝑙𝑎𝑠𝑡 𝑜𝑏𝑗𝑒𝑐𝑡𝑖𝑣𝑒 𝑣𝑎𝑙𝑢𝑒 ⟶ accept or reject the solution with a probability*.

STEP 8: Repeat Steps 5-7 until your desired stopping criterion is met.

STEP 9: Best feasible solution is found in the ‘accept-iteration’ where the objective value is near to the
original optimum.

* Probability = 𝑒 −Δ/𝑇 , Δ = 𝐶ℎ𝑎𝑛𝑔𝑒 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑏𝑗𝑒𝑐𝑡𝑖𝑣𝑒 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 = 𝑧𝑐𝑢𝑟𝑟𝑒𝑛𝑡 − 𝑧𝑙𝑎𝑠𝑡

POINTS TO REMEMBER
 Prior to the start of the solution, fix the number of ‘accept-iterations’ needed to trigger
temperature reduction – 𝑎 ∗ .
 If we let 𝑎 to be the number of ‘accept-iterations’ obtained so far in the iterative process and if
𝑎 = 𝑎 ∗ , then temperature is reduced in the next iteration. We do this for every 𝑎 ∗ number of
‘accept-iterations’.
 If the solution set is encountered previously, reject it and move to the next iteration.
 Changes in the solution set is made by considering the last accepted solution set.
 Common stopping criterions include:
 Temperature exceeds its minimum value.
 Number of iterations is exceeded.
 Changes in the objective value is too small.
 No improvements in the objective value.
PSEUDOCODE
Initialization Process

Iterative Process
EXAMPLE

Maximize 𝑧 = 2𝑥1 + 𝑥2 + 3𝑥3 + 2𝑥4 Optimum solution found by solving as an LPP:

𝑋 = 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 = 4.625, 0, 14.625, 14.5

Subject to

𝑥1 + 2𝑥2 − 3𝑥3 − 𝑥4 ≤ 10 with objective value 𝑧 = 82.125.

3𝑥1 − 2𝑥2 + 𝑥3 − 𝑥4 ≤ 14 Rounded solution: 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 = 5, 0, 15, 15

2𝑥1 + 𝑥2 − 2𝑥3 + 2𝑥4 ≤ 9 with objective value 85.

−𝑥1 + 𝑥2 + 𝑥3 ≤ 10 Set rounded solution as the initial solution.
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 are non-negative integers Set 𝑇0 = 0.75 𝐿𝑃𝑃 𝑂𝑏𝑗𝑒𝑐𝑡𝑖𝑣𝑒 𝑣𝑎𝑙𝑢𝑒 ≈ 62.

Set 𝑎 ∗ = 2. Set 𝑟 = 0.5.

 S 𝚫
𝑖 𝑰∗ 𝒛𝒄𝒖𝒓𝒓𝒆𝒏𝒕 𝒛𝒍𝒂𝒔𝒕 𝑻 𝒆 −𝑻 𝑹 Search/Accept/Reject 𝒂
𝑥1 𝑥2 𝑥3 𝑥4
Initial 5 0 15 15 2 85 −∞ 62 - - Infeasible solution: Search 0
1 4 0 15 15 1 83 −∞ 62 - - Infeasible solution: Search 0
2 4 0 15 14 1 81 −∞ 62 - - Infeasible solution: Search 0
3 4 0 14 14 0 78 −∞ 62 - - Feasible solution: Accept 1
4 4 0 13 14 1 75 78 62 - - Infeasible solution: Search 1
5 4 0 14 14 0 78 78 62 - - Redundant solution: Reject 1
6 4 0 13 13 0 73 78 62 0.92 0.11 𝑅 < 𝑒 −Δ/𝑇 : Accept 2
7 4 1 13 13 0 74 73 31 - - 𝑧𝑐𝑢𝑟𝑟𝑒𝑛𝑡 > 𝑧𝑙𝑎𝑠𝑡 : Accept 1
8 4 1 13 12 0 72 74 31 0.94 0.93 𝑅 < 𝑒 −Δ/𝑇 : Accept 2
9 4 1 12 12 0 69 72 15.5 0.82 0.96 𝑅 > 𝑒 −Δ/𝑇 : Reject 0
10 4 0 13 12 0 71 72 15.5 0.94 0.38 𝑅 < 𝑒 −Δ/𝑇 : Accept 1
 S 𝚫
𝑖 𝑰∗ 𝒛𝒄𝒖𝒓𝒓𝒆𝒏𝒕 𝒛𝒍𝒂𝒔𝒕 𝑻 𝒆 −𝑻 𝑹 Search/Accept/Reject 𝒂
𝑥1 𝑥2 𝑥3 𝑥4
Initial 5 0 15 15 2 85 −∞ 62 - - Infeasible solution: Search 0
1 4 0 15 15 1 83 −∞ 62 - - Infeasible solution: Search 0
2 4 0 15 14 1 81 −∞ 62 - - Infeasible solution: Search 0
3 4 0 14 14 0 78 −∞ 62 - - Feasible solution: Accept 1
4 4 0 13 14 1 75 78 62 - - Infeasible solution: Search 1
5 4 0 14 14 0 78 78 62 - - Redundant solution: Reject 1
6 4 0 13 13 0 73 78 62 0.92 0.11 𝑅 < 𝑒 −Δ/𝑇 : Accept 2
7 4 1 13 13 0 74 73 31 - - 𝑧𝑐𝑢𝑟𝑟𝑒𝑛𝑡 > 𝑧𝑙𝑎𝑠𝑡 : Accept 1
8 4 1 13 12 0 72 74 31 0.94 0.93 𝑅 < 𝑒 −Δ/𝑇 : Accept 2
9 4 1 12 12 0 69 72 15.5 0.82 0.96 𝑅 > 𝑒 −Δ/𝑇 : Reject 0
10 4 0 13 12 0 71 72 15.5 0.94 0.38 𝑅 < 𝑒 −Δ/𝑇 : Accept 1
 S 𝚫
𝑖 𝑰∗ 𝒛𝒄𝒖𝒓𝒓𝒆𝒏𝒕 𝒛𝒍𝒂𝒔𝒕 𝑻 𝒆 −𝑻 𝑹 Search/Accept/Reject 𝒂
𝑥1 𝑥2 𝑥3 𝑥4
Initial 5 0 15 15 2 85 −∞ 62 - - Infeasible solution: Search 0
1 4 0 15 15 1 83 −∞ 62 - - Infeasible solution: Search 0
2 4 0 15 14 1 81 −∞ 62 - - Infeasible solution: Search 0
3 4 0 14 14 0 78 −∞ 62 - - Feasible solution: Accept 1
4 4 0 13 14 1 75 78 62 - - Infeasible solution: Search 1
5 4 0 14 14 0 78 78 62 - - Redundant solution: Reject 1
6 4 0 13 13 0 73 78 62 0.92 0.11 𝑅 < 𝑒 −Δ/𝑇 : Accept 2
7 4 1 13 13 0 74 73 31 - - 𝑧𝑐𝑢𝑟𝑟𝑒𝑛𝑡 > 𝑧𝑙𝑎𝑠𝑡 : Accept 1
8 4 1 13 12 0 72 74 31 0.94 0.93 𝑅 < 𝑒 −Δ/𝑇 : Accept 2
9 4 1 12 12 0 69 72 15.5 0.82 0.96 𝑅 > 𝑒 −Δ/𝑇 : Reject 0
10 4 0 13 12 0 71 72 15.5 0.94 0.38 𝑅 < 𝑒 −Δ/𝑇 : Accept 1
 S 𝚫
𝑖 𝑰∗ 𝒛𝒄𝒖𝒓𝒓𝒆𝒏𝒕 𝒛𝒍𝒂𝒔𝒕 𝑻 𝒆 −𝑻 𝑹 Search/Accept/Reject 𝒂
𝑥1 𝑥2 𝑥3 𝑥4
Initial 5 0 15 15 2 85 −∞ 62 - - Infeasible solution: Search 0
1 4 0 15 15 1 83 −∞ 62 - - Infeasible solution: Search 0
2 4 0 15 14 1 81 −∞ 62 - - Infeasible solution: Search 0
3 4 0 14 14 0 78 −∞ 62 - - Feasible solution: Accept 1
4 4 0 13 14 1 75 78 62 - - Infeasible solution: Search 1
5 4 0 14 14 0 78 78 62 - - Redundant solution: Reject 1
6 4 0 13 13 0 73 78 62 0.92 0.11 𝑅 < 𝑒 −Δ/𝑇 : Accept 2
7 4 1 13 13 0 74 73 31 - - 𝑧𝑐𝑢𝑟𝑟𝑒𝑛𝑡 > 𝑧𝑙𝑎𝑠𝑡 : Accept 1
8 4 1 13 12 0 72 74 31 0.94 0.93 𝑅 < 𝑒 −Δ/𝑇 : Accept 2
9 4 1 12 12 0 69 72 15.5 0.82 0.96 𝑅 > 𝑒 −Δ/𝑇 : Reject 0
10 4 0 13 12 0 71 72 15.5 0.94 0.38 𝑅 < 𝑒 −Δ/𝑇 : Accept 1
 S 𝚫
𝑖 𝑰∗ 𝒛𝒄𝒖𝒓𝒓𝒆𝒏𝒕 𝒛𝒍𝒂𝒔𝒕 𝑻 𝒆 −𝑻 𝑹 Search/Accept/Reject 𝒂
𝑥1 𝑥2 𝑥3 𝑥4
Initial 5 0 15 15 2 85 −∞ 62 - - Infeasible solution: Search 0
1 4 0 15 15 1 83 −∞ 62 - - Infeasible solution: Search 0
2 4 0 15 14 1 81 −∞ 62 - - Infeasible solution: Search 0
3 4 0 14 14 0 78 −∞ 62 - - Feasible solution: Accept 1
4 4 0 13 14 1 75 78 62 - - Infeasible solution: Search 1
5 4 0 14 14 0 78 78 62 - - Redundant solution: Reject 1
6 4 0 13 13 0 73 78 62 0.92 0.11 𝑅 < 𝑒 −Δ/𝑇 : Accept 2
7 4 1 13 13 0 74 73 31 - - 𝑧𝑐𝑢𝑟𝑟𝑒𝑛𝑡 > 𝑧𝑙𝑎𝑠𝑡 : Accept 1
8 4 1 13 12 0 72 74 31 0.94 0.93 𝑅 < 𝑒 −Δ/𝑇 : Accept 2
9 4 1 12 12 0 69 72 15.5 0.82 0.96 𝑅 > 𝑒 −Δ/𝑇 : Reject 0
10 4 0 13 12 0 71 72 15.5 0.94 0.38 𝑅 < 𝑒 −Δ/𝑇 : Accept 1
 S 𝚫
𝑖 𝑰∗ 𝒛𝒄𝒖𝒓𝒓𝒆𝒏𝒕 𝒛𝒍𝒂𝒔𝒕 𝑻 𝒆 −𝑻 𝑹 Search/Accept/Reject 𝒂
𝑥1 𝑥2 𝑥3 𝑥4
Initial 5 0 15 15 2 85 −∞ 62 - - Infeasible solution: Search 0
1 4 0 15 15 1 83 −∞ 62 - - Infeasible solution: Search 0
2 4 0 15 14 1 81 −∞ 62 - - Infeasible solution: Search 0
3 4 0 14 14 0 78 −∞ 62 - - Feasible solution: Accept 1
4 4 0 13 14 1 75 78 62 - - Infeasible solution: Search 1
5 4 0 14 14 0 78 78 62 - - Redundant solution: Reject 1
6 4 0 13 13 0 73 78 62 0.92 0.11 𝑅 < 𝑒 −Δ/𝑇 : Accept 2
7 4 1 13 13 0 74 73 31 - - 𝑧𝑐𝑢𝑟𝑟𝑒𝑛𝑡 > 𝑧𝑙𝑎𝑠𝑡 : Accept 1
8 4 1 13 12 0 72 74 31 0.94 0.93 𝑅 < 𝑒 −Δ/𝑇 : Accept 2
9 4 1 12 12 0 69 72 15.5 0.82 0.96 𝑅 > 𝑒 −Δ/𝑇 : Reject 0
10 4 0 13 12 0 71 72 15.5 0.94 0.38 𝑅 < 𝑒 −Δ/𝑇 : Accept 1
 S 𝚫
𝑖 𝑰∗ 𝒛𝒄𝒖𝒓𝒓𝒆𝒏𝒕 𝒛𝒍𝒂𝒔𝒕 𝑻 𝒆 −𝑻 𝑹 Search/Accept/Reject 𝒂
𝑥1 𝑥2 𝑥3 𝑥4
Initial 5 0 15 15 2 85 −∞ 62 - - Infeasible solution: Search 0
1 4 0 15 15 1 83 −∞ 62 - - Infeasible solution: Search 0
2 4 0 15 14 1 81 −∞ 62 - - Infeasible solution: Search 0
3 4 0 14 14 0 78
Best!
−∞ 62 - - Feasible solution: Accept 1
4 4 0 13 14 1 75 78 62 - - Infeasible solution: Search 1
5 4 0 14 14 0 78 78 62 - - Redundant solution: Reject 1
6 4 0 13 13 0 73 78 62 0.92 0.11 𝑅 < 𝑒 −Δ/𝑇 : Accept 2
7 4 1 13 13 0 74 73 31 - - 𝑧𝑐𝑢𝑟𝑟𝑒𝑛𝑡 > 𝑧𝑙𝑎𝑠𝑡 : Accept 1
8 4 1 13 12 0 72 74 31 0.94 0.93 𝑅 < 𝑒 −Δ/𝑇 : Accept 2
9 4 1 12 12 0 69 72 15.5 0.82 0.96 𝑅 > 𝑒 −Δ/𝑇 : Reject 0
10 4 0 13 12 0 71 72 15.5 0.94 0.38 𝑅 < 𝑒 −Δ/𝑇 : Accept 1
EXPLANATION

 Initial Iteration: Rounded solution (5,0,15,15) is considered with objective value 85; Temperature is initialized
to 62. Infeasibility measure is found by the following steps:

 Substitute the point in all the 𝑐 constraints.

 If a constraint 𝑐𝑖 is satisfied, give penalty 𝑃𝑖 = 0; If not, give penalty 𝑃𝑖 = ∑𝑎𝑖𝑗 𝑥𝑗 − 𝑏𝑗 .

 For the initial iteration, the first and last constraints are satisfied but the remaining constraints are not satisfied, so
𝑃2 = 15 − 14 = 1 and 𝑃3 = 10 − 9 = 1. Sum of the penalties = Infeasibility measure. Hence, here the infeasibility
measure is found to be 2.

 Solution is infeasible because 𝐼 ∗ ≠ 0. Therefore, we’re allowed to search for a feasible solution.
EXPLANATION

First Iteration

 Target variable 𝑥1 = 5, the neighboring points are found to be 4,0,15,15 and 6,0,15,15 .

 Calculate the infeasibility measure at both points and pick the least out of it, the corresponding solution is
considered for this iteration. Since 𝐼 ∗ 4,0,15,15 < 𝐼 ∗ (6,0,15,15), we set our solution to 4,0,15,15 .

 𝑧𝑐𝑢𝑟𝑟𝑒𝑛𝑡 = 83 and 𝑧𝑙𝑎𝑠𝑡 = −∞ (default) since so far, we have not yet accepted any solution.

 Solution is infeasible since 𝐼 ∗ = 1, therefore, we are allowed to search for a feasible solution.

Second Iteration

As proceeded in first iteration.

EXPLANATION

Third Iteration

 Target variable 𝑥3 = 15, the neighboring points are found to be 4,0,14,14 and 4,0,16,14 .

 Calculate the infeasibility measure at both points and pick the least out of it, the corresponding solution is
considered for this iteration. Since 𝐼 ∗ 4,0,14,14 < 𝐼 ∗ (4,0,16,14), we set our solution to 4,0,14,15 .

 𝑧𝑐𝑢𝑟𝑟𝑒𝑛𝑡 = 78 and 𝑧𝑙𝑎𝑠𝑡 = −∞ (default) since, we have not yet accepted any solution.

 Solution is feasible since 𝐼 ∗ = 0.

 Comparing 𝑧𝑐𝑢𝑟𝑟𝑒𝑛𝑡 and 𝑧𝑙𝑎𝑠𝑡 , current value is much better. So, set 𝑧𝑙𝑎𝑠𝑡 = 78 for the upcoming iterations.

 Therefore, we accept the feasible solution obtained in this iteration. Don’t forget to set 𝑎 = 1 since we have now
obtained one ‘accept-iteration’!
EXPLANATION

Fourth Iteration

As proceeded in the previous iterations.

Note: 𝑧𝑙𝑎𝑠𝑡 = 78 since the last accepted solution obtained in 3rd iteration has an objective value of 78.

Fifth Iteration

As proceeded in the previous iterations.

Note: Previous solution set is encountered again, therefore, we reject the solution.
EXPLANATION

Sixth Iteration
As proceeded in the previous iterations.
Note:
1. Here, we didn’t use the solution set obtained in the 5th iteration to find neighboring points because, we have rejected the
solution in that iteration. So, we have used the solution obtained in the 4th iteration because it is the last accepted solution.
2. 𝑧𝑐𝑢𝑟𝑟𝑒𝑛𝑡 = 73 and 𝑧𝑙𝑎𝑠𝑡 = 78 in this iteration; Current solution is not better than the last one, but we still have the
option to accept or reject because the solution set is feasible.
3. To decide whether to accept or reject, we find 𝑒 −Δ/𝑇 and compare it with a random number. Since 𝑅 < 𝑒 −Δ/𝑇 , we accept
the solution. Thus, set 𝑧𝑙𝑎𝑠𝑡 = 73.
4. Also, 𝑎 = 2 because we now have two ‘accept-iterations’. So, the temperature is reduced in the next iteration and 𝑎 value
is reset to 0.
EXPLANATION

Seventh Iteration
As proceeded in the previous iterations.
Note:
1. Temperature is reduced to 31.

2. 𝑧𝑐𝑢𝑟𝑟𝑒𝑛𝑡 = 74 > 𝑧𝑙𝑎𝑠𝑡 = 73; therefore, we accept the solution and set 𝑧𝑙𝑎𝑠𝑡 = 74.
3. Set 𝑎 = 1 because we just accepted a solution.

Eigth Iteration
As proceeded in the previous iterations.
 EXPLANATION
Ninth Iteration
As proceeded in the previous iterations.
Note:
1. Since 𝑅 > 𝑒 −𝛥/𝑇 , we reject the solution.

2. Also, temperature is reduced here because we had obtained 𝑎 = 2 in the previous iteration.

Tenth Iteration
As proceeded in the previous iterations.
Note: Last accepted solution is found in the eighth iteration which is why neighbor of this solution is used in the iteration.
For the sake of simplicity, the book has limited to 10 iterations. However, the number of iterations can go beyond
thousands of iterations as well. Supposing that our stopping criterion to be not more than 10 iterations, the best
solution for our problem is found to be in the third iteration where S = 4,0,14,14 with objective value 78.
THANK YOU