# Efficient solver of a Integer programming

I am solving an Integer programming using MATLAB, yet the efficiency is low. Here is the problem:

Suppose $$v$$ is a $$N \times 1$$ vector. For $$v_i \in v$$, $$v_i \in \{0,1\}$$. $$D$$ is a 0-1 matrix, which means for each $$d_{ij} \in D$$, $$d_{ij} \in \{0,1\}$$.

The translation of this problem is to make element $$1$$ in $$v$$ to be as few as possible when the constraints are met. $$$$\begin{split} &\min \left\|\boldsymbol{v}\right\|_2 \\ &s.t.\ \begin{array}{c} D\boldsymbol{v} \ge \boldsymbol{1}\\ \end{array} \end{split} \label{eq:core_op}$$$$

Is there a good solver for this kind of problem in the field of optimization?

• Did you try with Gurobi? Jul 13 at 4:09
• @nicoguaro Will that be faster than MATLAB or Ceres? Jul 13 at 10:10
• Cplex is also one of the fastest solvers. What you can do aswell is to check if D is a totally unimodular matrix, because then the linear programming relaxation solves your IP.
– Pepe
Jul 13 at 11:29
• I don't know. It is a fast solver. You could give it a try. Jul 13 at 12:31
• This is a set covering problem, for which there's a huge literature. It's NP-Hard, so don't expect to find a solver that scales well to larger problems. Jul 26 at 19:54