CODEWITHSUNDEEP
booleanlinear-programming
Arun Sen
Arun Sen

Reputation: 1

Boolean expression in linear program

I have to express an AND condition in linear program. The Boolean variable z takes a value 1 if both Boolean variables x and y takes a value 1. Otherwise, z takes a value 0. How do I write it in linear program?

Upvotes: 0

Views: 287

Answers (1)

SimonT
SimonT

Reputation: 493

In a pure linear program boolean expressions are not possible.

If you are in an (mixed-)integer program and x,y,z are all binary variables then you can implement the AND by the following.

  • z >= x+y-1
  • z <= x
  • z <= y

Here the first ensures z=1 if x=y=1 and the last two forces z=0 if any of the two is not 1.

As @Erwin Kalvelagen pointed out in the comments this is better relaxed than the formulation using 2z <= x+y.

Upvotes: 2

Related Questions