On a cardinality-constrained transportation problem with market choice

It is well-known that the intersection of the matching polytope with a cardinality constraint is integral (Schrijver, 2003) [8]. In this note, we prove a similar result for the polytope corresponding to the transportation problem with market choice (TPMC) (introduced in Damci-Kurt et al. (2015)) when the demands are in the set {1, 2}. This result generalizes the result regarding the matching polytope. The result in this note implies that some special classes of minimum weight perfect matching problem with a cardinality constraint on a subset of edges can be solved in polynomial time. (C) 2015 Elsevier B.V. All rights reserved.