How do I iterate between 32 binary options?

Question

I have an optimization problem where I have 5 variables: A, B1, B2, C1, C2. I am trying to optimize these 5 variables to get the smallest root sum square value I can. I have a few optimization techniques that are working ok, but this one in particular is giving me some trouble.

I want to explore all 32 options of changing the variables and pick the smallest RSS value. What I mean by this is each variable can either be +/- an increment. And each choice leads to 2 more choices, with 5 variables thats 32 choices. ( 2^5 )

To clarify, I am not adding my variables: A, B1, B2 etc to each other, I am incrementing / decrementing them by an arbitrary amount. A +/- X, B1+/- X2, etc. And I am trying to figure out which combination of incrementation/ decrementation of my 5 variables will return the lowest Root sum square value.

                                   A
                                 +/ \-
                                B1   B1
                               +/\- +/\-
                              B2 B2 B2 B2

So on and so forth till all 5 levels are complete. I am not sure even where to start to attempt to solve this. What kind of data structure would be best for storing this? Is it an iterative, or a recursive solution. I don't need the answer to the problem, rather somewhere to look or somewhere to start. Thank you again for taking the time to look at this.

To clarify further confusion this is my optimization method. I ahve 5 variables, and 5 increments, each increment matches to a variable. (a,b,c,d,e,f) ---> (incA, incB, incC, indD, incE, incF)

I want to find the best combination of +/- incX to X ( x being one of the 5 variables )ie: the solution might be something like: a+incA , B-incB, c+incC, d+incD, e+incE, f-incF. There are 32 possibilities of combinations, after reading through all the answers below I have settled on this possible algorithm. ( see my answer below ) make edits and questions as necessary. This is not a perfect algorithm, it is for clarification and ease of understanding, i know it can be condensed.

//Settign all possible solutions to be iterated through later.
double[] levelA = new double[2];
double[] levelB = new double[2];
double[] levelC = new double[2];
double[] levelD = new double[2];
double[] levelE = new double[2];

levelA[0] = a + incA;
levelA[1] = a - incA;
levelB[0] = b + incB;
levelB[1] = b - incB;
levelC[0] = c + incC;
levelC[1] = c - incC;
levelD[0] = d + incD;
levelD[1] = d - incD;
levelE[0] = e + incE;
levelE[1] = e - incE;

double[] rootSumAnswers = new double[32];
int count = 0;

for(int i = 0; i < 2; i ++)
{
    for(int k = 0; k < 2; k++)
    {
        for(int j = 0; j < 2; j ++)
        {
            for(int n = 0; n < 2; n++)
            {
                for(int m = 0; m < 2; m++)
                {
                    rootSumAnswers[count++] = calcRootSum(levelA[i], levelB[k], levelC[j], levelD[n], levelE[m]);

                }
            }
        }
    }
}

//Finally, i find the minimum of my root sum squares and make that change permanent, and do this again.

Answer 1

You can produce a set containing all possible sets of operations (e.g. {-,-,-,-}, {-,-,-,+}, {-,-,+,-} etc.) using the following function which will output a list of bool arrays where true and false represent + and -. The vars parameter indicates the number of variables being combined. Note that for 5 variables, there are only 16 combinations (not 32 as you state) since there are only 4 operators when combining 5 variables (assuming the first variable cannot be negated):

public List<bool[]> GetOperators(int vars)
{
    var result = new List<bool[]>();

    for (var i = 0; i < 1 << vars-1; i++)
    {
        var item = new bool[vars - 1];
        for (var j = 0; j < vars-1; j++)
        {
            item[j] = ((i >> j) & 1) != 0;
        }
        result.Add(item);
    }
    return result;
}

Once you have this list, you can use it to combine the variables in all possible ways. First we define a helper function to take a set of variables and a single bool[] combination and applies it (it assumes that there are the correct number of elements in the combination for the number of variables passed):

private double Combine(double[] vars, bool[] combination)
{
    var sum = vars[0];
    for (var i = 1; i< vars.Length; i++)
    {
        sum = combination[i - 1] ? sum + vars[i] : sum - vars[i];
    }
    return sum;
}

You can also format the combination nicely using:

private string FormatCombination(double[] vars, bool[] combination)
{
    var result = vars[0].ToString("0.00##");
    for (var i = 1; i < vars.Length; i++)
    {
        result = string.Format("{0} {1} {2:0.00##}", result, combination[i - 1] ? "+" : "-", vars[i]);
    }
    return result;
}

Putting it all together to test all possible combinations:

var vars = new []
{
    1.23, // A
    0.02, // B1
    0.11, // B2
    0.05, // C1
    1.26  // C2
};

foreach (var combination in GetOperators(vars.Length))
{
    var combined = Combine(vars, combination);

    // Perform your operations on "combined" here...

    Console.WriteLine("{0} = {1}", FormatCombination(vars, combination), combined);
}

This will output:

1.23 - 0.02 - 0.11 - 0.05 - 1.26 = -0.21
1.23 + 0.02 - 0.11 - 0.05 - 1.26 = -0.17
1.23 - 0.02 + 0.11 - 0.05 - 1.26 = 0.01
1.23 + 0.02 + 0.11 - 0.05 - 1.26 = 0.05
1.23 - 0.02 - 0.11 + 0.05 - 1.26 = -0.11
1.23 + 0.02 - 0.11 + 0.05 - 1.26 = -0.07
1.23 - 0.02 + 0.11 + 0.05 - 1.26 = 0.11
1.23 + 0.02 + 0.11 + 0.05 - 1.26 = 0.15
1.23 - 0.02 - 0.11 - 0.05 + 1.26 = 2.31
1.23 + 0.02 - 0.11 - 0.05 + 1.26 = 2.35
1.23 - 0.02 + 0.11 - 0.05 + 1.26 = 2.53
1.23 + 0.02 + 0.11 - 0.05 + 1.26 = 2.57
1.23 - 0.02 - 0.11 + 0.05 + 1.26 = 2.41
1.23 + 0.02 - 0.11 + 0.05 + 1.26 = 2.45
1.23 - 0.02 + 0.11 + 0.05 + 1.26 = 2.63
1.23 + 0.02 + 0.11 + 0.05 + 1.26 = 2.67

---

Edit:

Per the changes to your question I have updated my answer. As others have mentioned, it may not be necessary to use a full search such as this, but you may find the method useful anyway.

GetOperators() changes slightly to return 2ⁿ combinations (rather than 2^n-1 as before):

public List<bool[]> GetOperators(int vars)
{
    var result = new List<bool[]>();

    for (var i = 0; i < 1 << vars; i++)
    {
        var item = new bool[vars];
        for (var j = 0; j < vars; j++)
        {
            item[j] = ((i >> j) & 1) != 0;
        }
        result.Add(item);
    }
    return result;
}

The Combine() method is changed to take a set of increments in addition to the variables and the combination to be used. For each element of the combination, if it is true, the increment is added to the variable, if it is false, it is subtracted:

private double[] Combine(double[] vars, double[] increments, bool[] combination)
{
    // Assuming here that vars, increments and combination all have the same number of elements
    var result = new double[vars.Length];
    for (var i = 0; i < vars.Length; i++)
    {
        result[i] = combination[i] ? vars[i] + increments[i] : vars[i] - increments[i];
    }

    // Returns an array of the vars and increments combined per the given combination
    // E.g. if there are 5 vars and the combination is: {true, false, true, true, false}
    // The result will be {var1 + inc1, var2 - inc2, var3 + inc3, var4 + inc4, var 5 - inc5}
    return result;
}

And FormatCombination() is also updated to display the new combination style:

private string FormatCombination(double[] vars, double[] increments, bool[] combination)
{
    var result = new List<string>(vars.Length);

    var combined = Combine(vars, increments, combination);

    for (var i = 0; i < vars.Length; i++)
    {
        result.Add(string.Format("{0:0.00##} {1} {2:0.00##} = {3:0.00##}", vars[i], combination[i] ? "+" : "-", increments[i], combined[i]));
    }
    return string.Join(", ", result.ToArray());
}

Putting it all together:

var vars = new[]
{
    1.23, // A
    0.02, // B
    0.11, // C
    0.05, // D
    1.26, // E
};

var increments = new[]
{
    0.04, // incA
    0.11, // incB
    0.01, // incC
    0.37, // incD
    0.85, // incD
};

foreach (var combination in GetOperators(vars.Length))
{
    var combined = Combine(vars, increments, combination);

    // Perform operation on combined here...

    Console.WriteLine(FormatCombination(vars, increments, combination));
}

Output (abridged):

1.23 - 0.04 = 1.19, 0.02 - 0.11 = -0.09, 0.11 - 0.01 = 0.10, 0.05 - 0.37 = -0.32, 1.26 - 0.85 = 0.41
1.23 + 0.04 = 1.27, 0.02 - 0.11 = -0.09, 0.11 - 0.01 = 0.10, 0.05 - 0.37 = -0.32, 1.26 - 0.85 = 0.41
1.23 - 0.04 = 1.19, 0.02 + 0.11 = 0.13, 0.11 - 0.01 = 0.10, 0.05 - 0.37 = -0.32, 1.26 - 0.85 = 0.41
1.23 + 0.04 = 1.27, 0.02 + 0.11 = 0.13, 0.11 - 0.01 = 0.10, 0.05 - 0.37 = -0.32, 1.26 - 0.85 = 0.41
...

Answer 2

Since my first answer was deleted since it was pseudocode instead of c#...I changed my abstract set into a stack...

I think a nice recursive approach works:

int FindBest(int increment, Stack<int> decided_vars, Stack<int> free_vars)
{
  if free_vars.size() == 0
  {
     return PerformCalculation(decided_vars);
  }

  int new_element = free_vars.Pop()
  new_element += increment;

  //check one case
  decided_vars.Push(new_element)
  int result1 = FindBest(increment, decided_vars, free_vars)

  //reset sets for second case
  decided_vars.Pop();
  new_element -= 2 * increment;
  decicded_vars.Push(new_element);
  int result2 = FindBest(increment, decided_vars, free_vars);

  //reset sets as they were to give back to parent
  decided_vars.Pop()
  free_vars.Push( new_element + increment )

  return max(result1, result2);
}

You can define PerformCalculation as the function you want to maximize/minimize.

Answer 3

A good method to optimize several parameters is the Nelder–Mead method or Downhill Simplex method. It "walks" through the parameter space in a quite natural way, without testing every permutation. See also Downhill Simplex method (with good graphics showing the principle).

I also found a code in C#; however, I didn't test it.