most recent 30 from http://mathoverflow.net 2013-05-25T19:56:53Z http://mathoverflow.net/feeds/question/106127 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/106127/is-it-possible-to-represent-non-linear-ranking-type-constraints-as-equivalent-lin stressed_geek 2012-09-01T18:53:07Z 2012-09-01T18:58:36Z

<p>I have formulated a linear program with binary indicator variables $z_i(a)$ which is equal to $1$ if the $i^{th}$ document is of rank $a$ and $0$ otherwise. </p> <p>The other variables in the linear program, $z^1_{ij}(a), z^2_{ij}(a)$ are defined as follows:</p> <p>\begin{eqnarray} z^1_{ij}(a) \equiv z_i(a) \sum_{b &lt; a} z_j(b), \ z^2_{ij}(a) \equiv z_i(a) \sum_{b\geq a} z_j(b). \end{eqnarray}</p> <p>I am trying to convert the above non-linear constraint to the following set of equivalent linear constraints:</p> <p>$$z^1_{ij}(a) + z^2_{ij}(a) = z_i(a), \forall i, j, a$$</p> <p>The problem I am facing is that, the above set of linear constraints are clearly not equivalent to the definition of $z^1_{ij}(a), z^2_{ij}(a)$. Any ideas if it is possible to convert such non-linear ranking type constraints to linear constraints? </p>