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