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

2012-03-09T21:14:18Z

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.

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

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