Running out of Memory

ILOG CPLEX 11.0 User's Manual > Discrete Optimization > Solving Mixed Integer Programming Problems (MIP) > Troubleshooting MIP Performance Problems > Running out of Memory

Running out of Memory

INDEX

PREVIOUS NEXT

A very common difficulty with MIPs is running out of memory. This problem almost always occurs when the branch & cut tree becomes so large that insufficient memory remains to solve a continuous LP, QP, or QCP subproblem. (In the rare case that the dimensions of a very large model are themselves the main contributor to memory consumption, you can try adjusting the memory emphasis parameter, as described in Lack of Memory.) 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 at 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. Since generation of cutting planes is not a frequent cause of memory consumption, apply these recommendations only as a last resort, after trying to resolve the problem with less drastic measures.

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.

Reset the Tree Memory Parameter

To avoid a failure due to running out of memory, set 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. That topic explains how to indicate to CPLEX that it should use disk for working storage.

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. At default settings, the limit is infinity (1e+75), but you can set it to a lower value (in megabytes).

Use Node Files for Storage

As noted in Using Node Files, ILOG CPLEX offers a node-file storage-feature to store some parts of the branch & cut tree in files as it progresses through its search. This feature allows ILOG CPLEX to explore more nodes within a smaller amount of computer memory. It also includes several options to reduce the use of physical memory. Importantly, it entails only a very small increase in runtime. In terms of performance, node-file storage offers a much better option than relying on generic swap space managed by your operating system.

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.

Note

Try node files whenever the MIP optimizer terminates with the condition "out of memory" and the node count is greater than zero. The message in such a situation looks like the following sample output.

Clique cuts applied:  30
CPLEX Error  1001: Out of memory.

Consider using CPLEX node files to reduce memory usage.

MIP-Error termination, integer feasible:  Objective =    5.6297000000e+04
Current MIP best bound =    5.5731783224e+04 (gap = 565.217, 1.00%)
Solution time =  220.75 sec.  Iterations = 16707  Nodes = 101 (58)

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

WorkMem in Concert Technology or CPX_PARAM_WORKMEM in the Callable Library
NodeFileInd in Concert Technology or CPX_PARAM_NODEFILEIND in the Callable Library
TreLim in Concert Technology or CPX_PARAM_TRELIM in the Callable Library
WorkDir in Concert Technology or CPX_PARAM_WORKDIR in the Callable Library

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. The default value of the WorkMem parameter is 128 megabytes. Setting it to higher values, even on a machine with very large memory, can be expected to result in only marginally improved efficiency. However, it is advisable to reduce this setting to approximately half the available memory of your machine if your machine has less than 256 megabytes of RAM to avoid defeating the purpose of node files, a situation that would occur if your application inadvertently triggers the swap space of your operating system.

When tree storage size exceeds the limit defined by WorkMem, and if the tree-memory limit has not been exceeded, then what happens next is decided by the setting of the node file indicator (NodeFileInd in Concert Technology or CPX_PARAM_NODEFILEIND in the Callable Library). If that parameter is set to zero, then optimization proceeds with the tree stored in memory until ILOG CPLEX reaches the tree memory limit (TreLim in Concert Technology or CPX_PARAM_TRELIM in the Callable Library). If the node file indicator 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). Table 14.14 summarizes these different options.

Table 14.14 Settings for the Node File Storage Parameter

Setting	Meaning	Comments
`0`	no node files	optimization continues
`1`	node file in memory and compressed	optimization continues (default)
`2`	node file on disk	files created in temporary directory
`3`	node file on disk and compressed	files created in temporary directory

Among the memory conservation tactics employed by ILOG CPLEX when the memory emphasis parameter has been set, the maximum setting for the node file indicator is automatically chosen, so that node-file storage will go to disk. You may still wish to adjust the working memory or tree limit parameters to fit the capabilities of your computer.

In cases where node files are written to disk, ILOG CPLEX will create a temporary subdirectory under the directory specified by the working directory parameter (WorkDir in Concert Technology or CPX_PARAM_WORKDIR in the Callable Library). 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 Concert Technology,

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.

Node files could grow very large. Use the parameter TreLim (CPX_PARAM_TRELIM) to limit the size of the tree so that it does not exceed available disk space, when you choose NodeFileInd (CPX_PARAM_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.

Change Algorithms

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, as explained in Table 14.6. 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 for variable selection; that is, set the parameter VarSel (CPX_PARAM_VARSEL) to the value 3. Strong branching requires substantial computational effort at each node to decide 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.

PREVIOUS NEXT