Global Optimal in GAMS Solvers (CPLEX and BARON)

[sarahazzam]

1- I have an Integer Linear programming problem I solved it using CPLEX solver (mip) with optcr=0 does this provide a local optimal solution or global solution?
If a use BARON (mip) instead will it be able to provide the global optimal solution as it is a deterministic global solver? DO I have to adjust a certain parameter to get the global optimal?


2- I have a problem with quadratic objective function and linear constraints (all decision variables are continuous). So it is a convex problem. I used BARON solver to solve it. Is the solution provided the global optimal solution or do I have to adjust a certain parameter?


Thanks in advance

[Fred]

1- I have an Integer Linear programming problem I solved it using CPLEX solver (mip) with optcr=0 does this provide a local optimal solution or global solution?

A global optimal solution.

If a use BARON (mip) instead will it be able to provide the global optimal solution as it is a deterministic global solver? DO I have to adjust a certain parameter to get the global optimal?

BARON will also find a global optimal solution if you set optcr=0

2- I have a problem with quadratic objective function and linear constraints (all decision variables are continuous). So it is a convex problem. I used BARON solver to solve it. Is the solution provided the global optimal solution or do I have to adjust a certain parameter?

Having a quadratic objective and linear constraints does not necessarily result in a convex problem. Whether it is convex or non-convex. With optcr=0, BARON will find a global optimal solution.
If the problem is convex, you could also solve it with CPLEX (again, with optcr=0 CPLEX will find a global optimal solution)

The cplex and Baron solver manuals may be of interest to you:
https://www.gams.com/latest/docs/S_CPLEX.html
https://www.gams.com/latest/docs/S_BARON.html

I hope this helps!

Fred

[sarahazzam]

Thanks very much Mr. Fred.

Can you tell me what is meant by the best possible solution that CPLEX compares the feasible solution at each node with to calculate the absolute and relative optimality gap ?

[Fred]

Hi,

"best possible" refers to the value of the best bound on the objective function value.

I hope this helps!

Fred

[sarahazzam]

So if the best bound on the objective function value is known from the beginning of the problem what's the need for the iterations i.e. How does CPLEX solver have an estimate for it?

[Fred]

Hi,

The "best bound" column in the CPLEX log refers to the best bound that is known so far. Look for example at the following excerpt of a CPLEX log for a maximization problem.

Code: Select all

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

      0     0       29.5688   108                     29.5688      157         
  [...]
*     0+    0                            8.0000       26.3005           228.76%
Found incumbent of value 8.000000 after 0.17 sec. (210.88 ticks)
Detecting symmetries...
      0     1       26.3005   145        8.0000       26.0000     1780  225.00%
Elapsed time = 0.17 sec. (211.37 ticks, tree = 0.01 MB, solutions = 1)
*   180+  137                           15.0000       26.0000            73.33%
                                                      Cuts: 7                  
Found incumbent of value 15.000000 after 0.33 sec. (450.84 ticks)
    180   139       25.0000    86       15.0000       26.0000     9648   73.33%
    380   298       18.2545    47       15.0000       26.0000    16231   73.33%
                                                     Cuts: 11                  
*   440+  347                           16.0000       25.9814            62.38%
                                                  Impl Bds: 3                  
Found incumbent of value 16.000000 after 0.53 sec. (770.33 ticks)
*   510+  396                           17.0000       25.9437            52.61%
Found incumbent of value 17.000000 after 0.58 sec. (832.62 ticks)
*   517   339      integral     0       18.0000       25.9437    19881   44.13%
Found incumbent of value 18.000000 after 0.58 sec. (835.88 ticks)
    620   428       23.0525    69       18.0000       25.6677    22019   42.60%

Cplex starts with a bound of 29.5688. Now the bound decreases (26.3005, 26.0000, 25.9814 ,...) and the objective value of the best integer solution increases (8.0000, 15.0000, 16.0000) .
This is how the branch and bound algorithm works see e.g. (https://en.wikipedia.org/wiki/Branch_and_bound).

The CPLEX documentation on how to interpret the node log may also be of interest.
https://www.ibm.com/support/knowledgece ... e_log.html

I hope this helps!

Fred

[sarahazzam]

Hi,

Thanks for these useful links. Another question if the solver found the integer solution =26 at the node 180 for example, it will stop as the optcr will be equal to zero while the best bound will still decrease in the following nodes. Or this case won't occur ?