Minimum-Length Trace Reconstruction via Integer Programming

We propose a new perspective for solving the trace-reconstruction problem. In this problem, multiple traces (or subsequences) are independently sampled from an unknown integer sequence. The goal is to find the shortest sequence that agrees with all traces. Our primary result is that this problem can be efficiently solved with an Integer Programming model under some mild assumptions. We introduced two sets of valid inequalities to further speed up the optimization process. We also compare our algorithm with classic depth-first searching. Through the experimental results, our algorithm shows a dramatic speed and efficiency advantage over DFS.