search

scipopt / scip

SCIP - Solving Constraint Integer Programs
Other
366 stars 63 forks source link

Problem with SOS2 has a different optimal solution based on the SOS weights #51

Closed pmlpm1986 closed 1 year ago

pmlpm1986 commented 1 year ago

I have been experimenting with special ordered sets of type 2 and noticed that I have been getting different optimal solutions based on the weights and their order.

The following SOS2 constraint (in .lp format) is recognised and solved correctly (objective = -2):

SOS

x10: S2::
  x4:1
  x5:2
  x6:3

The following SOS2 constraint (in .lp format) is recognised but not solved correctly (objective = 3):

SOS

x10: S2::
  x4:25
  x5:18
  x6:22

The correct solution is only produced when the weights are in monotonically ascending or descending order. I also tried to swap the order of the variables but it did not produce the right solution.

I am enclosing the aforementioned problems: sos2.zip

I found the same behaviour with CPLEX but not with CBC (correct result with both files). Is this a bug? Can somebody explain why this happens? Does the format require us to write the constraint with the variables and the weights in a specific order?

EDIT: Added information about the results with CBC.

pmlpm1986 commented 1 year ago

I just realised that the weights with SOS2 carry a significantly differently meaning than with SOS1. That is, different weights in an SOS1 do not change the problem but different weights in an SOS2 can: the weights determine the order and different weights can mean different segments with non-integer variables. This means that the bug is probably in CBC.