3
$\begingroup$

I have a linear programming problem $LP$ where all the variables $x_{i}$ take value in $\left[0, 1\right]$ (that is $0\leq x_{i} \leq 1$). All the constraints are as follow: $a_{1}+a_{2}+a_{3}=1$ that is each constraint is the sum of three distinct elements, for each elememt $a_{j}$ with $j\in \left\{1; 2; 3\right\}$ we have $a_{j}=x_{i}$ or $a_{j}=1-x_{i}$ and each sum is equal to $1$. It is not possible that the same variable $x_{i}$ appears two times in the same sum.

If for each variable $x_{i}$ we have that $LP$ is feasible whether we set $x_{i}=0$ or $x_{i}=1$, can we say that exists an integer solution of $LP$, that is a solution where each variable takes value in $\left\{0; 1\right\}$?

I give an example to make clearer my question.
Given:
$x_{1}+x_{2}+x_{3}=1$
$x_{4}+(1-x_{5})+x_{6}=1$
$(1-x_{7})+x_{8}+x_{9}=1$
$(1-x_{1})+(1-x_{5})+(1-x_{7})=1$
$0\leq x_{i} \leq 1$ $\forall i$

Foreach variable $x_{i}$ of the problem, one by one, we have that the problem is feasible whether we set $x_{i}=0$ or $x_{i}=1$.
The problem has at least an integer solution: $x_{1}=1$, $x_{2}=0$, $x_{3}=0$, $x_{4}=1$, $x_{5}=1$, $x_{6}=0$, $x_{7}=0$, $x_{8}=0$, $x_{9}=0$.

The question is: in general, for a problem where the constraints are the sums of three variables or their complement to $1$, the sums are equal to $1$ and $0\leq x_{i} \leq 1$ $\forall i$ (like in the given example), is it true that if the given problem is feasible whether we set, one by one, $x_{i}=0$ or $x_{i}=1$ foreach variable $x_{i}$ of the problem, then there is at least an integer solution of the given problem?

$\endgroup$
6
  • $\begingroup$ I find your problem description to be confusing. Are you saying that the constraints are $0 \le x_i \le 1, \Sigma_{i=1}^3 x_i=1$, and that these are all the constraints? Then you want to know whether the same problem, but with $x_i$ constrained to be zero or one, has the same optimal objective value as allowing $x_i$ to be continuous? $\endgroup$ – Mark L. Stone Mar 17 at 18:05
  • $\begingroup$ The constraints $0\leq x_{i} \leq 1$ are right, but about the sums I have constraints like $x_{i}+x_{j}+(1-x_k)=1$, $(1-x_{l})+x_{j}+(1-x_h)=1$, $(1-x_{i})+x_{g}+(1-x_l)=1$ and so on, that is each constraint is the sum of three elements, each element is a variables of the problem ($x_{i}$) or its complement to $1$ ($1-x_{i}$) and each sum is equal to $1$. $\endgroup$ – Mario Giambarioli Mar 17 at 20:37
  • $\begingroup$ If the original problem has a solution for which the variables are not all either 0 or 1, then if a constraint that all variables are 0 or 1 is added, the resulting problem is not necessarily feasible, and therefore the original optimal objective value can not be achieved. But this doesn't seem to be what you are asking. Or does it answer, n the negative, what you really meant to ask? $\endgroup$ – Mark L. Stone Mar 17 at 21:40
  • $\begingroup$ I have added an example to my question that should make clear what I mean. $\endgroup$ – Mario Giambarioli Mar 18 at 2:46
  • 1
    $\begingroup$ Interesting question. If I understand correctly, the requirement is that for any one variable in the problem, constraining that variable either to 0 or to 1 (with all others constrained between 0 and 1, but not necessarily integer) leaves the problem feasible. I would have expected that this would not guarantee that a fully binary-constrained version of the problem is feasible, but I haven't yet got a counterexample. $\endgroup$ – Geoffrey Brent Mar 18 at 5:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.