[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] [Fwd: I: Modelling binary variable]
From: |
Nigel Galloway |
Subject: |
Re: [Help-glpk] [Fwd: I: Modelling binary variable] |
Date: |
Thu, 10 Oct 2013 04:06:42 -0700 |
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] [Fwd: I: Modelling binary variable], Andrew Makhorin, 2013/10/02
- Re: [Help-glpk] [Fwd: I: Modelling binary variable], Nigel Galloway, 2013/10/08
- Re: [Help-glpk] [Fwd: I: Modelling binary variable], Meketon, Marc, 2013/10/08
- Re: [Help-glpk] [Fwd: I: Modelling binary variable], Michael Hennebry, 2013/10/08
- Re: [Help-glpk] [Fwd: I: Modelling binary variable], Meketon, Marc, 2013/10/08
- Re: [Help-glpk] [Fwd: I: Modelling binary variable], Meketon, Marc, 2013/10/09
- Re: [Help-glpk] [Fwd: I: Modelling binary variable],
Nigel Galloway <=
- Re: [Help-glpk] [Fwd: I: Modelling binary variable], Nigel Galloway, 2013/10/10