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?

  • $\begingroup$ How are the variables defined ? $x_i \in \mathbb R \ \ \forall i$ or $x_i \geq 0 \ \ \forall i$ ? $\endgroup$ – callculus Jul 4 '14 at 22:20
  • $\begingroup$ Variables are non-negative, so $x_i \geq 0$. $\endgroup$ – 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.

In my understanding, you have two alternatives:

  • 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)

  • you can follow nonlinear global optimization approaches.

You can look at http://www.math.unipd.it/~rinaldi/papers/thesis0.pdf and the references therein.

  • $\begingroup$ thank you, I found in that thesis the exact formulation of my problem, and some references about it. It is truly NP-hard, and the number of variables in my problem is not small, but maybe I can try something. $\endgroup$ – zeycus Jul 5 '14 at 8:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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