Originally posted by: EdKlotz
I think the question refers to starting tree search faster. I base this on both the previous thread that is referenced and a quick examination of CPLEX performance in the supportcase10 model.
But, regardless of the meaning of the question, the fundamental answer is essentially the same. Namely, get as much information as you can from the node log to figure out the source of the performance bottleneck, then use that info to take the appropriate remedial action. In the case of excessive time spent at the root node before the tree search, that means set the MIP display parameter to 5 to see as much as you can during the root node processing, and assess what happens. If you do that with supportcase10, you will see that the dual simplex method really struggles on the node LPs, and you can get better performance at the root (and perhaps also during the tree search node LPs; I didn't check) by using the barrier method to solve the node LPs.
Here's some of the node log output that is urging us to do this. For starters, when the model has a small aspect ratio, that suggests that the barrier method can work better; while the lack of restart capability is normally a disadvantage, it can help in that barrier can solve the dual model from scratch. And supportcase10 is a small aspect ratio, both in the original model and the presolved model:
Tried aggregator 1 time.
Reduced MIP has 105209 rows, 8955 columns, and 361245 nonzeros.
Reduced MIP has 8955 binaries, 0 generals, 0 SOSs, and 0 indicators.
So solving the dual model involves linear systems of dimension ~9000, while for the primal model they have dimension 105209.
And we get confirmation using barrier likely will help because it solved the initial root node fastest:
Iteration: 36046 Dual objective = 3.266938
Iteration: 36651 Dual objective = 3.268787
Removing perturbation.
Initializing dual steep norms . . .
Barrier solved model.
Iteration log . . .
Iteration: 1 Dual objective = 3.383924
Root relaxation solution time = 40.00 sec. (10001.55 ticks)
And then we see some long dual simplex runs at the root, despite the supposed advantage of an advanced start:
Iteration: 12938 Dual objective = 3.441677
Iteration: 13196 Dual objective = 3.441681
Iteration: 13453 Dual objective = 3.441687
Elapsed time = 110.72 sec. (40005.41 ticks, 13664 iterations)
Iteration: 13717 Dual objective = 3.441697
Iteration: 14002 Dual objective = 3.441704
So basically this suggests that we replace dual simplex with barrier for any computation during the root node processing that uses dual simplex. Rather than go incrementally, I tried everything I could think of at once, namely turning off cuts, turning off heuristics and setting variableselect to 4 to avoid some of the strong branching calculations used in the default variableselection. And then I set the subalgorithm parameter to 4 to use the barrier method for whatever was left. With that, I got:
Iteration: 56297 Dual objective = 3.380132
Iteration: 56893 Dual objective = 3.380327
Iteration: 57500 Dual objective = 3.380539
Removing perturbation.
Barrier solved model.
Winner waited 3.278 sec for lock, 0.083 sec for signal to be acknowledged
Iteration log . . .
Iteration: 1 Dual objective = 3.383924
Root relaxation solution time = 13.08 sec. (7926.90 ticks)
p graph rootfix: 0.00 s (0, 0.00 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
0 0 3.3839 6724 3.3839 21
Subproblem optimization logging appears only in clone logs.
0 2 3.3839 6724 3.3839 21
Elapsed time = 18.33 sec. (10074.21 ticks, tree = 0.02 MB, solutions = 0)
1 3 4.0552 5583 3.3842 41
So this starts the tree search within a minute, and CPLEX can then solve the model to optimality within 20 minutes:
Elapsed time = 1047.42 sec. (832874.40 ticks, tree = 0.19 MB, solutions = 2)
591 16 5.5649 5241 7.0000 5.3388 12862 23.73%
592 2 cutoff 7.0000 5.3388 13174 23.73%
593 17 5.7158 5140 7.0000 5.3388 12897 23.73%
594 4 5.9898 5919 7.0000 5.4441 13191 22.23%
595 3 cutoff 7.0000 5.4441 13270 22.23%
596 3 cutoff 7.0000 5.4441 13268 22.23%
597 3 cutoff 7.0000 5.4441 13269 22.23%
598 3 cutoff 7.0000 5.4441 13209 22.23%
599 2 cutoff 7.0000 5.4441 13226 22.23%
Root node processing (before b&c):
Real time = 17.42 sec. (9631.66 ticks)
Parallel b&c, 12 threads:
Real time = 1089.45 sec. (885451.84 ticks)
Sync time (average) = 271.89 sec.
Idle time (average) = 0.00 sec.
Wait time (average) = 0.00 sec.
------------
Total (root+branch&cut) = 1106.88 sec. (895083.51 ticks)
I'll leave it as an exercise for others to determine if some of these non default settings were unnecessary to start the tree search quickly, as well as examination of the detailed node log for supportcase22 to figure how to get that one to solve faster.
Regarding the broader questions about improving performance on particular MIPLIB or other models, here is a resource regarding examining the node log:
https://www.slideshare.net/IBMOptimization/2013-11-informsminingthenodelog
And here is a technote (including references to a couple of papers that go into more detail): https://www-01.ibm.com/support/docview.wss?uid=swg21400023
And here's a link that provides more info on one of the papers in the above technote (including recorded presentation of some of the material):
https://www.ibm.com/developerworks/community/blogs/jfp/entry/practical_guidelines_for_solving_difficult_mixed_integer_programs?lang=en
#CPLEXOptimizers#DecisionOptimization