On a cardinality-constrained transportation problem with market choice

被引：4

作者：

Walter, Matthias ^{[1
]}

Damci-Kurt, Pelin ^{[2
]}

Dey, Santanu S. ^{[3
]}

Kuecuekyavuz, Simge ^{[2
]}

机构：

[1] Univ Magdeburg, Inst Math Optimierung, D-39106 Magdeburg, Germany

[2] Ohio State Univ, Dept Integrated Syst Engn, Columbus, OH 43210 USA

[3] Georgia Inst Technol, Sch Ind & Syst Engn, Atlanta, GA 30332 USA

来源：

OPERATIONS RESEARCH LETTERS | 2016年 / 44卷 / 02期

基金：

美国国家科学基金会;

关键词：

Transportation problem with market choice; Cardinality constraint; Integral polytope;

D O I：

10.1016/j.orl.2015.12.001

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：170 / 173

页数：4

共 50 条

[31] An Exact CP Approach for the Cardinality-Constrained Euclidean Minimum Sum-of-Squares Clustering Problem
Haouas, Mohammed Najib
Aloise, Daniel
Pesant, Gilles
INTEGRATION OF CONSTRAINT PROGRAMMING, ARTIFICIAL INTELLIGENCE, AND OPERATIONS RESEARCH, CPAIOR 2020, 2020, 12296 : 256 - 272
[32] Branch-and-cut-and-price for the cardinality-constrained multi-cycle problem in kidney exchange
Lam, Edward
Mak-Hau, Vicky
COMPUTERS & OPERATIONS RESEARCH, 2020, 115 (115)
[33] Some observations about the extreme points of the Generalized Cardinality-Constrained Shortest Path Problem polytope
Maria Flavia Monaco
Marcello Sammarra
Luigi Moccia
Optimization Letters, 2008, 2 : 577 - 585
[34] An application of a cardinality-constrained multiple benchmark tracking error model on a plant enterprise selection problem
Ma, Qiuzhuo
Paudel, Krishna P.
Gu, Liting
Wen, Xiaowei
EUROPEAN REVIEW OF AGRICULTURAL ECONOMICS, 2018, 45 (05) : 1 - 45
[35] Some observations about the extreme points of the Generalized Cardinality-Constrained Shortest Path Problem polytope
Monaco, Maria Flavia
Sammarra, Marcello
Moccia, Luigi
OPTIMIZATION LETTERS, 2008, 2 (04) : 577 - 585
[36] Forest harvesting planning under uncertainty: a cardinality-constrained approach
Bajgiran, Omid Sanei
Zanjani, Masoumeh Kazemi
Nourelfath, Mustapha
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2017, 55 (07) : 1914 - 1929
[37] Sequential optimality conditions for cardinality-constrained optimization problems with applications
Christian Kanzow
Andreas B. Raharja
Alexandra Schwartz
Computational Optimization and Applications, 2021, 80 : 185 - 211
[38] A strong sequential optimality condition for cardinality-constrained optimization problems
Menglong Xue
Liping Pang
Numerical Algorithms, 2023, 92 : 1875 - 1904
[39] A memetic algorithm for cardinality-constrained portfolio optimization with transaction costs
Ruiz-Torrubiano, Ruben
Suarez, Alberto
APPLIED SOFT COMPUTING, 2015, 36 : 125 - 142
[40] Global aspects of the continuous reformulation for cardinality-constrained optimization problems
Laemmel, S.
Shikhman, V.
OPTIMIZATION, 2024, 73 (10) : 3185 - 3208

← 1 2 3 4 5 →