title: searching for a dedicated binary linear programming algorithm
body: <p>There are various linear programming solvers out there, among which lpSolve or GLPK. These are general LP solvers that are suitable for many purposes, but is there a dedicated LP solver for the binary case?</p>
  
  <p>To exemplify, my problem involves finding the minimum number of lines that cover all columns of a matrix, something like:</p>
  
  <pre><code>0    1    0    1
  1    0    0    1
  1    0    1    0
  </code></pre>
  
  <p>It can be seen the first and third rows cover all four columns, the second row being irrelevant. Denoting the three lines as A, B and C, the problem boils down to solving a system of inequations:</p>
  
  <pre><code>B + C &gt;= 1
  A &gt;= 1
  C &gt;= 1
  A + B &gt;= 1
  </code></pre>
  
  <p>This gives the solution:
  A = 1; B = 0; C = 1</p>
  
  <p>(which means the minimum number of lines is 2).</p>
  
  <p>Thanks in advance,
  Adrian</p>