  Sentence compression is an important problem in natural language processing
with wide applications in text summarization, search engine and human-AI
interaction system etc. In this paper, we design a hybrid extractive sentence
compression model combining a probability language model and a parse tree
language model for compressing sentences by guaranteeing the syntax correctness
of the compression results. Our compression model is formulated as an integer
linear programming problem, which can be rewritten as a Difference-of-Convex
(DC) programming problem based on the exact penalty technique. We use a
well-known efficient DC algorithm -- DCA to handle the penalized problem for
local optimal solutions. Then a hybrid global optimization algorithm combining
DCA with a parallel branch-and-bound framework, namely PDCABB, is used for
finding global optimal solutions. Numerical results demonstrate that our
sentence compression model can provide excellent compression results evaluated
by F-score, and indicate that PDCABB is a promising algorithm for solving our
sentence compression model.
