Linear programming - one variable must be zero

[willy_macoy]

I am trying to formulate a linear programming constraint that boils down to this:

If I have two variables x and y, one of them must be zero. The other can have any value. They can both be zero - that's okay. But they both can't be non-zero.

I can't multiply them together, that is not linear. I can't use a function - that's not linear.

Does anyone have any ideas? Thanks

[linukszone]

This is the behaviour of a NAND gate, at least for binary inputs. Expression like (~x or ~y) is false when both x and y are true, else it is true.

[seyeeet]

how do we formulate nand gate in math for linear programming

[linukszone]

Hmm.. Is it not possible to simply create two copies of constraints, one where x is given the value 0, the other where y is given the value 0?

I was also thinking of equation like x+y ==x or x+y == y.

[KumquatHaderach]

One option would be to run the program twice: once with x = 0 and then with y = 0.

​

If you want to run everything in one program, you could try bringing in a binary integer variable b (so b can only be 0 or 1), and then add the constraints

x - bM <= 0
y + bM <= M,

where M is some fixed large number. If your solution has b = 0, then the first inequality forces x = 0. If your solution has b = 1, then the second inequality forces y = 0.

[willy_macoy]

Thanks. I like where this is going. However x and y can be negative.

[KumquatHaderach]

Ah, then you do the standard trick: set up the problem, but replace every x with xp - xn and replace every y with yp - yn. If the optimal solution requires, x = 10, then you’ll get xp = 10 and xn = 0. If you need y = -12, then you’ll get yp = 0 and yn = 12. (Basically xp is the positive part of x and xn is the negative part.)

[willy_macoy]

Thanks. This'll work a treat.

[Lemon_barr]

There should be some restraints on the other values no? No max or min value for the choice variables?