1
$\begingroup$

I'm looking for the name of the problem stated below or, if available, even the algorithm to solve it. This is a hypothetical idea of mine, I don't actually have the necessary data to implement it. But I like the algorithm challenge behind it and would like to know more about it. I just can't find the name of the problem to look for further information on it.

I have the idea to build a search for computer builds that are dynamically generated from components. So the database knows that there are CPUs, Motherboards, RAMs etc and how these components can work together (e.g. an Intel 10th gen cpu can only work with specific motherboards). Based on that it can generate a complete build, it combines a CPU with a fitting motherboard, adds some compatible RAM, and a PSU with enough power to run the whole thing, tadaa a computer build. There would be very many such builds since you can combine the same cpu with many other motherboards, RAMs and PSUs. To limit the results, the user should be able to search based on some parameters and get complete computer builds suggested. For example if he searches for a computer that has a specific Motherboard, then the result only contains Builds with that motherboard and compatible CPUs/RAMs. Now he can further limit the total power consumption of the build to say 300 W and then the result has to contain all combinations of the given Motherboard with CPUs/RAMs that do not use more than the given amount of power. e.g. RAM r may not be possible with CPU c but with CPU d, because d uses less power.

Brute force searching this would require to calculate all the possible builds which can be very many. I can improve on this a bit by using backtracking. I would like to have the name of this problem class to search for other solutions on the internet. Thank you.

Improve this question
$\endgroup$
7
  • $\begingroup$ (limit the total power consumption the "single figure of merit" of gates used to be energy: power×delay time. Energy benchmarks for IT systems popped up in the late noughties.) $\endgroup$
    – greybeard
    Commented Jun 28, 2021 at 14:44
  • $\begingroup$ @greybeard I'm sorry, I don't understand what you mean? Is unclear what I mean by power consumption? $\endgroup$
    – findusl
    Commented Jun 28, 2021 at 15:32
  • 1
    $\begingroup$ How do you specify the compatibilities? Do you know for every pair of components if they are compatible or incompatible? $\endgroup$
    – Vincenzo
    Commented Jun 28, 2021 at 15:39
  • $\begingroup$ @Vincenzo I don't have the data so that is free to be done as required. Is it important for the general problem statement? I would imagine each item has some general tag, say intel 10th generation and then the other items are compatible with those tags. but some items are just compatible with any other item, like a PSU is compatible with any CPU as long as it gives enough power. $\endgroup$
    – findusl
    Commented Jun 28, 2021 at 15:45
  • $\begingroup$ @greybeard I have to admit I don't understand what you mean. I want to limit the amount of electrical power the build consumes, then I chose electrical power as the unit. Why would I chose energy? $\endgroup$
    – findusl
    Commented Jun 28, 2021 at 16:00

1 Answer 1

Reset to default
1
$\begingroup$

In full generality (no/little compatibility restrictions), this means you have to explore all possible combinations. The time to do that will be huge if there are many classes of components with many alternatives each.Your best bet is to order the component classes in some way, and then use a backtracking type search to explore the alternatives. It doesn't look like you can use some way to divide the subtasks into independent parts and apply e.g. dynamic programming, but perhaps you can split it into partial tasks (e.g. CPU/motherboard, GPU, storage subsystem, ...) and solve the parts separately.

  • Order the component clases in order of increasing compatibility with the next type, so as to narrow down the search tree early
  • Use heuristics, i.e., order each component class by some measure of how likely they are to satisfy the overall goal
  • See how to to evaluate (or at least bound) your overall goal for incomplete designs, so you can abort a branch of the search early if it can't be fulfilled (if optimizing, perhaps use branch and bound).
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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