Message Boards Message Boards

0
|
7608 Views
|
16 Replies
|
3 Total Likes
View groups...
Share
Share this post:

Find better representations for binary variables optimization?

Posted 4 years ago

I am trying to do optimization with binary variables, is there a better way to use than current method for the current version of Mathematica? I am using NelderMead method. Thanks.

z0 + z1 + z2 + z3 == 1, z4 + z5 + z6 + z7 == 1, 
z8 + z9 + z10 + z11 == 1, z12 + z13 + z14 + z15 == 1, 
z0 + z4 + z8 + z12 == 1, z1 + z5 + z9 + z13 == 1, 
z2 + z6 + z10 + z14 == 1, 
z3 + z7 + z11 + 
  z15 == 1, 0 <= z0 <= 1, 0 <= z1 <= 1, 0 <= z2 <= 1, 0 <= z3 <= 1, 0 \
<= z4 <= 1, 0 <= z5 <= 1, 0 <= z6 <= 1, 0 <= z7 <= 1, 0 <= z8 <= 1, 0 \
<= z9 <= 1, 0 <= z10 <= 1, 0 <= z11 <= 1, 0 <= z12 <= 1, 0 <= z13 <= \
1, 0 <= z14 <= 1, 0 <= z15 <= 1, {z0, z1, z2, z3, z4, z5, z6, z7, z8, 
  z9, z10, z11, z12, z13, z14, z15} \[Element] Integers
POSTED BY: Wael Al Hajailan
16 Replies
Anonymous User
Anonymous User
Posted 4 years ago

I'm not sure i understnad. if they are all 0 or 1 then the equation x1+x2+x3==1 cannot equal one unless only one is 1 (it is a matter only of whether the equations are consistent, not of optimizing). then there is only a matter of which is one, not of minimizing, which doesn't even constitute using logic (it would be a bit search). finally - there is no way to correct the inconsistent equation if that occurs.

perhaps an example, as Daniel Lichtblau, would be good

POSTED BY: Anonymous User

For the second item, the value for D00, D11, D22, and D33 are fixed. I am only trying to have the combination for P00, P11, P22, and P33 along with the fixed Dxx. So it should have 24 possible combinations of Pxx. For the third item, I am having all the possible combinations for both Pxx and Dxx. The value of Pxx could be any and the value of Dxx could be any. So, there are 32 binary variables to govern them. For both items, Pxx should be greater than Dxx in any combination before running the optimization. But I am taking care of that in the code.

P00 > D00, P11 > D11, P22 > D22, P33 > D33
POSTED BY: Wael Al Hajailan

No thanks for your help. Strange it should have because it did with another set of data. Can you please help me and send me the vector mapping for the those last two policies. If I used my way, it does not test all possible combinations and it just stopped and gave me the last tried answer.

2) I am only making possible combination for P:

P00 = z0 P0 + z1 P1 + z2 P2 + z3 P3;
P11 = z4 P0 + z5 P1 + z6 P2 + z7 P3;
P22 = z8 P0 + z9 P1 + z10 P2 + z11 P3;
P33 = z12 P0 + z13 P1 + z14 P2 + z15 P3;
z0 + z1 + z2 + z3 == 1, z4 + z5 + z6 + z7 == 1, 
z8 + z9 + z10 + z11 == 1, z12 + z13 + z14 + z15 == 1, 
z0 + z4 + z8 + z12 == 1, z1 + z5 + z9 + z13 == 1, 
z2 + z6 + z10 + z14 == 1, z3 + z7 + z11 + z15 == 1

3) I am making all combination of P&D, it is not like the first problem:

P00 = z0 P0 + z1 P1 + z2 P2 + z3 P3;
P11 = z4 P0 + z5 P1 + z6 P2 + z7 P3;
P22 = z8 P0 + z9 P1 + z10 P2 + z11 P3;
P33 = z12 P0 + z13 P1 + z14 P2 + z15 P3;
D00 = z16 D0 + z17 D1 + z18 D2 + z19 D3;
D11 = z20 D0 + z21 D1 + z22 D2 + z23 D3;
D22 = z24 D0 + z25 D1 + z26 D2 + z27 D3;
D33 = z28 D0 + z29 D1 + z30 D2 + z31 D3;
z0 + z1 + z2 + z3 == 1, z4 + z5 + z6 + z7 == 1, 
z8 + z9 + z10 + z11 == 1, z12 + z13 + z14 + z15 == 1, 
z0 + z4 + z8 + z12 == 1, z1 + z5 + z9 + z13 == 1, 
z2 + z6 + z10 + z14 == 1, z3 + z7 + z11 + z15 == 1
z16 + z17 + z18 + z19 == 1, z20 + z21 + z22 + z23 == 1, 
z24 + z25 + z26 + z27 == 1, z28 + z29 + z30 + z31 == 1, 
z16 + z20 + z24 + z28 == 1, z17 + z21 + z25 + z29 == 1, 
z18 + z22 + z26 + z30 == 1, z19 + z23 + z27 + z31 == 1
POSTED BY: Wael Al Hajailan
Posted 4 years ago

For your first request, I modify my code and add a Print to show only the last two items.

v=Select[Tuples[{0,1},16],
  Total[Take[#,{1,4}]]==...==1&];
Print[Drop[v,22]];

which displays

{{1,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0},{1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1}}

which corresponds to

{{z0,z5,z11,z14},{z0,z5,z10,z15}}

Is that what you were asking for?

For your second item, do I correctly understand that you are removing the assignments giving values to D00, D11, D22 and D33? If I do that then do I make any changes to the assignments to TC0, TC1, TC2 and TC3 which use D00, D11, D22 and D33? Do I understand that I then use the 8 constraints that follow to create the 24 alternatives as before? If so then I believe the current Select matches your equations you have given for this.

I do not believe I understand your third item? Are there now 32 binary variables instead of 16?

Note: If it might make my code any easier to understand there are two items.

Mathematica starts list indexes at one, not zero. You named your variables starting at zero. So z0 corresponds to #[[1]], z1 corresponds to #[[2]], etc.

Next, you can replace

{P00,P11,P22,P33,D00,D11,D22,D33}=
{z0 P0+z1 P1+z2 P2+z3 P3, z4 P0+z5 P1+z6 P2+z7 P3, z8 P0+z9 P1+z10 P2+z11 P3,
 z12 P0+z13 P1+z14 P2+z15 P3, z0 D0+z1 D1+z2 D2+z3 D3, z4 D0+z5 D1+z6 D2+z7 D3,
 z8 D0+z9 D1+z10 D2+z11 D3, z12 D0+z13 D1+z14 D2+z15 D3}/.r[[i]];

with

P00=z0 P0+z1 P1+z2 P2+z3 P3/.r[[i]];
P11=z4 P0+z5 P1+z6 P2+z7 P3/.r[[i]];
P22=z8 P0+z9 P1+z10 P2+z11 P3/.r[[i]];
P33=z12 P0+z13 P1+z14 P2+z15 P3/.r[[i]];
D00=z0 D0+z1 D1+z2 D2+z3 D3/.r[[i]];
D11=z4 D0+z5 D1+z6 D2+z7 D3/.r[[i]];
D22=z8 D0+z9 D1+z10 D2+z11 D3/.r[[i]];
D33=z12 D0+z13 D1+z14 D2+z15 D3/.r[[i]];

if that is any easier for you to understand.

POSTED BY: Bill Nelson

For the second item, I don't need the statements for all Dxx since they will not be changed. Only Pxx will have all possible combinations.

POSTED BY: Wael Al Hajailan
Posted 4 years ago

Can you perhaps adapt this

v=Select[Tuples[{0,1},16],
  Total[Take[#,{1,4}]]==1&&Total[Take[#,{5,8}]]==1&&
  Total[Take[#,{9,12}]]==1&&Total[Take[#,{13,16}]]==1&&
  #[[1]]+#[[5]]+#[[9]]+#[[13]]==1&&#[[2]]+#[[6]]+#[[10]]+#[[14]]==1&&
  #[[3]]+#[[7]]+#[[11]]+#[[15]]==1&&#[[4]]+#[[8]]+#[[12]]+#[[16]]==1&];
r=Map[MapThread[Rule,{{z0,z1,z2,z3,z4,z5,z6,z7,z8,z9,z10,z11,z12,z13,z14,z15},#}]&,v]

which finds the 24 acceptable assignments.

And then this

{P00,P11,P22,P33} = {z0 P0+z1 P1+z2 P2+z3 P3,z4 P0+z5 P1+z6 P2+z7 P3,
  z8 P0+z9 P1+z10 P2+z11 P3,z12 P0+z13 P1+z14 P2+z15 P3}/.r[[1]]
{D00,D11,D22,D33} = {z0 D0+z1 D1+z2 D2+z3 D3,z4 D0+z5 D1+z6 D2+z7 D3,
  z8 D0+z9 D1+z10 D2+z11 D3,z12 D0+z13 D1+z14 D2+z15 D3}/.r[[1]]

uses the first such assignment to find the first set of your eight expressions

POSTED BY: Bill Nelson

Yes you are right. I want to have 24 different combinations of a pair of P and D.

This is the code:

Const = {(P11 (t1)) PP0 == (P11 (t1) - P11 \[Alpha]1 \!\(
\*SubsuperscriptBox[\(\[Integral]\), \(0\), \(t1\)]\(\((t1 - x)\) f[
           x] \[DifferentialD]x\)\)) PP1, (P22 (t2) + P11 (t1) - 
       P11 \[Alpha]1 \!\(
\*SubsuperscriptBox[\(\[Integral]\), \(0\), \(t1\)]\(\((t1 - x)\) f[
           x] \[DifferentialD]x\)\)) PP1 == (P11 (t1)) PP0 + (P22 \
(t2) - P22 \[Alpha]2 \!\(
\*SubsuperscriptBox[\(\[Integral]\), \(0\), \(t2\)]\(\((t2 - x)\) f[
            x] \[DifferentialD]x\)\)) PP2, (P33 (t3) + P22 (t2) - 
       P22 \[Alpha]2 \!\(
\*SubsuperscriptBox[\(\[Integral]\), \(0\), \(t2\)]\(\((t2 - x)\) f[
           x] \[DifferentialD]x\)\)) PP2 == (P22 (t2)) PP1 + (P33 \
(t3) - P33 \[Alpha]3 \!\(
\*SubsuperscriptBox[\(\[Integral]\), \(0\), \(t3\)]\(\((t3 - x)\) f[
            x] \[DifferentialD]x\)\)) PP3, PP0 + PP1 + PP2 + PP3 == 1,
    PP0 > 0, PP1 > 0, PP2 > 0, PP3 > 0, t0 >= 0.1, t1 >= 0.1, 
   t2 >= 0.1, 
   t3 >= 0.1, {z0, z1, z2, z3, z4, z5, z6, z7, z8, z9, z10, z11, z12, 
     z13, z14, z15} \[Element] Integers};
Decision = {z0, z1, z2, z3, z4, z5, z6, z7, z8, z9, z10, z11, z12, 
   z13, z14, z15, PP0, PP1, PP2, PP3, t0, t1, t2, t3};
Sol = NMinimize[{ETC, Const}, Decision, Method -> "NelderMead"]

And this is the result:

{113.42, {z0 -> -1, z1 -> -1, z2 -> 0, z3 -> 1, z4 -> 0, z5 -> 0, 
  z6 -> 0, z7 -> 1, z8 -> 0, z9 -> 0, z10 -> 0, z11 -> 0, z12 -> 1, 
  z13 -> 1, z14 -> 1, z15 -> 0, PP0 -> 0.249059, PP1 -> 0.249473, 
  PP2 -> 0.250158, PP3 -> 0.25131, t0 -> 1.3903, t1 -> 1.24243, 
  t2 -> 1.14796, t3 -> 1.07981}}

As you notice, there is some variable of z are negative in the first, all zeros in the third, and more than one in the last. I am expecting the result to be lower than (113.286) by 10 or 12. The objective is to select the pair of P&D so that to have the minimum value around 102 or lower.

POSTED BY: Wael Al Hajailan
Posted 4 years ago

When I try to execute your code I get errors, probably because I do not have the definition of ETC or f[x] and possibly other symbols, so I can not experiment to see if small changes might give you better results. I also do not see how your code is making use of the 24 different combinations of P and D.

If you can provide additional information then I will take a few minutes and see what I can find.

POSTED BY: Bill Nelson

Please see attached the optimization file.

POSTED BY: Wael Al Hajailan
Posted 4 years ago

I moved your code around a little so that I could try NMinimize on each of the 24 acceptable assignments

K=100; pi=2.5; h=0.4; s=0.1; \[Lambda]=0.2; c1=(h/(h+pi)); c2=1-c1;
P0=1200; P1=950; P2=750; P3=600; D0=850; D1=650; D2=500; D3=400;
\[Alpha]0=0.0022919; \[Alpha]1=0.014506; \[Alpha]2=0.025709; \[Alpha]3=0.045571;
f[x_]:=\[Lambda] Exp[-\[Lambda] x];
v=Select[Tuples[{0,1},16],
  Total[Take[#,{1,4}]]==Total[Take[#,{5,8}]]==Total[Take[#,{9,12}]]==Total[Take[#,{13,16}]]==
    #[[1]]+#[[5]]+#[[9]]+#[[13]]==#[[2]]+#[[6]]+#[[10]]+#[[14]]==
    #[[3]]+#[[7]]+#[[11]]+#[[15]]==#[[4]]+#[[8]]+#[[12]]+#[[16]]==1&];
r=Map[MapThread[Rule,{{z0,z1,z2,z3,z4,z5,z6,z7,z8,z9,z10,z11,z12,z13,z14,z15},#}]&,v];
Table[
{P00,P11,P22,P33,D00,D11,D22,D33}={
  z0 P0+z1 P1+z2 P2+z3 P3, z4 P0+z5 P1+z6 P2+z7 P3, z8 P0+z9 P1+z10 P2+z11 P3,
  z12 P0+z13 P1+z14 P2+z15 P3, z0 D0+z1 D1+z2 D2+z3 D3, z4 D0+z5 D1+z6 D2+z7 D3,
  z8 D0+z9 D1+z10 D2+z11 D3, z12 D0+z13 D1+z14 D2+z15 D3}/.r[[i]];
e0:=Integrate[\[Alpha]0 P00 (t0-x) f[x],{x,0,t0}];
e1:=Integrate[\[Alpha]1 P11 (t1-x) f[x],{x,0,t1}];
e2:=Integrate[\[Alpha]2 P22 (t2-x) f[x],{x,0,t2}];
e3:=Integrate[\[Alpha]3 P33 (t3-x) f[x],{x,0,t3}];
TC0=K D00/(P00 t0)+(h(P00-D00)t0)(pi/(h+pi))/2+s D00 e0/(P00 t0);
TC1=K D11/(P11 t1)+(h(P11-D11)t1)(pi/(h+pi))/2+s D11 e1/(P11 t1);
TC2=K D22/(P22 t2)+(h(P22-D22)t2)(pi/(h+pi))/2+s D22 e2/(P22 t2);
TC3=K D33/(P33 t3)+(h(P33-D33)t3)(pi/(h+pi))/2+s D33 e3/(P33 t3);
ETC=PP0 TC0+PP1 TC1+PP2 TC2+PP3 TC3;
Const={(P11(t1))PP0==(P11(t1)-P11 \[Alpha]1 Integrate[(t1-x)f[x],{x,0,t1}])PP1,
  (P22(t2)+P11(t1)-P11 \[Alpha]1 Integrate[(t1-x)f[x],{x,0,t1}])PP1==
    (P11(t1))PP0+(P22(t2)-P22 \[Alpha]2 Integrate[(t2-x)f[x],{x,0,t2}])PP2,
  (P33(t3)+P22(t2)-P22 \[Alpha]2 Integrate[(t2-x)f[x], {x,0,t2}])PP2==
    (P22(t2))PP1+(P33(t3)-P33 \[Alpha]3 Integrate[(t3-x)f[x],{x,0,t3}])PP3,
  PP0+PP1+PP2+PP3==1, ETC>0, PP0>0, PP1>0, PP2>0, PP3>0, t0>=0.1, t1>=0.1, t2>=0.1, t3>=0.1};
Decision={PP0,PP1,PP2,PP3,t0,t1,t2,t3};
Sol=Flatten[{NMinimize[{ETC,Const},Decision, Method->"NelderMead"],r[[i]]}],
  {i,1,24}]

When I run that it fairly quickly responds with the minimum it found for each of the 24 cases.

None of the minimum are close to the value you are expecting.

There are a few things in the code that worry me a little, but I have not identified a serious problem yet.

Please check this very carefully to see if I might have damaged your code with my changes.

POSTED BY: Bill Nelson

I am trying to optimize an objective function by choosing the appropriate variables. So, I need a decision on each variable that is why I am using binary variables.

P00 = z0 P0 + z1 P1 + z2 P2 + z3 P3;
P11 = z4 P0 + z5 P1 + z6 P2 + z7 P3;
P22 = z8 P0 + z9 P1 + z10 P2 + z11 P3;
P33 = z12 P0 + z13 P1 + z14 P2 + z15 P3;

D00 = z0 D0 + z1 D1 + z2 D2 + z3 D3;
D11 = z4 D0 + z5 D1 + z6 D2 + z7 D3;
D22 = z8 D0 + z9 D1 + z10 D2 + z11 D3;
D33 = z12 D0 + z13 D1 + z14 D2 + z15 D3;
POSTED BY: Wael Al Hajailan

What I'd prefer to see is a complete stand-alone example.

POSTED BY: Daniel Lichtblau

I need to have combinations of P and D but with different rules and then to have the one with minimum cost. I will try different ways then I will see if it will work or not. Thanks.

POSTED BY: Wael Al Hajailan

What is being minimized? Is the goal speed, or quality of result?

POSTED BY: Daniel Lichtblau
Minimize[{z0 + z1 + z2 + z3 == 1, z4 + z5 + z6 + z7 == 1, 
z8 + z9 + z10 + z11 == 1, z12 + z13 + z14 + z15 == 1, 
z0 + z4 + z8 + z12 == 1, z1 + z5 + z9 + z13 == 1, 
z2 + z6 + z10 + z14 == 1, z3 + z7 + z11 + z15 == 1, 
Element[z0 | z1 | z2 | z3 | z4 | z5 | z6 | z7 | z8 | z9 | z10 | 
z11 | z12 | z13 | z14 | z15, Integers]}, {z0, z1, z2, z3, z4, z5, 
z6, z7, z8, z9, z10, z11, z12, z13, z14, z15}]

(*{z0 -> 0, z1 -> 0, z2 -> 0, z3 -> 1, z4 -> 0, z5 -> 0, z6 -> 0, 
z7 -> 1, z8 -> 0, z9 -> 0, z10 -> 0, z11 -> 1, z12 -> 1, z13 -> 1, 
 z14 -> 1, z15 -> -2}*)

Regards M.I.

POSTED BY: Mariusz Iwaniuk

The values of all z should be either one or zero.

POSTED BY: Wael Al Hajailan
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract