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

[Michael Hennebry]

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