Im looking for an algorithm that can solve or approximate the solution to a problem

Question

Let me first explain the problem using an analogy.

Let's say you have $N$ doors and $M$ keys. Each door can be opened with a combination of keys, each combination is also unique (i.e. there aren't be two doors that are opened with same combination).
For example, to open Door $1$ you need $3$ keys: $A, B$ and $C$. For Door $2$ you need $5$ keys: $C, F, G, E$ and $T$. All doors are accessible (there are no doors behind a door).

Now the question is: can you chose $k$ keys, $k < M$, so that combination of keys lets you open the maximum number doors respect to any other combination of $k$ keys and, if the answer to this question is affirmative, which keys should be picked?

This kind of problem can't be solved by exhaustion since, in my case, there are $100$ keys and just generating all combinations would take centuries (there would be around $5.5\cdot 10^{20}$ combinations if $k=20$).

Im not too knowledgeable in algorithms, but this seems like some kind of constraint satisfaction problem but not exactly. Anyway I'm kind of stuck. If I could just figure out what kind of problem this is and what its called I might just be able to solve this thing in less than a century.

Answer 1

You can solve this problem via integer linear programming. Let binary decision variable $x_i$ indicate whether you can open door $i$, and let binary decision variable $y_j$ indicate whether you select key $j$. The problem is to maximize $\sum_{i=1}^N x_i$ subject to \begin{align} \sum_{j=1}^M y_j &= k \\ x_i &\le y_j &&\text{if door $i$ requires key $j$}\\ x_i &\in \{0,1\} &&\text{for $i\in\{1,\dots,N\}$}\\ y_j &\in \{0,1\} &&\text{for $j\in\{1,\dots,M\}$} \end{align} By request, here's the SAS code (with more descriptive variable names than x and y) that I used to solve the sample instance:

proc optmodel;
   /* declare parameters and read data */
   set <str> RECIPES;
   read data lib.doors into RECIPES=[var1];
   num numIngredients_r {r in RECIPES} = countw(r,',;');
   set INGREDIENTS_r {r in RECIPES} = setof {k in 1..numIngredients_r[r]} scan(r,k,',;');
   set INGREDIENTS = union {r in RECIPES} INGREDIENTS_r[r];

   /* declare decision variables */
   var UseIngredient {INGREDIENTS} binary;
   var SelectRecipe {RECIPES} binary;

   /* declare objective */
   max NumSelectedRecipes = sum {r in RECIPES} SelectRecipe[r];

   /* declare constraints */
   con Cardinality:
      sum {i in INGREDIENTS} UseIngredient[i] = 200;
   con RecipeImpliesIngredient {r in RECIPES, i in INGREDIENTS_r[r]}:
      SelectRecipe[r] <= UseIngredient[i];

   /* call MILP solver */
   solve;

   /* output solution */
   create data SolutionIngredients from [i]={i in INGREDIENTS: UseIngredient[i].sol > 0.5};
   create data SolutionRecipes from [r]={r in RECIPES: SelectRecipe[r].sol > 0.5};
quit;

Note that the UNION set operator avoids reading a separate ingredients file, and so I did not need to exclude any data. The resulting optimal solution for 200 ingredients yields 1345 recipes.

Answer 2

Your problem definition is somewhat unclear: how can "the answer to this question" not be affirmative, since for every $k$ there will be some maximum number of doors that can be opened with $k$ keys?

If I understand correctly, your problem is: "Given the set of keys necessary to open each door and an integer $k$, what is the maximum number of doors you can open with $k$ keys"? This problem is NP-hard, even when each door requires exactly two keys. Indeed, this special case is the densest $k$-subgraph problem: given a graph, find a set of $k$ vertices with maximum induced number of edges. Each vertex in the graph is a "key" and each edge is a "door" requiring two keys. The best approximation factor known to be achievable in polynomial time is $O(M^{1/4+\epsilon})$, for arbitrarily small $\epsilon > 0$:

https://dl.acm.org/citation.cfm?doid=1806689.1806719

This result does not directly apply to your problem because in your setting, doors may require more than two keys, but it is surely worth looking into.

As an aside, if you were interested instead in finding the largest possible ratio between the number of doors opened and the number of keys necessary to open them, then your problem would become polynomial-time solvable (using techniques similar to those used for the densest subgraph problem, with no restriction on the size of the subgraph). See, e.g., Lemma 4 in the following paper:

https://arxiv.org/pdf/1802.02562.pdf

Answer 3

This problem is known as the Minimum k-Union problem. Let $D_j$ be the set of doors requiring the key $j$, then we need to pick a set of keys $T$ with $|T|=M-k$ minimizing the size of $\bigcup_{j\in T} D_j$. The answer to OP's question is given by the complement of $T$.

This problem is known to be NP-hard, and the exists an $O(n^{0.25+\epsilon})$-approximation algorithm - see https://stackoverflow.com/questions/12424155