Integer Linear Programming

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
• Riedel & Clark 2009 - Revisiting Optimal Decoding for Machine Translation IBM Model 4 Optimal decoding for IBM model 4 using an ILP
• 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
• 2018 - Multi-Sentence Compression with Word Vertex-Labeled Graphs and Integer Linear Programming

• 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)
• Ning et al 2019 - An Improved Neural Baseline for Temporal Relation Extraction, using the ILP from Ning et al 2017 - A Structured Learning Approach to Temporal Relation Extraction
• Chousa et al 2020 - SpanAlign: Sentence Alignment Method based on Cross-Language Span Prediction and ILP
• Gupta & Srinivasaraghavan 2020 - Explanation Regeneration via Multi-Hop ILP Inference over Knowledge Base
• Saha et al 2020 - PRover: Proof Generation for Interpretable Reasoning over Rules
• Sun et al 2021 - Probabilistic Graph Reasoning for Natural Proof Generation

• Not every problem solvable in polynomial-time has a compact extended ILP formulation (see Yannakakis’ problem, section 4.10.3, page 181 of Integer Programming by Conforti et al).

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

(Search “integer linear programming slides pdf” on Google)

• Ziko Kolter - Integer Linear Programming
• Tutorial at EACL 2017
• Integer Linear Programming at Duke
• MIT Sloan - ILP Lecture
• ILP Slides

• Structured Prediction Energy Networks