Originally posted by: furufuru

Hi,

I was wondering how I should deal with memory problem.
I use CPLEX12 64bit version on Linux Computer Cluseter.
Here is my environment.

---

Manufacturer Sun Microsystems (X4100, V60x, V20z) & Dell (SC1425)
Main Memory 5472 GB (2-4 GB per node)
Number of Nodes 785
Number of CPUs 14,654
CPU Type Pentium 4 Xeon (3.06GHz), Intel Xeon(64-bit) 3.2 GHz and single-core and dual-core Opteron (2.0 GHz and 2.2GHz)
OS Name Linux (CentOS 4)

---

Using MIP, I try to obtain solution for multiple traveling repair man problem which aims to minimize the average completion time.

If I increase the number of repairmen and tasks such as 10 repairmen and 18 tasks, I encountered out-of-memory problem.
It would be nice if we can have a solution close to the optimal one. But the gap shown in the log is very big to stop.
So, do you know any solutions to balance the memory size of tree, or something else?

I put the message from CPLEX below?
Thanks,
furuhata

---

Start a new iteration of solving the CPLEX model ...
Tried aggregator 1 time.
MIP Presolve eliminated 569 rows and 2304 columns.
MIP Presolve modified 306 coefficients.
Reduced MIP has 531 rows, 1135 columns, and 6122 nonzeros.
Reduced MIP has 1117 binaries, 0 generals, 0 SOSs, and 0 indicators.
Probing time = 0.00 sec.
Tried aggregator 1 time.
Presolve time = 0.02 sec.
Probing time = 0.01 sec.
Clique table members: 3694.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.01 sec.
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

• 0+ 0 64.3333 213 ---

0 0 0.0000 59 64.3333 0.0000 213 100.00%
0 0 0.0000 59 64.3333 Cuts: 132 389 100.00%
0 0 0.0000 58 64.3333 Cuts: 71 591 100.00%

• 0+ 0 63.6667 0.0000 591 100.00%
• 0+ 0 61.8333 0.0000 591 100.00%

0 2 0.0000 53 61.8333 0.0000 591 100.00%
Elapsed real time = 0.40 sec. (tree size = 0.01 MB, solutions = 3)
....
Elapsed real time = 1096.85 sec. (tree size = 9187.95 MB, solutions = 60)
Nodefile size = 9058.75 MB (5369.38 MB after compression)
2118551 2012753 15.0701 63 36.7222 11.4016 55938122 68.95%
2133136 2026542 23.9566 53 36.7222 11.4078 56360516 68.93%
2147519 2040092 16.4427 106 36.7222 11.4145 56768586 68.92%
2162680 2054358 14.7127 53 36.7222 11.4208 57211184 68.90%
2177665 2068462 32.4175 62 36.7222 11.4270 57574231 68.88%
2192276 2082228 18.6709 56 36.7222 11.4336 57935153 68.86%
2207828 2096872 13.0556 106 36.7222 11.4389 58340143 68.85%

There may be further error information in the clone logs.
GUB cover cuts applied: 1
Clique cuts applied: 8
Cover cuts applied: 113
Implied bound cuts applied: 284
Flow cuts applied: 52
Mixed integer rounding cuts applied: 63
Zero-half cuts applied: 8
Gomory fractional cuts applied: 40

Root node processing (before b&c):
Real time = 0.37
Parallel b&c, 8 threads:
Real time = 1155.69
Sync time (average) = 42.85
Wait time (average) = 0.28

---

Total (root+branch&cut) = 1156.05 sec.
Warning: MIP starts not constructed because of out-of-memory status.
Error: CPLEX Error 1001: Out of memory.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

One easy thing to try would to ask CPLEX to swap some of the search tree nodes to disk instead of keeping them in memory. To do so use parameters CPX_PARAM_NODEFILEIND (set it to 2 or 3) and CPX_PARAM_WORKMEM.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

This looks like a very interesting small problem. My first guess is that the biggest improvements can be made by working on your MIP formulation. Maybe there is a different way of modeling your problem that solves much nicer?

To reduce memory consumption, you could store node files to disk as suggested by Daniel. Additionally, you could use depth first search ("set mip str node 0" in the interactive), which is very memory friendly but may degrade performance. Finally, you may need to prevent cut separation at the local nodes by setting some separators to 1: "set mip cut cov 1" and "set mip cut impl 1".

Would you mind sending me your model to achterberg <at> de <dot> ibm <dot> com? I would really like to take a look at this. Maybe I can find better parameters.
Would I be allowed to pass this model to Yuji Shinano, a researcher at Zuse Institute Berlin who is developing ParaSCIP/ParaCPLEX, a distributed memory extension to SCIP and CPLEX? With such a nice cluster to your disposal, maybe this is something that you want to try...

Last question: what is your guess what the optimal solution value is? Is it more like 36.7 (the current incumbent) or closer to 11.4 (the dual bound)?
Tobias
#CPLEXOptimizers
#DecisionOptimization