0
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ Solve the two problems: with $x_1+x_2=0$ and with $x_1+x_2=2$. Then choose the better solution. $\endgroup$
    – user64494
    Sep 12, 2015 at 18:19
  • $\begingroup$ @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. $\endgroup$
    – Shane
    Sep 12, 2015 at 18:43
  • $\begingroup$ "The feasible set would no longer be convex" but it never was. The feasible set was already ${0,1}^n$ to begin with. $\endgroup$
    – Michael Grant
    Sep 12, 2015 at 19:16
  • $\begingroup$ @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. $\endgroup$
    – Shane
    Sep 12, 2015 at 20:16
  • $\begingroup$ True but most logical constraints can be represented using linear equations and inequalities. I am not sure of a binary constraint that cannot be. $\endgroup$
    – Michael Grant
    Sep 12, 2015 at 20:19

1 Answer 1

Reset to default
2
$\begingroup$

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)$$

where

$$g(x_2,\ldots,x_n)=f(x_2,x_2,\ldots,x_n).$$

$\endgroup$
1
  • $\begingroup$ That's a useful way of thinking about it. And obvious -- not sure how it didn't occur to me! I would have a slight preference for keeping the constraint explicit in the problem (as in some cases it might be worth relaxing it), but this is a pretty good solution, which I'll accept unless a better one comes along shortly. Thanks! $\endgroup$
    – Shane
    Sep 12, 2015 at 18:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .