2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

You can use uniform-cost search in the space of possible combinations of operations. Each node will be an ordered list of operations performed. Terminate the search when the maximum memory or time allotment is reached.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ In general, a branch & bound algorithm may be efficient, i.e. if many sequences break the resource criteria. For that purpose, you'd want to sort the list to start with expensive operations. $\endgroup$ – Raphael Mar 9 '15 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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