Loading...
research article
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.
Type
research article
Web of Science ID
WOS:000263602400012
Authors
Publication date
2009
Publisher
Published in
Volume
34
Start page
194
End page
209
Peer reviewed
NON-REVIEWED
EPFL units
Available on Infoscience
December 2, 2010
Use this identifier to reference this record