On a cardinality-constrained transportation problem with market choice. (English) Zbl 1408.90204
Summary: It is well-known that the intersection of the matching polytope with a cardinality constraint is integral [A. Schrijver, Combinatorial optimization. Polyhedra and efficiency (3 volumes). Berlin: Springer (2003; Zbl 1041.90001)]. In this note, we prove a similar result for the polytope corresponding to the transportation problem with market choice (TPMC) (introduced in [P. Damcı-Kurt et al., Discrete Appl. Math. 181, 54–77 (2015; Zbl 1311.90074)]) 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.
MSC:
| 90C11 | Mixed integer programming |
| 90B06 | Transportation, logistics and supply chain management |
| 90C35 | Programming involving graphs or networks |
References:
| [1] | Aardal, K.; Le Bodic, P., Approximation algorithms for the transportation problem with market choice and related models, Oper. Res. Lett., 42, 549-552, (2014) · Zbl 1408.90156 |
| [2] | Berger, A.; Bonifaci, V.; Grandoni, F.; Schäfer, G., Budgeted matching and budgeted matroid intersection via the gasoline puzzle, Math. Program., 128, 355-372, (2011) · Zbl 1223.05222 |
| [3] | Chvátal, V., On certain polytopes associated with graphs, J. Combin. Theory Ser. B, 18, 2, 138-154, (1975) · Zbl 0277.05139 |
| [4] | Damcı-Kurt, P.; Dey, S.; Küçükyavuz, S., On the transportation problem with market choice, Discrete Appl. Math., 181, 54-77, (2015) · Zbl 1311.90074 |
| [5] | Geunes, J.; Levi, R.; Romeijn, H. E.; Shmoys, D. B., Approximation algorithms for supply chain planning and logistics problems with market choice, Math. Program., 130, 85-106, (2009) · Zbl 1229.90011 |
| [6] | Kuehn, A. A.; Hamburger, M. J., A heuristic program for locating warehouses, Manage. Sci., 9, 4, 643-666, (1963) |
| [7] | R. Levi, J. Geunes, H.E. Romeijn, D.B. Shmoys, Inventory and facility location models with market selection, in: Proceedings of the 12th IPCO, 2005, pp. 111-124. · Zbl 1119.90323 |
| [8] | Schrijver, A., Combinatorial optimization, (2003), Springer · Zbl 0542.90067 |
| [9] | Van den Heuvel, W.; Kundakçıoğlu, O. E.; Geunes, J.; Romeijn, H. E.; Sharkey, T. C.; Wagelmans, A. P.M., Integrated market selection and production planning: complexity and solution approaches, Math. Program., 134, 395-424, (2012) · Zbl 1254.90064 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
