Simulated Annealing for NMinimize[] always returning the same solution

Question

I have a function defined as follows:

fourVertIsoHamilt[x11_, x12_, x13_, x14_, x21_, x22_, x23_, x24_, x31_, x32_, x33_, x34_, x41_, x42_, x43_, x44_] :=   
fourVertEnrgy[x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34, x41, x42, x43, x44] 
+ fourVertPenIso[ x12, x21, x22, x23, x24, x32, x33, x34, x44];

Where,

fourVertEnrgy[x11_, x12_, x13_, x14_, x21_, x22_, x23_, x24_, x31_, x32_, x33_, x34_, x41_, x42_, x43_, x44_] := 
1 + 2 x11 x12 + 2 x11 x13 + 2 x11 x14 + 2 x12 x13 + 2 x12 x14 + 2 x13 x14 - x11 - x12 - x13 - x14 + 
1 + 2 x21 x22 + 2 x21 x23 + 2 x21 x24 + 2 x22 x23 + 2 x22 x24 + 2 x23 x24 - x21 - x22 - x23 - x24 + 
1 + 2 x31 x32 + 2 x31 x33 + 2 x31 x34 + 2 x32 x33 + 2 x32 x34 + 2 x33 x34 - x31 - x32 - x33 - x34 + 
1 + 2 x41 x42 + 2 x41 x43 + 2 x41 x44 + 2 x42 x43 + 2 x42 x44 + 2 x43 x44 - x41 - x42 - x43 - x44 + 
1 + 2 x11 x21 + 2 x11 x31 + 2 x11 x41 + 2 x21 x31 + 2 x21 x41 + 2 x31 x41 - x11 - x21 - x31 - x41 + 
1 + 2 x12 x22 + 2 x12 x32 + 2 x12 x42 + 2 x22 x32 + 2 x22 x42 + 2 x32 x42 - x12 - x22 - x32 - x42 + 
1 + 2 x13 x23 + 2 x13 x33 + 2 x13 x43 + 2 x23 x33 + 2 x23 x43 + 2 x33 x43 - x13 - x23 - x33 - x43 + 
1 + 2 x14 x24 + 2 x14 x34 + 2 x14 x44 + 2 x24 x34 + 2 x24 x44 + 2 x34 x44 - x14 - x24 - x34 - x44;

and,

fourVertPenIso[ x12_, x21_, x22_, x23_, x24_, x32_, x33_, x34_, x44_] := 
x12 x24 + x12 x34 + x12 x44 + x22 x44 + x32 x44 + x21 x32 + x21 x33 + x21 x34 + x22 x33 + x23 x34;

I would like to minimize it using NMinimize with Simulated Annealing options. So, Mathematica the code is:

NMinimize[{fourVertIsoHamilt[x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34, x41, x42, x43, x44], 
x11 \[Element] Integers, x12 \[Element] Integers, x13 \[Element] Integers,    x14 \[Element] Integers, x21 \[Element] Integers,    x22 \[Element] Integers, x23 \[Element] Integers,    x24 \[Element] Integers, x31 \[Element] Integers, x32 \[Element] Integers, x33 \[Element] Integers, x34 \[Element] Integers, x41 \[Element] Integers,    x42 \[Element] Integers, x43 \[Element] Integers,    x44 \[Element] Integers, 
0 <= x11 <= 1, 0 <= x12 <= 1,    0 <= x13 <= 1, 0 <= x14 <= 1, 0 <= x21 <= 1, 0 <= x22 <= 1,    0 <= x23 <= 1, 0 <= x24 <= 1, 0 <= x31 <= 1, 0 <= x32 <= 1,    0 <= x33 <= 1, 0 <= x34 <= 1, 0 <= x41 <= 1, 0 <= x42 <= 1, 0 <= x43 <= 1, 0 <= x44 <= 1}, 
{x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34, x41, x42, x43, x44},   Method -> "SimulatedAnnealing"]

The global minima is zero which I am getting correctly. The problem is the only configuration my code is suggesting for the global minima is:

x11 -> 0, x12 -> 0, x13 -> 1, x14 -> 0, x21 -> 0, x22 -> 0, x23 -> 0, x24 -> 1, x31 -> 0, x32 -> 1, x33 -> 0, x34 -> 0, x41 -> 1, x42 -> 0, x43 -> 0, x44 -> 0

I repeated 10 times and got the same configuration all the time for the global minima 0.

Why isn't my code ever getting other solutions like:

x11-> 0, x22-> 0, x34->1, x43->1

Answer 1

I think the trick is to use the RandomSeed option as shown below:

Do[Print[NMinimize[{fourVertIsoHamilt[x11,x12,x13,x14,x21,x22,x23,x24,x31,x32,x33,x34,x41,x42,x43,x44],
x11\[Element]Integers,x12\[Element]Integers,x13\[Element]Integers,x14\[Element]Integers,x21\[Element]Integers,x22\[Element]Integers,x23\[Element]Integers,x24\[Element]Integers,x31\[Element]Integers,x32\[Element]Integers,x33\[Element]Integers,x34\[Element]Integers,x41\[Element]Integers,x42\[Element]Integers,x43\[Element]Integers,x44\[Element]Integers,
0<=x11<=1,0<=x12<=1,0<=x13<=1,0<=x14<=1,0<=x21<=1,0<=x22<=1,0<=x23<=1,0<=x24<=1,0<=x31<=1,0<=x32<=1,0<=x33<=1,0<=x34<=1,0<=x41<=1,0<=x42<=1,0<=x43<=1,0<=x44<=1},{x11,x12,x13,x14,x21,x22,x23,x24,x31,x32,x33,x34,x41,x42,x43,x44},
Method->{"SimulatedAnnealing","RandomSeed"->i}]],{i,10}]

Different values for the RandomSeed will give you other global minima.