most recent 30 from http://mathoverflow.net 2013-05-18T19:24:34Z http://mathoverflow.net/feeds/question/43483 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/43483/how-to-solve-this-integer-programming-problem eakbas 2010-10-25T05:40:56Z 2010-10-25T16:03:35Z

<p>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: </p> <p>$\sum_{i=1}^N || A_{i} \vec{x_{i}}- A_{i+1} \vec{x}_{i+1} ||_2^2$</p> <p>$\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$. </p> <p>How can I tackle this problem? Any hints or resources? </p>

http://mathoverflow.net/questions/43483/how-to-solve-this-integer-programming-problem/43486#43486 eakbas 2010-10-25T06:14:14Z 2010-10-25T16:03:35Z

<p>I think I found a solution using Dijkstra's shortest path algorithm. I would appreciate if anybody could check my solution.</p> <p>Construct a graph as follows: </p> <ol> <li><p>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.</p></li> <li><p>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.</p></li> <li><p>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.</p></li> <li><p>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. </p></li> </ol>