La Programación Lineal Entera (ILP) es uno de los paradigmas más exitosos y generales para resolver problemas de optimización computacionalmente intratables en ciencias de la computación. ILP es NP-completo y, hasta hace poco, nos faltaba un estudio sistemático de la complejidad de ILP a través del prisma de las interacciones variable-restricción. Esto cambió drásticamente en los últimos años gracias a una serie de resultados que juntos presentan un detallado panorama de complejidad para el problema centrado en la estructura de representaciones gráficas de instancias. El objetivo de esta encuesta es resumir estos desarrollos recientes, ponerlos en contexto y en un formato unificado, y hacerlos más accesibles para expertos de diversos ámbitos.