Originally posted by: SystemAdmin

[danielamaral said:]

Info:
- I'm running CPLEX11.
- The parameter reference states: "When the problem is a minimization problem, CPLEX cuts off any nodes that have an objective value at or above the upper cutoff value".

I'm developing an algorithm that calls mipopt multiple times, each time on a slightly different model (the differences are just the addition of 1 new constraint). CPLEX seems to be re-using the results from previous calls to solve each model. This, by itself, is fine, but one thing annoys me: I'm setting the CUTUP parameter to different values at each call, and sometimes CPLEX will return an optimal value that is the same as the upper bound I set! For instance, I will set up CUTUP with 44631 and run mipopt, the optimal solution will be 44631.

Questions:
- Why is this happening?
- Is there a way to really enforce the CUTUP parameter?
- How can I tell CPLEX not to reuse information from previous mipopt calls?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[notdarkyet said:]

Have a look at the parameter description of
CPX_PARAM_ADVIND
(which in the interactive cplex is "set adv value", where the adnmissible value depends on the cplex version you are using. It was n with 9.1 and is 0 with 11.2 in order not to use advanced starting information.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[danielamaral said:]

[quote author=notdarkyet link=topic=1176.msg3372#msg3372 date=1243891501]
Have a look at the parameter description of
CPX_PARAM_ADVIND
(which in the interactive cplex is "set adv value", where the adnmissible value depends on the cplex version you are using. It was n with 9.1 and is 0 with 11.2 in order not to use advanced starting information.


Thank you for the suggestion, notdarkyet, but I'm still having the exact same problem. This is the log of a run where I had the following settings:
- CUTUP parameter set to 44835.
- CPX_PARAM_ADVIND set to 0 (so that the previous calls to mipopt wouldn't interfere).

CPLEX still finds the "optimal" solution to be 44835, ignoring the CUTUP value!


Tried aggregator 1 time.
Presolve time =    0.08 sec.
Clique table members: 4430.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 2 threads.
Root relaxation solution time =    0.16 sec.

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

      0    0    44774.1220    15                  44774.1220      703
      0    0    44776.9047    26                  Covers: 6      722
      0    0    44778.5824    30                  Covers: 4      747
      0    0    44780.9802    29                  Covers: 7      765
      0    0    44784.0652    37                  Covers: 4      792
      0    0    44786.5963    32                  Covers: 6      818
      0    0    44790.3257    49                  Covers: 5      868
      0    0    44790.9914    35                  Covers: 4      910
      0    0    44792.4186    37                  Covers: 3      930
      0    0    44793.3100    44                  Covers: 3      946
      0    2    44793.3100    44                  44793.3100      946
    100    84    44806.1793    26                  44795.0843    2481
    200  146        cutoff                        44796.4304    5093
    300  228        cutoff                        44796.4304    7043
    400  292    44814.0454    18                  44801.3169    9694
    500  355        cutoff                        44801.3169    11074
    600  390    44806.6092    52                  44802.0621    15506
    700  412    44826.0226    26                  44802.0621    17807
    800  406    44822.7715    33                  44802.0621    19792
    900  398    44831.8016    14                  44802.0621    21739
  1000  380    44811.5096    45                  44802.0621    25009
Elapsed time =  14.60 sec. (tree size =  3.10 MB, solutions = 0)
  1100  423    44820.8269    23                  44802.0621    27338
  1200  489    44831.5106    25                  44804.3426    30524
  1300  563    44828.1932    26                  44804.3426    33724
  1400  622    44821.5201    38                  44805.3827    35820
  1500  668    44830.7893    29                  44807.3660    40781
  1600  737    44823.3472    47                  44808.2717    44602
  1700  813        cutoff                        44808.3752    47209
  1800  907    44822.2548    34                  44808.6900    49623
  1900  1007    44828.6691    20                  44808.6900    50778
  2000  1095    44826.8673    48                  44808.6900    52867
Elapsed time =  20.09 sec. (tree size =  9.48 MB, solutions = 0)
  2100  1193    44825.1544    39                  44808.6900    54268
  2200  1275    44826.2349    27                  44808.6900    56477
  2300  1330        cutoff                        44808.6900    58522
  2400  1298        cutoff                        44814.3064    64633
  2500  1280        cutoff                        44816.1276    70066
  2600  1274    44818.7833    49                  44816.6320    74734
  2700  1265    44825.2856    39                  44819.0049    79919
  2800  1240    44829.2585    36                  44819.7547    85035
  2900  1229    44825.2417    49                  44821.1321    89469
  3000  1212    44830.0840    16                  44821.7672    92996
Elapsed time =  25.40 sec. (tree size = 11.21 MB, solutions = 0)
  3100  1262    44832.6025    55                  44821.9806    95390
  3200  1225        cutoff                        44822.7322    98578
  3300  1133        cutoff                        44823.3823  101749
  3400  1048        cutoff                        44823.9447  104623
  3500  956        cutoff                        44824.5410  106301
  3600  869    infeasible                        44824.8581  107826
  3700  778        cutoff                        44825.4045  110006
  3800  680    infeasible                        44826.1786  111890
  3900  592    infeasible                        44826.7861  114417
  4000  506        cutoff                        44827.4290  116289
Elapsed time =  29.09 sec. (tree size =  4.91 MB, solutions = 0)
  4100  455    infeasible                        44827.7247  119053
  4200  379    infeasible                        44828.4340  120298
  4300  312    44830.9603    23                  44829.1759  123281
*  4315  316      integral    0    44835.0000    44829.2054  123716    0.01%
  4400  233        cutoff          44835.0000    44830.0199  126064    0.01%
  4500  148        cutoff          44835.0000    44831.0503  128417    0.01%
  4600    54    infeasible          44835.0000    44832.4550  129762    0.01%

Cover cuts applied:  430
Gomory fractional cuts applied:  3

Root node processing (before b&c):
  Real time            =    1.01
Parallel b&c, 2 threads:
  Real time            =  30.36
  Sync time (average)  =    2.14
  Wait time (average)  =    3.84
                          -------
Total (root+branch&cut) =  31.37 sec.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

Keep in mind that CutUp applies to the objective value of the LP relaxation.  There are two possible explanations (maybe more, but two that occur to me).  The first is that CPLEX finds an integer-feasible solution with objective 44835 using a node heuristic at a node whose LP bound is below 44835.  I don't think that's happening here -- I think the objective column is left blank, rather than saying "integral", when a heuristic finds an incumbent -- but you could check it by turning off node heuristics.  The second is simply that CPLEX detects an integer-feasible solution to the LP before it applies the bound cutoff.

You could try setting CutUp to something a bit smaller (44834.99, say), although I'm pretty sure that would not stop a node heuristic from reproducing the 44835 solution, and I wouldn't bet on it stopping CPLEX from accepting an integer-feasible LP solution with value 44835 if in fact integer feasibility is tested before CutUp is applied.

Is this really a problem?  I gather you want the rerun (with CutUp = 44835) to report the problem as infeasible?

/Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[jgregory said:]

The cutoff is behaving as designed.  Indeed, the documentation before CPLEX 11.2 was a little inaccurate on this detail - for that, I offer our apologies.  Here is the updated description in the CPLEX 11.2 Parameters Reference Manual (a change noted in the Release Notes for that version):

"Sets the upper cutoff tolerance. When the problem is a minimization problem, CPLEX cuts off or discards any solutions that are greater than the specified upper cutoff value. If the model has no solution with an objective value less than or equal to the cutoff value, CPLEX declares the model infeasible. In other words, setting an upper cutoff value c for a minimization problem is similar to adding this constraint to the objective function of the model: obj <= c."<br />
Paul's suggestion, to set your CutUp value enough smaller that there can be no ambiguity for your application's purposes, is sound. 
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[danielamaral said:]

Thank you Paul and John for the explanation. I had notice the discrepancy in the parameter description on CPLEX 11.2, but I thought the change had happened only in that version. Using the upper bound minus 1 (and setting CPX_PARAM_ADVIND to zero) solved my problem. Another thing I tried was adding a constraint to enforce the cutup, but I assume that makes the model a little more complicated to solve than just setting CUTUP.

Thanks again!
#CPLEXOptimizers
#DecisionOptimization