0
$\begingroup$

I am trying to optimize a large function with 1024 input variables using NMinimize. The caveat is, that the function should only be called with each of the variables as a binary value (0 or 1). The function evaluates with values other than 0 or 1, however it does not have a reasonable/physical meaning doing so. For context, the function describes the optical properties of a material structure with a parameterized geometry, where the 1024 binary input variables parameterize the geometry space.

I have tried the following:

vars = {x1, x2, x3, x4};
Testfunction[x1_, x2_, x3_, x4_] := x1^2 - x2 + (1 - x3)^2 + x4

It's obvious that the correct solution for the minimum of the above function with the binary constraints is x1=0, x2=1,x3=1,x4=0.

I tried using NMinimize as shown below and to use StepMonitor to figure out what values the minimizer tests:

testprogress = {};
testopt = NMinimize[{Hold[Testfunction[x1, x2, x3, x4]],
   vars \[Element] Integers &&
    vars < 2 &&
    vars > -1
   }
  , vars, MaxIterations -> 20, 
  StepMonitor :> AppendTo[testprogress, vars]]

This gives the right answer {-1., {x1 -> 0, x2 -> 1, x3 -> 1, x4 -> 0}}

HOWEVER, when looking into the data appended to testprogressI find that real numbers rather than (0,1) where used to find the solution.

In[283]:= testprogress

Out[283]= {{0.458386, 0.630475, 0.540562, 0.0205422}, {0.420176, 
  0.71166, 0.723082, 0.349868}, {0.420176, 0.955819, 0.564741, 
  0.286847}, {0.289378, 0.737188, 0.518322, 0.275842}, {0.289378, 
  0.737188, 0.518322, 0.275842}, {0.420775, 0.518111, 0.549715, 
  0.245677}, {0.22129, 0.595524, 0.745492, 0.295513}, {0.22129, 
  0.595524, 0.745492, 0.295513}, {0.22129, 0.595524, 0.643158, 
  0.295513}, {0.22129, 0.690378, 0.830813, 0.295513}, {0.22129, 
  0.762992, 0.830813, 0.295513}, {0.22129, 0.762992, 0.830813, 
  0.295513}, {0.277562, 0.915617, 0.992179, 0.295513}, {0.277562, 
  0.790024, 0.957812, 0.295513}, {0.277562, 0.790024, 0.957812, 
  0.0807183}, {0.277562, 0.790024, 0.541769, 0.370714}, {0.0588165, 
  0.788637, 0.993765, 0.370714}, {0.00163245, 0.788637, 0.91337, 
  0.370714}, {0.39818, 0.788637, 0.985537, 0.370714}, {0.156202, 
  0.516489, 0.985537, 0.226041}}

it seems to me that the solution provided is simply the last step in testprogressrounded.

Can I modify the behaviour of NMinimize to only test using 0 and 1 for the minimization? Are there other optimization routines in Mathematica that would allow to do so? Given the large (2^1024) space to search and the fact that the function evaluates to meaningless values when non-binary values are used it seems to me that I have to prevent searches with values other than 0 and 1 to find the optimum solution.

EDIT:

Thank you all for the input. I tried a combination of your solutions and still find perplexing behavior.

  1. it seems that while NMinimize allows combining variables in a vector to set constraints like I did 0>=vars<=1 , it shows different behavior in the step monitor option. Combining the advice I tried:
vars = {x1, x2, x3, x4};
testfunction[x1 : 0 | 1, x2 : 0 | 1, x3 : 0 | 1, x4 : 0 | 1] = 
  x1^2 - x2 + (1 - x3)^2 + x4;
testopt = 
 Reap[NMinimize[{Hold[testfunction[x1, x2, x3, x4]], 
    vars \[Element] Integers && vars <= 1 && vars >= 0}, vars, 
   MaxIterations -> 5, StepMonitor :> Sow[vars]]]

which yields

{{-1., {x1 -> 0, x2 -> 1, x3 -> 1, 
   x4 -> 0}}, {{{0.458386, 0.630475, 0.540562, 0.0205422}, {0.420176, 
    0.71166, 0.723082, 0.349868}, {0.420176, 0.955819, 0.564741, 
    0.286847}, {0.289378, 0.737188, 0.518322, 0.275842}, {0.289378, 
    0.737188, 0.518322, 0.275842}}}}

and

vars = {x1, x2, x3, x4};
testfunction[x1 : 0 | 1, x2 : 0 | 1, x3 : 0 | 1, x4 : 0 | 1] = 
  x1^2 - x2 + (1 - x3)^2 + x4;
testopt = 
 Reap[NMinimize[{Hold[testfunction[x1, x2, x3, x4]], 
    vars \[Element] Integers && vars <= 1 && vars >= 0}, vars, 
   MaxIterations -> 5, StepMonitor :> Sow[{x1, x2, x3, x4}]]]

which gives

{{-1., {x1 -> 0, x2 -> 1, x3 -> 1, 
   x4 -> 0}}, {{{0, 1, 1, 0}, {0, 1, 1, 0}, {0, 1, 1, 0}, {0, 1, 1, 
    0}, {0, 1, 1, 0}}}}

What is the real numbered data sowed when using StepMonitor :> Sow[vars]? Roman is right that the function testfunction[x1 : 0 | 1, x2 : 0 | 1, x3 : 0 | 1, x4 : 0 | 1] cannot be evaluated with non-integers.

In[69]:= testfunction[0.1, 0.2, 0.3, 0.4]

Out[69]= testfunction[0.1, 0.2, 0.3, 0.4]

Are the values stored when using StepMonitor :> Sow[vars] some internal numbers that are not actually used to evaluate testfunction like I think Daniel is hinting towards?

$\endgroup$
3
  • $\begingroup$ If you replace your StepMonitor :> AppendTo[testprogress, vars] with StepMonitor :> Sow[vars] you'll get much better performance. See here for a tutorial. $\endgroup$
    – Roman
    Aug 31, 2021 at 9:39
  • $\begingroup$ If you define your binary function as testfunction[x1 : 0 | 1, x2 : 0 | 1, x3 : 0 | 1, x4 : 0 | 1] = x1^2 - x2 + (1 - x3)^2 + x4, then you'll be sure that it can never be called with any arguments other than 0 or 1. $\endgroup$
    – Roman
    Aug 31, 2021 at 9:54
  • $\begingroup$ (1) Internal code is likely treating the values as integers by rounding before use in evaluating the objective function. The reason they are not generated as integers is that it is difficult to generate new values as integers for several methods used by NMinimize. (2) One common way to impose the restriction is to have constraints of the form 0<=x<=1 and Element[x,Integers]. $\endgroup$ Aug 31, 2021 at 12:55

2 Answers 2

1
$\begingroup$

I'm not sure if this is an "answer" to what you ask, but when I use

testprogress = {};
testopt = 
  NMinimize[{Hold[Testfunction[x1, x2, x3, x4]], 
    0 <= x1 <= 1 && 0 <= x2 <= 1 && 0 <= x3 <= 1 && 0 <= x4 <= 1 && 
     x1 \[Element] Integers && x2 \[Element] Integers && 
     x3 \[Element] Integers && x4 \[Element] Integers}, {x1, x2, x3, 
    x4}, MaxIterations -> 20, 
   StepMonitor :> AppendTo[testprogress, {x1, x2, x3, x4}]]

I see what I think you are expecting. That is, the reported variables are integers. In other words, the test progress is

(* {{0, 1, 1, 0}, {0, 1, 1, 0}, {0, 1, 1, 0}, {0, 1, 1, 0}, {0, 1, 1, 
   0}, {0, 1, 1, 0}, {0, 1, 1, 0}, {0, 1, 1, 0}, {0, 1, 1, 0}, {0, 1, 
   1, 0}, {0, 1, 1, 0}, {0, 1, 1, 0}, {0, 1, 1, 0}, {0, 1, 1, 0}, {0, 
   1, 1, 0}, {0, 1, 1, 0}, {0, 1, 1, 0}, {0, 1, 1, 0}, {0, 1, 1, 
   0}, {0, 1, 1, 0}}*)
$\endgroup$
1
  • $\begingroup$ Yes, the StepMonitor is a bit finicky and you have to write out {x1, x2, x3, x4} as an argument there instead of using vars. This has to do with lexical scoping, as far as I understand. $\endgroup$
    – Roman
    Aug 31, 2021 at 9:53
1
$\begingroup$

First of all an essential tip: Reduce all powers of x[i]^j to simple x[i], since that's the same for only 0 or 1 and it saves a factor of 10.000 of time.

Here an example:

vars = Array[x, 1024];
tf = Table[(RandomInteger[{2, 4}] + (-1)^RandomInteger[] vars[[i]])^
       RandomInteger[{1, 3}], {i, vars // Length}] // Total;

tf2 = Expand[tf] /. x[aa_]^bb_ -> x[aa];

th1 = Thread[0 <= vars <= 1];
th2 = Thread[# \[Element] Integers] & /@ vars;

c = 0; {testopt = 
        NMinimize[{tf2, Join[th1, th2]}, vars, StepMonitor :> c++], 
c} // Timing

.

{0.015, {{11223., {x[1] -> 1, x[2] -> 1, x[3] -> 1, x[4] -> 1, 
x[5] -> 0, x[6] -> 1, x[7] -> 1, x[8] -> 0, x[9] -> 0, x[10] -> 1,
 x[11] -> 1, x[12] -> 0, x[13] -> 1, x[14] -> 1, x[15] -> 0, 
x[16] -> 1, x[17] -> 0, x[18] -> 1, x[19] -> 0, x[20] -> 0, 
x[21] -> 1, x[22] -> 1, x[23] -> 1, x[24] -> 1, x[25] -> 0, 
x[26] -> 0, x[27] -> 0, x[28] -> 0, x[29] -> 0, x[30] -> 1, 
x[31] -> 1, x[32] -> 0, x[33] -> 0, x[34] -> 0, x[35] -> 1, 
x[36] -> 1, x[37] -> 0, x[38] -> 0, x[39] -> 0, x[40] -> 0, 
x[41] -> 0, x[42] -> 1, x[43] -> 1, x[44] -> 0, x[45] -> 1, 
x[46] -> 0, x[47] -> 1, x[48] -> 0, x[49] -> 0, x[50] -> 1, 
x[51] -> 1, x[52] -> 0, x[53] -> 1, x[54] -> 1, x[55] -> 0, 
x[56] -> 1, x[57] -> 1, x[58] -> 1, x[59] -> 0, x[60] -> 0, 
x[61] -> 0, x[62] -> 0, x[63] -> 0, x[64] -> 0, x[65] -> 1, 
x[66] -> 0, x[67] -> 0, x[68] -> 1, x[69] -> 1, x[70] -> 0, 
x[71] -> 0, x[72] -> 1, x[73] -> 0, x[74] -> 0, x[75] -> 0, 
x[76] -> 1, x[77] -> 0, x[78] -> 0, x[79] -> 0, x[80] -> 0, 
x[81] -> 0, x[82] -> 0, x[83] -> 0, x[84] -> 1, x[85] -> 0, 
x[86] -> 0, x[87] -> 1, x[88] -> 1, x[89] -> 0, x[90] -> 1, 
x[91] -> 1, x[92] -> 0, x[93] -> 1, x[94] -> 0, x[95] -> 1, 
x[96] -> 1, x[97] -> 1, x[98] -> 0, x[99] -> 0, x[100] -> 0, 
x[101] -> 0, x[102] -> 0, x[103] -> 0, x[104] -> 0, x[105] -> 0, 
x[106] -> 1, x[107] -> 1, x[108] -> 1, x[109] -> 0, x[110] -> 1, 
x[111] -> 1, x[112] -> 1, x[113] -> 1, x[114] -> 0, x[115] -> 1, 
x[116] -> 0, x[117] -> 0, x[118] -> 1, x[119] -> 0, x[120] -> 0, 
x[121] -> 1, x[122] -> 1, x[123] -> 1, x[124] -> 0, x[125] -> 0, 
x[126] -> 0, x[127] -> 1, x[128] -> 1, x[129] -> 0, x[130] -> 0, 
x[131] -> 0, x[132] -> 0, x[133] -> 0, x[134] -> 0, x[135] -> 1, 
x[136] -> 0, x[137] -> 0, x[138] -> 1, x[139] -> 0, x[140] -> 1, 
x[141] -> 1, x[142] -> 0, x[143] -> 1, x[144] -> 1, x[145] -> 1, 
x[146] -> 0, x[147] -> 1, x[148] -> 0, x[149] -> 1, x[150] -> 1, 
x[151] -> 1, x[152] -> 0, x[153] -> 1, x[154] -> 1, x[155] -> 0, 
x[156] -> 0, x[157] -> 0, x[158] -> 1, x[159] -> 1, x[160] -> 1, 
x[161] -> 0, x[162] -> 0, x[163] -> 1, x[164] -> 0, x[165] -> 0, 
x[166] -> 1, x[167] -> 0, x[168] -> 1, x[169] -> 0, x[170] -> 1, 
x[171] -> 1, x[172] -> 1, x[173] -> 1, x[174] -> 0, x[175] -> 1, 
x[176] -> 1, x[177] -> 1, x[178] -> 1, x[179] -> 0, x[180] -> 0, 
x[181] -> 1, x[182] -> 1, x[183] -> 0, x[184] -> 0, x[185] -> 0, 
x[186] -> 0, x[187] -> 1, x[188] -> 1, x[189] -> 0, x[190] -> 1, 
x[191] -> 0, x[192] -> 1, x[193] -> 1, x[194] -> 0, x[195] -> 1, 
x[196] -> 0, x[197] -> 1, x[198] -> 1, x[199] -> 1, x[200] -> 1, 
x[201] -> 1, x[202] -> 1, x[203] -> 0, x[204] -> 1, x[205] -> 1, 
x[206] -> 1, x[207] -> 0, x[208] -> 0, x[209] -> 0, x[210] -> 1, 
x[211] -> 0, x[212] -> 0, x[213] -> 0, x[214] -> 1, x[215] -> 0, 
x[216] -> 1, x[217] -> 1, x[218] -> 0, x[219] -> 0, x[220] -> 0, 
x[221] -> 1, x[222] -> 0, x[223] -> 1, x[224] -> 1, x[225] -> 1, 
x[226] -> 1, x[227] -> 0, x[228] -> 1, x[229] -> 1, x[230] -> 1, 
x[231] -> 0, x[232] -> 1, x[233] -> 0, x[234] -> 1, x[235] -> 0, 
x[236] -> 1, x[237] -> 1, x[238] -> 1, x[239] -> 0, x[240] -> 1, 
x[241] -> 1, x[242] -> 1, x[243] -> 1, x[244] -> 1, x[245] -> 0, 
x[246] -> 1, x[247] -> 1, x[248] -> 1, x[249] -> 0, x[250] -> 1, 
x[251] -> 1, x[252] -> 1, x[253] -> 0, x[254] -> 0, x[255] -> 0, 
x[256] -> 1, x[257] -> 0, x[258] -> 1, x[259] -> 0, x[260] -> 0, 
x[261] -> 0, x[262] -> 1, x[263] -> 0, x[264] -> 0, x[265] -> 0, 
x[266] -> 1, x[267] -> 1, x[268] -> 0, x[269] -> 1, x[270] -> 1, 
x[271] -> 0, x[272] -> 1, x[273] -> 0, x[274] -> 1, x[275] -> 0, 
x[276] -> 1, x[277] -> 0, x[278] -> 0, x[279] -> 0, x[280] -> 0, 
x[281] -> 0, x[282] -> 0, x[283] -> 0, x[284] -> 1, x[285] -> 0, 
x[286] -> 0, x[287] -> 1, x[288] -> 1, x[289] -> 0, x[290] -> 1, 
x[291] -> 1, x[292] -> 1, x[293] -> 1, x[294] -> 1, x[295] -> 1, 
x[296] -> 0, x[297] -> 1, x[298] -> 0, x[299] -> 1, x[300] -> 0, 
x[301] -> 1, x[302] -> 1, x[303] -> 0, x[304] -> 0, x[305] -> 0, 
x[306] -> 1, x[307] -> 1, x[308] -> 1, x[309] -> 0, x[310] -> 0, 
x[311] -> 1, x[312] -> 1, x[313] -> 0, x[314] -> 1, x[315] -> 0, 
x[316] -> 1, x[317] -> 0, x[318] -> 0, x[319] -> 0, x[320] -> 0, 
x[321] -> 1, x[322] -> 1, x[323] -> 1, x[324] -> 0, x[325] -> 1, 
x[326] -> 1, x[327] -> 0, x[328] -> 0, x[329] -> 1, x[330] -> 1, 
x[331] -> 1, x[332] -> 1, x[333] -> 0, x[334] -> 0, x[335] -> 0, 
x[336] -> 1, x[337] -> 0, x[338] -> 0, x[339] -> 1, x[340] -> 0, 
x[341] -> 0, x[342] -> 0, x[343] -> 1, x[344] -> 1, x[345] -> 1, 
x[346] -> 1, x[347] -> 0, x[348] -> 1, x[349] -> 1, x[350] -> 0, 
x[351] -> 0, x[352] -> 1, x[353] -> 1, x[354] -> 0, x[355] -> 0, 
x[356] -> 0, x[357] -> 1, x[358] -> 0, x[359] -> 1, x[360] -> 0, 
x[361] -> 0, x[362] -> 0, x[363] -> 0, x[364] -> 0, x[365] -> 0, 
x[366] -> 1, x[367] -> 1, x[368] -> 1, x[369] -> 0, x[370] -> 0, 
x[371] -> 0, x[372] -> 0, x[373] -> 0, x[374] -> 1, x[375] -> 1, 
x[376] -> 1, x[377] -> 1, x[378] -> 0, x[379] -> 0, x[380] -> 1, 
x[381] -> 0, x[382] -> 0, x[383] -> 1, x[384] -> 1, x[385] -> 0, 
x[386] -> 0, x[387] -> 0, x[388] -> 0, x[389] -> 0, x[390] -> 1, 
x[391] -> 0, x[392] -> 1, x[393] -> 0, x[394] -> 1, x[395] -> 0, 
x[396] -> 1, x[397] -> 1, x[398] -> 1, x[399] -> 0, x[400] -> 1, 
x[401] -> 0, x[402] -> 1, x[403] -> 1, x[404] -> 0, x[405] -> 0, 
x[406] -> 1, x[407] -> 1, x[408] -> 0, x[409] -> 0, x[410] -> 1, 
x[411] -> 0, x[412] -> 1, x[413] -> 0, x[414] -> 1, x[415] -> 0, 
x[416] -> 0, x[417] -> 0, x[418] -> 1, x[419] -> 1, x[420] -> 0, 
x[421] -> 0, x[422] -> 1, x[423] -> 1, x[424] -> 1, x[425] -> 0, 
x[426] -> 1, x[427] -> 0, x[428] -> 0, x[429] -> 0, x[430] -> 1, 
x[431] -> 0, x[432] -> 1, x[433] -> 0, x[434] -> 0, x[435] -> 1, 
x[436] -> 0, x[437] -> 0, x[438] -> 0, x[439] -> 0, x[440] -> 1, 
x[441] -> 1, x[442] -> 1, x[443] -> 0, x[444] -> 1, x[445] -> 0, 
x[446] -> 1, x[447] -> 1, x[448] -> 0, x[449] -> 1, x[450] -> 1, 
x[451] -> 1, x[452] -> 0, x[453] -> 0, x[454] -> 0, x[455] -> 0, 
x[456] -> 1, x[457] -> 1, x[458] -> 1, x[459] -> 0, x[460] -> 0, 
x[461] -> 1, x[462] -> 1, x[463] -> 0, x[464] -> 1, x[465] -> 1, 
x[466] -> 1, x[467] -> 0, x[468] -> 0, x[469] -> 1, x[470] -> 0, 
x[471] -> 1, x[472] -> 1, x[473] -> 1, x[474] -> 1, x[475] -> 0, 
x[476] -> 1, x[477] -> 1, x[478] -> 1, x[479] -> 1, x[480] -> 1, 
x[481] -> 0, x[482] -> 0, x[483] -> 0, x[484] -> 0, x[485] -> 0, 
x[486] -> 0, x[487] -> 0, x[488] -> 0, x[489] -> 0, x[490] -> 1, 
x[491] -> 0, x[492] -> 0, x[493] -> 0, x[494] -> 0, x[495] -> 1, 
x[496] -> 1, x[497] -> 0, x[498] -> 1, x[499] -> 1, x[500] -> 1, 
x[501] -> 1, x[502] -> 1, x[503] -> 1, x[504] -> 0, x[505] -> 0, 
x[506] -> 1, x[507] -> 1, x[508] -> 0, x[509] -> 1, x[510] -> 0, 
x[511] -> 0, x[512] -> 0, x[513] -> 1, x[514] -> 0, x[515] -> 1, 
x[516] -> 1, x[517] -> 1, x[518] -> 1, x[519] -> 0, x[520] -> 0, 
x[521] -> 0, x[522] -> 1, x[523] -> 1, x[524] -> 1, x[525] -> 1, 
x[526] -> 0, x[527] -> 0, x[528] -> 1, x[529] -> 0, x[530] -> 1, 
x[531] -> 1, x[532] -> 1, x[533] -> 0, x[534] -> 0, x[535] -> 1, 
x[536] -> 0, x[537] -> 0, x[538] -> 0, x[539] -> 1, x[540] -> 1, 
x[541] -> 0, x[542] -> 0, x[543] -> 1, x[544] -> 0, x[545] -> 1, 
x[546] -> 0, x[547] -> 1, x[548] -> 1, x[549] -> 0, x[550] -> 1, 
x[551] -> 1, x[552] -> 1, x[553] -> 1, x[554] -> 0, x[555] -> 0, 
x[556] -> 1, x[557] -> 1, x[558] -> 1, x[559] -> 0, x[560] -> 1, 
x[561] -> 0, x[562] -> 1, x[563] -> 0, x[564] -> 0, x[565] -> 0, 
x[566] -> 0, x[567] -> 0, x[568] -> 0, x[569] -> 0, x[570] -> 1, 
x[571] -> 0, x[572] -> 1, x[573] -> 0, x[574] -> 0, x[575] -> 0, 
x[576] -> 0, x[577] -> 1, x[578] -> 1, x[579] -> 1, x[580] -> 1, 
x[581] -> 1, x[582] -> 0, x[583] -> 0, x[584] -> 0, x[585] -> 0, 
x[586] -> 1, x[587] -> 0, x[588] -> 0, x[589] -> 0, x[590] -> 0, 
x[591] -> 0, x[592] -> 0, x[593] -> 1, x[594] -> 0, x[595] -> 0, 
x[596] -> 0, x[597] -> 0, x[598] -> 1, x[599] -> 1, x[600] -> 1, 
x[601] -> 1, x[602] -> 0, x[603] -> 0, x[604] -> 0, x[605] -> 1, 
x[606] -> 1, x[607] -> 0, x[608] -> 0, x[609] -> 0, x[610] -> 1, 
x[611] -> 0, x[612] -> 0, x[613] -> 0, x[614] -> 1, x[615] -> 1, 
x[616] -> 0, x[617] -> 1, x[618] -> 1, x[619] -> 1, x[620] -> 1, 
x[621] -> 1, x[622] -> 0, x[623] -> 1, x[624] -> 1, x[625] -> 0, 
x[626] -> 0, x[627] -> 0, x[628] -> 1, x[629] -> 0, x[630] -> 0, 
x[631] -> 0, x[632] -> 0, x[633] -> 1, x[634] -> 1, x[635] -> 1, 
x[636] -> 0, x[637] -> 1, x[638] -> 0, x[639] -> 0, x[640] -> 0, 
x[641] -> 1, x[642] -> 0, x[643] -> 0, x[644] -> 0, x[645] -> 1, 
x[646] -> 1, x[647] -> 0, x[648] -> 1, x[649] -> 1, x[650] -> 0, 
x[651] -> 0, x[652] -> 1, x[653] -> 1, x[654] -> 0, x[655] -> 0, 
x[656] -> 0, x[657] -> 1, x[658] -> 1, x[659] -> 0, x[660] -> 1, 
x[661] -> 1, x[662] -> 0, x[663] -> 1, x[664] -> 0, x[665] -> 1, 
x[666] -> 1, x[667] -> 1, x[668] -> 0, x[669] -> 1, x[670] -> 1, 
x[671] -> 0, x[672] -> 1, x[673] -> 0, x[674] -> 0, x[675] -> 1, 
x[676] -> 0, x[677] -> 1, x[678] -> 1, x[679] -> 0, x[680] -> 1, 
x[681] -> 1, x[682] -> 0, x[683] -> 1, x[684] -> 1, x[685] -> 1, 
x[686] -> 1, x[687] -> 0, x[688] -> 1, x[689] -> 0, x[690] -> 0, 
x[691] -> 0, x[692] -> 1, x[693] -> 0, x[694] -> 0, x[695] -> 0, 
x[696] -> 1, x[697] -> 1, x[698] -> 0, x[699] -> 1, x[700] -> 1, 
x[701] -> 1, x[702] -> 1, x[703] -> 0, x[704] -> 1, x[705] -> 0, 
x[706] -> 1, x[707] -> 1, x[708] -> 1, x[709] -> 1, x[710] -> 1, 
x[711] -> 0, x[712] -> 1, x[713] -> 0, x[714] -> 1, x[715] -> 0, 
x[716] -> 0, x[717] -> 0, x[718] -> 1, x[719] -> 0, x[720] -> 0, 
x[721] -> 1, x[722] -> 1, x[723] -> 1, x[724] -> 1, x[725] -> 1, 
x[726] -> 0, x[727] -> 0, x[728] -> 1, x[729] -> 1, x[730] -> 0, 
x[731] -> 0, x[732] -> 0, x[733] -> 0, x[734] -> 0, x[735] -> 0, 
x[736] -> 0, x[737] -> 0, x[738] -> 1, x[739] -> 1, x[740] -> 1, 
x[741] -> 1, x[742] -> 1, x[743] -> 1, x[744] -> 1, x[745] -> 0, 
x[746] -> 1, x[747] -> 0, x[748] -> 0, x[749] -> 0, x[750] -> 1, 
x[751] -> 1, x[752] -> 0, x[753] -> 0, x[754] -> 1, x[755] -> 1, 
x[756] -> 0, x[757] -> 0, x[758] -> 0, x[759] -> 0, x[760] -> 0, 
x[761] -> 0, x[762] -> 1, x[763] -> 1, x[764] -> 1, x[765] -> 1, 
x[766] -> 0, x[767] -> 1, x[768] -> 0, x[769] -> 1, x[770] -> 1, 
x[771] -> 1, x[772] -> 1, x[773] -> 0, x[774] -> 1, x[775] -> 0, 
x[776] -> 0, x[777] -> 1, x[778] -> 1, x[779] -> 0, x[780] -> 1, 
x[781] -> 0, x[782] -> 0, x[783] -> 0, x[784] -> 1, x[785] -> 1, 
x[786] -> 0, x[787] -> 1, x[788] -> 1, x[789] -> 1, x[790] -> 0, 
x[791] -> 1, x[792] -> 1, x[793] -> 1, x[794] -> 0, x[795] -> 1, 
x[796] -> 0, x[797] -> 0, x[798] -> 1, x[799] -> 0, x[800] -> 1, 
x[801] -> 0, x[802] -> 0, x[803] -> 1, x[804] -> 1, x[805] -> 0, 
x[806] -> 1, x[807] -> 1, x[808] -> 0, x[809] -> 1, x[810] -> 0, 
x[811] -> 0, x[812] -> 1, x[813] -> 1, x[814] -> 1, x[815] -> 0, 
x[816] -> 0, x[817] -> 1, x[818] -> 0, x[819] -> 0, x[820] -> 0, 
x[821] -> 1, x[822] -> 1, x[823] -> 0, x[824] -> 0, x[825] -> 1, 
x[826] -> 0, x[827] -> 1, x[828] -> 0, x[829] -> 1, x[830] -> 1, 
x[831] -> 1, x[832] -> 0, x[833] -> 1, x[834] -> 1, x[835] -> 0, 
x[836] -> 1, x[837] -> 0, x[838] -> 0, x[839] -> 0, x[840] -> 1, 
x[841] -> 0, x[842] -> 1, x[843] -> 1, x[844] -> 0, x[845] -> 0, 
x[846] -> 1, x[847] -> 1, x[848] -> 1, x[849] -> 0, x[850] -> 0, 
x[851] -> 1, x[852] -> 0, x[853] -> 1, x[854] -> 1, x[855] -> 0, 
x[856] -> 1, x[857] -> 1, x[858] -> 0, x[859] -> 0, x[860] -> 0, 
x[861] -> 1, x[862] -> 1, x[863] -> 0, x[864] -> 1, x[865] -> 1, 
x[866] -> 0, x[867] -> 1, x[868] -> 1, x[869] -> 0, x[870] -> 0, 
x[871] -> 0, x[872] -> 1, x[873] -> 1, x[874] -> 0, x[875] -> 1, 
x[876] -> 1, x[877] -> 1, x[878] -> 1, x[879] -> 1, x[880] -> 1, 
x[881] -> 1, x[882] -> 0, x[883] -> 0, x[884] -> 1, x[885] -> 1, 
x[886] -> 0, x[887] -> 0, x[888] -> 1, x[889] -> 1, x[890] -> 0, 
x[891] -> 0, x[892] -> 0, x[893] -> 0, x[894] -> 0, x[895] -> 1, 
x[896] -> 0, x[897] -> 0, x[898] -> 1, x[899] -> 1, x[900] -> 1, 
x[901] -> 0, x[902] -> 1, x[903] -> 0, x[904] -> 0, x[905] -> 0, 
x[906] -> 1, x[907] -> 1, x[908] -> 1, x[909] -> 0, x[910] -> 0, 
x[911] -> 1, x[912] -> 1, x[913] -> 0, x[914] -> 0, x[915] -> 0, 
x[916] -> 0, x[917] -> 1, x[918] -> 0, x[919] -> 1, x[920] -> 0, 
x[921] -> 1, x[922] -> 0, x[923] -> 0, x[924] -> 1, x[925] -> 0, 
x[926] -> 1, x[927] -> 0, x[928] -> 0, x[929] -> 1, x[930] -> 0, 
x[931] -> 0, x[932] -> 0, x[933] -> 0, x[934] -> 0, x[935] -> 1, 
x[936] -> 0, x[937] -> 0, x[938] -> 0, x[939] -> 1, x[940] -> 0, 
x[941] -> 1, x[942] -> 0, x[943] -> 0, x[944] -> 1, x[945] -> 1, 
x[946] -> 0, x[947] -> 1, x[948] -> 1, x[949] -> 1, x[950] -> 1, 
x[951] -> 0, x[952] -> 0, x[953] -> 1, x[954] -> 0, x[955] -> 0, 
x[956] -> 1, x[957] -> 1, x[958] -> 0, x[959] -> 1, x[960] -> 0, 
x[961] -> 0, x[962] -> 1, x[963] -> 0, x[964] -> 0, x[965] -> 1, 
x[966] -> 1, x[967] -> 1, x[968] -> 0, x[969] -> 0, x[970] -> 0, 
x[971] -> 0, x[972] -> 0, x[973] -> 1, x[974] -> 0, x[975] -> 0, 
x[976] -> 0, x[977] -> 0, x[978] -> 0, x[979] -> 0, x[980] -> 1, 
x[981] -> 1, x[982] -> 0, x[983] -> 1, x[984] -> 1, x[985] -> 1, 
x[986] -> 1, x[987] -> 1, x[988] -> 0, x[989] -> 0, x[990] -> 0, 
x[991] -> 0, x[992] -> 0, x[993] -> 0, x[994] -> 1, x[995] -> 0, 
x[996] -> 0, x[997] -> 0, x[998] -> 0, x[999] -> 0, x[1000] -> 0, 
x[1001] -> 1, x[1002] -> 0, x[1003] -> 1, x[1004] -> 1, 
x[1005] -> 0, x[1006] -> 0, x[1007] -> 1, x[1008] -> 0, 
x[1009] -> 1, x[1010] -> 1, x[1011] -> 0, x[1012] -> 1, 
x[1013] -> 0, x[1014] -> 0, x[1015] -> 0, x[1016] -> 0, 
x[1017] -> 0, x[1018] -> 0, x[1019] -> 0, x[1020] -> 0, 
x[1021] -> 0, x[1022] -> 1, x[1023] -> 1, x[1024] -> 0}}, 0}}

Don't know exactly how, but all is done in one iteration. Think linear algebra methods are used.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.