A tractable discrete fractional programming: application to constrained assortment optimization

作者：Xie, Tian^*; Ge, Dongdong

来源：Journal of Combinatorial Optimization, 2018, 36(2): 400-415.

DOI：10.1007/s10878-018-0302-x

• Fractional programming
• Dynamic programming
• Assortment optimization

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 variables and constraints, we further show that it can be efficiently solved by induction in time. In application, this method leads to an algorithm for assortment optimization problem under nested logit model with cardinality constraints (Feldman and Topaloglu, Oper Res 63: 812-822, 2015).

• 出版日期2018-8
• 单位上海财经大学