3
$\begingroup$

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?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user3680510 Sep 22 '20 at 10:09
  • $\begingroup$ 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. $\endgroup$ – Qian Zhang Sep 23 '20 at 3:48

Your Answer

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

Browse other questions tagged or ask your own question.