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

[Nigel Galloway]

Sorry wrong question, that tells me if the number set is odd or even.

-- 
  Nigel Galloway
  address@hidden

On Thu, Oct 10, 2013, at 04:06 AM, Nigel Galloway wrote:
> Michael,
> 
> Does this not imply that we could just say sum = 2a + z where a is an
> integer >=0 and z is binary?
> 
> -- 
>   Nigel Galloway
>   address@hidden
> 
> On Wed, Oct 9, 2013, at 06:00 AM, Meketon, Marc wrote:
> > 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.
> 
> -- 
> http://www.fastmail.fm - Send your email first class
> 
> 
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/help-glpk

-- 
http://www.fastmail.fm - IMAP accessible web-mail