Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

The other variables in the linear program, $z^1_{ij}(a), z^2_{ij}(a)$ are defined as follows:

\begin{eqnarray} z^1_{ij}(a) \equiv z_i(a) \sum_{b < a} z_j(b), \\ z^2_{ij}(a) \equiv z_i(a) \sum_{b\geq a} z_j(b). \end{eqnarray}

I am trying to convert the above non-linear constraint to the following set of equivalent linear constraints:

$$z^1_{ij}(a) + z^2_{ij}(a) = z_i(a), \forall i, j, a$$

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?

share|cite|improve this question
You haven't mentioned this, but it would seem obvious that you want the additional constraint that $\sum_{b} z_{j}(b)=1$. That is, document j has exactly one rank. Once you've added that constraint, the second constraint $z_{ij}^{1}(a)+z_{ij}^{2}(a)=z_{i}(a)$ is a trivial consequence of the definitions of $z_{ij}(a)^{1}$ and $z_{ij}(a)^{2}$. – Brian Borchers Sep 2 '12 at 3:14
Yes, you are correct, the second constraint is a trivial onsequence of the definitions of $z^1_{ij}(a)$ and $z^2_{ij}(a)$. That is why I am looking for stronger linear constraints. – stressed_geek Sep 3 '12 at 11:45

1 Answer 1

In addition to the binary restrictions, take

$z^1_{ij}(a) \geq z_i(a) + \sum_{b<a} z_j(b) - 1$

and similar for the second equation.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.