Optimization algorithms for finding the optimal settings in large search space

Question

I have $8$ independent variables, out of which:

• $6$ variables have $63$ states

• one variable has $200$ states

• one variable has $3$ states

Thus, in total, they create a search space of $63^6 \cdot 200 \cdot 3 \approx 32$ trillion. How can I find the optimal rows that minimize a custom objective function? Can we use combinatorial optimization algorithms? If so, what categories of algorithm, I need to look into for problems with such huge search spaces?

---

I am not much familiar in the field of optimization, but with some preliminary googling, I came across, google OR-tools, particularly constraints optimization. But, from my initial thoughts, I think it is bit hard to analytically describe my objective function. But, I haven’t tried it.

EDITED

This is how my objective function will look like.

$$\min y = x_1 - \frac{x_2-1}{x_1} + \frac{x_3-1}{x_1 x_2} - \frac{x_4-1}{x_1 x_2 x_3} + \frac{x_5-1}{x_1 x_2 x_3 x_4} - \frac{x_6-1}{x_1 x_2 x_3 x_4 x_5} + \frac{x_7-1}{x_1 x_2 x_3 x_4 x_5 x_6} - \frac{x_8-1}{x_1 x_2 x_3 x_4 x_5 x_6 x_7} $$

Constraints:

$$1\leq x_1\leq 200$$ $$1\leq x_2,x_3,x_4,x_5,x_6,x_7\leq 63$$ $$0\leq x_8\leq 2$$

$$0.01x_1+0.5(x_2+x_3+x_4+x_5+x_6+x_7)+15x_8=C$$

where $x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8$ are integers and $C$ is a constant.

So, from the above, I am guessing it mostly falls under MINLP or Constraints Optimization? But, in most of the online examples the objective functions are much simpler. Hence, what kind of algorithms is suitable for such complex objective functions?

Answer 1

"There is no free lunch": this applies also to optimization. You have to characterize your multi-variable objective function in order to get better algorithms than random picking.

You may want to look at:

• Linear or quadratic formulation, possibly after a change of variables: very effective softwares exist to deal with these cases. A typical combinatorial optimization problem such as TSP is actually best resolved by linear programming (with very elaborate models).
• Convexity, to get unicity of minimum, and allow methods such as interior-point.
• Symetries, to prune the search space.
• Monotone variation of function with regard to some variable.
• Simple lower bounds to the objective function, so that finding points with good (= low) objective value, enables to cut entire branches of the search tree, when it can be proven that they cannot contain a better result (branch-and-bound).
• etc.

Your search space is actually not that big: with a few orders of magnitude simplification, it may be reachable by exhaustive search. That depends also upon the time it takes to compute the objective function, and the computation hardware you have.

Another thing to consider is the problem context: usually some heuristics come to mind, relying on "physical" properties of the domain.

If the problem can be expressed as a sequence of choices, dynamic programming may be possible. You need to define a state that includes all necessary data to make further choices, and have a limited number of states. See knapsack problem as a typical example.

If there is no simplification, there are still elaborate algorithms to deal with. The general idea is to try a few combinations at random, then balance between exploration (of new zones in the search space) and exploitation (of the zones that have already given good results); MCTS (Monte-Carlo Tree Search) is an example.

If nothing goes or you do not have time to code algorithms, you may look at Black-Box optimization softwares: they apply all tricks of the trade for you. Well, not really: a good home made algorithm is usually vastly better, but it also takes vastly more time to code it, so that's a trade-off.

Answer 2

I would suggest that you consider an approach as follows:

Enumerate over all possible choices for $x_1,x_2,x_8$ (limiting $x_1$ to values such that $x_1-100C$ is a multiple of 50).

For each such value of $x_1,x_2,x_8$, use a black-box optimization method to minimize $y$, as a function of $x_3,\dots,x_7$. For instance, you might use local search methods (such as hill climbing or simulated annealing), or some other method such as projected gradient descent.

I expect this will likely get you a quite good approximation.

Why enumerate over all choices for $x_1,x_2,x_8$? I expect that $x_1,x_2$ have the greatest influence over $y$, so this approach amounts to enumerating over all possible values for the variables that have the greatest influence over $y$, and using a black-box optimization algorithm for the remaining variables.

Answer 3

I say just throw a good amount of computation at it.

In order for $C$ to be an integer, we must have $0.01 x_1$ be a multiple of $0.5$, therefore $x_1$ must be a multiple of $50$, so $x_1$ must be in the set $\{50, 100, 150, 200\}$. This means the size of your search space is actually $63^6 \cdot 4 \cdot 3 \approx 750$ billion.

Furthermore, we can infer that $\frac{x_1}{50}$ and $(x_2+x_3+x_4+x_5+x_6+x_7)$ must have the same parity, which might make it possible to cut the search space in half, leaving us with $\frac{1}{2} \cdot 63^6 \cdot 4 \cdot 3 \approx 375$ billion, which can be brute-forced in around 15 minutes using a consumer-grade 4-core computer (back of the envelope, assuming it’s possible to evaluate the function $10^8$ times per second per core).