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

[Meketon, Marc]

Michael.  This is also very clever.

Another explanation of your code is the following:

Variable  a  is a non-negative integer (and always <= N2hi),  b  is binary, z  
is binary.  There are 4 constraints:
(1) sum=2a+b
(2) z>=b-a
(3) z<=b
(4) z<=(1-N2hi/N2lo)b - a/N2lo + N2hi/N2lo

When sum=1 we must have a=0, b=1.  Constraints (2) becomes z >= 1, (3) becomes 
z <= 1, and (4) becomes z <=1.  Hence z = 1.

For any sum that is even,  a = sum/2 and  b=0.  Constraint (2) is then 
non-binding since b-a <=0 and we know z >=0.  Constraint (3) is z <=0.  
Constraint (4) (since b=0) is z <= (N2hi - a)/N2lo.  Since  0 <= a <= N2hi, 
this is a non-binding since constraint (3) is tighter.  Hence z=0.

For any sum that is odd, with sum >= 3, we know that 1 <= a <= N2lo and b = 1.  
Constraint (2) is non-binding because b-a <= 0.  Constraint (3) with z <= 1 is 
non-binding.  Constraint (4) becomes z <= 1-a/N2lo.  Since 1 <= a <= N2lo, we 
know 0 <= 1-a/N2lo < 1, implying z < 1 (strict inequality), and then the binary 
constraint forces z=0.


-----Original Message-----
From: Michael Hennebry [mailto:address@hidden
Sent: Tuesday, October 08, 2013 1:43 PM
To: Meketon, Marc
Cc: Nigel Galloway; Andrew Makhorin; address@hidden; address@hidden
Subject: Re: [Help-glpk] [Fwd: I: Modelling binary variable]

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

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

Z = Q[1]-Q[2]
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 .

--
Michael   address@hidden
"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. 
Thank you for your cooperation.