9
$\begingroup$

Consider a mixed integer linear program with an objective function that includes only integer variables. Objective integrality cuts are known as a class of valid inequalities that can be added to strengthen such a formulation: If the objective coefficients are all integers, then the objective value must be an integer because the variables are required to be integer.

I am wondering whether objective integrality cuts have been implemented in modern solvers? If not, what could be challenging when implementing objective integrality cuts? I am surprised that a commercial solver such as CPLEX does not seem to consider objective integrality cuts (I'm not sure about Gurobi). It is not uncommon for an optimization problem to have integer objective values (e.g., scheduling problems, assembly line balancing problems, etc). In such cases, the integrality cuts could play a significant role in solving the problem faster. Just to give an example, here is the log file for an instance of a real-world course scheduling problem solved by CPLEX 12.10 (the objective is to maximize the number of student-lesson allocations):

            Nodes                                         Cuts/
       Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap
    
    *     0+    0                           57.0000       80.0000            40.35%
          0     0       64.4321  3783       57.0000       64.4321       18   13.04%
          0     0       63.3571  3783       57.0000     Cuts: 297    16536   11.15%
          0     0       62.5714  3783       57.0000     Cuts: 744    37274    9.77%
          0     0       62.5714  3783       57.0000     Cuts: 472    58784    9.77%
          0     0       62.5714  3783       57.0000     Cuts: 400    80695    9.77%
          0     0       62.5714  3783       57.0000      Cuts: 50   100726    9.77%
          0     0       62.5536  3783       57.0000     Cuts: 405   122147    9.74%
    *     0+    0                           60.0000       62.5536             4.26%
          0     0        cutoff             60.0000       62.5536   122147    4.26%
          0     0       62.5536  3783       60.0000     Cuts: 487   163607    4.26%
    Heuristic still looking.
          0     2       62.5536  2211       60.0000       62.5536   217531    4.26%
    Elapsed time = 237.27 sec. (226054.16 ticks, tree = 0.02 MB, solutions = 2)
          1     3       62.5536  2220       60.0000       62.5536   287580    4.26%
          2     3       62.5536  2086       60.0000       62.5536   251100    4.26%
          3     4       62.5536  2162       60.0000       62.5536   309506    4.26%
.
.
.

       2469  1948       62.0000  1506       60.0000       62.5536  4209632    4.26%
    Elapsed time = 1212.46 sec. (840425.96 ticks, tree = 35.92 MB, solutions = 2)
       2501  1968       62.0000  1126       60.0000       62.5536  4229228    4.26%
       2544  1990       62.0000  1025       60.0000       62.5536  4254943    4.26%
       2555  2005       61.0000  1483       60.0000       62.5536  4266956    4.26%
    
    Performing restart 1
    
    Repeating presolve.
    Tried aggregator 2 times.
    MIP Presolve eliminated 463 rows and 676 columns.
    MIP Presolve modified 7567 coefficients.
    Aggregator did 43 substitutions.
    Reduced MIP has 8121 rows, 14050 columns, and 135496 nonzeros.
    Reduced MIP has 13853 binaries, 197 generals, 0 SOSs, and 0 indicators.
    Presolve time = 0.28 sec. (310.77 ticks)
    Tried aggregator 1 time.
    Reduced MIP has 8121 rows, 14050 columns, and 135496 nonzeros.
    Reduced MIP has 13853 binaries, 197 generals, 0 SOSs, and 0 indicators.
    Presolve time = 0.08 sec. (90.85 ticks)
    Represolve time = 0.62 sec. (575.33 ticks)
       2574     0       62.5000  2516       60.0000     Cuts: 122  4514780    4.17%
       2574     0       62.5000  2516       60.0000     Cuts: 528  4534076    4.17%
       2574     0       62.2000  2516       60.0000     Cuts: 220  4550193    3.67%
       2574     0       62.0000  2516       60.0000     Cuts: 200  4565065    3.33%
       2574     0       62.0000  2516       60.0000     Cuts: 240  4582021    3.33%
       2574     0       62.0000  2516       60.0000     Cuts: 203  4595338    3.33%
       2574     0       62.0000  2516       60.0000      Cuts: 94  4615273    3.33%
       2574     0       62.0000  2516       60.0000     Cuts: 212  4629574    3.33%
       2574     0       62.0000  2516       60.0000      Cuts: 31  4644396    3.33%
       2574     0       62.0000  2516       60.0000     Cuts: 228  4660555    3.33%
       2574     0       62.0000  2516       60.0000     Cuts: 103  4674035    3.33%
       2574     2       62.0000  1389       60.0000       62.0000  4674035    3.33%
       2575     3       62.0000  1826       60.0000       62.0000  4709875    3.33%
       2576     4       62.0000  1816       60.0000       62.0000  4747076    3.33%
       2577     5       62.0000  1818       60.0000       62.0000  4763581    3.33%
       2579     7       62.0000  1977       60.0000       62.0000  4816350    3.33%
       2580     4       62.0000  1936       60.0000       62.0000  4728882    3.33%
       2582    10       62.0000  2032       60.0000       62.0000  4891825    3.33%
    Elapsed time = 1711.68 sec. (1187756.21 ticks, tree = 0.05 MB, solutions = 2)
       2583     5       62.0000  1773       60.0000       62.0000  4764410    3.33%
       2586    11       62.0000  1604       60.0000       62.0000  4908032    3.33%

.
.
.

       6137  1599       61.3333  1125       60.0000       62.0000 12157124    3.33%
       6146  1598       61.9079  1424       60.0000       62.0000 12173722    3.33%
       6181  1609       61.3647  1111       60.0000       61.9995 12233657    3.33%
       6226  1625       61.0000  1003       60.0000       61.9995 12250334    3.33%
       6249  1636    infeasible             60.0000       61.9995 12278475    3.33%
       6283  1641    infeasible             60.0000       61.9951 12317307    3.33%
    Elapsed time = 3963.23 sec. (2538648.23 ticks, tree = 41.58 MB, solutions = 2)
       6301  1647       61.5000  1577       60.0000       61.9951 12418694    3.33%
       6364  1666    infeasible             60.0000       61.9934 12316289    3.32%
       6412  1733       61.7162  1227       60.0000       61.9904 12709071    3.32%
       6444  1736       61.0000  1106       60.0000       61.9904 12716961    3.32%
       6476  1656       61.7184  1323       60.0000       61.9904 12350981    3.32%
       6484  1769       61.7025  1211       60.0000       61.9903 12794727    3.32%
       6496  1735        cutoff             60.0000       61.9903 12743643    3.32%
       6511  1775       61.3971   941       60.0000       61.9903 12813587    3.32%
       6535  1743       61.0000   977       60.0000       61.9903 12757733    3.32%
       6569  1779       61.0000  1082       60.0000       61.9903 12830429    3.32%
    Elapsed time = 4023.28 sec. (2579373.65 ticks, tree = 43.78 MB, solutions = 2)
       6588  1791       61.4419  1166       60.0000       61.9903 12850058    3.32%
       6603  1791       61.8181  1268       60.0000       61.9903 12872281    3.32%
       6628  1793       61.5922  1131       60.0000       61.9903 12892286    3.32%
       6647  1795       61.5000  1150       60.0000       61.9903 12910529    3.32%
       6672  1795       61.3736  1376       60.0000       61.9903 12927013    3.32%
       6689  1840       61.0000  1093       60.0000       61.9832 13086892    3.31%
       6702  1814       61.8944  1642       60.0000       61.9803 12977507    3.30%
       6747  1842        cutoff             60.0000       61.9803 13106508    3.30%
       6767  1830       61.8605  1587       60.0000       61.9803 13007243    3.30%
       6792  1832       61.1159  1134       60.0000       61.9803 13051760    3.30%
    Elapsed time = 4078.46 sec. (2620380.80 ticks, tree = 45.21 MB, solutions = 2)
       6822  1832        cutoff             60.0000       61.9803 13070729    3.30%
       6842  1838       61.0000  1324       60.0000       61.9803 13062044    3.30%
       6866  1910       61.8334  1441       60.0000       61.9767 13384490    3.29%
       6874  1909       61.5960  1261       60.0000       61.9767 13405032    3.29%
       6878  1864       61.2500  1442       60.0000       61.9767 13189519    3.29%
       6884  1909       61.5172  1466       60.0000       61.9767 13425013    3.29%
       6907  1920       61.8302  1533       60.0000       61.9687 13538726    3.28%
       6939  1910       61.0000   944       60.0000       61.9687 13446020    3.28%
       6966  1909       61.4766   879       60.0000       61.9687 13459069    3.28%
       7001  1915       61.0000  1167       60.0000       61.9687 13472454    3.28%
    Elapsed time = 4145.74 sec. (2661009.25 ticks, tree = 47.80 MB, solutions = 2)
       7021  1967        cutoff             60.0000       61.9687 13747529    3.28%
       7040  1923       61.3571  1135       60.0000       61.9687 13504972    3.28%
       7070  1918        cutoff             60.0000       61.9681 13572484    3.28%
       7114  1984       61.0000  1237       60.0000       61.9681 13811339    3.28%
       7161  1985       61.3571   936       60.0000       61.9681 13791200    3.28%
       7195  1990       61.0000  1051       60.0000       61.9655 13802870    3.28%
       7241  2037       61.4184  1335       60.0000       61.9655 13856241    3.28%
       7273  2041       61.0000   718       60.0000       61.9605 13870340    3.27%
       7330  2027    infeasible             60.0000       61.9605 14163653    3.27%
       7381  2049       61.4755  1224       60.0000       61.9605 14182949    3.27%
    Elapsed time = 4206.36 sec. (2700755.48 ticks, tree = 51.38 MB, solutions = 2)
       7398  2062       61.7146  1275       60.0000       61.9605 14200049    3.27%
       7429  2012       61.2611  1148       60.0000       61.9605 14005744    3.27%
       7436  2052       61.3431  1829       60.0000       61.9605 13906393    3.27%
       7449  2070       61.0000   764       60.0000       61.9603 14231211    3.27%
       7490  2022       61.2747  1098       60.0000       61.9603 14022232    3.27%
       7530  2074        cutoff             60.0000       61.9521 14272106    3.25%
       7549  2039       61.7106  1072       60.0000       61.9521 14038477    3.25%
       7586  2048       61.8510  1416       60.0000       61.9521 14059524    3.25%
       7606  2230       61.0000  1314       60.0000       61.9502 14554729    3.25%
       7628  2179        cutoff             60.0000       61.9502 14392664    3.25%
    Elapsed time = 4270.14 sec. (2743050.11 ticks, tree = 53.81 MB, solutions = 2)
       7648  2120       61.0000   894       60.0000       61.9502 14322353    3.25%
       7672  2133       61.8597  1531       60.0000       61.9502 14308142    3.25%
       7686  2231       61.9079  1684       60.0000       61.9502 14601680    3.25%
       7699  2119       61.8254  1403       60.0000       61.9502 14351175    3.25%
       7714  2234       61.0000   998       60.0000       61.9470 14664571    3.25%
       7723  2236       61.0000  1212       60.0000       61.9470 14644039    3.25%
       7731  2134       61.8674  1343       60.0000       61.9470 14318333    3.25%
       7756  2238       61.0000   733       60.0000       61.9463 14674875    3.24%
       7776  2255       61.2500  1536       60.0000       61.9463 14725473    3.24%
       7786  2256       61.8481  1247       60.0000       61.9463 14735565    3.24%
    Elapsed time = 4332.20 sec. (2783199.85 ticks, tree = 56.46 MB, solutions = 2)
       7791  2257        cutoff             60.0000       61.9463 14745895    3.24%
       7808  2264       61.0000  1198       60.0000       61.9430 14946733    3.24%
       7821  2270       61.0000   984       60.0000       61.9430 14950291    3.24%
       7860  2290       61.0000  1212       60.0000       61.9430 14776599    3.24%
       7875  2295       61.0000   932       60.0000       61.9430 14786495    3.24%
       7895  2263       61.0000  1251       60.0000       61.9430 14884742    3.24%
       7934  2271    infeasible             60.0000       61.9430 14890638    3.24%
       7955  2303       61.7400  1119       60.0000       61.9430 14828629    3.24%
       7971  2317       61.0000   905       60.0000       61.9383 15097930    3.23%
       7990  2272       61.3033  1703       60.0000       61.9383 15027318    3.23%
    Elapsed time = 4388.94 sec. (2822866.25 ticks, tree = 57.50 MB, solutions = 2)
       8007  2333       61.0000   867       60.0000       61.9354 15151925    3.23%
       8029  2333       61.8355  1319       60.0000       61.9354 15165228    3.23%
       8046  2334       61.0000  1299       60.0000       61.9354 15178204    3.23%
       8060  2343       61.2530  1273       60.0000       61.9354 15191329    3.23%
       8078  2326       61.0000  1075       60.0000       61.9354 15125606    3.23%
       8098  2354       61.0000  1058       60.0000       61.9324 15218130    3.22%
       8156  2361       61.4800   969       60.0000       61.9324 15232884    3.22%
       8188  2266       61.0000  1072       60.0000       61.9324 15065570    3.22%
       8217  2352    infeasible             60.0000       61.9304 15355287    3.22%
       8241  2354       61.3676  1088       60.0000       61.9303 15369248    3.22%
    Elapsed time = 4446.48 sec. (2862230.01 ticks, tree = 60.96 MB, solutions = 2)
       8277  2365       61.0924  1171       60.0000       61.9303 15247471    3.22%
       8316  2426       61.0000   942       60.0000       61.9261 15559093    3.21%
       8336  2400       61.1240  1216       60.0000       61.9261 15508046    3.21%
       8367  2401       61.3986  1564       60.0000       61.9261 15517862    3.21%
       8416  2357       61.0000  1159       60.0000       61.9261 15407396    3.21%
       8469  2372    infeasible             60.0000       61.9261 15396690    3.21%
       8506  2369       61.0000   779       60.0000       61.9261 15418228    3.21%
       8547  2449       61.8355  1424       60.0000       61.9235 15744339    3.21%
       8574  2373        cutoff             60.0000       61.9235 15484108    3.21%
       8584  2373       61.3522  1138       60.0000       61.9235 15508231    3.21%
    Elapsed time = 4506.51 sec. (2901953.67 ticks, tree = 61.37 MB, solutions = 2)
       8620  2487    infeasible             60.0000       61.9189 15913518    3.20%
       8642  2512       61.0000   815       60.0000       61.9173 16054147    3.20%
       8682  2491       61.0000   693       60.0000       61.9173 15951697    3.20%
       8718  2489    infeasible             60.0000       61.9142 15960741    3.19%
       8783  2547       61.5657  1450       60.0000       61.9142 16227651    3.19%
       8824  2523    infeasible             60.0000       61.9142 16130680    3.19%
       8887  2489       61.0000   714       60.0000       61.9142 15813419    3.19%
       8920  2494    infeasible             60.0000       61.9142 15834833    3.19%
       8980  2492       61.0000   738       60.0000       61.9142 15857991    3.19%
       9006  2548    infeasible             60.0000       61.9142 16322787    3.19%
    Elapsed time = 4562.09 sec. (2940776.73 ticks, tree = 65.84 MB, solutions = 2)
       9025  2547       61.6203  1203       60.0000       61.9142 16235296    3.19%
       9050  2500       61.2500   975       60.0000       61.9142 16018633    3.19%
       9088  2552       61.8385  1463       60.0000       61.9036 16341978    3.17%
       9123  2553        cutoff             60.0000       61.8966 16365088    3.16%
       9164  2593       61.6620  1309       60.0000       61.8966 16502662    3.16%
       9196  2641       61.0000  1047       60.0000       61.8966 16746483    3.16%
       9243  2647       61.5000   913       60.0000       61.8966 16767595    3.16%
       9280  2599       61.0000  1102       60.0000       61.8966 16561253    3.16%
       9332  2627       61.7113  1186       60.0000       61.8966 16590406    3.16%
       9356  2628       61.0930  1225       60.0000       61.8966 16611364    3.16%
    Elapsed time = 4625.76 sec. (2981229.66 ticks, tree = 66.86 MB, solutions = 2)
       9380  2650       61.2630  1095       60.0000       61.8919 16836200    3.15%
       9399  2653       61.0000  1807       60.0000       61.8919 16868094    3.15%
       9434  2652       61.0000  1115       60.0000       61.8919 16872831    3.15%
       9452  2663       61.7739   989       60.0000       61.8919 16908281    3.15%
       9489  2689       61.0000   916       60.0000       61.8919 16922193    3.15%
       9515  2676        cutoff             60.0000       61.8825 17184971    3.14%
       9536  2676        cutoff             60.0000       61.8825 17197590    3.14%
       9559  2653       61.0000  1108       60.0000       61.8674 16989017    3.11%
       9596  2655        cutoff             60.0000       61.8674 16997530    3.11%
       9631  2692       61.0000  1068       60.0000       61.8674 17219131    3.11%
    Elapsed time = 4683.73 sec. (3020301.29 ticks, tree = 67.36 MB, solutions = 2)
       9677  2705    infeasible             60.0000       61.8674 17243510    3.11%
       9710  2692       61.2222   543       60.0000       61.8674 17047013    3.11%
       9730  2711        cutoff             60.0000       61.8674 17281318    3.11%
       9736  2713       61.5693  1157       60.0000       61.8674 17293726    3.11%
       9741  2718       61.0305  1214       60.0000       61.8674 17301128    3.11%
       9760  2762       61.0314  1247       60.0000       61.8451 17579803    3.08%
       9787  2817       61.0000  1424       60.0000       61.8451 17774155    3.08%
       9820  2797    infeasible             60.0000       61.8451 17700085    3.08%
       9837  2766       61.0000  1023       60.0000       61.8363 17608387    3.06%
       9847  2833       61.0000  1176       60.0000       61.8363 17815781    3.06%
    Elapsed time = 4754.33 sec. (3067906.75 ticks, tree = 70.23 MB, solutions = 2)
       9867  2812       61.1667  2051       60.0000       61.8363 17870760    3.06%
       9889  2837        cutoff             60.0000       61.8363 17858429    3.06%
       9931  2838       61.5000  1075       60.0000       61.8291 17872321    3.05%
       9978  2825       61.0000  1209       60.0000       61.8291 17970922    3.05%
      10067  2863       61.0000  1335       60.0000       61.8291 17909832    3.05%
      10155  2829    infeasible             60.0000       61.8291 17748554    3.05%
      10222  2813        cutoff             60.0000       61.8291 17982223    3.05%
      10288  2847    infeasible             60.0000       61.8165 18056261    3.03%
      10336  2857       61.1795  1001       60.0000       61.8165 18077392    3.03%
      10376  2947    infeasible             60.0000       61.8041 18445395    3.01%
    Elapsed time = 4810.86 sec. (3107326.40 ticks, tree = 74.47 MB, solutions = 2)
      10435  2859    infeasible             60.0000       61.8041 18125171    3.01%
      10489  2868        cutoff             60.0000       61.8041 18130255    3.01%
      10503  2951       61.4333  1405       60.0000       61.8041 18508519    3.01%
      10537  2874       61.0000   648       60.0000       61.8041 18151270    3.01%
      10559  2950        cutoff             60.0000       61.8041 18542058    3.01%
      10597  3003        cutoff             60.0000       61.7965 18672270    2.99%
      10637  2957       61.0000  1077       60.0000       61.7965 18584630    2.99%
      10671  2887       61.0000   967       60.0000       61.7965 18183141    2.99%
      10691  2883       61.0000   880       60.0000       61.7965 18207587    2.99%
      10727  2892       61.2927  1416       60.0000       61.7965 18231150    2.99%
    Elapsed time = 4873.31 sec. (3146013.14 ticks, tree = 73.37 MB, solutions = 2)
      10774  3047        cutoff             60.0000       61.7760 19014444    2.96%
      10826  2963        cutoff             60.0000       61.7760 18665600    2.96%
      10845  3013       61.5000  1202       60.0000       61.7701 18746676    2.95%
      10862  3054       61.0000  1081       60.0000       61.7701 18883472    2.95%
      10904  3069       61.0000   861       60.0000       61.7701 19268861    2.95%
      10949  3052       61.0000  1054       60.0000       61.7701 18921892    2.95%
      10980  3059       61.3111  1383       60.0000       61.7701 18940213    2.95%
      11001  3063       61.0000   848       60.0000       61.7701 19043353    2.95%
      11038  3073       61.0000   944       60.0000       61.7654 19067069    2.94%
      11059  3058       61.0000  1304       60.0000       61.7654 18971160    2.94%
    Elapsed time = 4933.79 sec. (3184940.39 ticks, tree = 76.15 MB, solutions = 2)
      11099  3079       61.0000  1048       60.0000       61.7654 18979024    2.94%
      11141  3078        cutoff             60.0000       61.7654 19001584    2.94%
      11181  3116       61.1591  1047       60.0000       61.7552 19553552    2.93%
      11211  3116       61.0000  1263       60.0000       61.7514 19559733    2.92%
      11246  3089       61.0000   779       60.0000       61.7514 19458460    2.92%
      11291  3132       61.4763  1437       60.0000       61.7514 19575665    2.92%
      11318  3130        cutoff             60.0000       61.7514 19597777    2.92%
      11357  3138    infeasible             60.0000       61.7514 19771799    2.92%
      11398  3141        cutoff             60.0000       61.7453 19780179    2.91%
      11451  3100    infeasible             60.0000       61.7453 19503913    2.91%
    Elapsed time = 4986.36 sec. (3224179.72 ticks, tree = 76.34 MB, solutions = 2)
      11509  3131        cutoff             60.0000       61.7453 19827301    2.91%
      11549  3162       61.1432  1142       60.0000       61.7360 19946929    2.89%
      11570  3129       61.0000   877       60.0000       61.7360 19663162    2.89%
      11634  3165       61.4550   983       60.0000       61.7360 19880048    2.89%
      11698  3166        cutoff             60.0000       61.7360 19902554    2.89%
      11734  3150       61.0000  1006       60.0000       61.7147 20159523    2.86%
      11790  3145    infeasible             60.0000       61.7147 20061632    2.86%
      11854  3165    infeasible             60.0000       61.7147 19948884    2.86%
      11893  3187    infeasible             60.0000       61.7147 20215485    2.86%
      11944  3183       61.4327  1461       60.0000       61.7147 20236691    2.86%
    Elapsed time = 5042.58 sec. (3262981.88 ticks, tree = 78.15 MB, solutions = 2)
      11977  3147       61.5000  1015       60.0000       61.7147 20121081    2.86%
      12027  3184        cutoff             60.0000       61.7066 20277701    2.84%
      12083  3176        cutoff             60.0000       61.7066 20300601    2.84%
      12124  3161       61.5000  1002       60.0000       61.6967 20771814    2.83%
      12154  3148       61.3691  1151       60.0000       61.6967 20381973    2.83%
      12194  3158    infeasible             60.0000       61.6967 20580807    2.83%
      12250  3150       61.0000  1240       60.0000       61.6919 20842945    2.82%
      12303  3141        cutoff             60.0000       61.6919 20449019    2.82%
      12364  3197        cutoff             60.0000       61.6835 21017417    2.81%
      12387  3206       61.0000  1339       60.0000       61.6835 21154927    2.81%
    Elapsed time = 5103.26 sec. (3302444.71 ticks, tree = 78.19 MB, solutions = 2)
      12437  3221    infeasible             60.0000       61.6835 21175005    2.81%
      12476  3221       61.0000   988       60.0000       61.6835 21199639    2.81%
      12508  3166    infeasible             60.0000       61.6835 20892100    2.81%
      12516  3162       61.0000  1108       60.0000       61.6835 20909465    2.81%
      12549  3186       61.0000  1307       60.0000       61.6667 21301906    2.78%
      12608  3158    infeasible             60.0000       61.6590 21568178    2.76%
      12698  3247       61.0000  1065       60.0000       61.6590 21277625    2.76%
      12755  3186    infeasible             60.0000       61.6590 21513465    2.76%
      12781  3181        cutoff             60.0000       61.6494 21535145    2.75%
      12844  3188       61.0000  1098       60.0000       61.6494 21381785    2.75%
    Elapsed time = 5168.29 sec. (3341418.56 ticks, tree = 76.25 MB, solutions = 2)
      12899  3201        cutoff             60.0000       61.6494 21784101    2.75%
      12936  3196        cutoff             60.0000       61.6321 21608725    2.72%
      12955  3197    infeasible             60.0000       61.6224 21811000    2.70%
      12980  3191       61.0000   677       60.0000       61.6224 21833958    2.70%
      13003  3165       61.0000   924       60.0000       61.6224 21638900    2.70%
      13026  3234       61.0000  1059       60.0000       61.6224 22075653    2.70%
      13065  3239        cutoff             60.0000       61.6224 22090956    2.70%
      13074  3210        cutoff             60.0000       61.6224 21909136    2.70%
      13115  3154    infeasible             60.0000       61.6224 21712230    2.70%
      13157  3232        cutoff             60.0000       61.6000 22137303    2.67%
    Elapsed time = 5227.01 sec. (3380933.18 ticks, tree = 75.92 MB, solutions = 2)
      13170  3225        cutoff             60.0000       61.6000 22153208    2.67%
      13183  3222       61.0000  1456       60.0000       61.6000 22164650    2.67%
      13206  3215       61.0000  1186       60.0000       61.6000 22296707    2.67%
      13237  3165       61.0000   987       60.0000       61.6000 22394542    2.67%
      13270  3127        cutoff             60.0000       61.5568 22670998    2.59%
      13302  3213        cutoff             60.0000       61.5568 22348758    2.59%
      13319  3116       61.0000  1003       60.0000       61.5568 22700891    2.59%
      13350  3104    infeasible             60.0000       61.5568 22721876    2.59%
      13371  3082        cutoff             60.0000       61.5568 22789932    2.59%
      13400  3079        cutoff             60.0000       61.5191 22900534    2.53%
    Elapsed time = 5287.62 sec. (3422572.94 ticks, tree = 73.30 MB, solutions = 2)
      13416  3064        cutoff             60.0000       61.5000 22968687    2.50%
      13448  3079       61.0000  1175       60.0000       61.5000 22927242    2.50%
      13460  3074        cutoff             60.0000       61.5000 22940326    2.50%
      13471  3058        cutoff             60.0000       61.5000 22994565    2.50%
      13495  3041        cutoff             60.0000       61.5000 23026843    2.50%
      13524  3047        cutoff             60.0000       61.5000 23023921    2.50%
      13561  2997        cutoff             60.0000       61.5000 23146081    2.50%
      13595  2979       61.0000   961       60.0000       61.5000 23194905    2.50%
      13635  2952    infeasible             60.0000       61.5000 23243440    2.50%
      13671  3026       61.0000  1011       60.0000       61.5000 23126969    2.50%
    Elapsed time = 5341.50 sec. (3461642.86 ticks, tree = 73.45 MB, solutions = 2)
      13685  2949       61.0000  1025       60.0000       61.5000 23284084    2.50%
      13702  2943        cutoff             60.0000       61.5000 23295585    2.50%
      13735  2951       61.0000   984       60.0000       61.5000 23274270    2.50%
      13745  3105       61.0000  1410       60.0000       61.5000 22804004    2.50%

In this case, the optimality gap is set to 2% and the optimization would have terminated earlier if the integrality of the objective function had been considered. I have seen this issue numerous times with more severe delays in the termination due to the solver not considering the integrality cuts. I could resolve this issue manually by introducing an auxiliary integer variable that captures the value of the original objective function in a constraint. However, I am wondering why this has not already been considered in modern solvers (perhaps it has, but it requires a certain configuration/implementation)?

$\endgroup$
4
  • $\begingroup$ If i read this log correctly it has the best integer solution 60 and the bound 61.5, so it is still not sure if there is a solution with 61? Can you clarify how it can terminate earlier? $\endgroup$ Dec 3 '20 at 17:09
  • $\begingroup$ i think the confusion comes from that you thought the third column is the best solution, but it is actually the fifth column. $\endgroup$ Dec 3 '20 at 18:25
  • 1
    $\begingroup$ @user3680510 There is no confusion. In this case, the optimality gap was set to 2% as mentioned in the question. CPLEX could have terminated the optimization earlier if it knew about integrality of the objective. It got the bound 61.9 after 3900 seconds and it could have stopped there since the integer bound is 61. $\endgroup$
    – rasul
    Dec 3 '20 at 22:16
  • $\begingroup$ yes i miss understood the question. $\endgroup$ Dec 4 '20 at 11:06
7
$\begingroup$

I am not familiar with objective integrality cuts, but I know that CPLEX has the option to set the parameter absolute objective difference cutoff. If you set this parameter to 1, CPLEX will terminate the search if the difference between the best integer solution and the best bound is strictly less than 1.

$\endgroup$
1
  • $\begingroup$ It seems that absolute objective difference cutoff can be used for the similar purpose as absolute MIP gap tolerance. However, neither of the two settings can resolve the issue here. $\endgroup$
    – rasul
    Dec 6 '20 at 1:54
4
$\begingroup$

AFAIK Lindo have implemented objective integrality cuts, but I don't know the details of the implementation. It's always a trade-off that depends on what type of problems a solver's users solve more frequently.

We don't use them in our solver because the slowdown we experience from the sheer number of constraints that must be added to impose integrality slows down the solving process overall, especially for pure integer (i.e. not binary) variables.

The other reason we avoid them is that they can be numerically unstable: say the relaxation has a value of 62.0001, should the cuts enforce rounding up to 63, or is this a numerical artifact? It is very hard to control this, especially for large problems where accumulation of error is significant. I have seen problems where the correct answer could go either way. All we need is to get unlucky on a single node of the branch and bound tree, and then we've missed the global solution.

$\endgroup$
2
  • $\begingroup$ For a maximization problem, objective integrality cuts can be added each time the best integer upper bound (UB) is updated (not each time the best UB is updated). Rounding errors are typical of any IP solver and they should be addressed any way. I think the simplest way to address such errors for the objective integrality cuts is to automatically introduce one auxiliary integer variable and one constraint as mentioned in my question. Then the cut generation and numerical errors are both handled through the default settings. $\endgroup$
    – rasul
    Dec 6 '20 at 1:12
  • $\begingroup$ There are many different ways to do this, I'm merely pointing out why it's not done in practice - it just doesn't work very well most of the time. $\endgroup$ Dec 6 '20 at 6:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.