分类优化是零售和在线广告等许多实际应用中出现的重要问题。 在这个问题中，目标是在存在（1）选择模型指定的消费者替代行为和（2）限制项目总重量的潜在容量约束的情况下，选择最大化预期收入的项目子集在分类中。 后者是许多应用中出现的自然约束。 我们首先从优化的角度展示这两个方面的挑战性。 首先，我们表明，即使对于最简单的选择模型，即多项 logit 模型，添加一般容量约束也会使问题成为 NP-hard 问题。 其次，我们表明，当混合数量不恒定时，即使是多项 logit 模型的混合的无约束分类优化也很难在任何合理的因子内近似。鉴于这些硬度结果，我们提出了容量接近最优的算法约束分类优化问题在一大类参数选择模型下，包括多项 logit、马尔可夫链、嵌套 logit 和 d 级嵌套 logit 选择模型的混合。 事实上，我们为一类容量受限的优化问题开发了接近最优的算法，这些问题的目标函数取决于少量的线性函数。 对于多项式 logit 模型（或马尔可夫链模型）的混合，我们算法的运行时间与段数（即转移矩阵的秩）呈指数关系。 因此，我们仅在段数恒定（或秩恒定）的情况下获得有效算法。 然而，根据我们的硬度结果，对于多项式 logit 选择模型的混合，任何接近最优的算法都将具有对混合数量的超多项式依赖
