Originally posted by: Aniika

Hello,

have a question regarding the functional principle of CPLEX:

I want to solve a mixed integer linear program with cplex. It's quite complex so I'm not able to solve it optimally for all instances in an adequate amount of time. Thus I want to work with the upper and lower bounds that are known at the time I stop calculations. The problem is, that I couldn't find out where the upper bounds are taken from/ how they are calculated.

Does anybody know, how CPLEX computes the upper bounds? Which relaxations are made in the beginning and can adjustment be made by using any specific parameter settings?

Any help would be very much appreciated!

Thanks, Anika

 

 

 

 

#CPLEXOptimizers
#DecisionOptimization

How upper bounds are computed depends on whether your objective is minimization or maximization.

For minimization the upper bound on the objective function is the objective value of the best known feasible solution (the incumbent solution).

For a maximization problem the upper bound is the maximum of the objective values of the LP relaxations of all open search tree nodes.

Not sure what you mean by "relaxations in the beginning". CPLEX uses  the linear relaxation of a MIP, that is, it discards all integrality constraints.

What exactly do you want to adjust by parameter settings?
 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Aniika

Hi Daniel, thanks a lot for your answer! I have a maximization problem. I wasn't sure which constraints would be relaxed. I thought, maybe it is possible that I can determine (by using parameters) which of my constraints should be relaxed... So I assume this is not possible and it's always the integrality constraint that is relaxed? Another thing I am wondering about is: I thought whenever cplex finds and proves an optimal solution, the current upper bound equals exactly this solution (as in that case upper and lower bound should be the same). Looking at my results, this is not always the case: Often there is still a 0.01% gap between the optimal solution and the upper bound. Do you know the reason for it?
#CPLEXOptimizers
#DecisionOptimization

CPLEX solves a MIP using branch-and-bound. This algorithm is based on solving the continuous relaxation at each node. So CPLEX has to at least relax the integrality constraints. And that is enough to solve the problem via B&B. CPLEX does not relax other constraints. There is a FeasOpt feature that allows you to relax certain constraints in your model. This is however designed to analyze and fix infeasible models, so it may not be what you want.

Where do you read this 0.01% gap from? If you read this from the node log then this is expected and correct. For example, the following is a valid node log:

...

    642   344     1135.3288    35     1160.0000     1119.4523    27272    3.50%
    643   345     1155.0882    14     1160.0000     1119.4523    27326    3.50%
*  2231   821      integral     0     1158.0000     1141.7079    87666    1.41%

Cover cuts applied:  18
Implied bound cuts applied:  80
Flow cuts applied:  77
Mixed integer rounding cuts applied:  69
Flow path cuts applied:  4
Zero-half cuts applied:  5
Multi commodity flow cuts applied:  3
Lift and project cuts applied:  4
Gomory fractional cuts applied:  2

Root node processing (before b&c):
  Real time             =    1.63 sec. (952.70 ticks)
Parallel b&c, 8 threads:
  Real time             =    1.31 sec. (849.80 ticks)
  Sync time (average)   =    0.19 sec.
  Wait time (average)   =    0.22 sec.
                          ------------
Total (root+branch&cut) =    2.94 sec. (1802.51 ticks)

Solution pool: 11 solutions saved.

MIP - Integer optimal solution:  Objective =  1.1580000000e+03
Solution time =    2.97 sec.  Iterations = 110189  Nodes = 3423
Deterministic time = 1802.51 ticks  (607.38 ticks/sec)

As you can see, the last gap explicitly displayed is 1.41 but the solution is still reported "integer optimal" (i.e. final gap is 0). CPLEX does not print out a log line for each search tree node explored. Thus the last gap displayed is not necessarily the gap of the solution reported in the end. You can change the frequency with which nodes are printed using parameter CPX_PARAM_MIPINTERVAL.

Note that by default CPLEX may stop with gaps that are slightly larger than 0. This is controlled by parameters CPX_PARAM_EPAGAP and CPX_PARAM_EPGAP. If CPLEX stops due to one of those parameters then the log in the interactive optimizer will look like this:

MIP - Integer optimal, tolerance (0.05/1e-06):  Objective =  1.1610000000e+03
Current MIP best bound =  1.1039922494e+03 (gap = 57.0078, 4.91%)
Solution time =    1.51 sec.  Iterations = 944  Nodes = 0 (1)
Deterministic time = 921.05 ticks  (611.47 ticks/sec)

The last log lines shown in the two examples above are only printed in the interactive optimizer. If you solve your model with a programming API you will have to check the CPLEX status to determine whether optimality was proven or not.

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Aniika

Thanks a lot! That's exactly what I wanted to know. Great that there are parameters I can use to control the "tolerance". I'm using Java API so I don't always print out the compelte log. I computed the gap of 0,01% by "abs(upper bound-lower bound)/upper bound"- I didn't read it anywhere. 

Thanks, Anika

 

 

#CPLEXOptimizers
#DecisionOptimization

In the Java API there is function IloCplex.getMIPRelativeGap() that returns the relative gap as computed by CPLEX, so you don't have to compute it on your own. As you can see here the definition is slightly different from what you computed (CPLEX divides by lower bound, not upper bound for a maximization problem).

In any case, if the relative gap is too big then you should check the return values of IloCplex.getStatus() and IloCplex.getCplexStatus() to verify why CPLEX stopped. You should also check the absolute gap (and the value of CPX_PARAM_EPAGAP) since it may be that CPLEX stopped due to CPX_PARAM_EPAGAP in which case the relative gap may still be large.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Guerlain

I'm trying to find the upper bound for my minimizing problem, bellow a result of one simulation if it's possible to let me know the upper bound :

Tried aggregator 2 times.

MIP Presolve eliminated 226 rows and 82 columns.

MIP Presolve modified 5 coefficients.

Aggregator did 17 substitutions.

Reduced MIP has 103 rows, 127 columns, and 397 nonzeros.

Reduced MIP has 103 binaries, 9 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.02 sec. (0.55 ticks)

Found incumbent of value 5274.900000 after 0.02 sec. (0.72 ticks)

Probing time = 0.02 sec. (0.14 ticks)

Tried aggregator 1 time.

Reduced MIP has 103 rows, 127 columns, and 397 nonzeros.

Reduced MIP has 103 binaries, 9 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.09 sec. (0.19 ticks)

Probing time = 0.02 sec. (0.14 ticks)

Clique table members: 64.

MIP emphasis: balance optimality and feasibility.

MIP search method: dynamic search.

Parallel mode: deterministic, using up to 4 threads.

Root relaxation solution time = 0.00 sec. (0.21 ticks)

 

        Nodes                                         Cuts/

   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

 

*     0+    0                         5274.9000       60.1500       30   98.86%

*     0+    0                         2976.5400       60.1500       30   97.98%

*     0+    0                         2976.1800       60.1500       30   97.98%

      0     0     1063.5200    18     2976.1800     1063.5200       30   64.27%

*     0+    0                         1938.5000     1063.5200       30   45.14%

      0     0     1289.8300    18     1938.5000      Cuts: 32       67   33.46%

*     0+    0                         1697.2800     1289.8300       67   24.01%

      0     0     1290.1400    12     1697.2800      Cuts: 13       72   23.99%

      0     0     1290.1400    12     1697.2800      Cuts: 12       74   23.99%

*     0+    0                         1432.1400     1290.1400       74    9.92%

      0     2     1290.1400    12     1432.1400     1326.2800       74    7.39%

Elapsed time = 0.56 sec. (6.56 ticks, tree = 0.01 MB, solutions = 6)

 

Clique cuts applied:  8

Implied bound cuts applied:  34

Mixed integer rounding cuts applied:  2

Zero-half cuts applied:  11

Multi commodity flow cuts applied:  2

Gomory fractional cuts applied:  2

 

Root node processing (before b&c):

  Real time             =    0.55 sec. (6.49 ticks)

Parallel b&c, 4 threads:

  Real time             =    0.50 sec. (3.57 ticks)

  Sync time (average)   =    0.00 sec.

  Wait time (average)   =    0.00 sec.

                          ------------

Total (root+branch&cut) =    1.05 sec. (10.06 ticks)

 

#CPLEXOptimizers
#DecisionOptimization