[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] [Fwd: I: Modelling binary variable]
From: |
Meketon, Marc |
Subject: |
Re: [Help-glpk] [Fwd: I: Modelling binary variable] |
Date: |
Wed, 9 Oct 2013 08:00:46 -0500 |
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.
- [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 <=
- Re: [Help-glpk] [Fwd: I: Modelling binary variable], Nigel Galloway, 2013/10/10
- Re: [Help-glpk] [Fwd: I: Modelling binary variable], Nigel Galloway, 2013/10/10