Network Formulations of Mixed-Integer Programs

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.


Published in:
Mathematics Of Operations Research, 34, 194-209
Year:
2009
Publisher:
INFORMS
ISSN:
0364-765X
Keywords:
Laboratories:




 Record created 2010-12-02, last modified 2018-09-25


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)