I have a sequence of matrices $\lbrace A\_i \rbrace\_{i=1}^N$ and I want to select a column from each of these matrices so that the following sum is minimized: 


$\sum\_{i=1}^N || A\_{i} \vec{x\_{i}}- A\_{i+1} \vec{x}\_{i+1} ||\_2^2$


$\vec{x}\_i$ is a binary vector which selects a column of $A\_i$. Formally: $x\_{ij} \in \lbrace 0,1 \rbrace$ for $\forall i, j$ and $\sum\_j x\_{ij} = 1$ for $\forall i$. 


How can I tackle this problem? Any hints or resources? 



How to solve this integer programming problem? 
I think I found a solution using Dijkstra's shortest path algorithm. I would appreciate if anybody could check my solution.


Construct a graph as follows: 


1. Create a starting node $s$ and connect it to each column of $A\_1$. The cost of these connections are all the same and equal to some arbitrary constant.
2. Create a terminal node $t$ and connect it to each column of $A\_N$. The cost of these connections are all the same and equal to some arbitrary constant.
3. Connect the $j^{th}$ column of $A\_i$ to the $k^{th}$ column of $A\_{i+1}$ with a cost of $|| A\_i \vec{y\_i} - A\_{i+1}\vec{y}\_{i+1}||\_2^2$ where $\vec{y\_i}$ is all zeros except its $j^{th}$ element, and $\vec{y}\_{i+1}$ is all zeros except its $k^{th}$ element.
4. Compute the shortest path between $s$ and $t$. Then, it is trivial to determine $\vec{x\_i}$s from the selected nodes in the solution.


