====== 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 [[https://www.isi.edu/natural-language/amr/smatch-13.pdf|Smatch]]).

===== Overviews =====
  * EMNLP 2017 Tutorial: [[https://www.aclweb.org/anthology/E17-5005.pdf|Paper]]
  * [[http://www.cis.upenn.edu/~danroth/Teaching/CIS-700-006/slides/17-Lec8-inference-applications.pptx|Dan Roth slides]]

===== Papers =====
  * [[https://www.aclweb.org/anthology/W04-2401.pdf|Roth & Yih 2004 - A Linear Programming Formulation for Global Inference in Natural Language Tasks]]
  * [[https://www.aclweb.org/anthology/P09-1039.pdf|Martins et al 2009 - Concise Integer Linear Programming Formulations for Dependency Parsing]]
  * [[https://www.aclweb.org/anthology/N09-2002.pdf|Riedel & Clark 2009 - Revisiting Optimal Decoding for Machine Translation IBM Model 4]] Optimal decoding for IBM model 4 using an ILP
  * [[https://www.isi.edu/natural-language/amr/smatch-13.pdf|Cai & Knight 2013 - Smatch: an Evaluation Metric for Semantic Feature Structures]]
  * [[https://arxiv.org/pdf/1609.07034.pdf|Banerjee et al 2016 - Multi-Document Abstractive Summarization Using ILP based Multi-Sentence Compression]]
    * Follow-up work (non ILP-based) here: [[https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7996331&casa_token=jZ-HBJM84t8AAAAA:-ACITeV2f0qoh8_p44VRZf2pchYpYNqYSq80lVkittMfd3xF_zHTLYdvyxtAjegvIJ25DKWQ&tag=1|2017 - Multi-Document Abstractive Summarization using Chunk-graph and Recurrent Neural Network]]
  * [[https://www.aclweb.org/anthology/N15-1145.pdf|Li et al 2015 - Improving Update Summarization via Supervised ILP and Sentence Reranking]]
  * [[https://www.aclweb.org/anthology/W18-1704.pdf|2018 - Multi-Sentence Compression with Word Vertex-Labeled Graphs and Integer Linear Programming]]


===== Neural Papers =====
  * [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.713.2787&rep=rep1&type=pdf|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)
  * [[https://www.aclweb.org/anthology/D18-1008.pdf|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)
  * [[https://www.aclweb.org/anthology/D19-1642.pdf|Ning et al 2019 - An Improved Neural Baseline for Temporal Relation Extraction]], using the ILP from [[https://www.aclweb.org/anthology/D17-1108.pdf|Ning et al 2017 - A Structured Learning Approach to Temporal Relation Extraction]]
  * [[https://www.aclweb.org/anthology/2020.coling-main.418.pdf|Chousa et al 2020 - SpanAlign: Sentence Alignment Method based on Cross-Language Span Prediction and ILP]]
  * [[https://www.aclweb.org/anthology/2020.textgraphs-1.13.pdf|Gupta & Srinivasaraghavan 2020 - Explanation Regeneration via Multi-Hop ILP Inference over Knowledge Base]]
  * [[https://aclanthology.org/2020.emnlp-main.9.pdf|Saha et al 2020 - PRover: Proof Generation for Interpretable Reasoning over Rules]]
  * [[https://aclanthology.org/2021.findings-acl.277.pdf|Sun et al 2021 - Probabilistic Graph Reasoning for Natural Proof Generation]]

===== Theoretical Results =====
  * 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).

===== Software =====
  * Gurobi: [[https://www.gurobi.com/academia/academic-program-and-licenses/|Free Academic License]], also [[https://www.gurobi.com/academia/|Gurobi - Academia]].  Currently the best ILP solver
  * CPLEX.  Another good ILP solver

===== Courses and Slides =====
(Search "integer linear programming slides pdf" on Google)
  * [[http://www.cs.cmu.edu/~arielpro/15780s17/slides/integer_prog.pdf|Ziko Kolter - Integer Linear Programming]]
  * [[https://ilpinference.github.io/eacl2017/outline.html|Tutorial at EACL 2017]]
  * [[https://www2.cs.duke.edu/courses/fall10/cps296.1/|Integer Linear Programming at Duke]]
  * [[https://ocw.mit.edu/courses/sloan-school-of-management/15-053-optimization-methods-in-management-science-spring-2013/lecture-notes/MIT15_053S13_lec10.pdf|MIT Sloan - ILP Lecture]]
  * [[https://www.isical.ac.in/~arijit/courses/autumn2016/ILP-Lecture-1.pdf|ILP Slides]]

===== Related Pages =====
  * [[Structured Prediction Energy Networks]]