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 条
  • [41] Optimal lot solution to cardinality constrained mean-variance formulation for portfolio selection
    Li, D
    Sun, XL
    Wang, J
    MATHEMATICAL FINANCE, 2006, 16 (01) : 83 - 101
  • [42] Improved lower bounds for the online bin packing problem with cardinality constraints
    Fujiwara, Hiroshi
    Kobayashi, Koji
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 29 (01) : 67 - 87
  • [43] Improved lower bounds for the online bin packing problem with cardinality constraints
    Hiroshi Fujiwara
    Koji Kobayashi
    Journal of Combinatorial Optimization, 2015, 29 : 67 - 87
  • [44] A matheuristic for solving the bilevel approach of the facility location problem with cardinality constraints and preferences
    Calvete, Herminia, I
    Gale, Carmen
    Iranzo, Jose A.
    Camacho-Vallejo, Jose-Fernando
    Casas-Ramirez, Martha-Selene
    COMPUTERS & OPERATIONS RESEARCH, 2020, 124
  • [45] An efficient Lagrange-Newton algorithm for long-only cardinality constrained portfolio selection on real data sets
    Wang, Yingxiao
    Kong, Lingchen
    Qi, Houduo
    JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2025, 461
  • [46] A surrogate similarity measure for the mean-variance frontier optimisation problem under bound and cardinality constraints
    Guijarro, Francisco
    Tsinaslanidis, Prodromos E.
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2021, 72 (03) : 564 - 579
  • [47] A hybrid approach to cardinality constraint portfolio selection problem based on nonlinear neural network and genetic algorithm
    Yaman, Ilgim
    Dalkilic, Turkan Erbay
    EXPERT SYSTEMS WITH APPLICATIONS, 2021, 169
  • [48] A NOVEL NONLINEAR NEURAL NETWORK BASED ON COEFFICIENT OF VARIATION FOR SOLVING CARDINALITY CONSTRAINT PORTFOLIO OPTIMIZATION PROBLEM
    Yaman, Ilgim
    Dalkilic, Turkan Erbay
    13TH INTERNATIONAL DAYS OF STATISTICS AND ECONOMICS, 2019, : 1681 - 1687
  • [49] Dual formulation of the sparsity constrained optimization problem: application to classification
    Gaudioso, M.
    Giallombardo, G.
    Hiriart-Urruty, J. -B.
    OPTIMIZATION METHODS & SOFTWARE, 2024, 40 (01) : 84 - 101
  • [50] Constrained shortest path tour problem: Branch-and-Price algorithm
    Martin, Sebastien
    Magnouche, Youcef
    Juvigny, Corentin
    Leguay, Jeremie
    COMPUTERS & OPERATIONS RESEARCH, 2022, 144
12345