Approximation schemes for covering and packing mixed-integer programs with a fixed number of constraints

This paper presents an algorithmic study of a class of covering mixed-integer linear programming problems which encompasses classic cover problems, including multidimensional knapsack, facility location and supplier selection problems. We first show some properties of the vertices of the associated polytope, which are then used to decompose the problem into instances of the multidimensional knapsack cover problem with a single continuous variable per dimension. The proposed decomposition is used to design a polynomial-time approximation scheme for the problem with a fixed number of constraints. To the best of our knowledge, this is the first approximation scheme for such a general class of covering mixed-integer programs. Moreover, we design a fully polynomial-time approximation scheme and an approximate linear programming formulation for the case with a single constraint. These results improve upon the previously best-known 2-approximation algorithm for the knapsack cover problem with a single continuous variable. Finally, we show a perfect compact formulation for the case where all variables have the same lower and upper bounds. Analogous results are derived for the packing and assignment variants of the problem.