# Zero-one linear programming with substitutable constraints

Suppose $x_1, x_2, \ldots, x_n$ each take values zero or one and we want to solve the following linear programming problem:

$$\min_{x_1,x_2,\ldots, x_n} f(x_1,x_2,\ldots,x_n)$$ subject to a bunch of constraints. Suppose $f$ is linear.

Can I have one of those constraints be $x_1+x_2 \ne 1$ (or alternatively $x_1+x_2=0$ OR $x_1+x_2=2$)?

It's still a well-defined problem with a constraint like that, but can we use standard algorithms to solve it? In some sense, it seems conceptually pretty easy. My hope is that this is a pretty standard problem and one that can be easily worked with in Gurobi or CPLEX, but I've never had to work with a constraint like this before.

• Solve the two problems: with $x_1+x_2=0$ and with $x_1+x_2=2$. Then choose the better solution. Sep 12, 2015 at 18:19
• @user64494 That's true. In principle I could do that. In practice, though, if I have a lot of constraints like that, the number of problems to solve goes up exponentially. Sep 12, 2015 at 18:43
• "The feasible set would no longer be convex" but it never was. The feasible set was already ${0,1}^n$ to begin with. Sep 12, 2015 at 19:16
• @MichaelGrant. You're right. That's more misleading than helpful. I had in my mind that if the $x$'s were real then $x_1+x_2\ne1$ would make the feasible set convex, but that's not really applicable here. Sep 12, 2015 at 20:16
• True but most logical constraints can be represented using linear equations and inequalities. I am not sure of a binary constraint that cannot be. Sep 12, 2015 at 20:19

The constraint is equivalent to saying $x_1=x_2$ so you can recast it into the problem:
$$\min_{x_2,\ldots,x_n} g(x_2,\ldots,x_n)$$
$$g(x_2,\ldots,x_n)=f(x_2,x_2,\ldots,x_n).$$