Originally posted by: excalibur1491

Hi all,

 

I have a question about what CPLEX tells me through the log. I have read this, and I have one question.

It says that the column Best Node tells me the best objective value achievable. Therefore, I understand it's the linear relaxation lower bound. Is this correct?

 

If so, what I want to know is: if I give CPLEX a problem with some real variable, some Binaries, a budget on how many binaries can be turned on and Indicator constraints for those binaries, what is really the value of the linear relaxation? Is it trying to assign a real value to the binaries like 0.14 for example? If that is the case, and a binary is given 0.14, would the indicators for that binary trigger?

 

This confuses me, because I have a model (minimizing) where I know that no solution with fewer turned-on binaries is better than a solution with at least one more binary turned on. But:

-if I remove the budget constraint and turn on all the binaries, I get an objective of 1.51.

-if I let CPLEX try to solve the problem (binaries unfixed, with budget), the best node I get is ~0.36. But clearly, turning on as many binaries as the budget allows is going to yield something >= 1.51.

So why is this Best Node worse than something that can be easily found to be the lower bound? What is CPLEX actually doing?

 

For the record, you can find the models attached. I use the mipex2 example given with CPLEX (also attached, for Python)

 

Thanks for the clarifications.

 

---

EDIT:

I just made a much smaller instance. Without budget and all binaries fixed I get 1.2 as the objective. The optimal (proven) solution with the budget is 49.1, but when I look at the log I only see values below 1.2 in the Best Node column. I also attached the files (named *_small.lp). Clearly, any assignment respecting the budget is above 49.1, as CPLEX proved optimality. My assumption is that the LP relaxation would turn on a bunch of binaries, but by turning on just enough that the all budget is used, you would get a solution of 1.2. So why is the Best node < 1.2?

Tried aggregator 1 time.
Reduced MIP has 51 rows, 83 columns, and 177 nonzeros.
Reduced MIP has 12 binaries, 0 generals, 0 SOSs, and 42 indicators.
Probing fixed 0 vars, tightened 21 bounds.
Probing time =    0.00 sec.
Tried aggregator 1 time.
Presolve time =    0.01 sec.
Probing time =    0.00 sec.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time =    0.00 sec.

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

      0     0        0.0000    12                      0.0000        3         
*     0+    0                          120.8333        0.0000        3  100.00%
      0     0        0.0000    12      120.8333   Impl Bds: 8        8  100.00%
*     0+    0                          103.7043        0.0000        8  100.00%
      0     0        0.0000    12      103.7043       Cuts: 5       12  100.00%
*     0+    0                           51.8074        0.0000       12  100.00%
      0     2        0.0000    12       51.8074        0.0000       12  100.00%
Elapsed real time =   0.06 sec. (tree size =  0.01 MB, solutions = 3)
*    27    21      integral     0       49.1559        0.9901      145   97.99%

Implied bound cuts applied:  6

Root node processing (before b&c):
  Real time             =    0.04
Parallel b&c, 8 threads:
  Real time             =    0.11
  Sync time (average)   =    0.00
  Wait time (average)   =    0.00
                          -------
Total (root+branch&cut) =    0.15 sec.
Time elapsed 0.162537097931
MIP_optimal
Solution status =  101 : MIP_optimal
Objective value =  49.155906651

Column v0: Value =       49.15590665
Column i_1_0: Value =      0.4915590665
Column i_2_0: Value =       49.15590665
Column i_1_1: Value =      0.2108124547
Column i_2_3: Value =       48.43665326
Column i_3_1: Value =      0.2108124547
Column i_4_1: Value =      0.2108124547
Column i_3_2: Value =      0.1335818869
Column i_4_4: Value =    0.007296410742
Column i_5_2: Value =      0.1335818869

And with all fixed:

Tried aggregator 2 times.
MIP Presolve eliminated 1 rows and 13 columns.
Aggregator did 28 substitutions.
All rows and columns eliminated.
Presolve time =    0.00 sec.
Time elapsed 0.00108122825623
MIP_optimal
Solution status =  101 : MIP_optimal
Objective value =  1.20833333333

Column v0: Value =       1.208333333
Column i_1_0: Value =       1.208333333
Column i_2_0: Value =       1.208333333
Column i_1_1: Value =              0.75
Column i_2_3: Value =      0.6666666667
Column i_3_1: Value =              0.75
Column i_4_1: Value =              0.75
Column i_3_2: Value =      0.5833333333
Column i_4_4: Value =      0.4583333333
Column i_5_2: Value =      0.5833333333

 

 

 

 

#CPLEXOptimizers
#DecisionOptimization