Integer Linear Programming with Sparse Columns

The thesis wants to study the problem of the admissibility of Integer Linear Programming (ILP) with sparse columns, i.e. with variables that appear in "few" inequalities. The focus will be on the case in which each variable can appear in at most two inequalities, a case whose computational complexity is still unknown.

La tesi vuole studiare il problema dell'ammissibilità per la Programmazione Lineare Intera (ILP) con colonne sparse, ossia con variabili che compaiono in “poche” disequazioni. Il focus sarà in particolare sul caso in cui ogni variabile possa comparire al più in due disequazioni, caso del quale tuttora non si conosce la complessità computazionale.