Topic
  • No replies
SystemAdmin
SystemAdmin
1883 Posts

Pinned topic Cplex performance tuning

‏2012-11-22T17:39:34Z |
Hi folks,

I am working on solving an assignment optimization problem and after building a model I obtained an mps file, see attachment. The problem is, cplex is not that good at solving it at its default settings. I tried some tuning options but nothing helps much (polish helped at some degree). One can assume that the problem is too difficult, but I implemented a set of heuristics (multiple small cplex runs by splitting the problem, fixing part of the variable to the last optimal solution) and it works much faster than giving the whole problem to cplex and waiting. So the question is, why do we need to implement a set of (almost) generic model-independent heuristics, it looks like it should be inside cplex itself. I have a feeling that I am missing something. Could you please share your thought, any ideas are appreciated.

The problem is an employees assignment to tasks problem, which includes work limitations and job distribution fairness.

For reference, attaching a run log for the attached model on my machine, where the whole run time is 1 hours from which last 0.5 hour is polishing.
My machine (notebook):
Win7, 64 bit
i7-2720QM @2.20GHz
8Gb RAM
CPLEX> set mip polishafter time 1800
New value for solution polishing starting time: 1800
CPLEX> set timelimit 3600
New value for time limit in seconds: 3600
CPLEX> optimize
Tried aggregator 2 times.
Aggregator has done 173 substitutions...
MIP Presolve eliminated 77744 rows and 5904 columns.
MIP Presolve modified 437697 coefficients.
Aggregator did 173 substitutions.
Reduced MIP has 31163 rows, 92916 columns, and 1502425 nonzeros.
Reduced MIP has 85173 binaries, 0 generals, 0 SOSs, and 0 indicators.
Probing time = 0.08 sec.
Tried aggregator 1 time.
MIP Presolve eliminated 1214 rows and 130 columns.
MIP Presolve modified 7280 coefficients.
Reduced MIP has 29949 rows, 92786 columns, and 1492274 nonzeros.
Reduced MIP has 86726 binaries, 2879 generals, 0 SOSs, and 0 indicators.
Presolve time = 9.08 sec.
Found feasible solution after 9.30 sec. Objective = 1995198.3269
Probing time = 0.09 sec.
Clique table members: 30497.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 160.88 sec.

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

  • 0+ 0 1995198.3269 67 ---
  • 0+ 0 509468.0159 67 ---
  • 0+ 0 509335.1220 67 ---
0 0 49612.8671 3785 509335.1220 49612.8671 67 90.26%
0 0 50898.9275 2873 509335.1220 Cuts: 149 91268 90.01%
0 0 51237.6485 2453 509335.1220 Cuts: 567 169296 89.94%
0 0 51237.6689 2370 509335.1220 Cuts: 437 240969 89.94%

Starting condition for polishing reached (PolishAfterTime).
Starting solution polishing.

0 2 51237.6689 2542 509335.1220 51237.6689 490597 89.94%
Elapsed real time = 2956.28 sec. (tree size = 0.01 MB, solutions = 3)
  • 1+ 1 283410.1766 51237.6689 490750 81.92%
  • 1+ 1 133124.8884 51237.6689 490750 61.51%
  • 1+ 1 82895.7889 51237.6689 490750 38.19%
  • 1+ 1 82534.1640 51237.6689 490750 37.92%
  • 1+ 1 82441.8193 51237.6689 490750 37.85%
  • 1+ 1 82422.6303 51237.6689 490750 37.84%
  • 1+ 1 76883.6499 51237.6689 490750 33.36%
  • 1+ 1 65244.0055 51237.6689 490750 21.47%
  • 1+ 1 65229.3388 51237.6689 490750 21.45%
  • 1+ 1 64023.4888 51237.6689 490750 19.97%
  • 1+ 1 63559.5591 51237.6689 490750 19.39%
  • 1+ 1 63543.2068 51237.6689 490750 19.37%
  • 1+ 1 63514.0285 51237.6689 490750 19.33%
  • 1+ 1 62550.5087 51237.6689 490750 18.09%
  • 1+ 1 62331.7082 51237.6689 490750 17.80%
  • 1+ 1 62155.1323 51237.6689 490750 17.56%
  • 1+ 1 61592.5664 51237.6689 490750 16.81%
  • 1+ 1 61488.4425 51237.6689 490750 16.67%

GUB cover cuts applied: 14
Clique cuts applied: 324
Cover cuts applied: 6
Implied bound cuts applied: 62
Flow cuts applied: 23
Mixed integer rounding cuts applied: 129
Zero-half cuts applied: 416
Gomory fractional cuts applied: 16

Root node processing (before b&c):
Real time = 1791.00
Parallel b&c, 8 threads:
Real time = 1800.07
Sync time (average) = 0.00
Wait time (average) = 0.00

Total (root+branch&cut) = 3591.07 sec.

Solution pool: 21 solutions saved.

MIP - Time limit exceeded, integer feasible: Objective = 6.1488442487e+004
Current MIP best bound = 5.1237668924e+004 (gap = 10250.8, 16.67%)
Solution time = 3600.25 sec. Iterations = 490750 Nodes = 1 (2)
Deterministic time = 1916313.80 ticks (532.27 ticks/sec)

---
Thanks a lot in advance,
Zahar