## LP relaxation for Integer Programming, where the input vector belongs to {-1,1}

lets say we have the following optimization problem:

min max $|Ax|$ .

s.t. $Hx \leq h$ .

and $x \in {-1,1}$

This is minimax problem that can be cast into an Integer Linear Program using Chebyshev programming

min $t$ .

s.t. $|Ax| \leq t$ .

$Hx \leq h$

and $x \in {-1,1}$

the trivial solution when relaxing this problem to an LP problem is the all zero vector. I am wondering how to avoid this trivial solution. I'm trying a lot to cast the problem in a different way, but I haven't succeeded.

-
 I'm not sure how you're modeling this. Is $x$ being modeled as an integer variable in $[-1,1]$, where $0$ is an admissible value? I would not do that. I would write it as $x = 1-2\delta$ where $\delta \in \{0,1\}$. In the LP relaxaton, the binary variable is relaxed thus: $\delta \in [0,1]$. This means that at all integer-feasible points, $x$ is either $-1$ or $1$. – Gilead Mar 10 2012 at 2:11