2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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}$. $\endgroup$
    – Brian Borchers
    Commented Sep 2, 2012 at 3:14
  • $\begingroup$ 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. $\endgroup$
    – stressed_geek
    Commented Sep 3, 2012 at 11:45

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .