Benchmark ========= This section presents the evaluation results of graph MaxCut algorithms under two settings: (1) **distribution-wise**, using the BA distribution; (2) **instance-wise**, using the Gset dataset. 1. Distribution-wise Benchmark ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. raw:: html
.. csv-table:: Table 1-1: Results for graph MaxCut on BA distribution :header: Nodes, Gurobi, S2V-DQN, S2V-DQN#Gurobi, ECO-DQN, ECO-DQN#Gurobi, Ours, Ours#Gurobi :widths: 6, 8, 8, 10, 8, 10, 8, 10 100, 283.7, 272.3, -4.0%, 283.63, -0.02%, 283.7, 0 200, 583.3, 557.2, -4.5%, 581.7, -0.26%, 582.2, -0.17% 300, 880.4, 825.4, -6.2%, 873.9, -0.74%, 878.0, -0.27% 400, 1179.2, 1100.6, -6.7%, 1165.3, -1.18%, 1174.2, -0.42% 500, 1477.6, 1374.9, -6.9%, 1167.2, -1.0%, 1471.4, -0.42% 600, 1774.5, 1647.2, -7.1%, 1752.6, -1.2%, 1769.1, -0.3% 700, 2068.6, 1907.3, -7.8%, 2043.3, -1.2%, 2062.6, -0.3% 800, 2361.0, 2182.1, -7.6%, 2331.3, -1.3%, 2358.7, -0.1% 900, 2655.9, 2425.5, -8.7%, 2616.9, -1.5%, 2647.0, -0.3% 1000, 2952.2, 2706.1, -8.3%, 2911.9, -1.3%, 2940.3, -0.4% .. note:: The relative difference (columns with "#Gurobi") represents the performance gap with Gurobi's result. Higher values are better. .. csv-table:: Table 1-2: Results for graph maxcut on ER distribution in distribution-wise scenario :header: "#Nodes", "dREINFORCE", "Gurobi", "dREINFORCE#Gurobi", "S2V-DQN#Gurobi", "dREINFORCE#S2V-DQN" :widths: auto 100, 507.83, 507.83, 0, -0.05% (100-200), 0.05% 200, 1858.93, 1856.13, 0.151%, -1.05% (200 ~ 300), 1.20% 300, 4063.20, 4062.93, 0, -2.65% (300 ~ 400), 2.66% 400, 7042.10, 7041.67, 0, -3.59% (400 ~ 500), 3.60% 500, 10862.30, 10862.40, 0, -5.77% (500 ~ 600), 5.77% 1000, 41735.16, 41765.87, -0.0735%, -5.07% (1000 ~ 1200), 5.00% 1100, 50219.47, 50286.8, -0.134%, -5.07% (1000 ~ 1200), 4.94% 1200, 59506.30, 59561.83, -0.093%, -5.07% (1000 ~ 1200), 4.98% 2000, 163637.97, 162162.30, 0.91%, --, -- 3000, 363228.49, 359632.17, 1.00%, --, -- .. csv-table:: Table 1-3: Results for graph maxcut on powerlaw (PL) distribution :header: "Nodes", "Greedy", "SDP", "SA", "GA", "Gurobi", "S2V-DQN (Pattern I)", "PI-GNN (Pattern I)", "ISCO (Pattern I)", "dREINFORCE (Pattern II)", "MCPG (Pattern II)", "Jumanji (Pattern I)" :widths: auto 100, 268.2, 270.6, 268.4, **282.9**, **282.9**, 278.5, 271.3, 282.8, **282.9**, **282.9**, **282.9** 200, 548.0, 554.4, 550.5, 578.0, **578.7**, 563.1, 572.5, 578.3, **578.7**, **578.7**, **578.7** 300, 824.6, 833.9, 826.4, 877.2, 877.2, 859.4, 843.2, 876.1, **879.5**, 878.2, **879.5** 400, 1107.1, 1117.8, 1110.1, 1173.2, 1173.1, 1152.7, 1135.8, 1169.6, **1178.4**, 1173.9, **1178.4** 500, 1386.6, 1399.0, 1391.5, 1471.5, 1468.1, 1440.2, 1455.3, 1467.0, **1475.6**, **1475.6**, 1460.4 600, 1660.5, 1683.4, 1664.1, 1768.3, 1760.8, 1725.6, 1693.7, 1758.5, **1773.9**, 1770.1, 1769.5 700, 1950.8, 1970.0, 1955.0, 2064.9, 2056.7, 2004.9, 1982.4, 2055.5, 2061.2, **2064.1**, 2058.6 800, 2228.0, 2260.7, 2232.2, 2361.4, 2349.8, 2302.4, 2346.7, 2353.4, **2378.9**, 2375.4, 2352.7 900, 2507.0, 2540.0, 2514.1, 2658.1, 2643.9, 2526.4, 2594.3, 2645.0, **2676.1**, 2671.9, 2667.4 1000, 2784.3, 2817.4, 2792.7, 2955.5, 2942.1, 2723.3, 2903.4, 2949.1, 2980.2, **2984.7**, 2963.9 2. Instance-wise Benchmark ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. csv-table:: Table 2-1: Results for graph MaxCut on the Gset dataset in instance-wise scenario :header: Graph, Nodes, Edges, BLS, DSDP, KHLWG, RUN-CSP, PI-GNN, iSCO, dREINFORCE, MCPG, Jumanji :widths: auto G14, 800, 4694, 3064, --, 2922, 3061, 2943, 3056, 3064, 3064, 3064 G15, 800, 4661, 3050, 2938, 3050, 2928, 2990, 3046, 3050, 3050, 2979 G22, 2000, 19990, 13359, 12960, 13359, 13028, 13181, 13289, 13359, 13359, 13261 G49, 3000, 6000, 6000, 6000, 6000, 6000, 5918, 5940, 6000, 6000, 5987 G50, 3000, 6000, 5880, 5880, 5880, 5880, 5820, 5874, 5880, 5880, 5872 G55, 5000, 12468, 10294, 9960, 10236, 10116, 10138, 10218, 10298, 10296, 10283 G70, 10000, 9999, 9541, 9456, 9458, --, 9421, 9442, 9586, 9578, 9554 .. csv-table:: Table 2-2: Results for TSP on the TSPLIB dataset in instance-wise scenario :header: Instance, LKH, S2V-DQN (Pattern I), PI-GNN (Pattern I), ISCO (Pattern I), dREINFORCE (Pattern II), MCPG (Pattern I), Jumanji (Pattern II), 2-opt, Cheapest, Christofides :widths: auto eil51, 426, 439, 445, 428, 428, 428, 428, 446, 494, 527 berlin52, **7542**, **7542**, 7657, **7542**, **7542**, **7542**, **7542**, 7788, 9013, 8822 st70, 675, 696, 690, 682, 682, 682, 682, 753, 776, 836 eil76, 538, 564, 575, 553, 553, 553, 553, 591, 607, 646 pr76, 108159, 108446, 108536, 108437, **108405**, **108405**, **108405**, 115460, 125935, 137258 rat99, 1211, 1280, 1291, 1272, 1260, 1260, 1260, 1390, 1473, 1399 kroA100, 21282, 21897, 21905, 21886, **21863**, **21863**, 21923, 22876, 24309, 26578 kroB100, 22141, 22692, 22783, 22634, **22607**, **22607**, 23107, 23496, 25582, 25714 kroC100, 20749, 21074, 21631, 21014, **21004**, **21004**, 21524, 23445, 25264, 24582 kroD100, 21294, 22102, 22304, 22107, **22019**, **22019**, 22087, 23967, 25204, 27863 kroE100, 22068, 22913, 22978, 22869, **22803**, **22803**, 23106, 22800, 25900, 27452 rd100, 7910, 8159, 8189, 8153, 8132, 8114, 8744, 8757, 8980, 10002 eil101, 629, 659, 669, 702, **651**, **651**, 664, 702, 693, 728 lin105, 14379, 15023, 15236, 15014, 14856, 14907, 15023, 15536, 16930, 16568 pr107, 44303, 45113, 45234, 45013, **44728**, 44765, 45128, 47058, 52816, 49192 pr124, 59030, 61623, 61614, 61514, **61137**, 61185, 63214, 64765, 65316, 64591 bier127, 118282, 121576, 122354, 120367, **120367**, **120139**, 121324, 128103, 141354, 135134 ch130, 6110, 6270, 6394, 6231, **6215**, 6238, 6368, 6470, 7279, 7367 pr136, 96772, 99474, 99356, 99136, 98075, **98013**, 104265, 110531, 109586, 116069 ch144, 58537, 59436, 59487, 59415, **59137**, **59137**, 602361, 60321, 73032, 74684 pr150, 6528, 6985, 6992, 6834, 6746, 6784, 7021, 7232, 7995, 7641 kroA150, 26524, 27888, 27956, 27726, 27162, **27134**, 27195, 29666, 29963, 32631 kroB150, 26130, 27209, 28413, 27135, **27027**, 27109, 27547, 29517, 31589, 33260 pr152, 73682, 75283, 77468, 77368, **74337**, **74337**, 75462, 77206, 88531, 82118 u159, 42080, 45433, 45624, 44632, **43501**, 43952, 44367, 47664, 49898, 48908 rat195, 2323, 2581, 2674, 2551, **2529**, **2529**, 2631, 2605, 2806, 2906 d198, 15780, 16453, 16654, 16231, **16018**, 16237, 16325, 16596, 17632, 19002 kroA200, 29368, 30965, 31632, 30826, **30537**, 30621, 31848, 32760, 35340, 37487 kroB200, 29437, 31692, 31953, 31321, 31189, **31024**, 31635, 33107, 35412, 34490 tsp225, 3916, 4154, 4161, 4109, **3967**, 4013, 4150, 4278, 4470, 4733 pr226, 80369, 81873, 81962, 81632, 81031, **80510**, 81310, 89262, 91023, 98101 gil262, 2378, 2537, 2561, 2536, 2487, **2485**, 2607, 2597, 2800, 2963 pr264, 49135, 52364, 52961, 52120, **52018**, 52115, 5326, 54547, 57602, 55955 a280, 2579, 2867, 2931, 2861, **2759**, 2768, 2964, 2914, 3128, 3125 pr299, 48191, 51895, 52136, 51134, 50107, **49357**, 51328, 54914, 58127, 58660 lin318, 42029, 45375, 45057, 45653, 44069, **44068**, 45231, 45263, 49440, 51484 linhp318, 41345, 45444, 45647, 44362, **43246**, 43627, 44367, 45263, 49440, 51484 .. csv-table:: Table 2-3 Total flop count in tensor-train network of various sizes. The compared methods are OE Greedy, CTG Greedy, and CTG Kahypar. :header: "Size", "OE Greedy", "CTG Greedy", "CTG Kahypar", "dREINFORCE (Pattern II)", "MCPG (Pattern II)" :widths: auto N=100, 30.927, 30.705, 30.710, 30.404, 30.404 N=200, 61.030, 60.808, 60.810, **60.507**, **60.507** N=400, 121.236, 121.014, 121.010, **120.713**, 120.968 N=600, 181.442, 181.220, 181.220, 180.919, 180.976 N=800, 241.648, 241.426, 241.430, **241.125**, **241.125** N=1000, 301.854, 301.632, 301.630, 301.331, 301.937 N=1500, --, --, 452.150, **451.846**, 451.925 N=2000, --, --, 602.660, **602.361**, 602.571 .. csv-table:: Table 2-4 Total flop count in Sycamore circuit of various cycles. The compared methods are OE Greedy, CTG Greedy, CTG Kahypar, AC-QDP, and RL-TNCO. :header: "Cycles", "OE Greedy", "CTG Greedy", "CTG Kahypar", "AC-QDP", "RL-TNCO", "dREINFORCE (Pattern II)", "MCPG (Pattern II)" :widths: auto m=12, 17.795, 17.065, 13.407, 13.037, 10.736, **10.117**, **10.117** m=14, 19.679, 19.281, 14.149, 13.851, 12.869, **12.029**, 12.726 m=16, 25.889, 23.152, 17.013, 17.061, --, **13.967**, 14.532 m=18, 26.793, 23.569, 17.681, 17.412, --, **17.113**, **17.113** m=20, 26.981, 25.622, 18.825, 18.823, 18.543, **18.158**, 18.17 .. raw:: html