Concept-based Summarization using Integer Linear Programming: From Concept Pruning to Multiple Optimal Solutions

In concept-based summarization, sentence selection is modelled as a budgeted maxi-mum coverage problem. As this problem is NP-hard, pruning low-weight concepts is required for the solver to find optimal solutions efficiently. This work shows that reducing the number of concepts in the model leads to lower ROUGE scores, and more importantly to the presence of mul-tiple optimal solutions. We address these issues by extending the model to provide a single optimal solution, and eliminate the need for concept pruning using an approx-imation algorithm that achieves compara-ble performance to exact inference.