The most 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 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 to instruct CPLEX to begin using disk for storage of nodes before it consumes all available memory.

To set the working memory parameter:

• In the Interactive Optimizer, use the command set workmem n using a value n that is smaller than the total available memory in megabytes.

• For the Component Libraries, set the parameter IloCplex::WorkMem or CPX_PARAM_WORKMEM.

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

To set the tree limit parameter:

• In the Interactive Optimizer, use the command set mip limits treememory .

• For the Component Libraries, set the parameter IloCplex::TreLim, or CPX_PARAM_TRELIM.

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, 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, so it has less overall impact on system resources. 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 summarized as follows, and described in detail in the next paragraphs:

ILOG CPLEX invokes node file storage when it reaches the working memory limit. By default, the limit is 128 (megabytes).

To set a limit on the size of the branch & cut tree held in memory:

• In the Interactive Optimizer, use the command set workmem n, substituting a value for n.

• When using the Component Libraries, set the parameter IloCplex::WorkMem or CPX_PARAM_WORKMEM.

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 32 megabytes. Higher values result in only marginally improved efficiency.

When tree storage size exceeds the limit defined by IloCplex::WorkMem / CPX_PARAM_WORKMEM, what happens next is determined by the setting of IloCplex::NodeFileInd / CPX_PARAM_NODEFILEIND. If the latter parameter is set to zero, then optimization proceeds with the tree stored in memory until CPLEX reaches the tree memory limit (IloCplex::TreLim / CPX_PARAM_TRELIM). If the parameter is set to 1 (the default), then a very 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 IloCplex::NodeFileInd /CPX_PARAM_NODEFILEIND, CPLEX will stop the optimization when the total memory used to store the tree exceeds the tree memory limit.

In cases where node files are written to disk, CPLEX will create a temporary subdirectory under the directory specified by the IloCplex::WorkDir / CPX_PARAM_WORKDIR parameter. The directory named by this parameter must exist before 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 95 or NT, 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()

• 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 may grow very large. You can limit their size by setting the file limit parameter:

• In the Interactive Optimizer, use the command set workmem with any positive value.

• In the Concert Technology Library, use the method IloCplex::setParam(Workmem, n), and in the Callable Library, use the routine CPXsetdblparam(env, CPX_PARAM_WORKMEM, n) where n is any positive value. The default value is 128 (megabytes).

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 to a higher backtracking parameter.

• 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 efficiency is sometimes 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. 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.

• On some problems, the automatic generation of cuts results in excessive memory use with little benefit in speed. In such cases, we recommend that you turn off cut generation.

  • In the Interactive Optimizer, use the commands set mip cuts all -1 to turn off all cuts. Use set mip cuts class -1 (where class may be cliques, covers etc.) to turn off individual classes of cuts.

  • In the Component Libraries, cuts may be turned off only by class; use the method IloCplex::setParam() or the routine CPXsetintparam() with the appropriate parameter to indicate which class of cuts to turn off (Cliques / CPX_PARAM_CLIQUES, Covers / CPX_PARAM_COVERS, etc) and the value -1 each time.

See Table 5.4 for a complete list of available cuts.