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.