[Scip] Regarding expressing a constraint in a linear program

Tobias Achterberg achterberg at zib.de
Fri Sep 21 14:11:17 MEST 2007


> I am trying to use SCIP to solve a linear program. I have a linear program
> in which all the variables are continuous
> variables which are free to have values from 0 to infinity. Among those
> there are two variables, only one of which can be non-zero. I am not sure
> how to express this as a linear constraint. Could you help me with this?

The probably best way would be to add an SOS1 constraint. Unfortunately, SCIP currently
does not support SOS1.

If there are no upper bounds on the two variables, you are in trouble. Otherwise, do the

Say, your continuous variables are y1 and y2 with upper bounds u1 and u2. Add two binary
variables z1, z2 to your model and add the constraints

  y1 - u1*z1 <= 0
  y2 - u2*z2 <= 0
  z1 + z2    <= 1

Because z1 and z2 are binary, at most one of the two variables y1 and y2 can be nonzero.

The issue with this approach are the numerical difficulties that you get when u1 and u2
are very large numbers. Thus, you should try hard to find valid upper bounds for the
variables in order to reduce u1 and u2.

Best, Tobias

More information about the Scip mailing list