help-glpk
[Top][All Lists]

## Re: [Help-glpk] [Fwd: I: Modelling binary variable]

 From: Meketon, Marc Subject: Re: [Help-glpk] [Fwd: I: Modelling binary variable] Date: Tue, 8 Oct 2013 14:02:16 -0500

```It was Nigel Galloway's code, not my code.

-----Original Message-----
Sent: Tuesday, October 08, 2013 1:43 PM
To: Meketon, Marc
Subject: Re: [Help-glpk] [Fwd: I: Modelling binary variable]

On Tue, 8 Oct 2013, Meketon, Marc wrote:

> Are you sure that Z = Q-Q?  For the case where x=1, x=0, x=0,
> we have Q=0, Q=0, Q=1, and then Q-Q = 1 which is the correct

Z = Q-Q
he has Q sorted in non-ascending order.
00 no ones  0-0=0
10 one one  1-0=1
11 two or more ones 1-1=0
exactly what you want
The size of N does not matter.

Meketon's code has the advantage of ease of coding and understanding, but it
doubles the dimensionality.

Assume one has an integer expression sum:
0<=sum<=N
One wants z==1 iff sum==1 else 0
Define N2lo=floor(N/2), N2hi=ceil(N/2)
Note N=N2lo+N2hi, H2hi-N2lo in {0, 1}
Add two (not N) more integer variables:
0<=a<=N2hi
b binary

require
sum=2a+b
z>=b-a
z<=b
z<=(1-N2hi/N2lo)b - a/N2lo + N2hi/N2lo

The last constraint on z should be multiplied by N2lo to ensure integrality of
the coefficients.

Done.

The first two constraints on z are fairly obvious.
The last needs more explanation.

The diagram below is for N==7.

3  0 -
2  0 0
a 1  0 0
0  0 1

0 1
b

The rectangle gives the values of z for all valid combinations of a and b.
The given constraints on z are all facets of the polyhedron.
The first is for facet (0, 0, 0)(0, 1, 1)(1, 0, 0).
The second for facet (0, 0, 0)(0, 1, 1)(N2hi, 0, 0).
The third for facet (N2lo, 1, 0)(0, 1, 1)(N2hi, 0, 0).
Substitution will verify.

Note that exhaustive testing is possible:
The number of combinations that need testing is at most 2*(N+1)**2 .

--
"On Monday, I'm gonna have to tell my kindergarten class, whom I teach not to
run with scissors, that my fiance ran me through with a broadsword."  --  Lily

This e-mail and any attachments may be confidential or legally privileged. If
you received this message in error or are not the intended recipient, you
should destroy the e-mail message and any attachments or copies, and you are
prohibited from retaining, distributing, disclosing or using any information
contained herein.  Please inform us of the erroneous delivery by return e-mail.