Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
We consider mixed-integer sets described by system of linear inequalities in which the constraint matrix A is totally unimodular; the right-hand side is arbitrary vector; and a subset of the variables is required to be integer. We show that the problem of checking nonemptiness of a set of this type is NP-complete, even in the case in which the linear system describes mixed-integer network flows with half-integral requirement on the nodes.
Rachid Guerraoui, El Mahdi El Mhamdi, Alexandre David Olivier Maurer, Le Nguyen Hoang
, , ,