Warm tip: This article is reproduced from serverfault.com, please click

Converting conditional constraints to linear constraints for Linear Programming

发布于 2020-12-14 07:18:21

I've two variables: C which is binary, and X which is non-negative

If C = 0 then X = 0; If C = 1 then X = X (meaning there's no constraint on X)

How should I format this conditional constraint into a linear constraint for LP?

Questioner
Mitchell Z
Viewed
0
Erwin Kalvelagen 2020-12-14 17:07:49

Note that strictly speaking LP models only contain continuous variables. So we assume this is a MIP model to be solved with a MIP solver.

Here are three ways to attack this, depending on the capabilities of the solver.

(1) If you use a solver that supports indicator constraints, you can simply use:

 c=0 ==> x=0

(2) For other solvers you can use:

 x <= M*c

where M is a (tight as possible) upper bound on x.

(3) Finally, if your solver supports SOS1 (Special Ordered Sets of type 1) sets, you can use:

 d = 1-c
 {d,x} ∈ SOS1
 d >= 0

(1) and (3) have the advantage that no bound is needed. If you have a good, tight bound on x, (2) is a good option.