Sorry wrong question, that tells me if the number set is odd or even. -- Nigel Galloway nigel_gallo...@operamail.com
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 > nigel_gallo...@operamail.com > > 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:henne...@web.cs.ndsu.nodak.edu] > > Sent: Tuesday, October 08, 2013 1:43 PM > > To: Meketon, Marc > > Cc: Nigel Galloway; Andrew Makhorin; help-glpk@gnu.org; > > pietro.scio...@archinet.it > > 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 henne...@web.cs.ndsu.nodak.edu > > "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 > Help-glpk@gnu.org > https://lists.gnu.org/mailman/listinfo/help-glpk -- http://www.fastmail.fm - IMAP accessible web-mail _______________________________________________ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
