Different results with zero optimality gap: MIP against SOS2

Dear all

I have a MIP model with some SOS2 constraints. I implement the SOS2 constraints with two approaches including SOS2 variable definition in GAMS, i.e. native SOS2 provided by CPLEX, and a MIP technique enforcing SOS2 constraints using integer variables. While the both models follow the same branching procedure in the beginning, the native SOS2 presents a premature convergence albeit with zero integrality gap resulting a different solution compared to the MIP technique outcome. Actually, the MIP technique converges to a better solution. Interestingly, for a smaller case study the results are exactly similar maybe suggesting that both the model is correct and equivalent.

The GAMS log files for SOSED (the native SOS2 model) and CCED (the MIP model), are as follows:

--- Starting compilation

--- Starting execution: elapsed 0:00:06.642

--- A.gms(335) 4 Mb

--- Generating MIP model CCED

--- 197 rows 313 columns 1,025 non-zeroes

--- 143 discrete-columns

--- Executing CPLEX: elapsed 0:00:06.652

IBM ILOG CPLEX 24.1.3 r41464 Released Jul 26, 2013 WEI x86_64/MS Windows

--- GAMS/Cplex licensed for continuous and discrete problems.

Cplex 12.5.1.0

Reading data...

Starting Cplex...

Tried aggregator 2 times.

MIP Presolve eliminated 14 rows and 27 columns.

Aggregator did 10 substitutions.

Reduced MIP has 173 rows, 276 columns, and 858 nonzeros.

Reduced MIP has 120 binaries, 0 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.00 sec. (0.68 ticks)

Probing time = 0.00 sec. (0.34 ticks)

Tried aggregator 1 time.

Reduced MIP has 173 rows, 276 columns, and 858 nonzeros.

Reduced MIP has 120 binaries, 0 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.02 sec. (0.50 ticks)

Probing time = 0.00 sec. (0.30 ticks)

Clique table members: 13.

MIP emphasis: balance optimality and feasibility.

MIP search method: dynamic search.

Parallel mode: none, using 1 thread.

Tried aggregator 1 time.

No LP presolve or aggregator reductions.

Presolve time = 0.00 sec. (0.11 ticks)

Initializing dual steep norms . . .

Iteration log . . .

Iteration: 1 Dual objective = 0.000000

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

Nodes Cuts/

Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 17936.1159 2 17936.1159 58

* 0+ 0 18169.2759 17936.1159 58 1.28%

Found incumbent of value 18169.275878 after 0.02 sec. (3.65 ticks)

0 0 17936.7683 5 18169.2759 Cuts: 2 76 1.28%

0 0 17936.7683 6 18169.2759 Cuts: 2 77 1.28%

0 0 17936.7683 7 18169.2759 MIRcuts: 1 79 1.28%

* 0+ 0 18076.0463 17936.7683 79 0.77%

Found incumbent of value 18076.046328 after 0.05 sec. (17.36 ticks)

0 2 17936.7683 7 18076.0463 17936.7683 79 0.77%

Elapsed time = 0.05 sec. (23.04 ticks, tree = 0.00 MB, solutions = 2)

* 10+ 10 17980.8047 17936.7683 137 0.24%

Found incumbent of value 17980.804661 after 0.06 sec. (24.63 ticks)

* 210+ 114 17973.5352 17937.0073 1530 0.20%

Found incumbent of value 17973.535181 after 0.09 sec. (67.11 ticks)

* 219 116 integral 0 17966.6633 17937.0073 1589 0.17%

Found incumbent of value 17966.663324 after 0.09 sec. (68.12 ticks)

* 1419+ 318 17959.4549 17939.2632 11379 0.11%

Found incumbent of value 17959.454929 after 0.31 sec. (291.85 ticks)

1453 298 17945.5295 1 17959.4549 17939.2632 11545 0.11%

2756 346 17955.2222 1 17959.4549 17945.5295 19968 0.08%

Cover cuts applied: 1

Mixed integer rounding cuts applied: 1

Gomory fractional cuts applied: 2

Root node processing (before b&c):

Real time = 0.05 sec. (23.01 ticks)

Sequential b&c:

Real time = 0.66 sec. (718.65 ticks)

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

Total (root+branch&cut) = 0.70 sec. (741.66 ticks)

MIP status(101): integer optimal solution

Cplex Time: 0.70sec (det. 741.66 ticks)

Fixing integer variables, and solving final LP...

Tried aggregator 1 time.

LP Presolve eliminated 170 rows and 280 columns.

Aggregator did 26 substitutions.

Reduced LP has 1 rows, 7 columns, and 7 nonzeros.

Presolve time = 0.00 sec. (0.13 ticks)

Initializing dual steep norms . . .

Iteration log . . .

Iteration: 1 Dual objective = 17959.454929

Fixed MIP status(1): optimal

Cplex Time: 0.00sec (det. 0.23 ticks)

Proven optimal solution.

MIP Solution: 17959.454929 (29320 iterations, 4195 nodes)

Final Solve: 17959.454929 (1 iterations)

Best possible: 17959.454929

Absolute gap: 0.000000

Relative gap: 0.000000

--- Restarting execution

--- Reading solution for model CCED

--- Executing after solve: elapsed 0:00:07.527

--- A.gms(341) 3 Mb

--- Generating MIP model SOSED

--- A.gms(342) 3 Mb

--- 41 rows 170 columns 479 non-zeroes

--- Executing CPLEX: elapsed 0:00:07.534

IBM ILOG CPLEX 24.1.3 r41464 Released Jul 26, 2013 WEI x86_64/MS Windows

--- GAMS/Cplex licensed for continuous and discrete problems.

Cplex 12.5.1.0

Reading data...

Starting Cplex...

Tried aggregator 1 time.

MIP Presolve eliminated 14 rows and 14 columns.

Reduced MIP has 27 rows, 156 columns, and 309 nonzeros.

Reduced MIP has 0 binaries, 0 generals, 13 SOSs, and 0 indicators.

Presolve time = 0.00 sec. (0.13 ticks)

Tried aggregator 1 time.

MIP Presolve eliminated 0 rows and 7 columns.

Reduced MIP has 27 rows, 149 columns, and 302 nonzeros.

Reduced MIP has 0 binaries, 0 generals, 13 SOSs, and 0 indicators.

Presolve time = 0.02 sec. (0.19 ticks)

MIP emphasis: balance optimality and feasibility.

MIP search method: dynamic search.

Parallel mode: none, using 1 thread.

Initializing dual steep norms . . .

Iteration log . . .

Iteration: 1 Dual objective = 0.000000

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

Nodes Cuts/

Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 17936.1159 1 17936.1159 37

* 0+ 0 18169.2759 17936.1159 37 1.28%

Found incumbent of value 18169.275878 after 0.05 sec. (0.63 ticks)

0 2 17936.1159 1 18169.2759 17936.3099 37 1.28%

Elapsed time = 0.05 sec. (1.98 ticks, tree = 0.00 MB, solutions = 1)

* 17 9 integral 0 18059.9491 17937.4838 87 0.68%

Found incumbent of value 18059.949070 after 0.05 sec. (2.64 ticks)

* 122 55 integral 0 18042.3514 17943.3545 305 0.55%

Found incumbent of value 18042.351449 after 0.06 sec. (6.56 ticks)

* 138 24 integral 0 17980.8047 17949.4262 337 0.17%

Found incumbent of value 17980.804661 after 0.06 sec. (7.10 ticks)

Root node processing (before b&c):

Real time = 0.05 sec. (1.97 ticks)

Sequential b&c:

Real time = 0.02 sec. (6.57 ticks)

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

Total (root+branch&cut) = 0.06 sec. (8.54 ticks)

MIP status(101): integer optimal solution

Cplex Time: 0.06sec (det. 8.54 ticks)

Fixing integer variables, and solving final LP...

Tried aggregator 1 time.

LP Presolve eliminated 39 rows and 168 columns.

Aggregator did 2 substitutions.

All rows and columns eliminated.

Presolve time = 0.00 sec. (0.05 ticks)

Fixed MIP status(1): optimal

Cplex Time: 0.00sec (det. 0.08 ticks)

Proven optimal solution.

MIP Solution: 17980.804661 (416 iterations, 183 nodes)

Final Solve: 17980.804661 (0 iterations)

Best possible: 17980.804661

Absolute gap: 0.000000

Relative gap: 0.000000

## Different results with zero optimality gap: MIP against SOS2

### Re: Different results with zero optimality gap: MIP against SOS2

Hi

Perhaps your problem has multiple solutions? You could use the solution of the first method as starting point for the second and see if the second algorithm and see if this reproduces this first solution. (the same vice versa).

Cheers

Renger

Perhaps your problem has multiple solutions? You could use the solution of the first method as starting point for the second and see if the second algorithm and see if this reproduces this first solution. (the same vice versa).

Cheers

Renger

____________________________________

Enjoy modeling even more: Read my blog on modeling at The lazy economist

Enjoy modeling even more: Read my blog on modeling at The lazy economist

### Re: Different results with zero optimality gap: MIP against SOS2

Many thanks for your attention. The original problem is non-convex with many local solutions. However, with a piecewise linearization technique, the approximate equivalent MILP model is built which is convex in the relaxed form (relaxing integer values). Consequently, it is expected that all MILP solution techniques converge to same solution. I could not found any parameters to set in SOS2 framework to further explore the problem space. As log files show the both approaches start from same root indicating the root node is same in the both models. However, the SOS2 solution technique stops at 17980.804661 displaying zero optimality gap which is certainly not true, as the other solution technique achieves more optimal solution with the zero optimality gap. If the challenge is stopping criteria in native SOS2 in CPLEX solver it should not print zero value for “Absolute gap “.