Chen Disser (1121212), страница 26
Текст из файла (страница 26)
In our search, we scale down γ and η by multiplying eachwhich is small when compared to the 160.45 seconds required for solving the original problempenalty value by a factor randomly generated between 0.4 and 0.6 if we cannot decrease the(Table 5.3).maximum violation of global constraints or improve the objective quality after solving five5.2.3consecutive subproblems.Strategies for updating penalty valuesAfter solving each subproblem, we use the following rule to update the penalty vectors γ5.3Experimental Resultsand μ of violated global constraints (Line 7 of Figure 5.2b):In this section, we compare the performance of CPOPT to that of other leading solvers. Inγ ←− γ + ρT |H(z)|,η ←− η + T max(0, G(z)),(5.3)CPOPT, if a partitioned subproblem defined in (3.31) is a MINLP, CPOPT first generatesa good starting point by solving it as a CNLP using SNOPT [32], while ignoring the inte-where ρ and are vectors for controlling the update rate of γ and η.We update each element of ρ and dynamically until the corresponding global constraintis satisfied.
Vector ρ is initialized to ρ0 and is updated as follows. For each global constraint143grality of integer variables. It then applies MINLP BB [54] to solve the subproblem. If thepartitioned subproblem is a CNLP, CPOPT applies SNOPT to solve it.We have compared CPOPT to two of the best MINLP solvers, MINLP BB [54] and144BARON [76], on a collection of MINLP benchmarks from the MacMINLP library [55].Table 5.3: Results on solving MINLP benchmarks from the MacMINLP library [55]. Results onMINLP BB implements a branch-and-bound algorithm with a sequential-quadratic-programmingMINLP BB and BARON were obtained by submitting jobs to the NEOS server [61] and BARON’s(SQP) solver for solving continuous subproblems, whereas BARON is a mixed-integer con-site [76], respectively; results of other solvers were collected on an AMD Athlon MP2800 PC runningstrained solver implementing the branch-and-reduce algorithm.
The complete results onRH Linux AS4 and a time limit of 3,600 sec. All timing results are in seconds and should beMacMINLP benchmarks are reported in Table 5.3. For each problem, we show the numbercompared within a solver but not across solvers because they might be run on different computers.Solutions with the best quality are boxed. “−” means that no feasible solutions were found in theof constraints nc , the number of variables nv , and the solution quality and the solution timetime limit.(in seconds) for each solver.
We can see that CPOPT is faster than BARON and MINLP BBin most large problems where it takes more than 10 seconds to solve by CPOPT. It can alsosolve some large problems that cannot be solved by BARON and MINLP BB, such as TRIM-Test ProblemIDBATCHnc73MINLP BBnv46LOSS12.C-RELOAD-14a 308 342We have also compared CPOPT to two of the best CNLP solvers, Lancelot [17], anaugmented Lagrangian method, and SNOPT [32], an SQP solver, on the CNLPs from theC-RELOAD-14b 308 342C-RELOAD-14c 308 342CUTE library [13]. We have shown the results on large CUTE benchmarks that cannot beC-RELOAD-14d 308 342solved by either SNOPT or Lancelot in Table 5.5. The results show that CPOPT can findC-RELOAD-14e 308 342the best solution for most test problems, that it is one to two orders of magnitude faster,C-RELOAD-q-24 968 632and that it is able to solve large problems that no other solver can tackle.
The completeC-RELOAD-q-25 1033 658results on other CUTE benchmarks in Table 5.7. On these small problems that are easy toC-RELOAD-q-49 1430 3733solve, the three solvers have same solution quality for most problems. CPOPT is usuallyC-RELOAD-q-104 3338 13936slower than SNOPT due to partitioning overhead and slightly faster than LANCELOT forthe small problems in Table 5.7.C-SCHED11673Ex12.6.35792Ex12.6.45788Ex12.6.576130Ex12.6.697180FEEDLOC24789MITTELMAN716OPTPRLOC2930Sol.TimeBARONSol.TimeCPOPT(MINLP BB)Sol.2.85E5 0.58 2.59E5 2.03 2.59E5 -1.01 1.43 -1.01 0.98-1.01 -1.03 1.45 -1.01 1.12-1.01 -1.00 1.53 -1.00 1.08-1.00 -1.03 1.48 -1.03 0.99-1.03 -1.03 1.54 -1.03 1.03-1.03 -1.13 143.05 -1.13 56.34 -1.13 -1.12 210.43 -1.12 121.46 -1.12 −−−-1.13 −−−−-1.14 -3.06E4 0.42 -3.06E4 0.32 -3.06E4 19.6 2319.6 423.119.6 708.6 8.6 478.28.6 15.1410.3 845.510.3 16.3 1816.3 937.416.3 0.0 145.49 0.0 252.410.0 16 0.2616 0.0116 -8.06 0.87 -8.06 3.74-8.06 Time1.922.352.202.012.172.2836.8550.4769.45353.740.6413.432.94216.72149.40157.390.011.58continued on next page145146Table 5.5: Results on solving selected CNLP benchmarks from the CUTE library [13].
Re-continued from previous pageIDPUMPnc34nv24SPACE-25235 893SPACE-25-r160 818Sol.−Time−484.33 183.54484.33 124.58SPACE-960-i6497 5537−−SPACE-9608417 15137−−SPACE-960-r5537 12257−−SPRING817STOCKCYCLE974800.86 −0.08−TRIMLON2128 5.3 TRIMLON4242412.210TRIMLON5303512.5143.42TRIMLON6364818.819TRIMLON74263−−TRIMLON1272168−−TRIMLOSS46410510.899TRIMLOSS59016112.6190TRIMLOSS6120 215−−TRIMLOSS7154 345−−TRIMLOSS12384 800−−WIND-FAC14150.25 7.52147Sol.TimeSol.131124 977 130788 484.33 321.01 484.33 484.33 248.94 484.33 −−7.65E6 −−7.84E6 −−5.13E6 0.86 0.740.86 436341 n/a 119948.7 5.3 4.115.3 8.3 11.08.3 10.3 55.310.3 15.6 1092.9 15.6 18.117.5 990.7−−95.5−−10.6−−10.7−−22.1−−26.7 −−138.8 0.25 2.950.25 Timesults of all solvers were collected on an AMD Athlon MP2800 PC running RH Linux AS484.53and a time limit of 3,600 sec.
Solutions with the best quality are boxed. “−” means that no190.42feasible solutions were found in the time limit.127.75Test Problem187.43ID1206.43DTOC6160.45EIGMAXB0.59ncLANCELOTnv5000 10001101 101Sol.0.91 Time--1.34--GILBERT 1000 1000 2459.46 1.12-0.84123.43OPTCDEG 4000 6001--24.5ORTHREGC 5000 10005--15.94ORTHREGD 5000 10003--65.34ORTHRGDM 5000 10003345.50ORTHRGDS 5000 10003 912.414.392.73HADAMARD 256 129KISSING903 127CPOPT(SNOPT)Time--6.45SNOPTSol.1513.80 4.5610167.82 250.00 2340.34--9.76VANDERM1 199 100----76.85VANDERM3 199 100----69.03VANDERM4 199 100----323.947.911481.87Time58.0524.334700.61 689.18 2454.67 39.557.880.99 0.77 73.4519.6545.76 10.23 46.983469.05 557.98 2614.34 143.658729.64 208.27 7932.92 123.494.2059.32Sol.1.02E6 894.65 0.0 0.0 0.0 20.34105.3445.3436.7052.33Table 5.7: Results on solving CNLP benchmarks from the CUTE library [13].
Results of allsolvers were collected on an AMD Athlon MP2800 PC running RH Linux AS4 and a timecontinued from previous pageIDnc nvSol.TimeSol.TimeSol.Timelimit of 3,600 sec. Solutions with the best quality are boxed. “−” means that no feasibleHIMMELP2 2 1-62.050.63-62.050.01-62.050.09solutions were found in the time limit.HIMMELP6 2 5-59.010.69-59.010.01-59.010.09Test ProblemIDLANCELOTSNOPTCPOPT(SNOPT)nc nvSol.TimeSol.TimeSol.TimeALJAZZAF 3 175.00.4675.000.0175.000.10ALLINITC30.44*30.490.0130.490.104 1ALSOTAME 2 10.0820.570.080.010.0849 15--BATCH46 73--259180.350.01BT115 30.8250.620.820.010.820.09BT125 36.1880.476.190.016.190.09BT65 20.2770.560.280.010.280.09BT75 3306.50.51360.380.01360.380.0922.570.501.350.011.350.09HS1007 4680.60.72680.630.01680.630.09HS1017 51809.7*1809.760.011809.760.14HS1027 5911.9*911.880.01911.880.12HS1037 5--543.670.01543.670.11HS1048 53.950.583.950.013.950.10HS1079 650550.595055.010.015055.010.10HS1089 13-0.8660.580.000.010.000.10HS1099 10--0.000.010.000.10HS11110 3-47.760.83-47.710.01-47.710.11HS11410 11-1768.81.64-1768.810.01-1768.810.10HS11715 532.350.6032.350.0132.350.10HS11916 8244.90.54244.900.01244.900.10HS122 1-30.00.46-30.000.01-30.000.09HS182 25.00.655.000.015.000.10HS192 2-6961.80.58-6961.810.01-6961.810.09HS202 340.20.5238.200.0138.200.09HS232 52.00.542.00.012.00.09HS242 3-1.00.550.000.010.000.09HS263 10.00.650.000.010.000.09HS273 10.040.490.040.010.040.09HS293 1-22.60.530.000.010.000.0994680129.58 0.01 94680129.58 0.10259180.35 0.11BT85 21.00.571.000.011.000.09CB23 31.9520.601.950.011.950.09CRESC46 8--0.870.010.870.10CSFI15 4-49.070.63-49.080.01-49.080.09DIPIGRI7 4680.60.68680.630.01680.630.090.01.122471.900.012471.900.10DNIEPER 61 24 1.87 × 104 0.8318744.010.0118744.010.130.000.010.000.10EXPFITA4 10.09AVION2DIXCHLNG 10 5HONG5 22 1.13 × 10−3 0.65GAUSSELM 14 11-2.250.550.00104.900.000.12HIMMELBI 100 12-1735.61.23-1755.000.01-1755.000.13HIMMELBJ 45 14---1755.000.01-1755.000.09continued on next pagecontinued on next page149150continued from previous pagecontinued from previous pageIDnc nvSol.TimeSol.TimeSol.TimeIDnc nvSol.TimeSol.TimeSol.TimeHS303 11.00.521.000.011.000.09HS754 55174.40.5629.890.0129.890.09HS323 21.00.541.000.011.000.09HS775 20.24150.560.240.010.240.09HS333 2-4.00.55-4.00.01-4.00.09HS785 3-2.920.58-2.920.01-2.920.09HS343 2-0.8340.38-0.830.01-0.830.09HS795 30.07880.5713.970.0113.970.09HS363 1-33000.550.000.010.000.09HS805 30.0540.580.0540.010.0540.09HS373 2-34560.480.000.010.000.10HS835 3-306660.52 -30665.540.01-30665.540.09HS394 2-1.00.52-1.000.01-1.000.09HUBFIT2 10.01690.460.020.010.020.09HS404 3-0.250.58-0.250.01-0.250.09LOADBAL 31 310.4530.690.450.010.450.12HS414 11.9260.522.000.012.000.09LOOTSMA3 2--2.000.012.000.09HS424 213.860.5613.860.0113.860.09MADSEN3 60.6160.550.620.010.620.09HS434 3-44.00.49-44.000.01-44.000.09MARATOS2 1-1.00.40-1.000.01-1.000.09HS465 20.00.540.000.010.000.09MATRIX26 20.00.520.000.010.000.09HS546 10.00.580.190.010.190.09MISTAKE9 13HS556 66.6670.496.330.016.330.09HS567 4-3.4560.550.000.010.000.12NGONEHS572 10.030650.571.700.011.700.12ODFITSHS603 10.03260.620.030.010.030.09HS613 2-143.650.57-143.650.01-143.65HS623 1-262730.61 -26272.510.01-26272.51HS633 2961.720.55961.720.01-1.00.58-1.000.01-1.000.1024.970.5624.980.0124.980.108 8-0.50.5124.980.1524.980.2710 6-23800.50-2380.030.01-2380.030.10OPTCNTRL 32 205500.51550.000.01550.000.100.10OPTPRLOC 30 30-16.424.02-16.420.01-16.420.110.10ORTHREGB 27 60.00.760.000.010.000.100.560.000.010.000.09961.720.09MWRIGHT 5 3PENTAGON 6 15 1.509 × 10−4HS72 1-1.7320.56-1.730.01-1.730.09POLAK13 22.7180.532.720.012.720.09HS714 217.010.6217.010.0117.010.09POLAK312 105.9330.825.930.025.930.15HS734 329.90.5229.890.0129.890.10POLAK53 250.00.5250.000.0150.000.10HS744 55126.50.5029.890.0129.890.09POLAK65 4-44.00.74-44.000.01-44.000.11continued on next page151continued on next page1525.4continued from previous pageSummaryIDnc nvSol.TimeSol.TimeSol.TimeIn this section, we have presented a constraint-partitioning approach that exploits the con-RK2317 110.08330.750.080.010.080.09straint structure of large-scale MINLP and CNLP benchmark problems.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
