> From: [EMAIL PROTECTED] [mailto:help-glpk- > [EMAIL PROTECTED] On Behalf Of Andrew Makhorin > Sent: Monday, November 21, 2005 3:07 AM > To: Pedro Oguri > Cc: [email protected] > 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 [EMAIL PROTECTED] _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
