Search code examples
booleanconstraintscvxpymixed-integer-programminginequality

How to set not equal to constraint to a boolean vector variable

Suppose I have a simplified problem like this

x1 = cp.Variable(boolean=True)
x2 = cp.Variable(boolean=True)
sum = x1 + x2
prob = cp.Problem(cp.Maximize(sum))
prob.solve(verbose=True)

The possible combinations of x1, x2 are (0,0),(0,1),(1,0),(1,1). How can I remove (1,1) from my feasible region, so the optimal sum could be 1 instead of 2?

I tried the following, but it didn't work.

cp.transforms.indicator([x1==1, x2==1])>=1
Solution

  • Just add a linear-constraint:

    x1 = cp.Variable(boolean=True)
x2 = cp.Variable(boolean=True)

constraints = [x1 + x2 <= 1]     # !!!!!
objective = x1 + x2

prob = cp.Problem(objective, constraints)
prob.solve(verbose=True)

    A more general example (from below comment):

    Exclude (1,0,1,0) from 4-variable (x0,x1,x2,x3)

In propositional logic:

    !(x0 & !x1 & x2 & !x3)

Boolean Algebra -> De Morgan's laws:

    !(x0 & !x1 & x2 & !x3)
<-> !x0 | x1 | !x2 | x3     <- *C*onjunctive *N*ormal *F*orm

Linearization of CNF (basically: sum of literals >= 1):

Logic:              !x0    | x1  |  !x2    | x3
Linear inequality:  (1-x0) + x1  +  (1-x2) + x3 >= 1

    In discrete optimization, these kind of inequalities are often coined nogoods as they are often used iteratively to forbid solutions.