Originally posted by: ziczyq

Hi ALL,

I am using Benders' Decomposition in CPLEX 12.8 callable library. My problem has binary variable and continuous variable in the master problem, and only continuous variable in the subproblems. I annotated the problem by myself. But it seems that CPLEX always ignore my annotation, putting all integer variables in the master problem and all continuous variables in one subproblem. Am I wrong? Or the built in Benders' Decomposition cannot solve my problem at all?

Thanks!

What happens if you set the Benders strategy parameter to USER (1) (i.e., to force the use of user supplied annotations)? This should either tell you if something is wrong with your annotations or work as expected.

Originally posted by: ziczyq

Thanks for reply. I did set the Benders strategy parameter to 1 and apply my annotation. The weird thing is CPLEX did not report any error and just ignored my annotations. It annotated the model automatically.  If I delete the continuous variables in the master problem, leaving only binary variables,  and delete the annotation of these variables correspondingly, the Benders strategy applies my annotation. I do not know if it is because CPLEX cannot solve problems with mixed integer variables in master problem. 

How exactly do you detect that CPLEX ignores your decomposition?

Can you call CPXwriteparam(env, "params.prm") right before calling the solve function and post the created params.prm file here?

If possible, can you share the model and annotation file as well?

Originally posted by: ziczyq

Thanks for reply!

Please check all three attachments for the formulation of the problem, the annotation file, and the parameter. Following is the output of the results.

# of variables in LP =1071
# of linear constraints in LP =2475
CPXPARAM_TimeLimit                               10800
Found incumbent of value 65901.789390 after 0.00 sec. (0.22 ticks)
Tried aggregator 2 times.
MIP Presolve eliminated 71 rows and 57 columns.
MIP Presolve modified 1438 coefficients.
Aggregator did 30 substitutions.
Reduced MIP has 2374 rows, 984 columns, and 7102 nonzeros.
Reduced MIP has 186 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (4.32 ticks)
Probing time = 0.00 sec. (4.46 ticks)
Tried aggregator 1 time.
Reduced MIP has 2374 rows, 984 columns, and 7102 nonzeros.
Reduced MIP has 186 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.01 sec. (3.85 ticks)
Probing time = 0.00 sec. (4.45 ticks)
Clique table members: 1.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 16 threads.
Root relaxation solution time = 0.03 sec. (14.78 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

*     0+    0                        65901.7894       29.1765            99.96%
*     0+    0                          679.7847       29.1765            95.71%
      0     0       52.1656   168      679.7847       52.1656      532   92.33%
*     0+    0                          655.5982       52.1656            92.04%
      0     0       67.5243    12      655.5982    MIRcuts: 1      574   89.70%
      0     0      101.7263     4      655.5982      Cuts: 38     3030   84.48%
      0     0      111.2561     4      655.5982       Cuts: 6     3496   83.03%
      0     0      111.2834     4      655.5982      Cuts: 11     3659   83.03%
      0     0      111.3997     4      655.5982      Cuts: 10     3987   83.01%
      0     0      128.7455     5      655.5982   Flowcuts: 4     4004   80.36%
      0     0      129.2962     5      655.5982      Cuts: 14     4010   80.28%
      0     0      129.2983     5      655.5982   Flowcuts: 3     4015   80.28%
      0     0      129.3039     5      655.5982       Cuts: 5     4018   80.28%
      0     2      129.3039     5      655.5982      129.3039     4018   80.28%
Elapsed time = 2.08 sec. (930.00 ticks, tree = 0.01 MB, solutions = 2)
      2     3      160.4308   135      655.5982      150.7682     4718   77.00%
*    19     4      integral     0      205.6418      160.4308     7552   21.99%
     20    11      576.6306   141      205.6418      160.4308     5853   21.99%

Implied bound cuts applied:  12
Flow cuts applied:  29
Mixed integer rounding cuts applied:  16

Root node processing (before b&c):
  Real time             =    1.94 sec. (923.99 ticks)
Parallel b&c, 16 threads:
  Real time             =    2.86 sec. (599.43 ticks)
  Sync time (average)   =    2.42 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    4.80 sec. (1523.43 ticks)
Risk-Averse Extensive Formulation optimization time = 4.811 seconds
Risk-Averse Extensive Formulation objective value = 205.642
number of nodes = 21
solution status = 101

In the annotation file, eta should be in the master problem, which is in the subproblem now. Also, the first index+1 after each variable indicates the number of subproblem it belongs to (i.e, u.0.14 means it belongs to the first subproblem. while u.1.14 means it belongs to the second subproblem). CPLEX did not report any error. But my annotation is ignored. I do not know where is wrong.

The partition.txt file is the input of partition and colidx in function CPXsetlongannotations(), following the format (indices:value). eta is #186 variable in this partition file, and the value is 0. However, in the annotation file, it is 1. I do not know why this happens.

Some things are wrong here:

1. In the log you posted, the only non-default parameter is the time limit, while in the .prm file also the benders strategy parameter is set. So the two do not correspond.

2. The Benders partition is invalid:

CPLEX> read Benders.lp
Problem 'Benders.lp' read.
Read time = 0.01 sec. (0.22 ticks)
CPLEX> read benders.ann
ANN file 'benders.ann' read.
CPLEX> read benders.prm
Parameter file 'benders.prm' read.
CPLEX> opt
CPXPARAM_TimeLimit                               10800
CPXPARAM_Benders_Strategy                        1
CPLEX Error  2002: Invalid Benders decomposition.

Error termination, CPLEX Error  2002.
Solution time =    0.00 sec.
Deterministic time = 0.00 ticks  (0.39 ticks/sec)

Maybe this is because of the eta variable?

3. Indeed there is a mismatch between partition.txt and benders.ann. But that mismatch almost certainly comes from your code, not CPLEX. It looks like an off-by-one error. Can you double-check or post here the code that converts the information in partition.txt and then calls CPXsetlongannotation()?

EDIT: Even when I edit benders.ann so that variable 'eta' goes into master, CPLEX still rejects the partition as invalid. So something is wrong either with the partition itself or with the code that handles partition.txt. Note that the fact that CPLEX errors out with "invalid partition" proves that CPLEX does not ignore your partition :-)

Originally posted by: ziczyq

Thanks Daniel!

1. I just double check, the log file is wrong, this is the correct log file:

# of variables in Benders Decompostion =1071
# of linear constraints in Benders Decompostion =2475
CPXPARAM_TimeLimit                               10800
CPXPARAM_Benders_Strategy                        1
Found incumbent of value 65901.789390 after 0.00 sec. (0.22 ticks)
Tried aggregator 2 times.
MIP Presolve eliminated 71 rows and 57 columns.
MIP Presolve modified 1438 coefficients.
Aggregator did 30 substitutions.
Reduced MIP has 2374 rows, 984 columns, and 7102 nonzeros.
Reduced MIP has 186 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.03 sec. (4.32 ticks)
Probing time = 0.00 sec. (4.46 ticks)
Tried aggregator 1 time.
Reduced MIP has 2374 rows, 984 columns, and 7102 nonzeros.
Reduced MIP has 186 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.03 sec. (3.85 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0       29.1765                        Benders: 1        0
      0     0       29.1765                        Benders: 1        1
      0     0       29.1765                        Benders: 1        2
      0     0       52.1656                        Benders: 1        4
      0     0       52.1656                        Benders: 1        5
Tried aggregator 1 time.
MIP Presolve modified 122 coefficients.
Reduced MIP has 6 rows, 187 columns, and 719 nonzeros.
Reduced MIP has 186 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.27 ticks)
Probing time = 0.00 sec. (2.92 ticks)
Tried aggregator 1 time.
Reduced MIP has 6 rows, 187 columns, and 719 nonzeros.
Reduced MIP has 186 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (0.26 ticks)
Probing time = 0.01 sec. (2.92 ticks)
Clique table members: 1.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 16 threads.
Root relaxation solution time = 0.00 sec. (0.09 ticks)
*     0+    0                          655.5982       52.1656            92.04%
      0     0       52.1656     4      655.5982       52.1656        9   92.04%
      0     0       53.9361     2      655.5982       Cuts: 4       12   91.77%
      0     0      160.4308     3      655.5982       Cuts: 6       18   75.53%
      0     0      160.4308     3      655.5982       Cuts: 4       20   75.53%
      0     0      162.1314     4      655.5982    MIRcuts: 2       25   75.27%
*     0+    0                          205.6418      162.1314            21.16%

Repeating presolve.
Tried aggregator 1 time.
MIP Presolve eliminated 4 rows and 148 columns.
MIP Presolve modified 214 coefficients.
Reduced MIP has 2 rows, 39 columns, and 75 nonzeros.
Reduced MIP has 38 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (0.61 ticks)
Probing time = 0.00 sec. (0.08 ticks)
Tried aggregator 1 time.
Reduced MIP has 2 rows, 39 columns, and 75 nonzeros.
Reduced MIP has 38 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.05 ticks)
Represolve time = 0.03 sec. (1.01 ticks)
Probing time = 0.00 sec. (0.08 ticks)
Clique table members: 1.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 16 threads.
Root relaxation solution time = 0.00 sec. (0.03 ticks)
*     0+    0                          205.6418      162.1314            21.16%
      0     0        cutoff            205.6418                     32    0.00%

Benders cuts applied:  2
Flow cuts applied:  1
Mixed integer rounding cuts applied:  2

Root node processing (before b&c):
  Real time             =    2.36 sec. (1537.09 ticks)
Parallel b&c, 16 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) =    2.36 sec. (1537.09 ticks)
Benders optimization time = 2.38 seconds
Benders objval = 205.642

2. One of my guess is the eta variable. Since eta is a continuous variable, I doubt that if CPLEX can solve the problem with mixed-integer variable in the master problem. I deleted "eta" in the model and the annotation file, and Benders did work, following my annotation and decomposing the problem into two subproblems. 

3. The partition.txt file is the annotation I want. However, benders.ann is the annotation file CPLEX generated automatically. Yes, there is a mismatch. And if you take a look at the partition.txt, you will find #305 variable is with value 2. I want it in the second subproblem. While in the benders.ann, which is the automatically generated file,  it is 1.

Attachment are the input array in the function:

status = CPXsetlongannotations(a->BPenv, BP, anno_idx1, CPX_ANNOTATIONOBJ_COL, cur_numcols, colidx, partition);

cur_numcols=1071

and anno_idx1 is obtain from:

status = CPXgetlongannotationindex(a->BPenv, BP, CPX_BENDERS_ANNOTATION, &anno_idx1);

I really appreciate your help. I have been stuck here for few weeks.

How exactly do you create the .ann file? Do you use CPXwriteannotations() or CPXwritebendersannotation()? Note that the latter will not write your user-defined annotation, as stated clearly in the reference documentation.

It is hard to relate your array files to the model in LP format since in the LP file the variables have different indices (for example eta has index 0). Right after calling

CPXsetlongannotations(a->BPenv, BP, anno_idx1, CPX_ANNOTATIONOBJ_COL, cur_numcols, colidx, partition);

could you please add the following code

CPXwriteprob(a->BPenv, BP, "Benders.sav.gz", NULL);

CPXwriteannotations(a->BPenv, BP, "Benders.ann");

dump cur_numcols, colidx, partition as before

and then attach the created output files (Benders.sav.gz, Benders.ann, colidx,txt, partition.txt) here?

Originally posted by: ziczyq

Hi Daniel, 

Also, cur_numcols=1071. The benders.ann file I attached before is from CPXwritebendersannotation(). The attached Benders.ann is from CPXwriteannotations(). Do you mean the index in the annotation file?

Thanks again. Please let me know if you need anything from me. I am really confused by what is happening here.

If I do this in the interactive

CPLEX> read Benders.sav.gz
CPLEX> read Benders.ann
CPLEX> set benders strat 1
CPLEX> opt

Then I get a log like this:

Found incumbent of value 65901.789390 after 0.03 sec. (0.16 ticks)
Tried aggregator 2 times.
MIP Presolve eliminated 71 rows and 57 columns.
MIP Presolve modified 1438 coefficients.
Aggregator did 30 substitutions.
Reduced MIP has 2374 rows, 984 columns, and 7102 nonzeros.
Reduced MIP has 186 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.01 sec. (2.42 ticks)
Tried aggregator 1 time.
Reduced MIP has 2374 rows, 984 columns, and 7102 nonzeros.
Reduced MIP has 186 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (1.57 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0       29.1765                        Benders: 2        0         
      0     0       29.1765                        Benders: 1        2         
      0     0       29.1765                        Benders: 1        4         
      0     0       37.3869                        Benders: 1        6         
      0     0       52.1656                        Benders: 1        7
...

Benders cuts applied:  2
Mixed integer rounding cuts applied:  4

Root node processing (before b&c):
  Real time             =    1.01 sec. (1076.03 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) =    1.01 sec. (1076.03 ticks)

Solution pool: 4 solutions saved.

MIP - Integer optimal solution:  Objective =  2.0564179718e+02
Solution time =    1.01 sec.  Iterations = 41  Nodes = 0 (1)
Deterministic time = 1076.04 ticks  (1064.95 ticks/sec)

So as you can see, CPLEX is separating Benders cuts. Since the benders strategy is explicitly set to 1 this means your partitioning was accepted/applied and was valid. Note that this log output is roughly the same as the correct log output you posted above.

So again, what makes you conclude that CPLEX did not apply your partitioning? From your (corrected) log and my log it looks CPLEX does apply your partitioning in both cases.