On a cardinality-constrained transportation problem with market choice

DOI10.1016/J.ORL.2015.12.001MaRDI QIDQ1785735zbMATH OpenOpenAlexFDO

Authors Matthias Walter, Pelin Damcı-Kurt, Santanu S. Dey, Simge Küçükyavuz

Publication date 1 October 2018

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.8723

zbMATH Keywords

cardinality constraintintegral polytopetransportation problem with market choice

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Mixed integer programming (90C11) Programming involving graphs or networks (90C35)

Abstract: It is well-known that the intersection of the matching polytope with a cardinality constraint is integral [8]. We prove a similar result for the polytope corresponding to the transportation problem with market choice (TPMC) (introduced in [4]) when the demands are in the set $1,2$. This result generalizes the result regarding the matching polytope and also 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.

Recommendations

• On the transportation problem with market choice
• Constrained weighted matchings and edge coverings in graphs
• On cardinality constrained polymatroids
• Approximation algorithms for the transportation problem with market choice and related models
• scientific article; zbMATH DE number 795216

Cites work

• Approximation algorithms for supply chain planning and logistics problems with market choice
• Approximation algorithms for the transportation problem with market choice and related models
• Budgeted matching and budgeted matroid intersection via the gasoline puzzle
• scientific article; zbMATH DE number 3862930 (Why is no real title available?)
• Integrated market selection and production planning: complexity and solution approaches
• Inventory and Facility Location Models with Market Selection
• On certain polytopes associated with graphs
• On the transportation problem with market choice

Cited in

(5)

• Extended formulations for vertex cover
• Analyzing a two-staged multi-objective transportation problem under quantity dependent credit period policy using \(q\)-fuzzy number
• Decentralized algorithms for distributed integer programming problems with a coupling cardinality constraint
• On the transportation problem with market choice
• Intra market optimization for express package carriers with station to station travel and proportional sorting

This page was built for publication: On a cardinality-constrained transportation problem with market choice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1785735)