Is it possible to represent non-linear ranking type constraints as equivalent linear constraints?

Question

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?

What is b in your original constraints? Do you mean $z_i(a) \sum_{b<a} z_j(b)$ on the rhs? — David Nehme, Sep 01 '12 at 18:53

score 3 · Accepted Answer · answered Sep 01 '12 at 19:02

3

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}

answered Sep 01 '12 at 19:02

David Nehme

233
1
9

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. – stressed_geek Sep 01 '12 at 19:17
1

There are more compact, but weaker ways. For example: $2 z^1_{ij}(a) \le z_i(a) + \sum_{b < a} z_j(b)$. – David Nehme Sep 01 '12 at 19:48

score 3 · Answer 2 · answered Sep 01 '12 at 20:24

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.

Is it possible to represent non-linear ranking type constraints as equivalent linear constraints?

2 Answers2