The task of aligning corresponding phrases across two related sentences is an important component of approaches for natural language problems such as paraphrase detection, textual inference and text-to-text generation. In this work, we examine a state-of-the-art structured prediction model for this task which uses a phrase-based representation and is forced to decode alignments using approximate search. We propose instead a straightforward exact decoding solution based on integer linear programming that yields order-of-magnitude improvements in decoding speed while further improving alignment performance. This decoding strategy permits us to consider syntactic constraints which significantly increase the precision of the model.