Balancing the profit and capacity under uncertainties: a target‐based distributionally robust knapsack problem. (15th July 2021)

• Record Type: Journal Article
• Authors: Ding, Jianpeng; Chen, Liuxin; Ke, Ginger Y.; Li, Yuanbo; Zhang, Lianmin
• Is Part Of: International transactions in operational research. Volume 29:Number 2(2022)
• Page Start: 760
• Page End: 782
• Publication Date: 2021-07-15
• Subjects: target -- distributionally robust optimization -- knapsack problem -- profit and capacity; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.13031
• Languages: English
• ISSNs: 0969-6016

Abstract

Abstract: As a well‐developed optimization problem, the knapsack problem has been broadly applied in various fields involving resource allocations, especially production planning. In this paper, we propose a target‐based distributionally robust knapsack problem (TDRKP), considering both uncertain profit and capacity, as well as the impact of a given target for profit. Based on a shortfall risk measure and piecewise utility function, the violation risk of the target is investigated. To solve the model efficiently, TDRKP is reformulated into computationally tractable form as a second‐order conic program. Through a series of numerical experiments, we verify that the proposed TDRKP formulation performs better than both the sample average approximation model and the minimizing violation probabilities model.