Originally posted by: davidfk

Hi all,

I have tried CPLEX' automatic Benders decomposition for a set of problems (CPLEX v12.10). In most cases, Benders runs out of memory very quickly. I can see that memory consumption grows heavily and quickly. So quickly, that it appears to be a bug. This does not occur with standard B&B. I tried but I cannot attach the model (10MB), unfortunately. I ran it from the command line with a time limit of 900s and benders strategy 3. The log is attached below.

A second question: Is it possible to obtain the decomposition that CPLEX' automatic Benders applies? I.e. is it possible to find out what CPLEX moves into (how many?) subproblems?

CPLEX> set timelimit 900
New value for time limit in seconds: 900
CPLEX> set benders strat 3
New value for choice of benders decomposition to use: 3
CPLEX> opt
Version identifier: 12.10.0.0 | 2019-11-26 | 843d4de2ae
CPXPARAM_Benders_Strategy                        3
CPXPARAM_TimeLimit                               900
Tried aggregator 2 times.
MIP Presolve eliminated 2230 rows and 99 columns.
MIP Presolve added 4342 rows and 0 columns.
MIP Presolve modified 2785 coefficients.
Aggregator did 9541 substitutions.
Reduced MIP has 16485 rows, 169118 columns, and 415839 nonzeros.
Reduced MIP has 159939 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.45 sec. (284.10 ticks)
Found incumbent of value 6.4529012e+07 after 1.80 sec. (1246.29 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 4342 rows and 0 columns.
MIP Presolve added 4342 rows and 0 columns.
Reduced MIP has 16485 rows, 169118 columns, and 415839 nonzeros.
Reduced MIP has 159939 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.23 sec. (154.23 ticks)
Warning: MIP starts not constructed because of out-of-memory status.

Root node processing (before b&c):
  Real time             =    8.67 sec. (3922.53 ticks)
Parallel b&c, 8 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    8.67 sec. (3922.53 ticks)
CPLEX Error  1001: Out of memory.

Error termination, CPLEX Error  1001.
Solution time =    8.70 sec.
Deterministic time = 3929.39 ticks  (451.45 ticks/sec)

Originally posted by: davidfk

As no one has been able to answer so far: The model that causes the issues (see above) can actually be decomposed into a very large number of subproblems, and one possibility for CPLEX to run out of memory is that CPLEX actually does decompose it into a large number of subproblems. At least it is one possible explanation. If I use annotations and move all continuous variables into a single subproblem, no memory issues arise.

Remaining question: I run CPLEX from the command line. When I use annotations, i.e. I set benders strategy to '1', the command "write benders.ann" will create a valid annotations file (identical to the one I read in). If I use automatic benders, i.e. I set benders strategy to '3', the command "write benders.ann" generates an empty annotations file. I would expect the command to write the annotations corresponding to the decomposition CPLEX automatic benders actually uses. How can I get information about how CPLEX decomposes the problem?

In the interactive, writing the automatic decomposition is not officially supported. But it can be done. Please drop a message to daniel(dot)junglas(at)de(dot)ibm(dot)com if you want to know how.

Alternatively, you can use this small Python script to create an annotation file with the CPLEX default decomposition:

import sys
import cplex

with cplex.Cplex(sys.argv[1]) as cpx:
    cpx.write_benders_annotation(sys.argv[2])

The script takes two command line arguments: first is the model, second is the file to create.

If you could share your model with the email address above then we could also investigate your hypothesis that the issue is the large number of subproblems.

Originally posted by: davidfk

Hi Daniel, thanks for the script.

Using the python script, I can generate the annotation file for the model and it turns out that CPLEX decomposes it into 206 different subproblems.

I have just sent you the model by email; I'd be happy if you can share some insights on why memory consumption is so large using the automatic decomposition.

Thanks, David