A tractable discrete fractional programming: application to constrained assortment optimization

Tian Xie () and Dongdong Ge ()
Additional contact information
Tian Xie: Shanghai University of Finance and Economics
Dongdong Ge: Shanghai University of Finance and Economics

Journal of Combinatorial Optimization, 2018, vol. 36, issue 2, No 5, 400-415

Abstract: 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)$$ O ( m 2 n ) variables and $$O(m^2 n^2)$$ 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)$$ O ( m 3 n 2 log m n ) time. In application, this method leads to an $$O(m^3 n^2 \log mn)$$ O ( m 3 n 2 log m n ) algorithm for assortment optimization problem under nested logit model with cardinality constraints (Feldman and Topaloglu, Oper Res 63: 812–822, 2015).

Keywords: Fractional programming; Dynamic programming; Assortment optimization; 90C32; 90C39; 90B50 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0302-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:36:y:2018:i:2:d:10.1007_s10878-018-0302-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0302-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().