7
$\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 idea if it is possible to represent non-linear ranking type constraints as equivalent linear constraints?

Improve this question
$\endgroup$
2
  • $\begingroup$ What is b in your original constraints? Do you mean $z_i(a) \sum_{b<a} z_j(b)$ on the rhs? $\endgroup$
    – David Nehme
    Commented Sep 1, 2012 at 18:53
  • $\begingroup$ yes, sorry about that. Corrected now. $\endgroup$
    – stressed_geek
    Commented Sep 1, 2012 at 18:57

2 Answers 2

Reset to default
3
$\begingroup$

There are several ways to convert your model to linear constraints. For example

\begin{eqnarray} z^1_{ij}(a) + z^2_{ij}(a) &=& z_i(a) \ \ \forall i,j,a \\ z^1_{ij}(a) &\le& 1- \sum_{b \ge a} z_j(b) \ \ \forall i,j,a \\ z^2_{ij}(a) & \le& 1- \sum_{b < a} z_j(b) \ \ \forall i,j,a \end{eqnarray}

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you very much, this should work fine. By the way, if you get a chance I would be curious to know what are other possible ways. $\endgroup$
    – stressed_geek
    Commented Sep 1, 2012 at 19:17
  • 1
    $\begingroup$ There are more compact, but weaker ways. For example: $2 z^1_{ij}(a) \le z_i(a) + \sum_{b < a} z_j(b)$. $\endgroup$
    – David Nehme
    Commented Sep 1, 2012 at 19:48
3
$\begingroup$

In general, whenever you have a mixed-integer program where the only nonlinearities are polynomials of binary variables, it is possible to reformulate the program so that it is a mixed-integer linear program, using the work of Fred Glover, and subsequent related work.

See:

  • F. Glover. Further reduction of zero-one polynomial programming problems to zero-one linear programming problems. Operations Research, Volume 21, pages 156-161, 1971.

  • F. Glover, E. Woolsey. Converting the 0-1 polynomial programming problem to a 0-1 linear program. Operations Research, Volume 22, pages 180-182, 1974.

  • F. Glover. Improved linear integer programming formulations of nonlinear integer problems. Management Science, Volume 22, pages 455-460, 1975.

  • F. E. Torres. Linearization of mixed-integer products. Mathematical Programming, Volume 49, pages 427-428, 1991.

  • O. Kettani, M. Oral. Equivalent formulations for nonlinear integer problems for efficient optimization. Management Science, Volume 36, pages 115-119, 1990.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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