# Almost linear programming problem

I have a problem that is almost the typical in linear programming, but not quite. All variables take real non-negative values. Certain simple linear inequalities and equalities should hold. But what does not fit (at least, at first) the typical LP problem is the goal: I want to minimize the number of variables taking strictly positive values.

Is there a trick to handle this as a simple LP problem? Should this be done with mixed integer linear programming? If not, how would you try to solve it?

• How are the variables defined ? $x_i \in \mathbb R \ \ \forall i$ or $x_i \geq 0 \ \ \forall i$ ? – callculus Jul 4 '14 at 22:20
• Variables are non-negative, so $x_i \geq 0$. – zeycus Jul 5 '14 at 8:26

Your problem is actually to minimize $||x||_0$, the so call zero-norm. In general is an NP-Hard problem, so as you said only resemble linear programming in the fact you have linear constraints.
• you can use binary variables to model the $x$ being zero o not. This is widely use for instance in the unit commitment problem (I guess it is referred to as semi-continuous variables)