Luận án Một số lớp bài toán tối ưu không lồi: Thuật toán và ứng dụng

9.7 {5}†1282.7| 5789.7 {5}†1389.5 |5789.7 {5}† 1368.7|5789.7 12.9|0 MSO K M 10 23.6 54.0| 69.1 53.1| 72.4 59.2| 70.3 54.2| 71.4 10.3 |3.2 11 25.4 105.4| 74.5 72.8| 80.4 118.5| 76.7 92.3 | 76 38.6|7.3 4 12 34 170.8| 99.4 149.5| 105.4 174.6| 102.4 174.3| 103.2 12.5 | 5.7 MSO 13 30 258.3| 89.9 213.8 | 96.6 260.9| 89.3 249.2| 91.4 18.1|7.6 (Group 1) 14 34.3 427.9|105.4 327.9 |109.9 426.4|104.5 406.7 |107.1 23.4 | 4.9 15 45.3 654.4|134.2 491.8|139.2 701.3|136.7 616.9|144.6 29.9| 7.2 10 34.2 885.7|100.8 799.5 |114.8 925.0 |103.1 816.0|110.1 13.6|12.2 5 11 43.1 942.0|128 757.6 |140.9 1032.1|129.6 920.0|135.6 26.6| 9.2 12 45.33 {1}†2533.8|137.6 {1}†2004.7|144.2 {1}† 2693.8| 139.2 {1}†2111.0|141.2 25.6|4.6 Avg. 35.03 {1}† 670.3|104.3 {1}†541.2| 111.5 {1}† 710.2 |105.8 {1}†604.5| 109.0 23.8|6.5 14 32.6 341.6|97.3 284.4|101.4 345.2|96.7 345.7|100.4 17.7|4.6 5 15 38.6 1032.7|117.2 926.3 |132.6 1096.4|118.5 1042.6|127 15.5|11.6 16 37.8 786.9 |117.8 749.7 |120.4 857.6|117 716.2|124.6 16.5| 6.1 MSO 10 33.4 474.9|101.7 344.0|111.1 433.8|101 454.6|111.2 27.6|9.2 (Group 2) 6 11 27.6 302.2|81.2 276.4|86.6 314.8|85.6 297.2|84.6 12.2| 6.2 12 44.5 922.7|133.8 871.7 |151.1 872.7|137.6 930.1|147.5 6.3| 11.4 13 36.6 829.6|109.2 733.3|116.1 911.2|111.4 704.9|113.5 22.6|5.9 10 45.5 612.6|136.7 587.6|146.9 744.6|139.9 554.0|144 25.6| 6.9 7 11 45.6 1857.3|136.8 1660.0|149.2 1897.3|139.5 1953.3 |149.7 15.0|8.6 12 57 {1}†2565.4|173.4 {1}† 2239.7|187.3 {1}†2545.8|179.1 {1}†2281.8 |179.9 12.7|7.4 Avg. 39.92 {1}†972.6|120.5 {1}† 867.3| 130.3 {1}†1001.9 |122.6 {1}† 928.0| 128.2 13.4|7.5 † Số các ví dụ không giải được trong thời gian cho phép 7200s. 73 Bảng 3.3: Kết quả tính toán theo Thuật toán 3.1- RE Time (s)| iterations Diff.(%) Bài toán m n #YN Prio. 1 Prio. 2 LIFO FIFO 10 9.8 2.78 |30.4 2.8 |31.3 2.73 |30.4 2.69 |30.4 4.1|3.0 20 38 10.12|114.9 9.99|114.8 10.1|114.9 10.04|114.8 1.3|0 30 115.8 32.86| 348.2 32.58 | 348 32.59| 348 32.46| 347.9 1.2 | 0 40 311.2 92.54|930.9 95.02 |931.3 93.74|931.8 95.47|930.2 3.2|0 50 444.2 137.3| 1325.6 146.9| 1327.3 147.9| 1327.1 150.4 | 1325.2 9.5|0 3 60 917.1 312.1|2739.7 317.9|2737.9 318.7|2741.3 319.9|2734.7 2.3|0 70 1643.4 579.3|4895.3 580.1 |4895.9 583.9|4896.4 583.8 |4885.8 0| 0 80 2295.8 824.4| 6835 808.1 | 6838.7 813.2| 6839.7 826.2| 6832.2 2.2| 0 M 90 3107.8 1217.1| 9256 1183.1|9257.9 1196.3|9266.5 1196.8|9248.4 2.9| 0 O 100 5849.1 2556.6 | 17413.8 2453.8 | 17422.5 2489.6| 17429.9 2464.2| 17398.2 4.2| 0 K 10 11.6 5.06 |54.7 4.8 |54.9 4.77|54.9 4.77|54.8 6.1| 0 4 20 136.8 73.09| 797.3 72.45| 797.5 71.71| 797.6 71| 797.1 2.9| 0 30 397.6 231.0|2394.8 226.6 |2390.4 228.6|2394.2 228.0|2390 1.9|0 40 1808.6 1217.8|11652.2 1173.0|11652.6 1205.4|11651.5 1189.1 |11634.3 3.8|0 10 16.2 11.71|135 11.75 |135 11.53|135 11.52|135 2.0|0 5 20 161.2 208.9| 2029.1 189.1 | 2030 190.4| 2029.2 196.8 | 2028.4 10.5|0 30 730.6 {1}† 1245.6|11367.1 {1}† 1199.9| 11367 {1}† 1231.6|11369.3 {1}† 1228.6 |11358.7 3.8|0 6 10 23.4 28.53|324.5 28.42 |324.5 27.96|324.5 27.6|324.5 3.4|0 20 272 911.7 |9262.9 923.4 |9260.1 941.0 |9264.6 971.5|9259.4 6.6 | 0 7 10 23.1 83.0|961.1 83.79 |962.4 84.46|961.3 85.9|960.7 3.5|0 8 10 29.9 166.4 | 1817.5 171.1|1817.7 173.1| 1817 175.6| 1817.7 5.5|0 Avg. 873.49 {1}†473.7|4032.7 {1}†462.6| 4033.2 {1}†469.5 |4034.5 {1}†470.2|4029 2.4|0 25 14.1 3.61 |41.6 3.61 |41.7 3.61|42 3.53 |41.2 2.3|0 100 176.8 50.5|478.3 49.25|468.5 50.28|477.7 49.14 |465.7 2.3|0 225 674.9 287.1|1774.3 286.3|1739.5 295.1|1779.3 286|1728.3 3.1|3.0 M 3 400 1860.5 1038.1| 4721 993.7| 4545.4 1063.7| 4722 1032.2| 4538.7 7.0|4.0 O 625 3567.8 2690.4|8992.8 2476.2 |8458.1 2675.5|8837.2 2517.2|8505.6 8.7| 6.3 A 900 6181.3 {1}†4905.9| 14697.7 4679.7 | 14234.5 {1}† 4809.2| 14421 4810.4 | 14348.8 +|+ #YN = 5929.1 #YN = 5929.1 25 31.4 13.8 |154.8 13.73 |158.3 13.59 | 156.8 13.33 |154 3.5|2.8 4 100 971.1 605.3 |4609.4 560.1|4492.6 586.3|4530 580.5|4424.3 8.1| 4.2 225 5018.6 {5}† 5735.1| 22753.2 {5}† 4694| 21319 {5}† 5348.5| 21904.4 {5}† 5074.3| 21173.6 22.2|3.5 Avg. 2055.17 {6}†1703.3| 6469.2 {5}†1528.5| 6162 {6}†1649.5 |6318.9 {5}† 1596.3|6153.4 +|+ MSO K M 10 23.6 62.5| 72 60.7| 71.7 68.9| 71.8 64.5| 71.6 11.9 |0 11 25.4 136.1| 76.8 97.1| 77.1 154.1| 77.3 121.4 | 76.8 37.0|0 4 12 34 205.4|102.2 176.7 |102.3 211.8|102.6 201.1|101.6 16.6 | 0 MSO 13 30 307.2| 90.1 254.9| 90.8 323.3| 90.5 309.5| 89.8 21.2|1.1 (Group 1) 14 34.3 511.4|103.5 398.9 |103.9 525.9|104.2 495.0 | 103.7 24.1 | 0 15 45.3 735.7|136.5 588.6|135.8 811.8|136.5 690.4|135.6 27.5|0 10 34.2 1102.5|102.1 1020.9 |102.6 {1}† 488.7|88.3 1015.7|101.7 +|+ #YN = 29.44 5 11 43.1 973.0|129.3 863.6|129.7 1071.0| 129.9 981.7|128.8 19.4| 0 12 45.3 {1}†2783.8|136.8 {1}†2229.0|136.8 {1}†2959.1|137.1 {1}†2696.9|136.8 24.7|0 Avg. 35.03 {1}† 757.5|105.5 {1}†632.3| 105.6 {2}† 735.0 |104.2 {1}†730.7| 105.2 +| + 14 32.6 383.6|99 316.4 |98.6 387.4|98.7 352.3|98.4 18.3|0 5 15 38.6 1219.6|116.8 1071.3|117 1294.4|116.8 1185.3|116.9 17.2|0 16 37.8 853.6|114.3 802.8|114.6 918.7|114.5 776.0|114.4 15.5| 0 MSO 10 33.4 506.0|100.4 375.5|100.8 472.4|100.8 486.4|100.4 25.8|0 (Group 2) 6 11 27.6 348.1|83.6 310.8|83.8 352.0|83.9 332.1|83.7 11.7| 0 12 44.5 986.1|133.7 907.0 |134.4 945.3|134 976.8|134 8.0| 0 13 36.6 922.5| 110.5 824.0| 110.9 1014.8| 110.5 799.6 |110.5 21.2|0 10 45.5 692.6|137.2 661.5|137.2 839.5|137.3 583.0 |137.1 30.6| 0 7 11 45.6 2061.0|137.3 1822.8 |137.5 2224.5|137.5 2028.3 |137.4 18.1|0 12 57 {1}†2776.7|171.6 {1}† 2456.6|171.4 {2}†2404.3|156 {1}†2585.4 |171.2 +|+ #YN = 51.75 Avg. 39.92 {1}†1075.0|120.4 {1}† 952.4| 120.6 {2}†1085.3 |119 {1}† 1013.0| 120.4 +|+ † Số các ví dụ không giải được trong thời gian cho phép 7200s. 74 Bảng 3.4: Kết quả tính toán theo Thuật toán 3.1- NEWVERTEX Time (s)| iterations Diff.(%) Bài toán m n #YN Prio. 1 Prio. 2 LIFO FIFO 10 9.8 2.9 | 30.4 2.8 | 30.4 2.7| 30.4 2.71| 30.4 7.4|0 20 38 10.42| 114.9 10.18| 114.8 10.18| 114.9 10.21| 114.8 2.4|0 30 115.8 33.91| 348.2 33.79| 348 33.36| 348.1 33.68| 347.9 1.6 | 0 40 311.2 91| 931.3 90.94| 931.8 90.47 | 932.4 90.16| 930.6 0|0 50 444.2 135.2| 1325.6 134.4| 1327.3 133.9| 1326.8 133.6| 1324.8 1.2|0 3 60 917.1 292.7| 2741 292.3 | 2738.7 292.6 | 2742.1 289.5| 2736 1.1|0 70 1643.4 546.43| 4895.2 546.4 | 4895.9 545.2| 4900.1 543.5 | 4885.6 0| 0 80 2295.8 786.4|6835 784.9|6838.7 783.4|6840.7 783.8|6833.8 0| 0 M 90 3107.8 1143.62| 9257.2 1143.4 | 9258.7 1140.9| 9270.4 1138.3 | 9250 0| 0 O 100 5849.1 2383.58| 17413.7 2374.1 | 17422.5 2373.7| 17430.9 2365.5 | 17399.8 0| 0 K 10 11.6 4.93|54.7 4.81|54.9 4.74|54.9 4.73|54.9 4.2| 0 4 20 136.8 71.74| 797.3 71.69| 797.5 71.71| 797.9 71.82| 797.1 0| 0 30 397.6 228.03|2394.8 228.5|2390.4 228.6|2395.3 225.3|2390.5 1.5|0 40 1808.6 1169.7 | 11652.3 1166.4| 11652.7 1168.7| 11658.1 1165.3| 11636.8 0|0 10 16.2 12.1|136.2 11.65|136.2 11.64|136.2 11.62|136.2 4.1|0 5 20 161.2 189.6| 2029.1 185.3 | 2030 186.6 | 2030.2 184.7| 2028.5 2.7|0 30 657.5 {1}† 1019.9|11366.7 {1}† 1109.2 |11367 {1}† 1122.0|11373.9 {1}†1103.5|11362.44 2.7|0 6 10 23.4 28.43|324.5 28.2 |324.5 28.2|324.5 28.1|324.5 1.2|0 20 272 1181.3| 9262.9 899.2| 9260.1 977.5| 9261 940.23 | 9259.7 31.4 | 0 7 10 23.1 116.2|961.1 90.8 |962.4 98.1|962.1 106.9|960.7 28|0 8 10 29.9 254.2| 1817.5 177.3| 1817.7 197.7| 1817.6 218.0| 1817.7 43.4|0 Avg. 873.49 {1}†462.0|4032.8 {1}†447.0| 4033.3 {1}†452.5 |4035.6 {1}†450.0|4029.7 3.4|0 25 14.1 3.76|41.6 3.7|41.7 3.59 |41.8 3.57|41.5 5.3|0 100 176.8 50.3|478.8 48.5 |468.7 49 |480.2 48 |467.7 4.8|2.3 225 674.9 273.35 |1775.5 270.1|1740.7 273.2|1782.7 265.6|1736.1 2.9| 2.7 M 3 400 1860.5 877.0| 4732.1 852.2| 4546.3 874.6| 4718.4 849.7| 4569.8 3.2|4.1 O 625 3567.8 2042.3| 9019.3 1952.3| 8458.4 2030.3|8857.9 1961.1|8576.1 4.6| 6.6 A 900 6181.3 4397.2| 15341.1 4139.5 | 14236.5 4354.0| 15070.7 4150.3 | 14476.2 6.2|7.8 25 31.4 14.3 |154.5 14.6|158.4 14.3|157.9 14.0|154.2 4.3|2.7 4 100 971.1 563.4|4613 550.3|4489.1 561|4592 542.3|4449.1 3.9| 3.7 225 5018.6 {5}† 4580.4 | 22824.6 {5}† 4334| 21332.2 {5}† 4524.9| 22319.2 {5}† 4307.3| 21386.6 6.3|7.0 Avg. 2055.17 {5}†1422.4|6553.4 {5}†1351.7|6163.6 {5}†1409.4 |6446.8 {5}†1349.1|6206.4 5.2|5.9 MSO K M 10 23.6 59.9| 72 58.5| 71.7 66.1| 71.7 61.0| 71.4 11.5|0 11 25.4 137.2| 76.8 97.5| 77.1 154.0| 77.1 120.2 | 76.7 36.7|0 4 12 34 197.0|102.2 177.5| 102.3 211.2|102.3 200.4|101.5 9.2| 1.1 MSO 13 30 307.2| 90.1 251.6| 90.8 313.9| 90.5 278.4| 89.4 19.8|1.5 (Group 1) 14 34.3 511.3|103.5 395.0|103.9 523.7|103.9 492.8 |103.3 24.6| 0 15 45.3 674.8|135.9 547.3|135.4 761.8|136.2 662.4|135.1 28.2|0 10 34.2 1083.2|102.1 882.9|101 1145.5|103 1022.9|102.1 22.9|1.9 5 11 43.1 958.3|129.2 860.0 |133.9 1069.1 |129.8 964.3|133 19.6| 3.5 12 45.3 {1}†2800.9|136.8 {1}†2259.4 |136.8 {1}†2969.3 |137 {1}†2355.7 |136.3 23.9|0 Avg. 35.03 {1}† 747.8|105.4 {1}†614.4| 105.9 {1}† 801.6 |105.7 {1}†684.2| 105.4 23.4| 0 14 32.6 380.3|99 317.6|98.6 381.1|98.7 368.4|98.4 16.7 | 0 5 15 38.6 1208.6|116.8 1032.7 |117 1277.1|116.9 1229.3|116.6 19.1|0 16 37.8 868.2|114.3 778.0|114.6 914.0|114.4 770.7|114.1 15.7| 0 MSO 10 33.4 536.3|100.4 377.6|100.8 470.5|100.7 477.2|100.3 29.6|0 (Group 2) 6 11 27.6 370.5|83.6 312.7|83.8 358.9|83.9 333.4|83.5 15.6| 0 12 44.5 1056.0|133.7 909.7|134.4 936.2|134.2 963.5|134 13.8| 0 13 36.6 985.1|110.5 825.5|110.9 1008.6|110.6 799.3|110.4 20.8|0 10 45.5 647.6|137.2 634.8|137.2 803.7|137.5 623.9|137.1 22.4| 0 7 11 45.6 1956.5|137.3 1795.3 | 137.5 2089.0|137.7 2057.0 |137.4 11.1|0 12 57 {1}†2753.6|171.6 {1}† 2442.2|171.4 {1}†2807.9|171.8 {1}†2559.0 |171.1 13.0|0 Avg. 39.92 {1}†1076.3| 120.4 {1}† 942.6| 120.6 {1}†1104.7 |120.6 {1}† 1018.2| 120.3 14.7|0 † Số các ví dụ không giải được trong thời gian cho phép 7200s. 75 Bảng 3.5: Kết quả tính toán theo Thuật toán 3.1 với các thủ tục cập nhật miền tìm kiếm và các cách quản lí khác nhau Avg. Time (s)| iterations Diff.(%) Bài toán Thuật toán 3.1 #YN Prio. 1 Prio. 2 LIFO FIFO MOK RA 873.49 {3}†522.5|3780.6 {1}†484.4| 4021 {3}†489.6 |3781.2 {2}†504.8| 3923.1 +|+ RE 873.49 {1}†473.7|4032.7 {1}†462.6| 4033.2 {1}†469.5 |4034.5 {1}†470.2|4029 2.4|0 NEWVERTEX 873.49 {1}†462.0|4032.8 {1}†447.0| 4033.3 {1}†452.5 |4035.6 {1}†450.0|4029.7 3.4|0 MOA RA 2055.17 {5}†1473.3| 5789.7 {5}†1282.7| 5789.7 {5}†1389.5 |5789.7 {5}† 1368.7|5789.7 12.9|0 RE 2055.17 {6}†1703.3| 6469.2 {5}†1528.5| 6162 {6}†1649.5 |6318.9 {5}† 1596.3|6153.4 +|+ NEWVERTEX 2055.17 {5}†1422.4|6553.4 {5}†1351.7|6163.6 {5}†1409.4 |6446.8 {5}†1349.1|6206.4 5.2|5.9 MSO RA 35.03 {1}† 670.3|104.3 {1}†541.2| 111.5 {1}† 710.2 |105.8 {1}†604.5| 109.0 23.8|6.5 (Group1) RE 35.03 {1}† 757.5|105.5 {1}†632.3| 105.6 {2}† 735.0 |104.2 {1}†730.7| 105.2 +| + NEWVERTEX 35.03 {1}† 747.8|105.4 {1}†614.4| 105.9 {1}† 801.6 |105.7 {1}†684.2| 105.4 23.4| 0 MSO RA 39.92 {1}†972.6|120.5 {1}† 867.3| 130.3 {1}†1001.9 |122.6 {1}† 928.0| 128.2 13.4|7.5 (Group2) RE 39.92 {1}†1075.0|120.4 {1}† 952.4| 120.6 {2}†1085.3 |119 {1}† 1013.0| 120.4 +|+ NEWVERTEX 39.92 {1}†1076.3| 120.4 {1}† 942.6| 120.6 {1}†1104.7 |120.6 {1}† 1018.2| 120.3 14.7|0 † Số các ví dụ không giải được trong thời gian cho phép 7200s. Dựa vào kết quả số ta rút ra một số kết luận sau: • Thuật toán 3.1- RA: Kết quả số trong Bảng 3.2 cho thấy thuật toán này chịu tác động của việc chọn u (từ tập đỉnh chính) cho cả lớp bài toán tuyến tính (với số chiều cao) và toàn phương. Đặc biệt, với một số cỡ bài toán, sự khác biệt được thể hiện rõ ràng khi có một số ví dụ giải được trong giới hạn thời gian cho phép với cách chọn này nhưng lại không giải được với cách chọn khác của u (xem trường hợp bài toán (MOK) trong Bảng 3.2). Ngoài ra, ta thấy rằng Thuật toán 3.1- RA với cách quản lí Prio. 2 cho kết quả tốt nhất với hầu hết các bài toán, trong khi đó Prio. 1 và FIFO, theo thứ tự không nên sử dụng cho thuật toán này cho trường hợp bài toán tuyến tính và toàn phương. • Thuật toán 3.1- RE: Theo Bảng 3.3, thuật toán này khá ổn định với lớp bài toán (MOK). Tuy nhiên Diff. nhận giá trị + | + với cả ba lớp bài toán còn lại (MOA, MSO (Group 1) và MSO (Group 2)). Điều đó có nghĩa là sự ảnh hưởng của việc quản lí tập đỉnh chính T đến Thuật toán 3.1- RE khác nhau đối với các lớp bài toán khác nhau. Tương tự như Thuật toán 3.1- RA, với hầu hết các ví dụ thử nghiệm, Prio. 2 tỏ ra hữu hiệu; trong khi đó Prio. 1 và LIFO lần lượt không tốt cho lớp bài toán tuyến tính và toàn phương. • Thuật toán 3.1- NEWVERTEX: So với Thuật toán 3.1- RA và Thuật toán 3.1- RE thì Thuật toán 3.1- NEWVERTEX ít phụ thuộc vào cách quản lí gói (nhỏ hơn 10%) cho hầu hết các ví dụ của bài toán tuyến tính nguyên (MOK, MOA). Sự khác biệt về thời gian tính toán chỉ cao cho ba trường hợp có số chiều cao nhất của bài toán (MOK). Nhưng kết quả trung bình của hai lớp bài toán tuyến tính thử nghiệm vẫn nhỏ. Ngược lại, trong trường hợp bài toán toàn phương, Thuật toán 3.1- NEWVERTEX cũng bị chi phối bởi cách quản lí tập đỉnh chính, đặc biệt với lớp bài toán (MSO (Group 1)). Tương tự như hai thuật toán trên, Prio. 2 hiệu quả nhất và LIFO đắt nhất cho Thuật toán 3.1- NEWVERTEX với 76 bài toán toàn phương. Chú ý rằng sự chênh lệch về số bước lặp (tương ứng với số bài toán con cảm sinh trong quá trình tìm kiếm) giữa các gói quản lí khác nhau của mỗi thuật toán là không đáng kể. Giá trị Diff. của bước lặp hầu hết nhỏ hơn 10% và trong nhiều trường hợp là 0%. Điều đó chứng tỏ rằng, với cùng một cách cập nhật miền tìm kiếm, việc thay đổi cách quản lí tập đỉnh chính không thực sự ảnh hưởng đến số bài toán con được sinh ra hay số đỉnh chỉnh của miền tìm kiếm. Tuy nhiên một gói quản lí tốt sẽ giúp thuật toán làm việc với những bài toán con dễ giải và từ đó có thể giảm được thời gian tính toán. Điều này có thể thấy rõ trong Bảng 3.5. Tóm lại, ta có một số nhận xét sau. • Mặc dù có sự phụ thuộc khác nhau vào các gói quản lí nhưng cả ba thuật toán Thuật toán 3.1- RA, Thuật toán 3.1- RE, Thuật toán 3.1- NEWVERTEX đều hiệu quả với Prio. 2 cho cả trường hợp tuyến tính và toàn phương. Trong khi đó Prio. 1 và LIFO lần lượt cho kết quả không tốt với tất cả các thuật toán với trường hợp tuyến tính và toàn phương. • Với cách quản lí tốt nhất Prio. 2 ta có thể so sánh sự hiệu quả của các thủ tục cập nhật miền tìm kiếm đối với lược đồ GM dựa vào Bảng 3.5. Cụ thể là, thủ tục RA tốt nhất cho lớp bài toán (MOA), (MSO (Group 1)) và (MSO (Group 2)) trong khi đó NEWVERTEX là một thủ tục tốt cho lớp bài toán MOK. 3.3 Thuật toán giải bài toán tối ưu trên tập hữu hiệu của bài toán tối ưu đa mục tiêu rời rạc Bài toán tối ưu một hàm số thực trên tập hữu hiệu của một bài toán tối ưu đa mục tiêu lần đầu được nghiên cứu trong bài báo của Philip [26] cho trường hợp tuyến tính. Do nhu cầu ứng dụng bài toán đã trở thành đề tài thu hút được sự quan tâm của nhiều nhà toán học (xem [27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37] và danh mục các tài liệu tham khảo kèm theo). Tuy nhiên theo hiểu biết của chúng tôi, cho đến nay chưa có nghiên cứu nào cho trường hợp ràng buộc của bài toán đa mục tiêu cho bởi một tập gồm hữu hạn các điểm, những tập như vậy trong thực tế thường được lấy thông qua các phương pháp thống kê. Do đó trong luận án này chúng tôi xét một lớp các bài toán tối ưu trên tập hữu hiệu XE của bài toán (MODO), trong đó hàm mục tiêu (của bài toán tối ưu trên tập hữu hiệu) là đơn điệu tăng tựa lõm và bài toán (MODO) có miền ràng buộc X bao gồm hữu hạn các điểm cho trước. Chúng tôi nghiên cứu và đề xuất thuật toán toàn cục giải bài toán tối ưu trên tập hữu hiệu này. Để giải quyết vấn đề trên, đầu tiên chúng tôi đưa bài toán tối ưu không lồi này về bài toán tối ưu trên bao Edgeworth-Pareto của tập ảnh với hi vọng có thể khai thác một số tính chất đặc biệt của tập này, chẳng hạn như: là tập lồi với số chiều đầy đủ, đỉnh của nó là những điểm hữu hiệu [75]. Gần đây có một số công trình nghiên cứu 77 vấn đề xấp xỉ bao Edgeworth-Pareto của bài toán bài toán tối ưu đa mục tiêu nguyên với các hàm mục tiêu đơn điệu, chẳng hạn như phương pháp xấp xỉ Hausdorff [72, 73] hay xấp xỉ đa diện dựa trên ý tưởng của phương pháp nhánh cận [75]. Tuy nhiên, theo hiểu biết của chúng tôi, cho đến nay những nghiên cứu về bao Edgeworth-Pareto của bài toán tối ưu đa mục tiêu xét trong mục này vẫn chưa có. Vì vậy, để có được cái nhìn cụ thể hơn, chúng tôi đề xuất một thuật toán tính toàn bộ tập đỉnh của bao Edgeworth- Pareto của bài toán tối ưu đa mục tiêu rời rạc (MODO) với miền ràng buộc X bao gồm hữu hạn các điểm cho trước. Thuật toán này sẽ hỗ trợ cho việc xây dựng thuật toán toàn cục giải bài toán tối ưu trên tập hữu hiệu mà chúng tôi đang xét. Sự hiệu quả của các thuật toán đề xuất được minh họa thông qua thử nghiệm số cho nhiều ví dụ sinh ngẫu nhiên với nhiều cỡ bài toán từ nhỏ đến lớn. 3.3.1 Mô tả bài toán Xét bài toán tối ưu đa mục tiêu rời rạc (MODO) như trong Mục 3.1, tức V min f(x) = (f1(x), f2(x), . . . , fm(x)) (MODO) v.đ.k. x ∈ X, với X ⊂ Rn bao gồm hữu hạn những điểm cho trước, fi : X → R, i = 1, . . . ,m là các hàm mục tiêu. Các tập Y,XE, YN được định nghĩa như trong Mục 3.1. Kí hiệu convY là bao lồi của Y. Tập Y  = convY + Rm+ được gọi là bao Edgeworth-Pareto của tập Y (xem [74, 75]). Khi đó ta có Y  = {y ∈ Rm|y = z + d, z ∈ convY, d ∈ Rm+}. Dễ thấy dimY  = m. Với tập lồi đa diện P, kí hiệu V (P ) là tập đỉnh của P. Từ định nghĩa các tập Y, Y , YN ta dễ dàng thu được bao hàm thức V (Y ) ⊂ YN ⊂ Y ⊂ Y . (3.4) Giả sử tập đỉnh V (Y ) = {v1, v2, ..., vl}. Khi đó: • Với mỗi k ∈ {1, 2, ..., l}, vk 6∈ conv({v1, v2, ..., vl} \ {vk}) + Rm+ . • Nếu y ∈ Y  thì tồn tại một véc-tơ d ∈ Rm+ sao cho y = z + d, trong đó z là tổ hợp lồi của {v1, v2, ..., vl}. Xét bài toán tối ưu trên tập hữu hiệu dưới đây: min{ϕ(f(x)) | x ∈ XE}, (P ) 78 trong đó ϕ : Rm → R. Từ định nghĩa của tập giá trị hữu hiệu YN ta có kết quả sau: Mệnh đề 3.2. Điểm x∗ là nghiệm tối ưu toàn cục của bài toán (P ) nếu và chỉ nếu y∗ ∈ YN , với f(x∗) = y∗, là nghiệm tối ưu toàn cục của bài toán min{ϕ(y) | y ∈ YN}. (OP ) Xét bài toán tối ưu trên bao Edgeworth-Pareto min{ϕ(y) | y ∈ Y }. (OP ) Mệnh đề dưới đây nêu mối quan hệ giữa bài toán (OP ) và bài toán (OP ) trong trường hợp ϕ(y) là hàm tựa lõm, đơn điệu tăng trên Y . Mệnh đề 3.3. Giả sử ϕ(y) là hàm đơn điệu tăng, tựa lõm trên Y . Khi đó i) Bài toán (OP ) đạt nghiệm tối ưu tại ít nhất một đỉnh của Y . ii) Nếu y∗ ∈ V (Y ) là nghiệm tối ưu của bài toán (OP ) thì nó cũng là nghiệm của bài toán (OP ). Chứng minh. Khẳng định đầu của mệnh đề là hiển nhiên vì hàm ϕ là tựa lõm, đơn điệu tăng và Y  là tập lồi đa diện. Giả sử y∗ ∈ V (Y ) là một nghiệm tối ưu của (OP ), tức là ϕ(y∗) ≤ ϕ(y) với mọi y ∈ Y . Do YN ⊂ Y ⊂ Y  nên ϕ(y∗) ≤ ϕ(y) với mọi y ∈ YN . Cũng vì y∗ ∈ V (Y ) và V (Y ) ⊂ YN (theo (3.4)), ta có y∗ ∈ YN . Vậy y∗ là một nghiệm tối ưu của bài toán (OP ). 3.3.2 Thuật toán toàn cục giải bài toán (P ) Từ Mệnh đề 3.2 và Mệnh đề 3.3 ta thấy rằng, nếu ϕ là hàm là hàm tựa lõm, đơn điệu tăng trên Y  thì ta có thể chuyển việc giải bài toán (P ) về bài toán tìm cực tiểu của hàm ϕ trên V (Y ) - tập các đỉnh của bao Edgeworth-Pareto trong không gian ảnh. Thông thường, số phần tử của tập V (Y ) nhỏ hơn rất nhiều so với số phần tử của tập Y, YN hay V (convY ). Xem minh họa ở Hình 3.9. 79 .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . .. . . . . . . . .. x x x x x x x x x xb a x . . . . . . . Điểmthuộc tập Y X Điểm thuộc tập YN Hình 3.9: Số phần tử của tập V (Y ) nhỏ hơn rất nhiều so với số phần tử của tập Y, YN hay V (convY ) Như vậy, nếu xác định được toàn bộ tập đỉnh của bao Edgeworth-Pareto của Y thì ta giải xong bài toán (P ). Sau đây chúng tôi đề xuất một thuật toán tìm toàn bộ tập này. Với mỗi j ∈ {1, . . . ,m}, kí hiệu Yj ⊂ Rm−1 là tập thu được từ Y bằng cách xóa tọa độ thứ j. Dựa vào các tập V (Y j ) ⊂ Yj, j ∈ {1, . . . ,m}, chúng tôi đề xuất thuật toán tính V (Y ) như sau. Thuật toán 3.2: Tính tập đỉnh của bao Edgeworth-Pareto của Y, tức tập V (Y ). Bước 1: Lấy yM ∈ Rm sao cho yM > yU . Bước 2: Với mỗi j = 1, ...,m – Xác định Yj := {pj(y)|y ∈ Y }, trong đó pj(y) thu được từ y = (y1, ..., yj, ..., ym)T bằng cách xóa tọa độ thứ j. – Tính Vj := {v ∈ Rm|pj(v) ∈ V (Y j ), vj = yMj }. Bước 3: Lấy Y ′ := Y ∪ ( m⋃ j=1 Vj) ∪ {yM} và xác định V (Y ) theo công thức V (Y ) = V (convY ′) ∩ Y. Chú ý 3.2. (i) Thuật toán 3.2 là thuật toán đệ quy theo số chiềum của tập Y . (ii) Có thể xem Thuật toán 3.2 như là một thủ tục với đầu vào là Y và m; đầu ra là EPH(Y,m) := V (Y ). Khi đó, với m = 1 rõ ràng ta có bao Edgeworth-Pareto của tập Y ⊂ R là EPH(Y, 1) = min{y|y ∈ Y }. 80 Dưới đây là một ví dụ đơn giản minh họa cho Thuật toán 3.2 cho trường hợp m = 2. Ví dụ 3.4. Xét tập Y := {a, b, c, d} với a := (1, 1), b := (1, 0), c := (0,−1), d := (−1,−1) như minh họa ở Hình 3.10. Bước 1: Tính yM1 := 2 > max{y1 | (y1, y2) ∈ Y } = 1, yM2 := 3 > max{y2 | (y1, y2) ∈ Y } = 1. Bước 2: Xác định Y1 = {1, 0,−1,−1}, Y2 = {1, 1, 0,−1}. Y 1 = conv({−1, 0, 1})+R+ = [−1,+∞), Y 2 = conv({−1, 0, 1})+R+ = [−1,+∞). Và V (Y 1 ) = {−1}, V (Y 2 ) = {−1}, V1 = {v = (v1, v2) ∈ R2, v2 ∈ V (Y 1 ), v1 = yM1 = 2} = {(2,−1)} = {yM1}, V2 = {v = (v1, v2) ∈ R2, v1 ∈ V (Y 2 ), v2 = yM2 = 3} = {(−1, 3)} = {yM2}. Bước 3: Y ′ = Y ∪ {V1, V2} ∪ {yM} = Y ∪ {(2,−1), (−1, 3)} ∪ {(2, 3)}. V (Y ) = (convY ′) ∩ Y = {(−1,−1)}. 81 321 1 a d -1 c-1 b . . . 0 y M2 y M1 y M Hình 3.10: Minh họa Ví dụ 3.4 Tính đúng đắn và dừng hữu hạn của thuật toán được thể hiện qua định lí sau. Định lí 3.1. Thuật toán 3.2 dừng sau hữu hạn bước lặp cho ta tập tất cả các đỉnh của bao Edgeworth-Pareto Y . Chứng minh. Ta chia chứng minh thành một số bước như sau: (i) Lấy S = V (convY ′) \ ( ( m⋃ j=1 Vj) ∪ {yM} ) . Ta sẽ chứng minh rằng S ⊂ Y. Thật vậy, vì y ≤ yM với mọi y ∈ convY ′ kéo theo yM là một đỉnh của convY ′. Với j = 1, lấy v ∈ V1 và giả sử rằng v 6∈ V (convY ′). Do v1 = yM1 ≥ y1 với mọi y = (y1, ..., ym) ∈ convY ′, ta thấy rằng v là tổ hợp lồi của những điểm thuộc Y ′ nằm trên mặt y1 = yM1 , điều đó có nghĩa là v = ∑ vµ∈V1 λµv µ + λMy M (3.5) = ∑ vµ∈V1 λµv µ + λMq + λM(y M − q), (3.6) trong đó ∑ vµ∈V1 λµ + λM = 1, λµ, λM ∈ [0, 1], q ∈ Y. Từ (3.6) ta có thể viết p1(v) = ∑ vµ∈V1 λµp1(v µ) + λMp1(q) + α, 82 trong đó p1(vµ), p1(q) ∈ Y1 = p1(Y ), α = λMp1((yM − q)) ∈ p1(Rp+) = Rp−1+ . Vì p1(v) ∈ V (Y 1 ) ta có λµ = 1 với p1(vµ) = p1(v), λµ = 0 với p1(vµ) 6= p1(v) và λM = 0. Kết hợp với (3.5) ta kết luận v là một đỉnh của convY ′. Lập luận tương tự cho những trường hợp còn lại j = 2, . . . ,m. Như vậy, (∪mj=1Vj) ∪ {yM} ⊂ V (conv(Y ′)). Kết hợp với định nghĩa của Y ′ = Y ∪ ( m⋃ j=1 Vj) ∪ {yM} ta thu được S ⊂ Y. (ii) Ở bước này ta chứng minh rằng với mỗi j ∈ {1, ...,m} và v ∈ Vj, tồn tại v¯ ∈ S sao cho pj(v¯) = pj(v). Không mất tính tổng quát ta sẽ xét trường hợp j = 1, những trường hợp còn lại của j ta sẽ làm tương tự. Cố định v ∈ V1 và đặt v¯ = argmin{y1|y ∈ Y, p1(y) = p1(v)}. Ta sẽ chứng minh rằng v¯ ∈ S. Thật vậy, vì p1(v¯) ∈ V (Y 1 ) nên v¯ không thể là tổ hợp lồi của những điểm thuộc Y ′ mà hình chiếu của nó trên không gian p1(Rm) := {(y2, ..., ym), ∀j = 2, ...,m} khác p1(v¯).Mặt khác, vì v¯1 = min{y1|y ∈ Y, p1(y) = p1(v)} = min{y1|y ∈ Y ′, p1(y) = p1(v)}, ta có v¯ 6∈ conv(Y ′ \ {v¯}) + Rm+ chính là điều cần chứng minh. (iii) Bây giờ ta sẽ chứng minh rằng Y  = S. Hiển nhiên, S ⊂ Y , vì vậy ta chỉ cần chỉ ra rằng Y  ⊂ S. Thật vậy, lấy điểm y ∈ Y , khi đó tồn tại z ∈ convY, d ∈ Rm+ sao cho y = z + d. Do z ∈ convY ⊂ convY ′, ta có thể biểu diễn z thành tổ hợp lồi của V (convY ′), nghĩa là z = l∑ k=1 λkv k + m∑ j=1 ∑ vµj∈Vj λjµv µj + λMy M , (3.7) trong đó λk, λjµ, λM ∈ [0, 1] và l∑ k=1 λk + m∑ j=1 ∑ vµj∈Vj λjµ + λM = 1. Từ (ii), với mỗi vµj ∈ Vj có v¯µj ∈ S sao cho vµj = v¯µj +αjµej với αjµ > 0. Như vậy, từ (3.7) kéo theo z = l∑ k=1 λkv k + m∑ j=1 ∑ vµj∈Vj λjµv¯ µj + λMv 1 + m∑ j=1 ∑ vµj∈Vj αjµe j + λM(y M − v1), (3.8) = l∑ k=1 λkv k + m∑ j=1 ∑ vµj∈Vj λjµv¯ µj + λMv 1 + d¯, (3.9) 83 trong đó d¯ = m∑ j=1 ∑ vµj∈Vj αjµe j + λM(y M − v1) ∈ Rm+ , suy ra y ∈ S và Y  ⊂ S. (iv) Cuối cùng ta chứng minh khẳng định V (Y ) = S = V (convY ′) ∩ Y. Trước hết ta chỉ ra rằng vk 6∈ conv({v1, v2, ..., vl} \ {vk}) + Rm+ , với mọi k ∈ {1, 2, ..., l}. Thật vậy, giả sử ngược lại vk = u+β, trong đó u là tổ hợp lồi của {v1, v2, ..., vl} \ {vk} và β ∈ Rm+ . Chú ý rằng, với mỗi j ∈ {1, ...,m}, vk + (yMj − vkj )ej ∈ conv(Y ′) và yMj > v k j do đó tồn tại số tj > 0 sao cho v k + tej ∈ convY ′ với 0 ≤ t ≤ tj. Vì convY ′ lồi nên conv( m⋃ j=1 {vk + tej|0 ≤ t ≤ tj}) ⊂ convY ′. Đặt v := vk + λβ, khi đó tồn tại λ > 0 thỏa v ∈ conv( m⋃ j=1 {vk + tej|0 ≤ t ≤ tj}), tức là v ∈ convY ′, và do đó vk = λλ+1u + 1λ+1v, điều này trái với vk ∈ V (convY ′). Từ (iii) và (iv) ta kết luận rằng V (Y ) = S = V (convY ′) ∩ Y. Định lí đã được chứng minh. Chú ý 3.3. Do convY = conv(V (convY )) và như đã biết trong nhiều trường hợp tập V (convY ) nhỏ hơn tập Y rất nhiều nên với Thuật toán 3.2 ta có thể thay thế Y bằng V (convY ). Để tìm V (convY ) ta có thể sử dụng những thuật toán đã biết chẳng hạn như thuật toán Quickhull [76]. Cuối cùng, chúng tôi đề xuất thuật toán giải toàn cục bài toán (P ) trong trường hợp hàm ϕ đơn điệu tăng và tựa lõm trên Y . Thuật toán 3.3: Giải toàn cục bài toán (P ). Bước 1. Dùng một thuật toán đã biết để tính V (convY ), chẳng hạn thuật toán Quickhull [76]. Bước 2. Áp dụng Thuật toán 3.2 với Y := V (convY ) tính tập đỉnh V (Y ) của bao Edgeworth-Pareto Y . 84 Bước 3. Tính giá trị hàm mục tiêu ϕ tại các điểm của V (Y ) để tìm ra y∗ ∈ argmin{ϕ(y) | y ∈ V (Y )}. Khi đó y∗ là nghiệm tối ưu của bài toán (OP ) và giá trị x∗ thỏa mãn f(x∗) = y∗ chính là nghiệm tối ưu toàn cục của bài toán (P ). 3.3.3 Kết quả tính toán thử nghiệm Chúng tôi lập trình thử nghiệm các thuật toán bằng Matlab phiên bản R2012a, trên máy tính cá nhân với cấu hình RAM 8G, Intel core i7 2.26 GHz và hệ điều hành Win7-64bit. Để tính tập đỉnh của bao lồi của Y chúng tôi sử dụng lệnh "convhulln" trong Matlab ("convhulln" được thiết kế dựa trên thuật toán Quickhull [76]). Dữ liệu của bài toán được sinh ngẫu nhiên theo sơ đồ sau • f(x) = Cx, trong đó ma trận C ∈ {0, 1}m×n được sinh ngẫu nhiên. • X chứa p (p ∈ N) véc-tơ trong Rn, được viết dưới dạng ma trận cấp p× n. Các phần tử của X được sinh ngẫu nhiên trong đoạn [0, 1000]. • Hàm ϕ có dạng ϕ1(y) = min{B1(y)T z | z ∈ {0, 1}n, aT z ≤ b} hoặc ϕ2(y) = min{B2(y)T z | z ∈ {0, 1}n, aT z ≤ b}, trong đó a ∈ Rm là một véc-tơ nguyên được sinh ngẫu nhiên trong đoạn [0, 1000], b = 12 m∑ i=1 ai. và Bk(y) : Rm → Rn, k = 1, 2 được cho bởi công thức B1i (y) = Π n j=1y αij j , α i j ≥ 0, yj ≥ 0, i = 1, . . . , n; j = 1, . . . ,m và B2i (y) = n∑ j=1 αij log(yj + 1), α i j ≥ 0, yj ≥ 0, i = 1, . . . , n; j = 1, . . . ,m. Rõ ràng ϕ1 và ϕ2 là các hàm đơn điệu tăng và tựa lõm theo y. Như vậy ta có thể áp dụng Thuật toán 3.3 để giải bài toán (P ). Chúng tôi tính ϕ tại mỗi điểm y bằng cách sử dụng CVX 2.1 kèm theo Gurobi Solver 6.0 (academic version at and cho việc giải bài toán quy hoạch nguyên. 85 Thuật toán 3.2 và Thuật toán 3.3 được thử nghiệm cho trường hợp p = 106, p = 105 và m = 2, 3, 4, 5. Các hệ số {αij}i=1,...,nj=1,...,m được sinh ngẫu nhiên trong đoạn [0, 1], [0, 0.5] và trong [0, 0.25] theo thứ tự với n = 20, n = 50 và n = 100. Với mỗi cỡ bài toán chúng tôi chạy cho 10 ví dụ sinh ngẫu nhiên và lấy kết quả trung bình cho 10 ví dụ đó. Kí hiệu #S là số phần tử trung bình của tập S cho 10 ví dụ, trong đó S có thể là V (convY ), V (Y ) hoặc YN . Chúng tôi so sánh Thuật toán 3.3 với cách làm trực tiếp - tính YN từ tập Y và sau đó tính giá trị hàm mục tiêu tại tất cả các điểm của YN để thu được nghiệm tối ưu của bài toán (Thuật toán 3.4). Cách tính YN từ tập Y tương tự như [68, Thuật toán 8.1, trang 209]. Chi tiết Thuật toán 3.4 như sau. Thuật toán 3.4: Giải toàn cục bài toán (P ) bằng cách làm trực tiếp. Bước 1: Tính YN =MinY từ tập Y đã biết theo thuật toán đã biết (chẳng hạn, [68, Thuật toán 8.1, trang 209]). Bước 2: Tính giá trị hàm mục tiêu ϕ tại các điểm của YN để tìm ra y∗ ∈ argmin{ϕ(y) | y ∈ YN} là nghiệm tối ưu của bài toán (OP ). Điểm x∗ ∈ X thỏa mãn f(x∗) = y∗ chính là nghiệm tối ưu toàn cục của bài toán (P ). Bảng 3.6: Kết quả tính toán thử nghiệm Thuật toán 3.2 p = 105 p = 106 m n #V (convY ) #V (Y ) CPU(s) #V (convY ) #V (Y ) CPU(s) 20 17.4 3.6 0.0952 20.2 4.3 0.7972 2 50 15.3 3.6 0.1092 17.6 3.9 0.9313 100 15.7 3.8 0.1544 17.7 3.8 1.3775 20 80.8 9.1 0.117 111.8 9.9 0.9859 3 50 77.7 9.4 0.1778 94 8.9 1.0889 100 72.2 7.2 0.2059 87.9 9.5 1.3806 20 301 18.6 0.1763 450.9 18.4 1.2511 4 50 256.3 12.5 0.1981 356.5 15.7 1.2293 100 231.8 13.3 0.2262 307.2 15.3 1.4087 20 853.3 23.2 0.5772 1477.6 38 2.5943 5 50 658.7 21.8 0.4586 1060 25.8 2.3228 100 621.8 19.8 0.4352 967.2 24.7 2.5225 86 Bảng 3.7: Kết quả so sánh Thuật toán 3.3 và Thuật toán 3.4 ϕ1-CPU(s) ϕ2-CPU(s) p m n #V (convY ) #V (Y ) #YN Thuật toán 3.3 Thuật toán 3.4 Thuật toán 3.3 Thuật toán 3.4 20 17.4 3.6 8.1 0.4961 1.5647 0.4118 1.4945 2 50 15.3 3.6 6.2 0.5148 1.4305 0.4212 1.3884 100 15.7 3.8 6.7 0.5476 1.2355 0.468 1.2168 20 80.8 9.1 25.8 0.883 3.4382 0.8268 3.4164 3 50 77.7 9.4 24.4 1.0436 3.705 0.9204 3.6379 105 100 72.2 7.2 15.8 0.9079 3.3524 0.8315 3.2885 20 301 18.6 55.4 1.7628 8.2446 1.702 8.1838 4 50 256.3 12.5 40.4 1.3073 8.1417 1.1778 7.9202 100 231.8 13.3 40.7 1.3666 6.1527 1.2558 5.9187 20 853.3 23.2 73.3 2.6767 17.6843 2.4476 17.0915 5 50 658.7 21.8 74.7 2.5085 16.0198 2.3478 15.8404 100 621.8 19.8 71.7 2.028 10.1697 1.989 10.0543 20 20.2 4.3 8.4 1.1716 6.4912 1.1794 6.4319 2 50 17.6 3.9 6.9 1.2527 7.5161 1.2698 7.5161 100 17.7 3.8 7.4 1.7004 5.2385 1.7098 5.1886 20 111.8 9.9 23.9 1.8548 14.1774 1.8174 14.11654 3 50 94 8.9 26.4 1.9812 17.6796 1.8751 17.5361 106 100 87.9 9.5 27.9 2.3057 19.8917 2.1887 19.848 20 450.9 18.4 61.2 2.8532 57.0823 2.6676 56.8982 4 50 356.5 15.7 61 2.4617 41.3278 2.4461 41.0922 100 307.2 15.3 64.3 2.6411 42.4744 2.6005 42.2607 20 1477.6 38 153.5 5.694 119.2986 5.577 119.26276 5 50 1060 25.8 96.3 4.6691 90.2169 4.4164 90.1218 100 967.2 24.7 104.9 4.6597 79.9053 4.4725 79.7103 Từ các kết quả số thu được ta rút ra một số nhận xét sau • Thuật toán 3.2 tính tập đỉnh của bao Edgeworth-Pareto của một bài toán tối ưu đa mục tiêu hiệu quả ngay cả trong trường hợp số lượng điểm của tập ràng buộc là 106 và số lượng hàm mục tiêu là 5. • Thuật toán 3.3 sử dụng bao Edgeworth-Pareto giải bài toán tối ưu một hàm tựa lõm, đơn điệu tăng trên một tập hữu hiệu của một bài toán tối ưu đa mục tiêu rời rạc hiệu quả hơn Thuật toán 3.4 khi tập ràng buộc rời rạc có số lượng điểm lớn và việc tính giá trị hàm mục tiêu tại mỗi điểm đòi hỏi nhiều thời gian tính toán. Kết luận Chương 3 của luận án nghiên cứu thuật toán giải hai bài toán tối ưu không lồi trong tối ưu đa mục tiêu rời rạc. • Bài toán tìm toàn bộ tập giá trị hữu hiệu của bài toán tối ưu đa mục tiêu rời rạc. - Sử dụng khái niệm đa khối nửa mở cho biểu diễn miền kiếm của bài toán tối ưu đa mục tiêu rời rạc. - Chúng tôi đề xuất một thủ tục cập nhật miền tìm kiếm mới sử dụng cho lược đồ chung GM để tìm toàn bộ tập giá trị hữu hiệu. 87 - Nghiên cứu sự ảnh hưởng của việc quản lí những bài toán con được lưu trong suốt quá trình tìm kiếm thông qua việc khảo sát lược đồ chung GM với bốn cách quản lí khác nhau. - Thuật toán mới đề xuất được lập trình so sánh với các thuật toán đã biết cho rất nhiều ví dụ có sẵn và sinh ngẫu nhiên với nhiều cỡ bài toán từ nhỏ đến lớn. Kết quả số cho thấy sự hiệu quả của lược đồ chung GM phụ thuộc lớp bài toán cần giải, thủ tục cập nhật miền tìm kiếm và cách quản lí các bài toán con được lưu. • Bài toán tối ưu trên tập hữu hiệu. - Chúng tôi xét một lớp bài toán tối ưu trên tập hữu hiệu với hàm mục tiêu đơn điệu tăng và tựa lõm, miền ràng buộc là tập hữu hiệu của một bài toán tối ưu đa mục tiêu rời rạc. - Chúng tôi đề xuất thuật toán tính toàn bộ tập đỉnh của bao Edgeworth- Pareto trong không gian ảnh và sử dụng kết quả này cho việc đề xuất thuật toán toàn cục giải bài toán tối ưu trên tập hữu hiệu đang xét. - Tính hiệu quả của các thuật toán đề xuất được thể hiện thông qua việc lập trình thử nghiệm cho nhiều ví dụ sinh ngẫu nhiên với nhiều cỡ bài toán khác nhau. 88 KẾT LUẬN CHUNG 1. Những đóng góp chính của luận án Luận án nghiên cứu các thuật toán giải một số bài toán tối ưu không lồi có nhiều ứng dụng trong thực tế, cụ thể là: Đối với bài toán phân bổ tài nguyên cho mạng không dây OFDMA/TDD, chúng tôi đã xây dựng mô hình toán học cho bài toán này dưới dạng một bài toán quy hoạch tuyến tính nhị phân. Sau đó, sử dụng tiếp cận liên tục (kĩ thuật hàm phạt) bài toán được đưa về dạng một bài toán tối ưu DC. Cuối cùng chúng tôi đề xuất thuật toán toàn cục nhánh cận kết hợp DCA để giải bài toán này. Đối với bài toán năng lượng phủ cảm biến cho mạng cảm biến vô tuyến, chúng tôi xuất phát từ mô hình bài toán tối ưu không lồi liên tục khó (với ràng buộc không lồi), được đề xuất bởi Astorino và Miglionico [38]. Bằng cách khai thác các tính chất từ cấu trúc đơn điệu của bài toán, chúng tôi đã đề xuất ba thuật toán mới giải bài toán trên, bao gồm: một thuật toán tìm nghiệm địa phương, một thuật toán toàn cục dựa trên lược đồ nhánh-giảm-cận cổ điển và một thuật toán cải tiến thuật toán nhánh- giảm-cận cổ điển. Trong đó, các thuật toán toàn cục thu được sau khi bài toán gốc được đưa về một bài toán tối ưu đơn điệu rời rạc tương đương. Đối với bài toán tìm toàn bộ tập giá trị hữu hiệu cho bài toán tối ưu đa mục tiêu rời rạc, sử dụng khái niệm đa khối nửa mở cho biểu diễn miền kiếm của bài toán tối ưu đa mục tiêu rời rạc, chúng tôi đề xuất một thủ tục cập nhật miền tìm kiếm mới dùng cho lược đồ GM để tìm toàn bộ tập giá trị hữu hiệu của bài toán tối ưu đa mục tiêu rời rạc. Ngoài ra, chúng tôi còn nghiên cứu sự ảnh hưởng của việc quản lí những bài toán con được lưu trong suốt quá trình tìm kiếm thông qua việc khảo sát lược đồ GM với một số cách quản lí khác nhau. Đối với bài toán tối ưu trên tập hữu hiệu, chúng tôi xét một lớp bài toán dạng này với hàm mục tiêu không giảm tựa lõm, miền ràng buộc là tập hữu hiệu của một bài toán tối ưu đa mục tiêu rời rạc với ràng buộc cho bởi tập hữu hạn các điểm. Chúng tôi đề xuất thuật toán tính toàn bộ tập đỉnh của bao Edgeworth-Pareto trong không gian ảnh và sử dụng kết quả này cho việc đề xuất thuật toán toàn cục giải bài toán trên. Tất cả các thuật toán được đề xuất trong luận án đều được lập trình thử nghiệm và so sánh với các phương pháp khác trên rất nhiều các bộ dữ liệu sinh ngẫu nhiên và có sẵn. Kết quả số được tổng hợp, phân tích kĩ lưỡng cho thấy được tính hiệu quả và ý nghĩa của việc đề xuất các thuật toán này. 89 2. Hướng nghiên cứu tiếp theo Tiếp tục triển khai tìm hiểu những bài toán xuất phát từ những vấn đề trong thực tế và nghiên cứu xây dựng mô hình toán học cùng thuật toán và phương pháp giải cho các bài toán đó. 90 DANH MỤC CÁC CÔNG TRÌNH Đà CÔNG BỐ CỦA LUẬN ÁN [1] N.C. Nam, P.T. Hoai (2017), "A continuous DC programming approach for re- source allocation in OFDMA/TDD wireless networks", Computers & Opera- tions Research, Vol. 82, pp. 95-101. (ISI) [2] P.T. Hoai, L.T.H. An, N.C. Nam (2017), "An exact approach for solving the supplier selection problem in multi-service outsourcing", in: Conference Pro- ceedings of IESM 2017 7 th International Conference on Industrial Engineering and Systems Management Saarbru¨cken, Germany, October 11-13, pp. 541-546. [3] P.T. Hoai, H. Tuy (2018), "Monotonic optimization for sensor cover energy problem", Optimization Letters, Vol. 12 (7), pp. 1569–1587. (ISI) [4] P.T. Hoai, L.D. Muu, T.N. Thang (2018), "Optimization over the efficient set of multiple objective discrete programs using the Edgeworth-Pareto hull in out- come space", Pacific Journal of Optimization, Vol. 14 (4), pp. 581–594. (ISI) [5] P.T. Hoai, L.T.H. An, N.C. Nam (2018), "Half-open polyblock for the represen- tation of the search region in multiobjective optimization problems: its applica- tion and a computational experience", revised. 91 TÀI LIỆU THAM KHẢO [1] H. Tuy (1964), "Concave programming under linear contraints", Soviet Math. Dokl., Vol. 5, pp. 1437-1440. [2] H. Tuy (2016), "Convex Analysis and Global Optimization", the second edition, Springer International Publishing AG Switzerland. [3] L.T.H. An, P.D. Tao (2018), "DC programming and DCA: thirty years of devel- opments", Math. Program., Ser. B, https://doi.org/10.1007/s10107-018-1235-y. [4] L.T.H. An, P.D. Tao (2001), "A continuous approach for globally solving linearly constrained quadratic zero-one programming problems", Optimization, Vol. 50, pp. 93-120. [5] H.P. Benson (1998), "An outer approximation algorithm for generating all effi- cient extreme points in the outcome set of a multiple objective linear program- ming problem", J. Global Optim., Vol. 13, pp. 1-24. [6] I. Das, J.E. Dennis (1998), "Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems", SIAM J. Optim., Vol. 8, pp. 631-657. [7] Y.Y. Haimes, L.S. Lasdon, D.A. Wismer (1971), "On a bicriterion formulation of the problems of integrated system identification and system optimization", IEEE Trans. Syst. Man Cyber., Vol. 1, pp. 296-297. [8] P.L. Yu (1985), "Multiple-criteria decision making: Concepts, techniques and extensions", Plenum Press, New York. [9] A. Ben-Tal (1980), "Characterization of Pareto and lexicographic optimal solu- tions", Lecture Notes in Eco. and Math. Sys., Springer-Verlag, Berlin, Heidel- berg, Vol. 177, pp. 1-11. [10] R.E. Steuer (1986), "Multiple criteria optimization: Theory, computation and application", Wiley, New York. [11] M. Laumanns, L. Thiele, E. Zitzler (2006), "An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method", Eur. J. Oper. Res., Vol. 169(3), pp. 932-942. 92 [12] T. Ralphs, M. Saltzman, M.M. Wiecek (2006), An improved algorithm for solv- ing biobjective integer programs, Ann. Oper. Res., Vol. 147, pp. 43-70. [13] K. Da¨chert, K. Klamroth (2015), "A linear bound on the number of scalariza- tions needed to solve discrete tricriteria optimization problems", J. Glob. Optim., Vol. 61(4), pp. 643-676. [14] C. Dhaenens, J. Lemesre, E.G. Talbi (2010), "K-PPM: A new exact method to solve multiobjective combinatorial optimization problems", Eur. J. Oper. Res., Vol. 200(1), pp. 45-53. [15] J. Lemesre, C. Dhaenens, E.G. Talbi (2007), "Parallel partitioning method (PPM): A new exact method to solve bi-objective problems", Comput. Oper. Res., Vol. 34(8), pp. 2450-2462. [16] J. Sylva, A. Crema (2004), "A method for finding the set of non-dominated vec- tors for multiple objective integer linear programs", Eur. J. Oper. Res., Vol. 158(1), pp. 46-55. [17] B. Lokman, M. Ko¨ksalan (2013), "Finding all nondominated points of multiob- jective integer programs", J. Glob. Optim., Vol. 57(2), pp. 347-365. [18] M. O¨zlen, M. Azizog˘lu (2009), "Multi-objective integer programming: a general approach for generating all non-dominated solutions", Eur. J. Oper. Res., Vol. 199, pp. 25-35. [19] W. Zhang, M. Reimann (2014), "A simple augmented ε-constraint method for multi-objective mathematical integer programming problems", Eur. J. Oper. Res., Vol. 234(1), pp. 15-24. [20] G. Mavrotas (2009), "Effective implementation of the ε-constraint method in multiobjective mathematical programming problems", Appl. Math. Comput., Vol. 213(2), pp. 455-465. [21] G. Mavrotas, K. Florios (2013), "An improved version of the augmented ε- constraint method (AUGMECON2) for finding the exact Pareto set in multiob- jective integer programming problems", Appl. Math. Comput., Vol. 219(18), pp. 9652-9669. [22] G. Kirlik, S. Sayın (2014), "A new algorithm for generating all nondominated points of multiobjective discrete optimization problems", Eur. J. Oper. Res., Vol. 232, pp. 479-488. 93 [23] K. Da¨chert, K. Klamroth, R. Lacour D. Vanderpotten (2017), "Efficient compu- tation of the search region in multi-objective optimization", Eur. J. Oper. Res., Vol. 160, pp. 841-855. [24] K. Klamroth, R. Lacour, D. Vanderpooten (2015), "On the representation of the search region in multi-objective optimization", Eur. J. Oper. Res., Vol. 245, pp. 767-778. [25] A. Przybylski, X. Gandibleuc, M. Ehrgott (2009), "A two phase method for multi-objective integer programming and its application to the assignment prob- lem with three objectives", Discrete Optimization, Vol. 7, pp. 149-165. [26] J. Philip (1972), "Algorithms for vector maximization problem", Math. Prog., Vol. 2, pp. 85-106. [27] H.P. Benson (1984), "Optimization over the efficient set", J. Math. Anal. Appl., Vol. 98, pp. 562-580. [28] H.P. Benson (1991), "An all-linear programming relaxation algorithm for opti- mizing over the efficient set", J. Glob. Optim., Vol. 1, pp. 84-104. [29] L.T.H. An, L.D. Muu, P.D. Tao (1996), "Numerical solution for optimization over the efficient set by d.c. optimization algorithms", Vol 19(3), Oper. Res. Lett., pp. 117-128. [30] S. Bolintineanu (1993), "Minimization of a quasi-concave function over an effi- cient set", Math. Prog., Vol 61, pp. 89-110. [31] H. Bonnel, J. Collonge (2013), "Stochastic optimization over a Pareto set asso- ciated with a stochastic multiobjective optimization problem", J. Optim. Theory & Appl., DOI 10.1007/s10957-013-0367-8. [32] J.P. Dauer, T. Fosnaugh (1995), "Optimization over the efficient set", , J. Glob. Optim., Vol. 7, pp. 261-277. [33] J. Fu¨lo¨p (1994), "A cutting plane algorithm for linear optimization over the ef- ficient set", in: Generalized Convexity, Lecture notes in Economics and Mathe- matical System, Vol. 405, pp. 374-385, Springer-Verlag, Berlin. [34] R. Horst, N.V. Thoai, Y. Yamamoto, D. Zenke (2007), "On optimization over the efficien set of linear multicriteria programming", J. Optim. Theory Appl., Vol. 134, pp. 433-443. [35] N.T.B. Kim, L.D. Muu (2002), "On the projection of the efficient set and poten- tial application", Optim., Vol. 51, pp. 401-421. 94 [36] H.Q. Tuyen, L.D. Muu (2001), "Biconvex programming approach to optimiza- tion over the weakly efficient set of a multiple objective affine fractional pro- gramming problem", Oper. Res. Lett., Vol. 28, pp. 81-92. [37] P.T. Thach, H. Konno, D. Yokoda (1996), "Dual approach to optimization on the set of Pareto-optimal solutions", J. Optim. Theo. Appl., Vol. 88, pp. 869-707. [38] A. Astorino, G. Miglionico (2016), "Optimizing sensor cover energy via DC programming", Optim. Lett., Vol. 10 (2), pp. 355-368. [39] P.D. Tao, L.T.H. An (1997), "Convex analysis approach to DC programming: theory, algorithms and applications", Acta Math. Vietnam., Vol. 22(1), pp. 289- 355, Dedicated to Hoang Tuy on the occasion of his seventieth birthday. [40] Nguyễn Văn Hiền, Lê Dũng Mưu và Nguyễn Hữu Điển (2014), "Giáo trình giải tích lồi ứng dụng", Nhà xuất bản Đại học Quốc gia Hà Nội. [41] H. Tuy, M. Minoux, N.T.H. Phuong (2006), "Discrete monotonic optimization with application to a discrete location problem", SIAM J. Optim., Vol. 17, pp. 78-97. [42] H. Tuy (2000), "Monotonic optimization: Problems and solution approaches", SIAM J. Optim., Vol. 11, pp. 464-494. [43] Hoàng Tụy (2006), "Lí thuyết tối ưu", Bài giảng lớp cao học Viện Toán học. [44] L.T.H. An, P.D. Tao, L.D. Muu (1999), "Exact penalty in d.c programming", Vietnam Journal of Mathematics, Vol. 27(2), pp. 169-178. [45] L.T.H. An, P.D. Tao (2005), "The DC (Difference of convex functions) program- ming and DCA revisited with DC models of real world nonconvex optimization problems", Ann. Oper. Res., Vol. 133, pp. 23- 46. [46] L.T.H. An, P.D. Tao (2014), "DC programming in communication systems: chal- lenging problems and methods, Vietnam J. Comput. Sci., Vol. 1, pp. 15-28. [47] T. Ali-Yahiya, A.L. Beylot, G. Pujolle (2010), "Downlink resource allocation strategies for ofdma based mobile wimax", Telecommunication Systems, Vol. 44, pp. 29-37. [48] E.B. Rodrigues, F. Casadevall (2011), "Control of the trade-off between resource efficiency and user fairness in wireless networks using utility-based adaptive resource allocation", IEEE Communications Magazine, Vol. 49, pp. 90-98. 95 [49] A. Bacioccola, C. Cicconett, L. Lenzini, E. Mingozzi, A. Erta (2007), "A down- link data region allocation algorithm for ieee 802.16e ofdma", in: Proc. 6th Int. Conf. Information, Communications and Signal Processing, pp. 1-5. [50] T. Wand, H. Feng, B. Hu (2008), "Two-dimensional resource allocation for ofdma system", in: Proc. IEEE Int. Conf. Communications Workshop,Beijing, China, pp. 1-5. [51] C. Cicconetti, L. Lenzini, A. Lodi, S. Martello, E. Mingozzi, M. Monaci (2014), "Efficient two-dimensional data allocation in ieee 802.16 ofdma", IEEE/ACM Transactions on Networking, Vol. 22 (5), pp. 1645-1658. [52] E. Rodrigues, F. Casadevall, P. Sroka, M. Moretti, G. Dainelli (2009), "Resource allocation and packet scheduling in ofdma-based cellular networks", in: Proc. 4th International Conference on Cognitive Radio Oriented Wireless Networks and Communications, pp. 1-6. [53] N.C. Nam, P.T. Hoai, T.V. Huy (2015), "DC Programming and DCA ap- proach for resource allocation aptimization in OFDMA/TDD wireless net- works", Springer International Publishing Switzerland 2015, H.A. Le Thi et al. (eds.), Advanced Computational Methods for Knowledge Engineering, Ad- vances in Intelligent Systems and Computing, 358, DOI: 10.1007/978-3-319- 17996-4_5. [54] L.T.H. An, P.D. Tao (2002), "DC Programming: Theory, Algorithms and Appli- cations. The State of the Art", 26 pages. Proceedings of The First International Workshop on Global Constrained Optimization and Constraint Satisfaction (Co- cos’ 02)", Valbonne-Sophia Antipolis, France. [55] R. Horst and H. Tuy (1993), "Global Optimization: Deterministic Approaches", the second edition, Springer, Berlin, New York. [56] N.T.B. Kim (2014), "Các phương pháp tối ưu: lí thuyết và thuật toán", Nhà xuất bản Bách Khoa, Hà Nội. [57] P.D. Tao, N.C. Nam, L.T.H. An (2009), "DC Programming and DCA for globally solving the value-at-risk", Comput. Manag. Sci., Vol. 6(4), pp. 477-501. [58] P.D. Tao, N.C. Nam, L.T.H. An (2010), "An efficient combined DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs", J. Glob. Optim., Vol. 48(4), pp. 595-632. [59] J. Yick, B. Mukherjee, D. Ghosal (2008), "Wireless sensor network survey", Comput. Netw., Vol. 52, pp. 2292-2330. 96 [60] R. Mulligan (2010), "Coverage in wireless sensor networks: a survey", Netw. Protoc. Algorithms, Vol. 2, pp. 27–53 [61] A. Alfieri, A. Bianco, P. Brandimarte, C.F. Chiasserini (2007), "Maximizing sys- tem lifetime in wireless sensor networks", Eur. J. Oper. Res., Vol. 181, pp. 390- 402. [62] N. Bartolini, T. Calamoneri, T. La Porta, C. Petrioli, S. Silvestri (2012), "Sen- sor activation and radius adaptation (SARA) in heterogeneous sensor net- works", ACM Trans. Sensor Netw. (TOSN), Vol. 8(3), aricle 24, 34 pages, https://doi.org/10.1145/2240092.2240098. [63] M. Cardei, D. Du (2005), "Improving wireless sensor network lifetime through poweraware organization", Wirel. Netw., Vol. 11, pp. 333-340. [64] M. Cardei, J. Wu (2006), "Energy-efficient coverage problems in wireless ad- hoc sensor networks", Comput. Commun., Vol. 29, pp. 413-420. [65] M. Cardei, L. Mingming, M.O. Pervaiz (2005), "Maximum network lifetime in wireless sensor networks with adjustable sensing ranges", In: Proceedings of the IEEE International Conference onWireless andMobile Computing, Networking and Communications (WiMob), Vol. 3, pp. 438-445. [66] R. Cerulli, R. De Donato, A. Raiconi (2012), "Exact and heuristic methods to maximize network lifetime in wireless sensor networks with adjustable sensing ranges", Eur. J. Oper. Res., Vol. 220, pp. 58-66. [67] Z. Zhou, S.R. Das, H. Gupta (2009), "Variable radii connected sensor cover in sensor networks", ACM Trans. Sensor Netw., Vol. 5, pp. 8-36. [68] M. Ehrgott (2005), "Multicriteria Optimization", Springer, Berlin. [69] D. Klein, E. Hannan (1982), "An algorithm for the multiple objective integer linear programming problem", Eur. J. Oper. Res., Vol. 9(4), pp. 378-385. [70] M. O¨zlen, B.A. Burton, C.A.G. MacRae (2014), "Multi-objective integer pro- gramming: an improved recursive algorithm", J. Optim. Theory Appl., Vol. 160(2), pp. 470-482. [71] B. Feng, Z.P. Fan, Y. Li (2011), "A decision method for supplier selection in multi-service outsourcing", Int. J. Production Economics, Vol. 132, pp. 240-250. [72] A.I. Pospelov (2016), "Haussdorf methods for approximating the convex Edgeworth-Pareto hull in integer problems with monotone objectives", Comput. Math. & Math. Phys., Vol. 56, pp. 1388-1401. 97 [73] R.V. Efremov (2015), "Convergence of Haussdorf approximation method for the Edgeworth-Pareto hull of a compact set", Comput. Math. and Math. Phys., Vol. 25, pp. 1171-1178. [74] M. Ehrgott, X. Gandibleux, A. Przybylski (2016), "Exact Methods for Multi- Objective Combinatorial Optimisation", Inter. Series in Oper. Res. & Manag. Sci., Vol. 233, pp. 817-850. [75] A.I. Pospelov (2009), "Approximating the Convex Edgeworth Pareto Hull in Integer Multi objective Problems with Monotone Criteria", Comput. Math. & Math. Phys., Vol. 49 (10), pp. 1686-1699. [76] C.B. Barber, D.P. Dobkin, H.T. Huhdanpaa (1996), "The Quickhull Algorithm for Convex Hulls", ACM Transactions on Mathematical Software, Vol. 22(4), pp. 469-483. 98