Sortimentoptimering är ett viktigt problem som uppstår i många praktiska tillämpningar såsom detaljhandel och online-reklam. I ett sortiment optimering problem, är målet att välja en delmängd av objekt som maximerar de förväntade intäkterna i närvaro av substitution beteende konsumenter som anges av en val modell. I detta dokument överväger vi den kapacitetsbegränsade versionen av problemet med optimering av sortimentet under flera olika modeller, inklusive Multinomial Logit (MNL), Nested Logit (NL) och blandningen av Multinomial Logit (MMNL) modeller. Målet är att välja en intäktsmaximerande delmängd av objekt med total vikt eller kapacitet som mest en given bunden. Vi presenterar ett helt polynom tid approximationsschema (FPTAS) för dessa modeller när antalet blandningar eller bon är konstant. Våra FPTAS använder idéer som liknar FPTAS för Knapsack-problemet. Drifttiden för vår algoritm beror exponentiellt på antalet blandningar i MMNL-modellen. Vi visar att förvånansvärt nog är det exponentiella beroendet av antalet blandningar nödvändigt för en nästan optimal algoritm för MMNL:s valmodell. I synnerhet visar vi att det inte finns någon algoritm med körtid polynom i antalet objekt, n och blandningar, K som ger en approximation bättre än O(1/K 1−δ ) för alla δ > 0 för även den okonstruerade sortiment optimering över en allmän MMNL modell. Vår minskning ger en procedur för att bygga en naturlig familj av hårda riktmärken instanser för sortimentet optimeringsproblem över MMNL som kan vara av oberoende intresse. Dessa fall är ganska jämförbara med de övervägningsbaserade modellerna (Jagabathula och Rusmevitientong (2014)) där övervägningsuppsättningen härrör från en grafisk modell. Vi presenterar också några specialfall med MMNL- och NL-modeller där vi kan få ett FPTAS med polynomberoende av antalet blandningar.
När valfunktionen beskrivs av en blandning av multinomala logitmodeller är sortimentsproblemet NP-hård, men olika heltalsprogrammeringsmetoder och approximationsalgoritmer är kända [3, REF 15].
Near-Optimal Algorithms for Capacity Constrained Assortment Optimization
{'venue': 'SSRN Electronic Journal', 'journal': 'SSRN Electronic Journal', 'mag_field_of_study': ['Mathematics']}