Contents
How to express Boolean operations in an integer linear program?
I have an integer linear program (ILP) with some variables x i that are intended to represent boolean values. The x i ‘s are constrained to be integers and to hold either 0 or 1 ( 0 ≤ x i ≤ 1 ). I want to express boolean operations on these 0/1-valued variables, using linear constraints.
How to set Y 1 to a Boolean?
More specifically, I want to set y 1 = x 1 ∧ x 2 (boolean AND), y 2 = x 1 ∨ x 2 (boolean OR), and y 3 = ¬ x 1 (boolean NOT). I am using the obvious interpretation of 0/1 as Boolean values: 0 = false, 1 = true.
How to express the forced logical implication of x 1?
Forced logical implication: To express that x 1 ⇒ x 2 must hold, simply use the linear constraint x 1 ≤ x 2 (assuming that x 1 and x 2 are already constrained to boolean values).
When to use linear inequalities in Boolean cast?
Cast to boolean (version 1): Suppose you have an integer variable x, and you want to define y so that y = 1 if x ≠ 0 and y = 0 if x = 0. If you additionally know that 0 ≤ x ≤ U, then you can use the linear inequalities 0 ≤ y ≤ 1, y ≤ x, x ≤ U y; however, this only works if you know an upper and lower bound on x.
1 Integer Programming and LP relaxation De nition 10.1.1 An integer program is a linear program in which all variables must be integers. As in a linear program, the constraints in an integer program form a polytope. However, the feasible set is given by the set of all integer-valued points within the polytope, and not the entire polytope.
How to use linear inequalities with linear constraints?
Logical AND: Use the linear constraints y 1 ≥ x 1 + x 2 − 1, y 1 ≤ x 1, y 1 ≤ x 2, 0 ≤ y 1 ≤ 1, where y 1 is constrained to be an integer. This enforces the desired relationship. (Pretty neat that you can do it with just linear inequalities, huh?)