<p>Probably, this is not an intended answer.  The sparsity constraint can be naturally represented in integer programming. </p>

<p>(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.</p>

<p>(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. </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-03-29T08:18:19.703Z
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
CC BY-SA 2.5
2011-03-29T12:59:28.553Z
@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
CC BY-SA 2.5
2011-03-27T18:46:14.507Z
2011-03-27T18:46:14.507Z
Yoshio Okamoto
<p>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.</p>

<p>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. </p>

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

CC BY-SA 3.0
2012-12-02T05:01:09.260Z
2012-12-02T05:01:09.260Z
daveagp
<p>I am studying the properties of sparse integer programming problems, Would like to know if there are any interesting known problems of that type ?</p>

<p>I would define sparse problems as problems that have their output mostly populated by zero values.</p>

<p>Thank you </p>

CC BY-SA 2.5
2011-03-26T19:14:32.230Z
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
CC BY-SA 2.5
2011-03-27T01:34:12.073Z
That's an odd definition. I'd normally think of sparse IPs as those involving sparse constraint matrices.
Suresh Venkat
CC BY-SA 2.5
2011-03-29T08:21:29.623Z
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
CC BY-SA 3.0
2012-12-02T07:16:58.233Z
FWIW, it's known that zero-sum matrix games admit *approximately* optimal strategies that are sparse [[LY94](http://scholar.google.com/scholar?cluster=3566670601422099115&hl=en&as_sdt=0,5)].
Neal Young
CC BY-SA 3.0
2012-12-02T17:21:07.263Z
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](http://web.williams.edu/Mathematics/sjmiller/public_html/416/currentnotes/LinearProgramming.pdf)].
Neal Young
<ds.algorithms><reference-request><linear-programming><integer-programming>
Known sparse integer programming problems
3ashmawy
# Known sparse integer programming problems

(Asked by: username_0 on 2011-03-26)

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

**Tags:** ds.algorithms, reference-request, linear-programming, integer-programming

> **Comments:**
> **username_1**: 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.  
> **username_2**: That's an odd definition. I'd normally think of sparse IPs as those involving sparse constraint matrices.  
> **username_0**: 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.  
> **username_3**: FWIW, it's known that zero-sum matrix games admit *approximately* optimal strategies that are sparse [[LY94](http://scholar.google.com/scholar?cluster=3566670601422099115&hl=en&as_sdt=0,5)].  
> **username_3**: 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](http://web.williams.edu/Mathematics/sjmiller/public_html/416/currentnotes/LinearProgramming.pdf)].  

---

## 2 answers

### Answer by username_4 on 2011-03-27. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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 ?  
> **username_4**: @username_0: 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.  

---

### Answer by username_5 on 2012-12-02. Score: 1

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


---

