A very common difficulty with MIPs is running out of memory. This problem occurs when the branch & cut tree becomes so large that insufficient memory remains to solve an LP or QP subproblem. As memory gets tight, you may observe warning messages from ILOG CPLEX as it attempts various operations in spite of limited memory. In such a situation, if ILOG CPLEX does not find a solution shortly, it terminates the process with an error message.

The information about a tree that ILOG CPLEX accumulates in memory can be substantial. In particular, ILOG CPLEX saves a basis for every unexplored node. Furthermore, when ILOG CPLEX uses the best bound or best estimate strategies of node selection, the list of unexplored nodes itself can become very long for large or difficult problems. How large the unexplored node list can be depends on the actual amount of memory available, the size of the problem, and algorithm selected.

A less frequent cause of memory consumption is the generation of cutting planes. Gomory fractional cuts, and, in rare instances, Mixed Integer Rounding cuts, are the ones most likely to be dense and thus use significant memory under default/automatic settings. You can try turning off these cuts, or any of the cuts you see listed as being generated for your model (in the cuts summary at the end of the node log), or simply all cuts, through the use of parameter settings discussed in the section on cuts in this manual; doing this carries the risk that this will make the model harder to solve and only delay the eventual exhaustion of available memory during branching.

Certainly, if you increase the amount of available memory, you extend the problem-solving capability of ILOG CPLEX. Unfortunately, when a problem fails because of insufficient memory, it is difficult to project how much further the process needed to go and how much more memory is needed to solve the problem. For these reasons, the following suggestions aim at avoiding memory failure whenever possible and recovering gracefully otherwise.

To avoid a failure due to running out of memory, we recommend setting the working memory parameter, WorkMem, to a value significantly lower than the available memory on your computer (in megabytes), to instruct ILOG CPLEX to begin compressing the storage of nodes before it consumes all of available memory. See the related topic "Use Node Files for Storage" , for other choices of what should happen when WorkMem is exceeded.

Because the storage of nodes can require a lot of space, it may also be advisable to set a tree limit on the size of the entire tree being stored so that not all of your disk will be filled up with working storage. The call to the MIP optimizer will be stopped once the size of the tree exceeds the value of TreLim, the tree limit parameter. Under default settings the limit is infinity (1e+75), but you can set it to a lower value (in megabytes)

On some platforms, even when the current tree size is within system limits, memory fragmentation may be so great that performance becomes poor. To overcome that kind of fragmentation, we recommend that you stop optimization, write a tree file (using the TRE format), exit ILOG CPLEX, restart it, read in the model and tree file, and continue optimization then.

ILOG CPLEX offers a node file storage feature to store some parts of the branch & cut tree in files. If you use this feature, ILOG CPLEX will be able to explore more nodes within a smaller amount of computer memory.This feature includes several options to reduce the use of physical memory, and it entails a very small increase in runtime. Node file storage offers a much better option than relying on swap space.

This feature is especially helpful when you are using steepest-edge pricing as the subproblem simplex pricing strategy because pricing information itself consumes a great deal of memory.

There are several parameters that control the use of node files. They are:

• WorkMem
• NodeFileInd
• TreLim
• WorkDir

When tree storage size exceeds the limit defined by WorkMem, what happens next is determined by the setting of NodeFileInd. If the latter parameter is set to zero, then optimization proceeds with the tree stored in memory until ILOG CPLEX reaches the tree memory limit (TreLim). If the NodeFileInd parameter is set to 1 (the default), then a fast compression algorithm is used on the nodes to try to conserve memory, without resorting to writing the node files to disk. If the parameter is set to 2, then node files are written to disk. If the parameter is set to 3, then nodes are both compressed (as in option 1) and written to disk (as in option 2). Thus, regardless of the setting of NodeFileInd, ILOG CPLEX will stop the optimization when the total memory used to store the tree exceeds the tree memory limit Table 8.12 summarizes these different options.

In cases where node files are written to disk, ILOG CPLEX will create a temporary subdirectory under the directory specified by the WorkDir parameter. The directory named by this parameter must exist before ILOG CPLEX attempts to create node files. By default, the value of this parameter is ".", which means the current working directory.

ILOG CPLEX creates the temporary directory by means of system calls. If the system environment variable is set (on Windows platforms, the environment variable TMP; on UNIX platforms, the environment variable TMPDIR), then the system ignores the ILOG CPLEX node-file directory parameter and creates the temporary node-file directory in the location indicated by its system environment variable. Furthermore, if the directory specified in the ILOG CPLEX node-file directory parameter is invalid (for example, if it contains illegal characters, or if the directory does not allow write access), then the system chooses a location according to its own logic.

The temporary directory created for node file storage will have a name prefixed by cpx. The files within it will also have names prefixed by cpx.

ILOG CPLEX automatically removes the files and their temporary directory when it frees the branch & cut tree:

• in the Interactive Optimizer,
  • at problem modification;
  • at normal termination;
• from the Concert Technology Library,
  • when you call env.end()
  • when you modify the extracted model
• from the Callable Library,
  • when you call a problem modification routine;
  • when you call CPXfreeprob().

If a program terminates abnormally, the files are not removed.

ILOG CPLEX uses node file storage most effectively when the amount of working memory is reasonably large so that it does not have to create node files too frequently. A reasonable amount is to use approximately half the memory, but no more than 128 megabytes. Higher values result in only marginally improved efficiency.

Node files could grow very large. Use the TreMem parameter to limit the size of the tree so that it does not exceed available disk space, when you choose NodeFileInd settings 2 or 3. It is usually better to let ILOG CPLEX terminate the run gracefully, with whatever current feasible solution has been found, than to trigger an error message or even a program abort.

When ILOG CPLEX uses node-file storage, the sequence of nodes processed may differ from the sequence in which nodes are processed without node-file storage. Nodes in node-file storage are not accessible to user-written callback routines.

The best approach to reduce memory use is to modify the solution process. Here are some ways to do so:

• Switch the node selection strategy to best estimate, or more drastically to depth-first. Depth-first search rarely generates a long, memory-consuming list of unexplored nodes since ILOG CPLEX dives deeply into the tree instead of jumping around. A narrowly focused search, like depth-first, also often results in faster processing times for individual nodes. However, overall solution time is generally much worse than with best-bound node selection because each branch is searched exhaustively to its deepest level before it is fathomed in favor of better branches.
• Another memory-conserving strategy is to use strong branching (VarSel parameter value 3) for variable selection. Strong branching requires substantial computational effort at each node to determine the best branching variable. As a result, it generates fewer nodes and thus makes less overall demand on memory. Often, strong branching is faster as well.