Integer linear programs (ILPs) have been used to solve NP-hard decoding algorithms in NLP. They have been used in dependency parsing, coreference resolution, summarization, and many others. Often, ILP formulations are used to solve a decoding problem exactly before a specialized algorithm has been developed (for an example, see Smatch).

• EMNLP 2017 Tutorial: Paper
• Dan Roth slides

• Roth & Yih 2004 - A Linear Programming Formulation for Global Inference in Natural Language Tasks
• Martins et al 2009 - Concise Integer Linear Programming Formulations for Dependency Parsing
• Cai & Knight 2013 - Smatch: an Evaluation Metric for Semantic Feature Structures
• Banerjee et al 2016 - Multi-Document Abstractive Summarization Using ILP based Multi-Sentence Compression
  • Follow-up work (non ILP-based) here: 2017 - Multi-Document Abstractive Summarization using Chunk-graph and Recurrent Neural Network
• Li et al 2015 - Improving Update Summarization via Supervised ILP and Sentence Reranking

• Cao et al 2015 - Ranking with Recursive Neural Networks and Its Application to Multi-document Summarization Their best model uses an ILP decoder with RNN (see table 3)
• Lamm et al 2018 - Textual Analogy Parsing: What’s Shared and What’s Compared among Analogous Facts Their best model uses a neural CRF with an ILP decoder for prediction (table 3)
• Chousa et al 2020 - SpanAlign: Sentence Alignment Method based on Cross-Language Span Prediction and ILP
• Ning et al 2019 - An Improved Neural Baseline for Temporal Relation Extraction
• Gupta & Srinivasaraghavan 2020 - Explanation Regeneration via Multi-Hop ILP Inference over Knowledge Base

• Gurobi: Free Academic License, also Gurobi - Academia. Currently the best ILP solver
• CPLEX. Another good ILP solver