Consider the following linear program (LP)

$$ \begin{align*} &\text{maximize }& &c^\prime x\\ &\text{subject to }& &Ax \leq b\\ & && 0\leq x_i \leq 1 \quad \forall i \end{align*} $$

We know that $b$ is integral, $A_{i,j} \in \{-1,0,1\}$. However, $A$ is not necessary totally unimodular. We also know that $c_i\in\{-1,1\}$ for all $i$. Does this condition force the solution of the LP to be integral? If so, how to prove it?

My intuition is that as each variable has a weight in the objective function, their optimal value has to be at the extreme, being either $0$ or $1$, so I expect an integral (binary) solution. Also, I have solved a number of instances, and all of them had integral solutions. Can anyone help me to prove or disprove this?


The answer is negative. Consider the following problem (corresponding to max-clique of $K_3$, the complete graph on three vertices): $$\max x_1+x_2+x_2$$ $$ x_1 + x_2 \leq 1 $$ $$ x_1 + x_3 \leq 1 $$ $$ x_2 + x_3 \leq 1 $$ $$ 0 \leq x_i \leq 1 $$ The optimal solution is $x_i = 0.5$.

  • $\begingroup$ Thanks, in between I also realized that it does not hold. I need to see if I can make any further assumptions to make it hold. My A matrix is usually very sparse, might even be free of feedback loops. $\endgroup$ – hdb Dec 29 '16 at 18:01
  • $\begingroup$ Hi, I have posted a more specific description about the problem, see here: math.stackexchange.com/questions/2093433/… $\endgroup$ – hdb Jan 11 '17 at 14:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.