CONFORTI, Michele; DI SUMMA, Marco; EISENBRAND, Fritz; … - Center for Operations Research and Econometrics (CORE), … - 2006
We consider mixed-integer sets of the type M IX T U = {x : Ax b; xi integer, i I}, where A is a totally unimodular matrix, b is an arbitrary vector and I is a nonempty subset of the column indices of A. We show that the problem of checking nonemptiness of a set M IX T U is NP-complete when A...