# How to find all covers and minimal covers?

Consider a constraint of type $$c_1x_1+c_2x_2+\cdots+c_nx_n\leq C$$ with $$x_i$$ binary.

We call a cover a subset of the $$n$$ indices such that the sum of the corresponding coefficients is higher than the right-hand-side $$C$$. A cover is minimal if, by removing an index of the cover, it is not a cover anymore.

Question: what is a general procedure for finding all covers and all minimal covers?

• For what reason do you want to know them? The covers can simply be enumerated by chosing a subset of the elements and verfiying that the weights are larger than the right-hand-side, but this no practical procedure since there are exponentiel many covers in general. – user3680510 Sep 22 '20 at 10:09
• I don't have an answer for a non-enumeration based methods for finding all covers or all minimal covers. But if you just need to find one minimal cover that violated by a LP relaxed solution or prove that none such minimal cover exists, then there are some fast heuristics for that. – Qian Zhang Sep 23 '20 at 3:48