Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
Would a call a formulation for a perfect matching sparse? You have variable for every edge, but for n vertices only about n/2 are different from zero in the output. –  Marcus Ritt Mar 26 '11 at 19:14
5  
That's an odd definition. I'd normally think of sparse IPs as those involving sparse constraint matrices. –  Suresh Venkat Mar 27 '11 at 1:34
    
Thank you Marcus and sorry for the late reply. I have actually checked the problem and it falls into the same category, I think that I will include it in my analysis. –  3ashmawy Mar 29 '11 at 8:21
2  
FWIW, it's known that zero-sum matrix games admit approximately optimal strategies that are sparse [LY94]. –  Neal Young Dec 2 '12 at 7:16
1  
FWIW, if you have an LP of the form $\min\{c\cdot x : Ax \ge b; x \ge 0\}$ or $\max\{c\cdot x : Ax \le b; x \ge 0\}$, where $A$ has $m$ constraints, a standard fact is that any basic feasible solution has at most $m$ non-zero entries e.g. [Lemma 1.13]. –  Neal Young Dec 2 '12 at 17:21

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
Thank you a lot for the formulation Yoshio. However there are problems such as portfolio optimization where even for large scale instances, the integer variables are mostly populated by 0s (k is significantly small compared to the problem size). This type of problem is not defined by a cardinality constraint and I am looking for some practical problems that have the same behavior. In your professional experience have you came across such problems ? –  3ashmawy Mar 29 '11 at 8:18
    
@3ashmawy: Would you give me more detail about what you refer to as portfolio optimization? There are a lot of models for portfolio optimization proposed in the literature. –  Yoshio Okamoto Mar 29 '11 at 12:59

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."

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.