RE: [Help-glpk] Setting a constraint

[Robert Fourer]

> From: address@hidden [mailto:help-glpk-
> address@hidden On Behalf Of Andrew Makhorin
> Sent: Monday, November 21, 2005 3:07 AM
> To: Pedro Oguri
> Cc: address@hidden
> Subject: Re: [Help-glpk] Setting a constraint
> 
> > Is it possible to set this constraint ?
> >
> > SUM (Xi * Yj) <= 1
> >
> > where Xi and Yj are variables in {0,1}.
> 
> Your inequality can be written as follows:
> 
>    sum zk <= 1
> 
> where zk are binary variables such that zk = xi * yj (or,
> equivalently, zk = xi & yj). The latter constraints are still
> non-linear, however, they can be written as the following equivalent
> linear constraints:
> 
>    0 <= xi + yj - 2 * zk <= 1
> 
> which describe the same polytope.

This linear reformulation is mathematically quite correct, but unfortunately it
can lead to integer programs that are hard to solve, or indeed impossible to
solve within reasonable resources.  Polynomial expressions in 0-1 variable have
been extensively studied, however, and quite a few clever linearizations have
been proposed, which use fewer integer variables or approximate the
integer-feasible region more tightly. See, for example,

F Glover and E Woolsey, Further reduction of zero-one polynomial
programming problems to zero-one linear programming problems.
Operations Research 21 (1973) 156-161.

M Oral and O Kettani, A linearization procedure for quadratic and cubic
mixed-integer problems. Operations Research 40 (1992) S109-S116.

WP Adams and RJ Forrester, A simple recipe for concise mixed 0-1
linearizations. Operations Research Letters 33 (2005) 55-61.

Bob Fourer
address@hidden