# Enumerate all combinations of operations that fit memory and time criteria

I have the following problem:

$x$ is the number of operations I have to perform.

$O=\{o_1,o_2,\ldots o_n\}$ is the set of possible operations.

I know beforehand the cost in terms of time and memory of every operation $o_i \in O$.

I have a limited amount of memory and computation time, $M$ and $T$ respectively.

What is the most efficient way to generate the list of computable combinations? i.e. I need to generate a set of computables $C=\{c_1,c_2,\ldots c_m\}$ such as:

• $\forall c_i \in C, c_i$ is a combination (with possible repetition) of $O$ and $|c|=x$
• $\forall c_i \in C$ the memory and time consumption should be less than $M$ and $T$ respectively.

I think this is an operations research problem, but I can be wrong. If so, what branch of operations research? If not, then what is the most suitable approach?

There are exponentially many possible sequences of operations ($n^x$, in the worst case). Therefore, in general, there is no efficient algorithm to compute the list of all sequences of operations. The problem can be solved in a feasible amount of time only if $x$ is small. If $x$ is very small, just enumerate all sequences of length $x$. As a special case, if the first $j$ in the sequence have a total time usage greater than $T$, you can ignore all sequences starting with that prefix. As Raphael says, a branch & bound algorithm may be efficient, if many sequences break the resource criteria. For that purpose, you'd want to sort the list to start with expensive operations.