|
I am studying the properties of sparse integer programming problems, Would like to know if there are any interesting known problems of that type ? I would define sparse problems as problems that have their output mostly populated by zero values. Thank you |
|||||||||||||||||
|
|
Probably, this is not an intended answer. The sparsity constraint can be naturally represented in integer programming. (1) For the binary integer programming (the variables take only values 0 and 1), an extra constraint that "the sum of variables is at most $k$" leads to a solution with at most $k$ non-zeros. (2) If your problem is not binary and each variable takes the value in $\{0,\ldots,M\}$, then for each variable $x_i$ we introduce another 0/1 variable $y_i$, and give an extra constraint as $y_i \leq x_i \leq M y_i$. This means that $y_i=0$ if and only if $x_i=0$, so the sparsity can be described by means of $y$. Namely, we introduce the sparsity constraint $\sum y_i \leq k$ as (1) above. I'm imagining you're to look at an analogue of linear programming (or convex programming) with sparsity constraint to integer programming. However, linear programming with sparsity constraint is no longer linear programming, while integer programming with sparsity constraint is still integer programming (as described above). Their natures are totally different. Or, if you need some "interesting" examples, I would say "any combinatorial optimization problem with cardinality constraint". That's almost equivalent to a binary integer programming with the constraint that the sum of variables is at most a certain number. |
|||||
|
|
You can exhaustively guess all possible sets of non-zero variables and then solve the resulting integer programs to optimality (this is a famous result of Lenstra), so there should be an O(n^(constant+k))-time algorithm. This works even without getting the hairy big-M constraints, e.g. if no upper bound on the variables is known. If it's a maximization problem, you could extend this to get an alpha-approximation in O(n^(constant+k/alpha)) time since it's enough to guess the k/alpha most profitable nonzero variables. I have a paper with a coauthor called "Approximability of Sparse Integer Programs" but this refers to the notion of sparseness identified by Suresh above. I guess I would call the version you want a "sparse-solution integer program." |
|||
|
|
