Originally posted by: SystemAdmin
Yes, this is a really well studied problem in the literature.
One has to distinguish between minimum and minimal cover. A minimal cover is an inclusion-wise minimal cover, i.e., a cover that is no longer a cover if you remove any single variable. A minimum cover is a cover that minimizes some objective function. If the objective function is linear with strictly positive for all coefficients, then every minimum cover is also minimal, but not vice versa.
Turning a cover into a minimal cover is trivial: you just sequentially remove every variable that can be removed without destroying the cover property. Of course, the resulting cover depends on the order of the variables, i.e., it is sequence dependent.
Calculating a minimum cover is harder, because this is the knapsack problem, which is NP hard. But in practice, for reasonably sized problems, a dynamic programming algorithm should be very efficient.
You can find some brief overview in my thesis "Constraint Integer Programming" in Chapter 8.1, and for more details look at the references that are mentioned there.
Tobias
#DecisionOptimization#MathematicalProgramming-General