Editing Integer programming (section)

== Sparse integer programming ==
It is often the case that the matrix <math>A</math> that defines the integer program is ''[[Sparse matrix|sparse]]''. In particular, this occurs when the matrix has a [[Block matrix|block structure]], which is the case in many applications. The sparsity of the matrix can be measured as follows. The ''graph'' of <math>A</math> has vertices corresponding to columns of <math>A</math>, and two columns form an edge if <math>A</math> has a row where both columns have nonzero entries. Equivalently, the vertices correspond to variables, and two variables form an edge if they share an inequality. The ''sparsity measure'' <math>d</math> of <math>A</math> is the minimum of the [[tree-depth]] of the graph of <math>A</math> and the [[tree-depth]] of the graph of the transpose of <math>A</math>. Let <math>a</math> be the ''numeric measure'' of <math>A</math> defined as the maximum absolute value of any entry of <math>A</math>. Let <math>n</math> be the number of variables of the integer program. Then it was shown in 2018<ref>{{cite conference
 | last1 = Koutecký | first1 = Martin
 | last2 = Levin | first2 = Asaf
 | last3 = Onn | first3 = Shmuel
 | editor1-last = Chatzigiannakis | editor1-first = Ioannis
 | editor2-last = Kaklamanis | editor2-first = Christos
 | editor3-last = Marx | editor3-first = Dániel
 | editor4-last = Sannella | editor4-first = Donald
 | arxiv = 1802.05859
 | contribution = A parameterized strongly polynomial algorithm for block structured integer programs
 | doi = 10.4230/LIPICS.ICALP.2018.85
 | pages = 85:1–85:14
 | publisher = Schloss Dagstuhl – Leibniz-Zentrum für Informatik
 | series = LIPIcs
 | title = 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9–13, 2018, Prague, Czech Republic
 | volume = 107
 | year = 2018| doi-access = free
 }}</ref> that integer programming can be solved in [[strongly polynomial]] and [[fixed-parameter tractable]] time parameterized by <math>a</math> and <math>d</math>. That is, for some computable function <math>f</math> and some constant <math>k</math>, integer programming can be solved in time <math>f(a,d)n^k</math>. In particular, the time is independent of the right-hand side <math>b</math> and objective function <math>c</math>. Moreover, in contrast to the classical result of Lenstra, where the number <math>n</math> of variables is a parameter, here the number <math>n</math> of variables is a variable part of the input.