<p>Rephrasing in matrix form as I understand it, you would like to select the columns of a given matrix that add to the given &quot;target&quot; vector, which can be reduced to solving a linear system with binary variables, which can be written as an <strong>integer program</strong> (IP).</p>
<p><span class="math-container">$$\begin{array}{ll} \underset{\mathrm x \in \mathbb Z^n}{\text{minimize}} &amp; 0\\ \text{subject to} &amp; \mathrm A \mathrm x = \mathrm b\\ &amp; \mathbb 0_n \leq \mathrm x \leq \mathbb 1_n\end{array}$$</span></p>
<p>where <span class="math-container">$m \times n$</span> matrix <span class="math-container">$\rm A$</span> and <span class="math-container">$m$</span>-vector <span class="math-container">$\rm b$</span> are given. In the example you gave, <span class="math-container">$m=4$</span> and <span class="math-container">$n=5$</span>.</p>
<p>Using Python:</p>
<pre><code>import cvxpy as cp
import numpy as np

A = np.array([( 0, 2, 1, 1, 5),
              ( 0, 1, 1, 4, 2),
              ( 0, 0, 1, 0, 5),
              ( 1, 0, 1, 3, 2)])

b = np.array([( 2),
              ( 5),
              ( 1),
              ( 5)])

# optimization variables
x = cp.Variable(5, integer=True)

# create optimization problem
prob = cp.Problem(cp.Minimize(0),
                  [ A @ x == b, np.zeros(5) &lt;= x, x &lt;= np.ones(5) ])

# solve optimization problem
solution = prob.solve()

print(&quot;Solution = &quot;, x.value)
</code></pre>
<p>which outputs the following</p>
<pre><code>Solution = [1. 0. 1. 1. 0.]
</code></pre>
<p>Thus, to obtain the &quot;target&quot; vector exactly, just add the 1st, 3rd and 4th columns, as you mentioned. If you want an approximation, you probably want to use Boolean least-squares.</p>

CC BY-SA 4.0
2021-03-15T11:54:30.933Z
Thank you very much @Rodrigo. I confirm that the script works and it is what I was looking for, CVXPY looks very powerful indeed. However, the script returns `Solution = None` when the problem is infeasible. How can I get the closest solution to the target `b`?
Enric Moreu
CC BY-SA 4.0
2021-03-15T16:39:23.767Z
@EnricMoreu To get the closest solution, try to remove the equality constraint and minimize the $1$-norm of the error vector via `cp.minimize( norm(A @ x - b, 1) )`. Let me know if this works (or not).
Rodrigo de Azevedo
CC BY-SA 4.0
2021-03-16T19:07:45.037Z
It worked like a charm. Thank you!
Enric Moreu
CC BY-SA 4.0
2021-03-14T01:29:47.700Z
2021-03-14T01:59:50.940Z
2021-03-14T01:59:50.940Z
Rodrigo de Azevedo
<p>Given a target list</p>
<pre><code>a = [2,4,1,4]`
</code></pre>
<p>and a list of lists</p>
<pre><code>b = [[0,0,0,1],
     [2,1,0,0],
     [1,0,1,1],
     [1,4,0,3],
     [5,2,5,2]]`
</code></pre>
<p>how can I find a combination of lists that approximates the target list when added together?</p>
<p>E.g., in this case <code>b[0] + b[2] + b[3]</code> is the optimal combination because it matches <code>a</code>.</p>

CC BY-SA 4.0
2021-03-12T18:42:58.797Z
This is NP-hard; see set cover and exact cover.  It is also not clear what you mean by "approximate"; that needs a formal definition.  In any case, this does not appear to be a research-level question in theoretical CS, so it appears to be off-topic here.
D.W.
<co.combinatorics>
Subset sum for lists
Enric Moreu
# Subset sum for lists

(Asked by: username_0 on 2021-03-12)

Given a target list
a = [2,4,1,4]`

and a list of lists
b = [[0,0,0,1],
     [2,1,0,0],
     [1,0,1,1],
     [1,4,0,3],
     [5,2,5,2]]`

how can I find a combination of lists that approximates the target list when added together?
E.g., in this case b[0] + b[2] + b[3] is the optimal combination because it matches a.

**Tags:** co.combinatorics
> **Comments:**
> **username_1**: This is NP-hard; see set cover and exact cover.  It is also not clear what you mean by "approximate"; that needs a formal definition.  In any case, this does not appear to be a research-level question in theoretical CS, so it appears to be off-topic here.  

---

## 1 answers

### Answer by username_2 on 2021-03-14. Score: 0 | Accepted answer

Rephrasing in matrix form as I understand it, you would like to select the columns of a given matrix that add to the given "target" vector, which can be reduced to solving a linear system with binary variables, which can be written as an integer program (IP).
$$\begin{array}{ll} \underset{\mathrm x \in \mathbb Z^n}{\text{minimize}} & 0\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & \mathbb 0_n \leq \mathrm x \leq \mathbb 1_n\end{array}$$
where $m \times n$ matrix $\rm A$ and $m$-vector $\rm b$ are given. In the example you gave, $m=4$ and $n=5$.
Using Python:
import cvxpy as cp
import numpy as np

A = np.array([( 0, 2, 1, 1, 5),
              ( 0, 1, 1, 4, 2),
              ( 0, 0, 1, 0, 5),
              ( 1, 0, 1, 3, 2)])

b = np.array([( 2),
              ( 5),
              ( 1),
              ( 5)])

# optimization variables
x = cp.Variable(5, integer=True)

# create optimization problem
prob = cp.Problem(cp.Minimize(0),
                  [ A @ x == b, np.zeros(5) <= x, x <= np.ones(5) ])

# solve optimization problem
solution = prob.solve()

print("Solution = ", x.value)

which outputs the following
Solution = [1. 0. 1. 1. 0.]

Thus, to obtain the "target" vector exactly, just add the 1st, 3rd and 4th columns, as you mentioned. If you want an approximation, you probably want to use Boolean least-squares.

> **Comments:**
> **username_0**: Thank you very much @Rodrigo. I confirm that the script works and it is what I was looking for, CVXPY looks very powerful indeed. However, the script returns `Solution = None` when the problem is infeasible. How can I get the closest solution to the target `b`?  
> **username_2**: @EnricMoreu To get the closest solution, try to remove the equality constraint and minimize the $1$-norm of the error vector via `cp.minimize( norm(A @ x - b, 1) )`. Let me know if this works (or not).  
> **username_0**: It worked like a charm. Thank you!  

---

