文件名称：嵌套Logit模型下分类优化的精确方法-研究论文
文件大小：1.39MB
文件格式：PDF
更新时间：2024-06-09 08:42:41
combinatorial optimization revenue management assortment
我们研究了寻找最佳产品类别以最大化预期收入的问题，其中使用Nested Logit选择模型对客户偏好进行建模。 已知该问题在特定情况下可以多项式求解，否则在NP-hard条件下只有文献中存在的近似算法可以解决。 我们提供了一种精确的通用方法，该方法将量身定制的Branch-and-Bound算法嵌入分数编程框架中。 与现有文献相反，在现有文献中，对嵌套的结构或产品的组合和特征进行了假设，对输入数据没有进行任何假设。 尽管我们的方法在输入大小上不是多项式，但是它可以解决大型实例的最一般问题设置。 我们表明分数编程方案的参数化子问题是一个高度非线性的二进制优化问题，可通过嵌套分解，这是该方法的主要优势。 为了解决每个嵌套的子问题，我们提出了一种两阶段方法。 在第一阶段，我们根据单巢子问题的新推导的结构特性来固定大量变量。 这可以显着减小问题的大小。 在第二阶段，我们设计了具有问题特定上限的量身定制的分支定界算法。 数值结果表明，该方法能够求解五个嵌套的嵌套实例，每个嵌套多达5,000种产品。 对于我们的方法，最具挑战性的例子是那些混合了巢的不相似参数的样本，其中一些小于一个，而另一些大于一个。 关键字：组合优化，收益管理，分类优化，分数规划，嵌套logit。