Warning: the term solution refers to the best solution found at the end of the optimization phase. For QUBO-based methods, constraints are incorporated into the objective function through penalty coefficients. At the end of the optimization process, there is no guarantee that all constraints are satisfied. For example, for instance 125 in the Medium-Scale category, the optimal value is -216.92, whereas the solution found by A_QUBM is -213.04. This indicates that the solution -213.04 does not satisfy all the constraints, which can be readily verified by examining the solution details.
  1. Remarks

    The primary cost function is:

    ob_function
    For all experiments, we used α = 100 because cos(βi, j, k) ≤ 1 and di, j ≥ distance of 2 layers, and the distance of 2 layers is designed to be more significant than 100 μm. The dataset gets precisely the position of the layer without measurement.

    For example:

    We have only two segments on a track: x1, 2, x2, 3 and d1, 2 = 100, d2, 3 = 300 corresponding.

    With cos(β1, 2, 3) = 1, the cost of this track is:

          cost = 100. 1/(100+300).1.1 = 0.25
  2. Parameters

    3. We used the following parameters:

  3. Denoted
      Denoted:
    • Instance_name: name of instance
    • S*: Optimal solution cost
    • S: Solution cost found
    • TP (s): Time preprocessing duration
    • TR (s): Resolution time
    • TT (s): Total time: TT = TP + TR
    • GAP (%): The error percentage: GAP = [(S - S*)/S*].100%
    • ATT: Average of total time
    • AGAP (%): Average of GAP
    • PS (%): Percentage of having solution followed by the method
  4. Results

    The average results of total time and GAP of all datasets by methods.

    Comparison of datasets by methods
    Dataset A_QUBM C_BLP C_QCBM C_QUBM D_QCBM D_QUBM
    ATT AGAP PS ATT AGAP PS ATT AGAP PS ATT AGAP PS ATT AGAP PS ATT AGAP PS
    Small scale instances 0.55 0.08 1 0.72 0 1 1.25 0 1 0.23 0 1 3.72 0 1 3.14 0 1
    Medium scale instances 39.665 17.7879 1 194.673 0.0002 1 234.851 0.0002 1 994.497 5.206 1 36.662 5.9394 1 58.347 2.0338 1
    Large scale instances 588.218 52.3212 1 4031.6625 0.0004 0.4 3045.72 39.701 0.4 2986.6325 37.9886 0.4 384.8378 52.0929 0.9 420.8417 14.2745 0.6

    The detailed results of all datasets by methods

    Small scale instances:

    Small scale results A_QUBM C_BLP C_QCBM C_QUBM D_QCBM D_QUBM
    No. tracks S* TP S TR TT GAP S TR TT GAP S TR TT GAP S TR TT GAP S TR TT GAP S TR TT GAP
    10 -17.35 0 -17.35 0.08 0.08 0 -17.35 0.01 0.01 0 -17.35 0 0 0 -17.35 0.01 0.01 0 -17.35 0.03 0 0 -17.35 3.06 3 0
    20 -34.7 0 -34.7 0.22 0.22 0 -34.7 0 0 0 -34.7 0.01 0.01 0 -34.7 0.01 0.01 0 -34.7 0.03 0 0 -34.7 3.08 2.99 0
    30 -52.05 0.01 -52.05 0.15 0.16 0 -52.05 0 0.01 0 -52.05 0.01 0.01 0 -52.05 0.01 0.02 0 -52.05 0.04 0.01 0 -52.05 3.13 3 0
    40 -69.39 0.02 -69.39 0.19 0.21 0 -69.39 0.05 0.07 0 -69.39 0.01 0.03 0 -69.39 0.03 0.04 0 -69.39 5.11 5.08 0 -69.39 3.2 3.01 0
    50 -86.73 0.04 -86.73 0.23 0.27 0 -86.73 0.01 0.05 0 -86.73 0.01 0.04 0 -86.73 0.03 0.06 0 -86.73 5.11 5.1 0 -86.73 3.17 3.03 0
    60 -104.09 0.07 -104.09 0.29 0.36 0 -104.09 0.01 0.08 0 -104.09 0.01 0.08 0 -104.09 0.03 0.1 0 -104.09 5.11 5.11 0 -104.09 3.2 3.07 0
    70 -121.45 0.15 -121.45 0.38 0.53 0.0002 -121.45 0.15 0.3 0 -121.45 0.83 0.97 0 -121.45 0.1 0.25 0 -121.45 5.12 5.2 0 -121.45 3.39 3.15 0
    80 -138.8 0.24 -138.8 0.47 0.71 0.0003 -138.8 0.57 0.81 0 -138.8 4.45 4.69 0 -138.8 0.13 0.37 0 -138.8 5.35 5.5 0 -138.8 3.29 3.23 0
    90 -156.16 0.38 -155.66 0.73 1.12 0.3199 -156.16 3.24 3.63 0 -156.16 5.61 5.99 0 -156.16 0.21 0.59 0 -156.16 5.31 5.58 0 -156.16 3.71 3.38 0.0002
    100 -173.5 0.57 -172.76 1.29 1.86 0.432 -173.5 1.65 2.215 0 -173.5 0.15 0.72 0 -173.5 0.31 0.87 0 -173.5 5.2 5.64 0 -173.5 3.51 3.56 0.0002

    Medium-scale instances:

    Medium scale results A_QUBM C_BLP C_QCBM C_QUBM D_QCBM D_QUBM
    No. tracks S* TP S TR TT GAP S TR TT GAP S TR TT GAP S TR TT GAP S TR TT GAP S TR TT GAP
    125 -216.92 1.49 -213.04 1.04 2.53 1.787 -216.92 0.17 1.66 0.0001 -216.92 0.09 1.58 0.0001 -216.92 0.33 1.82 0.0001 -216.92 5.54 6.8 0.0001 -216.92 4.36 5.21 0.0004
    150 -260.29 2.95 -251.92 1.54 4.49 3.215 -260.29 0.43 3.39 0.0001 -260.29 0.21 3.16 0.0001 -260.29 1.61 4.56 0.0001 -260.29 5.5 7.96 7.96 -259.54 6.11 7.87 0.2876
    175 -303.69 5.69 -286.47 2.51 8.21 5.6707 -303.69 1.48 7.17 0.0001 -303.69 0.54 6.23 0.0001 -303.69 54.99 60.68 0.0001 -303.69 5.96 11.13 0.0004 -302.2 8.64 12.76 0.4922
    200 -347.06 9.5 -314.65 3.35 12.85 9.3385 -347.06 5.88 15.38 0.0002 -347.06 2.06 11.56 0.0002 -347.06 93.09 102.59 0.0002 -347.06 5.63 14.51 0.0008 -342.19 11.12 18.58 1.4045
    225 -390.48 15.85 -340.33 4.86 20.71 12.8434 -390.48 54.3 70.15 0.0002 -390.48 23.55 39.4 0.0002 -390.48 296.12 311.97 0.0002 -389.72 5.94 20.86 0.1926 -384.49 16.94 29.98 1.5338
    250 -433.87 24.22 -358.35 6.87 31.09 17.4059 -433.87 128.78 153 0.0002 -433.87 73.35 97.57 0.0002 -433.87 360.04 384.26 0.0001 -432.91 6.33 29.25 0.2227 -423.47 25.05 45.44 2.3968
    275 -477.27 35.75 -367.95 9.15 44.89 22.9049 -477.27 360.03 395.78 0.0002 -477.27 853.02 888.77 0.0002 -477.02 360.05 395.79 0.0523 -469.71 6.8 40.79 1.5843 -466.87 34.69 65.27 2.1791
    300 -520.68 52.24 -358.73 13.45 65.69 31.1025 -520.68 360.06 412.3 0.0002 -520.68 360.06 412.3 0.0003 -478.67 360.09 412.33 8.0688 -491.84 7.29 57.3 5.5382 -495.1 48.31 93.6 4.9119
    325 -564.07 72.37 -370.34 16.85 89.23 34.3459 -564.07 360.08 432.45 0.0003 -564.07 360.06 432.44 0.0003 -495.15 3600.13 3672.51 12.2184 -490.35 8.09 77.46 13.0692 -545.27 70.33 131.55 3.3324
    350 -607.46 95.33 -368.94 21.63 116.96 39.2652 -607.46 360.12 455.45 0.0002 -607.46 360.17 455.5 0.0002 -414.77 4503.13 4598.46 31.7201 -371.85 9.3 100.56 38.7853 -584.38 89.72 173.21 3.799

    Large-scale instances:

    Large scale results A_QUBM C_BLP C_QCBM C_QUBM D_QCBM D_QUBM
    No. tracks S* TP S TR TT GAP S TR TT GAP S TR TT GAP S TR TT GAP S TR TT GAP S TR TT GAP
    375 -650.86 128.87 -377.49 27.92 156.79 42.0017 -650.87 3703.66 3832.52 0.0003 -650.87 3600.23 3729.1 0.0003 -494.41 3600.28 3729.14 24.0377 -438.32 11.41 134.10 32.66 -617.75 116.17 228.39 5.09
    400 -694.26 169.28 -379.47 44.76 214.04 45.34 -694.26 3600.11 3769.39 0.0004 -694.26 3600,07 3769.35 0.0003 -333.02 360.0871 529.3661 52.0328 -342.97 11.45 174.5 50.5988 -643.12 139.12 290.87 7.3657
    425 -737.63 215.67 -389.89 52.43 268.1 47.1438 -737.64 4438.03 4653.71 0.0003 -146.77 3837.62 4053.29 80.103 -467.41 3600.65 3816.32 36.6345 -362.44 13.69 221.11 50.8651 -656.03 173.83 363.83 11.0636
    450 -781.04 270.89 -382.79 82.35 353.23 50.9894 -781.04 3600.14 3871.03 0.0004 -781.04 3600.25 3871.14 0.0004 -474.49 3600.81 3871.7 39.2493 -380.24 15.39 277.03 51.3163 -552.62 211.01 451.8 29.2459
    475 -824.43 338.92 -396.13 4.86 20.71 12.8434 - - - - - - - - - - - - -372.08 17.86 345.79 54.8675 -700.36 271.68 546.49 15.0483
    500 -867.83 408.56 -399.11 150.1 558.66 54.0106 - - - - - - - - - - - - -390.28 20.01 416.47 55.0278 -713.06 273.63 643.67 17.8348
    525 -911.24 513.66 -399.47 243.59 757.25 56.1622 - - - - - - - - - - - - -395.32 24.11 522.62 56.617 - - - -
    550 -954.62 606.75 -406.97 258.09 864.84 57.3683 - - - - - - - - - - - - -400.93 30.63 637.38 58.0011 - - - -
    575 -998 723.46 -412.9 353.11 353.11 58.6274 - - - - - - - - - - - - -410.31 33.07 734.54 58.887 - - - -
    600 -1041.38 848.31 -420.55 340.6 1188.91 59.6161 - - - - - - - - - - - - - - - - - - - -
Remark:
1) Method C_BLP, C_QCBM and C_QUBM use Cplex for solving and are not quantum methods. The resolution time exceed 1 hour for some instances. The instances that can not be solved with Cplex in less than one hour are marked with "-"

2)D_QCBM and D_QUBM are Dwave based methods. We use a free account and the maximal computational time is limited to 20min i.e. 1200 seconds. Some instances have not be solved with D_QCBM and D_QUBM due to this limitation.