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.

flag	asked Mar 9 2012 at 21:14 azaz104 1

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

Browse other questions tagged integer-programming linear-programming nonlinear-programming approximation-algorithms or ask your own question.

question feed