Covering problems

In the context of linear programming, one can think of any minimization linear program as a covering problem if the coefficients in the constraint matrix, the objective function, and right-hand side are nonnegative.[1] More precisely, consider the following general integer linear program:

minimize	${\displaystyle \sum _{i=1}^{n}c_{i}x_{i}}$
subject to	${\displaystyle \sum _{i=1}^{n}a_{ji}x_{i}\geq b_{j}{\text{ for }}j=1,\dots ,m}$
	${\displaystyle x_{i}\in \left\{0,1,2,\ldots \right\}{\text{ for }}i=1,\dots ,n}$.

Such an integer linear program is called a covering problem if ${\displaystyle a_{ji},b_{j},c_{i}\geq 0}$ for all ${\displaystyle i=1,\dots ,n}$ and ${\displaystyle j=1,\dots ,m}$.

Intuition: Assume having ${\displaystyle n}$ types of object and each object of type ${\displaystyle i}$ has an associated cost of ${\displaystyle c_{i}}$. The number ${\displaystyle x_{i}}$ indicates how many objects of type ${\displaystyle i}$ we buy. If the constraints ${\displaystyle A\mathbf {x} \geq \mathbf {b} }$ are satisfied, it is said that ${\displaystyle \mathbf {x} }$ is a covering (the structures that are covered depend on the combinatorial context). Finally, an optimal solution to the above integer linear program is a covering of minimal cost.

There are various kinds of covering problems in graph theory, computational geometry and more; see Category:Covering problems. Other stochastic related versions of the problem can be found.[2]