Which of the following represents the general form of a covering integer…
2025
Which of the following represents the general form of a covering integer program, as a generalization of set cover
- A.
Minimize C.x subject to Ax ≤ b, with all variables integral
- B.
Maximize Ax subject to C.x ≤ b, where x is binary
- C.
Minimize C.x subject to Ax ≥ b, where x is integral and non-negative
- D.
Minimize x subject to Aᵀx ≤ C with x ≥ 0
Attempted by 48 students.
Show answer & explanation
Correct answer: C
A covering integer program minimizes an objective function subject to constraints where the left-hand side must be greater than or equal to a right-hand side vector. Option 2 correctly specifies minimizing C.x subject to Ax >= b, which aligns with the standard definition of covering problems like set cover.