Video synopsis is a temporally compact representation of the original video, which facilitates the subsequent video processing, such as video storage, browsing and retrieval. Most of conventional methods easily lose some important objects and can not represent the original videos completely. Therefore, this paper proposes a novel method based on object trajectory optimization. The method extracts object trajectories using an improved multi-object tracking method, and optimizes the temporal shift labels of those trajectories. The optimal labels are then formulated as the maximum a posteriori state of a special Markov random field, which can be solved by the relaxed linear programming method. The synopsis video is obtained by integrating the optimal labels into the background sequence. Extensive experiments on both public and collected video sequences suggest that our method outperforms other methods in accuracy. In particular, our method can retain most essential information of the video sources in shorter synopsis videos.