Originally posted by: Falcon_G

Hi everybody

I have an IP (Min) and all my coefficients are integer.

My bestObjValue is often fractional. Therefore, I should be able to say objExpr>=ceil (getbestObjValue).

in the normal situation, my lower  bound increases very slowly and x to x+1 takes hundreds of nodes. Therefore, rounding up my bestLB is already a non-negligible gain.

I did not find anywhere in the documentation where I can impose a new best lower bound.

I wonder if anyone has done this before?

thank you in advance.

best 

Originally posted by: EdKlotz

CPLEX can usually figure out these type of rounding on the best node objective value by itself.   So, you should not need to do this type of operations yourself. The fact that CPLEX doesn't do that in this cases raises some questions about the model characteristics.   Specifically,  you indicated that all coefficients are integer.    Do you mean all matrix coefficients, or is that true for the right hand side values as well.   And are all the variables in the model restricted to be integer, or are some of them continuous?

Originally posted by: Falcon_G

thanks for your reply.

yes all are integer : the variables and all the coefficients whether in objective or in constraints (matrix and rhs).

I do not really see that such rounding appears even after a few hundreds of nodes.

best

Originally posted by: EdKlotz

OK, can you post the CPLEX node log of the problematic run?

Originally posted by: Falcon_G

     47    39    15245.8571    23                  13570.5781      721                r(12)(14) D     47     45     15
     48    39    15411.4286    14                  13570.5781      737                  r(1)(5) D     48     46     16
     49    40    15487.4286    14                  13570.5781      750                  t(5)(3) D     49     48     17
    238   163    15268.2500     8                  14032.1944     3672                  r(1)(5) U    238    237     14
Elapsed time = 53.91 sec. (1093.15 ticks, tree = 0.05 MB, solutions = 0)
    528   343    infeasible                        14397.4286     8126                r(21)(24) D    528    527     10
    529   342    infeasible                        14397.4286     8136                r(21)(24) U    529    527     10
    530   343    15248.8889    19                  14400.5000     8145                  z(5)(5) U    530    409     12
    531   344    15358.7692    16                  14400.5000     8152                r(12)(14) D    531    530     13
    532   345    15447.3523    35                  14400.5000     8172                 r(6)(11) D    532    531     14
    533   346    17309.5000     4                  14400.5000     8184                 r(6)(11) U    533    531     14
    534   347    17901.0000     4                  14400.5000     8207                r(21)(24) D    534    533     15
    535   346    infeasible                        14400.5000     8229                r(13)(15) U    535    534     16
    536   345    infeasible                        14400.5000     8235                r(13)(15) D    536    534     16
    537   346    14868.6000    32                  14401.1447     8273                t(14)(17) U    537     12      9
Elapsed time = 73.61 sec. (2075.13 ticks, tree = 0.11 MB, solutions = 0)

As far as I can see, you have fractional objective values for feasible solutions like 14397.4286, 14400.5000 and 14401.1447. So it looks like your objective function can be fractional. How do you reason that you can round up the dual bound?

Originally posted by: Falcon_G

Thanks Daniel

Actually the column for feasible solution is missing as no feasible solution is found yet. the column you see corresponds to the best LB. isn't it?

Ah, yes, sorry, I misread the log.

But the output is still expected. CPLEX can not just round up the dual bound. But what it can do is the following: If there is a feasible solution with objective value x and it can be shown that every objective value must be integral, then it can prune any node with dual bound larger that x-1+eps. This should be essentially the same.

Originally posted by: Falcon_G

so even if I add a cut like:

objExpr>=ceil (getbestObjValue).

it will ignore it? 

Originally posted by: EdKlotz

CPLEX will not ignore it.   But, as I said in my previous post today, adding such a cut can adversely affect performance.    Besides the degeneracy and pseudo cost issues I previously mentioned, the use of the cut callback will disable dynamic search; that too could slow down performance.   But, better to give it a try than to speculate.    So, add the cut and see if it helps.   

Originally posted by: EdKlotz

You can address the integrality of the objective in a MILP with all integer variables either by adjusting the lower bound as you have described, or by adjusting the cutoff value associated with the best integer solution found so far.    CPLEX does the latter, rather than the former.    So, you can indeed see fractional objective values in the best node (i.e. lower bound) column of the node log, like you reported.   But, with an all integer objective value, you won't see CPLEX explore node LPs with relaxation objective values within 1.0 of the best integer solution objective.    Adding a constraint like you describe actually has some disadvantages in terms of introducing degeneracy into the node LPs and distorting the branching information obtained in CPLEX's pseudo cost calculations.   I believe that is why CPLEX refrains from tightening the model in the way you describe.

That said, I did some tests with the model stein45.mps, available publicly from the MIPLIB 3.0 web site at http://miplib.zib.de/miplib3/miplib.html.   While CPLEX behaved as I described above when running to optimality, I was somewhat surprised to see that it did not take advantage of the tightening you describe when running with a non default MIP gap.    For example, since the minimal objective is 30, with a MIP gap setting of .04 (i.e. 4%)  I expected CPLEX to use the integrality  of the objective to stop here:

 38804  7464        cutoff             30.0000       28.0000   281037    6.67%
  38805  7463        cutoff             30.0000       28.0000   281042    6.67%
 38806  7464       29.0000    22       30.0000       28.0135   281061    6.62%
  38807  7463        cutoff             30.0000       28.0135   281064    6.62%
  38808  7462        cutoff             30.0000       28.0135   281069    6.62%

After all, at this point, we know that the best possible integer objective is 29.0, so we are within the requested 4% gap.

Contrary to my expectations, CPLEX continued until the fractional best node value truly guaranteed a 4% gap:

 48363  3157        cutoff             30.0000       28.7778   335335    4.07%
 48364  3156        cutoff             30.0000       28.8000   335338    4.00%

I will take a closer look at this and reply again when I have an explanation of this.

Meanwhile, getting back to your original question, CPLEX does not have any API calls to adjust the lower bound in the way you describe.   However, you can always add such a constraint using CPLEX's cut callback functionality.   You would query the best node value within the callback framework, then use the rounded value in your cut.  But, as described above, you may find that this actually hurts performance rather than helps.

Originally posted by: Falcon_G

Thank you for your comments. much appreciated.

best

Originally posted by: EdKlotz

One followup to my previous post.   Regarding CPLEX's lack of exploitation of the integrality in the objective as illustrated on stein45, the primary issue there is that CPLEX has API functions to query the best node and relative MIP gap, and doing this early termination would have created all sorts of confusion and inconsistency regarding those routines.    However, Daniel reminded me  that you can use CPLEX's informational callback to query CPLEX's best node value.  You can then do the integer rounding of the gap yourself, and use that rounded gap to assess whether you want to stop the optimization.   This also would probably be better than explicitly adding the cut on the lower bound as discussed in the thread, as, unlike the cut callback,  the informational callback does not disable dynamic search.

Finally, note that CPLEX's will handle objective functions that have greatest common divisors(gcds) other than 1.0 in an analogous way.   This applies not only to integer gcds > 1, but fractional gcds < 1.  

Originally posted by: Falcon_G

thank you indeed.

honestly, I did not understand the last note on gcds etc and why should it play role here?