RE: [Help-glpk] Setting a constraint

[Michael Hennebry]

On Mon, 21 Nov 2005, Robert Fourer wrote:

>
> > 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

I assume that this represents a nested summation over i and j.

> > >
> > > 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,

For this particular polynomial, adequate facets
of the polytope might not be too hard to find.

The vertices can be described as follows:
x = 0 or y = 0 or SUM x[i] = 1 and SUM y[j] = 1
                   i                j
x, y binary

This polytope is full dimensional.
It includes a simplex which includes the
origin and every column of the identity matrix.
0<=x<=1 and 0<=y<=1 represent facets.

At the very least,
an adequate set of facets will cut off any infeasible integer points.
You don't need to deal with all of them explicitly,
just ones near the boundary.
These are the ones for which (SUM x[i], SUM y[j]) in { (1, 2), (2, 1) } .
                               i         j

In what follows, q represents a vector (x, y) to be cut off.

If q is outside the convex hull,
a facet can be found by trying to solve the following LP

max aq - 1
 a

s.t. ap <= 1  for p in F' subsetof F = feasible set

If the objective is bounded and >0,
a is the set of coefficients and 1 is the rhs.
If the objective is not bounded,
the coefficients are given by the direction
and the rhs is 0.
This might give you a constraint violated by a member of F.
In that case, add the member that violates it the most to F'
and try again.
Finding this member involves solving four easily solved subproblems.

For any facet you find,
you can find another by permuting the coefficients on x or y.
Thus, you only need the above facet finder for two values of x and y:
((1, 0, ...), (1, 1, 0, ...)) and ((1, 1, 0, ...), (1, 0, ...)).
If F' is initialized with a full dimensional simplex,
you won't need to deal with a direction of a.

I suspect more analysis would result in more simplification.

> 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.

-- 
Mike   address@hidden
"I AM DEATH, NOT TAXES.  *I* ONLY TURN UP ONCE."  --  Death