2
$\begingroup$

I am solving a (rather large) MILP in CPLEX in Java. I also wrote a solution extractor method, which works most of the time. However, when CPLEX tries to solve my problem with the dual simplex method it seems to get stuck in the solve method? Hence, it now seems as if for some instances I get feasible solutions and for some instances I do not get any results. Could someone tell me how to extract the solution after Dual simplex solved model. is shown?

See below the output when I run my program for a particular instance where this happens

Version identifier: 20.1.0.0 | 2020-11-10 | 9bedb6d68
CPXPARAM_MIP_Display                             4
Tried aggregator 4 times.
Aggregator has done 6411 substitutions...
MIP Presolve eliminated 256991 rows and 123355 columns.
Aggregator did 6411 substitutions.
Reduced MIP has 362983 rows, 181240 columns, and 4585972 nonzeros.
Reduced MIP has 181240 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 39.05 sec. (17751.56 ticks)
Found incumbent of value 32237.000000 after 39.61 sec. (18374.96 ticks)
Probing time = 21.42 sec. (2888.50 ticks)
Tried aggregator 1 time.
Detecting symmetries...
MIP Presolve eliminated 4741 rows and 2406 columns.
Reduced MIP has 358242 rows, 178834 columns, and 4570728 nonzeros.
Reduced MIP has 178834 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 18.57 sec. (9204.98 ticks)
Probing time = 20.17 sec. (3421.28 ticks)
Clique table members: 2377190.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Parallel mode: deterministic, using up to 2 threads for parallel tasks at root LP.
Parallel mode: deterministic, using up to 6 threads for concurrent optimization:
 * Starting dual Simplex on 1 thread...
 * Starting Barrier on 4 threads...
 * Starting primal Simplex on 1 thread...
Tried aggregator 1 time.
No LP presolve or aggregator reductions.
Presolve time = 0.47 sec. (369.39 ticks)
Initializing dual steep norms . . .

Iteration log . . .
Iteration:     1   Dual objective     =       1291014.000000
Perturbation started.
Iteration:  4747   Dual objective     =        714309.000000
Iteration:  5555   Dual objective     =        523779.984383
Iteration: 10103   Dual objective     =         46821.953292
Iteration: 10521   Dual objective     =         46718.953200
Iteration: 11120   Dual objective     =         46483.953192
Iteration: 12129   Dual objective     =         45479.953182
Iteration: 13402   Dual objective     =         45416.453121
Iteration: 13886   Dual objective     =         45416.453096
Iteration: 16049   Dual objective     =         45373.452990
Iteration: 16504   Dual objective     =         45352.452976
Iteration: 18783   Dual objective     =         45174.452915
Iteration: 19302   Dual objective     =         45157.452894
Iteration: 21563   Dual objective     =         45003.952882
Iteration: 21999   Dual objective     =         45003.952855
Iteration: 24088   Dual objective     =         45002.952775
Iteration: 24511   Dual objective     =         45002.952757
Iteration: 26440   Dual objective     =         44996.952672
Iteration: 26883   Dual objective     =         44996.952651
Iteration: 28880   Dual objective     =         44951.952592
Iteration: 29350   Dual objective     =         44951.952565
Iteration: 31194   Dual objective     =         44951.952511
Iteration: 31614   Dual objective     =         44951.952500
Iteration: 33440   Dual objective     =         44951.952454
Iteration: 33816   Dual objective     =         44951.952445
Iteration: 35776   Dual objective     =         44939.952389
Iteration: 36188   Dual objective     =         44939.952378
Iteration: 37895   Dual objective     =         44934.952342
Iteration: 38258   Dual objective     =         44934.952334
Iteration: 39992   Dual objective     =         44934.952290
Iteration: 40415   Dual objective     =         44934.952276
Iteration: 42148   Dual objective     =         44934.952218
Iteration: 42596   Dual objective     =         44934.952207
Iteration: 44288   Dual objective     =         44934.952166
Iteration: 44696   Dual objective     =         44934.952157
Iteration: 46364   Dual objective     =         44934.952117
Elapsed time = 11.94 sec. (10072.72 ticks, 46750 iterations)
Iteration: 46750   Dual objective     =         44934.952109
Iteration: 48418   Dual objective     =         44934.952063
Iteration: 48800   Dual objective     =         44934.952053
Iteration: 50478   Dual objective     =         44933.952017
Iteration: 50855   Dual objective     =         44933.952008
Iteration: 52495   Dual objective     =         44932.951967
Iteration: 52871   Dual objective     =         44932.951939
Iteration: 54498   Dual objective     =         44932.951894
Iteration: 54891   Dual objective     =         44932.951884
Iteration: 56494   Dual objective     =         44932.951842
Iteration: 56893   Dual objective     =         44932.951832
Iteration: 58507   Dual objective     =         44932.951794
Iteration: 58930   Dual objective     =         44932.951785
Iteration: 60503   Dual objective     =         44932.951744
Iteration: 60947   Dual objective     =         44932.951727
Iteration: 62484   Dual objective     =         44932.951691
Iteration: 62893   Dual objective     =         44932.951681
Iteration: 64455   Dual objective     =         44932.951646
Iteration: 64803   Dual objective     =         44932.951638
Iteration: 66337   Dual objective     =         44932.951604
Iteration: 66764   Dual objective     =         44932.951595
Iteration: 68275   Dual objective     =         44931.951606
Iteration: 68681   Dual objective     =         44931.951596
Iteration: 70148   Dual objective     =         44931.951546
Iteration: 70503   Dual objective     =         44931.951537
Iteration: 71959   Dual objective     =         44931.951498
Iteration: 72367   Dual objective     =         44931.951489
Iteration: 73825   Dual objective     =         44930.951523
Iteration: 74213   Dual objective     =         44930.951515
Iteration: 75638   Dual objective     =         44930.951481
Iteration: 76028   Dual objective     =         44930.951472
Iteration: 77482   Dual objective     =         44928.951558
Iteration: 77830   Dual objective     =         44928.951550
Elapsed time = 29.53 sec. (20072.92 ticks, 78930 iterations)
Iteration: 79190   Dual objective     =         44923.951818
Iteration: 79546   Dual objective     =         44923.951776
Iteration: 80689   Dual objective     =         44923.951738
Iteration: 81117   Dual objective     =         44923.951686
Iteration: 82374   Dual objective     =         44923.451750
Iteration: 82908   Dual objective     =         44923.451737
Iteration: 83963   Dual objective     =         44923.451721
Iteration: 84621   Dual objective     =         44923.451714
Iteration: 85808   Dual objective     =         44923.451700
Iteration: 86535   Dual objective     =         44922.951750
Iteration: 87513   Dual objective     =         44922.951741
Iteration: 88444   Dual objective     =         44922.951734
Elapsed time = 49.14 sec. (30075.03 ticks, 89122 iterations)
Iteration: 89482   Dual objective     =         44922.951728
Iteration: 90388   Dual objective     =         44922.951724
Iteration: 91240   Dual objective     =         44922.951723
Iteration: 91955   Dual objective     =         44922.951677
Iteration: 92467   Dual objective     =         44922.951604
Iteration: 93907   Dual objective     =         44922.951510
Iteration: 94436   Dual objective     =         44922.951486
Iteration: 95844   Dual objective     =         44922.951456
Iteration: 96160   Dual objective     =         44921.951557
Iteration: 97240   Dual objective     =         44921.951508
Iteration: 97679   Dual objective     =         44921.951496
Iteration: 99022   Dual objective     =         44921.951449
Iteration: 99486   Dual objective     =         44921.951442
Iteration: 100587   Dual objective     =         44921.951422
Elapsed time = 78.04 sec. (40075.21 ticks, 101042 iterations)
Iteration: 101199   Dual objective     =         44921.951415
Iteration: 102215   Dual objective     =         44921.951405
Iteration: 103030   Dual objective     =         44921.951399
Iteration: 103844   Dual objective     =         44921.951396
Iteration: 104803   Dual objective     =         44921.951390
Elapsed time = 98.67 sec. (50077.16 ticks, 105500 iterations)
Iteration: 105553   Dual objective     =         44921.951389
Iteration: 106271   Dual objective     =         44921.951376
Iteration: 107425   Dual objective     =         44921.951361
Iteration: 108079   Dual objective     =         44921.951353
Iteration: 109143   Dual objective     =         44921.951339
Iteration: 109949   Dual objective     =         44921.951333
Iteration: 110720   Dual objective     =         44921.951327
Iteration: 111893   Dual objective     =         44921.951314
Elapsed time = 124.84 sec. (60077.82 ticks, 112539 iterations)
Iteration: 112866   Dual objective     =         44921.951309
Iteration: 113557   Dual objective     =         44921.951304
Iteration: 114346   Dual objective     =         44921.951302
Iteration: 115001   Dual objective     =         44921.951294
Iteration: 115927   Dual objective     =         44921.951284
Iteration: 116682   Dual objective     =         44921.951275
Elapsed time = 152.09 sec. (70078.53 ticks, 117075 iterations)
Iteration: 117666   Dual objective     =         44921.951263
Iteration: 118605   Dual objective     =         44921.951244
Iteration: 119619   Dual objective     =         44921.951234
Iteration: 120489   Dual objective     =         44921.951228
Iteration: 121253   Dual objective     =         44921.951222
Elapsed time = 175.56 sec. (80078.92 ticks, 121646 iterations)
Iteration: 121909   Dual objective     =         44921.951218
Iteration: 122949   Dual objective     =         44921.951208
Iteration: 123999   Dual objective     =         44921.951196
Iteration: 125006   Dual objective     =         44921.951184
Iteration: 125730   Dual objective     =         44921.951180
Iteration: 126557   Dual objective     =         44921.951169
Elapsed time = 201.92 sec. (90079.88 ticks, 126803 iterations)
Iteration: 127660   Dual objective     =         44921.951159
Iteration: 128702   Dual objective     =         44921.951151
Iteration: 129649   Dual objective     =         44921.951136
Iteration: 130473   Dual objective     =         44921.951131
Iteration: 131335   Dual objective     =         44921.951122
Elapsed time = 224.98 sec. (100080.62 ticks, 131595 iterations)
Iteration: 132398   Dual objective     =         44921.951110
Iteration: 133270   Dual objective     =         44921.951100
Iteration: 134153   Dual objective     =         44921.951089
Iteration: 135137   Dual objective     =         44921.951086
Elapsed time = 247.17 sec. (110082.18 ticks, 135427 iterations)
Iteration: 136050   Dual objective     =         44921.951084
Iteration: 136841   Dual objective     =         44921.951078
Iteration: 137798   Dual objective     =         44921.951069
Iteration: 138701   Dual objective     =         44921.951064
Iteration: 139608   Dual objective     =         44921.951053
Elapsed time = 275.51 sec. (120082.63 ticks, 139834 iterations)
Iteration: 140291   Dual objective     =         44921.951048
Iteration: 141246   Dual objective     =         44921.951042
Iteration: 142083   Dual objective     =         44921.951023
Iteration: 143085   Dual objective     =         44921.951015
Elapsed time = 299.14 sec. (130086.30 ticks, 143505 iterations)
Iteration: 143914   Dual objective     =         44921.951013
Iteration: 144608   Dual objective     =         44921.951002
Iteration: 145777   Dual objective     =         44921.950974
Elapsed time = 319.66 sec. (140089.17 ticks, 146556 iterations)
Iteration: 146663   Dual objective     =         44921.950966
Iteration: 147499   Dual objective     =         44921.950957
Iteration: 148424   Dual objective     =         44921.950944
Iteration: 149273   Dual objective     =         44921.950936
Elapsed time = 342.05 sec. (150092.52 ticks, 149796 iterations)
Iteration: 150182   Dual objective     =         44921.950925
Iteration: 151207   Dual objective     =         44921.950910
Iteration: 152107   Dual objective     =         44921.950892
Iteration: 153006   Dual objective     =         44921.950875
Iteration: 154175   Dual objective     =         44921.950865
Elapsed time = 366.08 sec. (160094.15 ticks, 154489 iterations)
Iteration: 155283   Dual objective     =         44921.950847
Iteration: 156355   Dual objective     =         44921.950835
Iteration: 157760   Dual objective     =         44921.950814
Iteration: 158940   Dual objective     =         44921.950798
Elapsed time = 390.36 sec. (170095.40 ticks, 159574 iterations)
Iteration: 160390   Dual objective     =         44921.950783
Removing perturbation.

Dual simplex solved model.
```
$\endgroup$
3
  • $\begingroup$ This is a big model. You probably need some patience. Also, make sure you have enough memory. $\endgroup$ Oct 11, 2022 at 13:36
  • $\begingroup$ How come it takes so long after it indicates the model is solved? Any tips on how to lower the running time, besides shrinking the model? $\endgroup$
    – Juul9191
    Oct 11, 2022 at 14:33
  • 2
    $\begingroup$ Only the root node has been solved. For large models, Cplex has to do quite a lot of work between nodes 0 and 1. $\endgroup$ Oct 11, 2022 at 14:51

1 Answer 1

2
$\begingroup$

You are solving a MIP not just an LP. Dual simplex solves the LP relaxation of the MIP. After that, the branch and cut process starts. That will usually take even more time than solving the root node/LP relaxation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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