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{equation} \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} \end{equation}

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

  • $\begingroup$ Did you try with Gurobi? $\endgroup$
    – nicoguaro
    Jul 13 at 4:09
  • $\begingroup$ @nicoguaro Will that be faster than MATLAB or Ceres? $\endgroup$
    – Frank
    Jul 13 at 10:10
  • $\begingroup$ 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. $\endgroup$
    – Pepe
    Jul 13 at 11:29
  • $\begingroup$ I don't know. It is a fast solver. You could give it a try. $\endgroup$
    – nicoguaro
    Jul 13 at 12:31
  • $\begingroup$ 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. $\endgroup$ Jul 26 at 19:54

Your Answer

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

Browse other questions tagged or ask your own question.