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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Sep 12, 2015 at 18:47

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.