-2
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Mar 12 at 18:42
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Mar 15 at 11:54
  • $\begingroup$ @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). $\endgroup$ Mar 15 at 16:39
  • 1
    $\begingroup$ It worked like a charm. Thank you! $\endgroup$ Mar 16 at 19:07

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