3
$\begingroup$

Suppose I have 8 vectors: $v_1+v_2+...+v_8$. Assign coefficients to each vector: $S=a_1v_1+a_2v_2+...+a_8v_8$,

I want $S$ to be a resultant vector $\vec{R}$ of my choosing.

The problem is to find the minimal sum of coefficients such that the previous equation holds.

Let $C=\sum_{n=1}^{8}a_n$ and $a_1,a_2,...,a_8\in \mathbb{N\cup0}$

$v_1,v_2,...,v_8:S=R \wedge C=C_{min}$, Where $C_{min}$ is the minimum value of $C$ such that $S=R$.

Note the condition of the coefficients being nonnegative integers.

Example

: Say I have these vectors: $[1,2], [-1,2],[1,-2],[-1,-2],[2,1],[-2,1],[2,-1],[-2,-1]$ (These are actually representative of all the possible knight moves in chess.)

Let $a_1,a_2,...,a_8$ represent the number of each vector when added together (coefficient). Suppose I want the resultant vector to equal $[3,-3]. $

The optimal 'coefficient set' would be $\{0,0,1,0,0,0,1,0\}$. I.e. $a_1=0,a_2=0,a_3=1,...,a_8=0$. With $C=0+0+1+...+0=2$


Is there an analytical or at the very least a solution to this with a mathematical formula which can be computed numerically. (perhaps with multivariable calculus, linear algebra, etc.)?

OR if it doesn't seem possible, an efficient computational solution will suffice. Or at the very least an efficient method where the number of combinations to trial doesn't grow exponentially, so it can be trialled for large numbers?

If it is a numerical/brute force method, I want it to be reasonable for up to at least $\max(a_i)=100, i\in\{{1,2,...,8}\}$, (you don't need a maximum, but for my attempt, it meant that I could reduce the sample space).

My computational attempt: for a set maximum $\max(a_i)$, loop every combination of these and check the result to hence find which reach the target. Then I search for the one with the lowest $C$ value. As you may expect, the number of combinations grows exponentially. With $max(a_i)>=7$ being unviable.

$\endgroup$
13
  • $\begingroup$ You want the coefficients to be integers, but then you write they are in ${\bf N}\cup\{0\}$, so I guess you actually want them to be nonnegative integers. Then the following is guaranteed to work: first, try all the combinations with coefficients summing to one; then all with coefficients summing to two; and so on; stop when you get the resultant vector you want. Well, you didn't say you wanted an efficient method. $\endgroup$ Nov 4, 2019 at 8:50
  • 1
    $\begingroup$ This is an integer program. $\endgroup$ Nov 4, 2019 at 8:52
  • 1
    $\begingroup$ @GerryMyerson Ah. I will make an edit to the post. I tried a method like you mentioned but it blows up to too many combinations after about $\max{a}=9$. That is, 9^8 combinations (43 million). $\endgroup$
    – Simplex1
    Nov 4, 2019 at 10:14
  • 1
    $\begingroup$ How many coordinates do your vectors have ? $\endgroup$ Nov 7, 2019 at 6:54
  • $\begingroup$ @EwanDelanoy 2. It is an (x,y) vector. $\endgroup$
    – Simplex1
    Nov 7, 2019 at 7:31

1 Answer 1

2
$\begingroup$

As others have suggested, you can solve the problem via integer linear programming (ILP). Let $v_n^i$ be the $i$th component of vector $v_n$, and let $R^i$ be the $i$th component of $R$. With the decision variables $a_n$ that you defined, the problem is to minimize $\sum_n a_n$ subject to: \begin{align} \sum_n v_n^i a_n &= R^i &&\text{for all $i$}\\ a_n &\in \mathbb{N} &&\text{for all $n$} \end{align} You can use any ILP solver to find the optimal values, without artificially putting upper bounds on $a_n$.

Here is SAS code to solve your sample instance:

proc optmodel;
   set DIMS = 1..2;
   num r {DIMS} = [3,-3];
   set VECTORS = 1..8;
   num v {VECTORS, DIMS} = [1,2,−1,2,1,−2,−1,−2,2,1,−2,1,2,−1,−2,−1];

   var A {VECTORS} >= 0 integer;
   min Z = sum {n in VECTORS} A[n];
   con C {i in DIMS}:
      sum {n in VECTORS} v[n,i] * A[n] = r[i];

   solve;
   print A;
quit;

I get an optimal objective value of 2, achieved by $a=(0, 0, 1, 0, 0, 0, 1, 0)$.

$\endgroup$
1
  • $\begingroup$ This is the obvious answer. $\endgroup$ Nov 7, 2019 at 14:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .