  Sentence compression is an important problem in natural language processing.
In this paper, we firstly establish a new sentence compression model based on
the probability model and the parse tree model. Our sentence compression model
is equivalent to an integer linear program (ILP) which can both guarantee the
syntax correctness of the compression and save the main meaning. We propose
using a DC (Difference of convex) programming approach (DCA) for finding local
optimal solution of our model. Combing DCA with a parallel-branch-and-bound
framework, we can find global optimal solution. Numerical results demonstrate
the good quality of our sentence compression model and the excellent
performance of our proposed solution algorithm.
