LP relaxation for Integer Programming, where the input vector belongs to {-1,1} - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T13:46:32Z http://mathoverflow.net/feeds/question/90762 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90762/lp-relaxation-for-integer-programming-where-the-input-vector-belongs-to-1-1 LP relaxation for Integer Programming, where the input vector belongs to {-1,1} azaz104 2012-03-09T21:14:18Z 2012-03-09T21:14:18Z <p>lets say we have the following optimization problem:</p> <p>min max $|Ax|$ .</p> <p>s.t. $Hx \leq h$ .</p> <p>and $x \in {-1,1}$</p> <p>This is minimax problem that can be cast into an Integer Linear Program using Chebyshev programming</p> <p>min $t$ .</p> <p>s.t. $|Ax| \leq t$ .</p> <p>$Hx \leq h$ </p> <p>and $x \in {-1,1}$</p> <p>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.</p>