A tractable discrete fractional programming: application to constrained assortment optimization |
| |
Authors: | Tian Xie Dongdong Ge |
| |
Institution: | 1.Research Institute for Interdisciplinary Sciences, School of Information Management and Engineering,Shanghai University of Finance and Economics,Shanghai,China |
| |
Abstract: | In this note, we consider a discrete fractional programming in light of a decision problem where limited number of indivisible resources are allocated to several heterogeneous projects to maximize the ratio of total profit to total cost. For each project, both profit and cost are solely determined by the amount of resources allocated to it. Although the problem can be reformulated as a linear program with \(O(m^2 n)\) variables and \(O(m^2 n^2)\) constraints, we further show that it can be efficiently solved by induction in \(O(m^3 n^2 \log mn)\) time. In application, this method leads to an \(O(m^3 n^2 \log mn)\) algorithm for assortment optimization problem under nested logit model with cardinality constraints (Feldman and Topaloglu, Oper Res 63: 812–822, 2015). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|