論文の概要: Outer Approximation and Super-modular Cuts for Constrained Assortment Optimization under Mixed-Logit Model
- arxiv url: http://arxiv.org/abs/2407.18532v1
- Date: Fri, 26 Jul 2024 06:27:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-29 14:20:08.054903
- Title: Outer Approximation and Super-modular Cuts for Constrained Assortment Optimization under Mixed-Logit Model
- Title（参考訳）: 混合ロジットモデルによる制約配置最適化のための外部近似と超モジュラーカット
- Authors: Hoang Giang Pham, Tien Mai,
- Abstract要約: 混合ロジット顧客選択モデルに基づくアソシエーション最適化問題について検討する。
既存の正確な手法は、主にMILP (mixed-integer linear programming) やCONIC (Second-order cone) の修正に依存している。
我々の研究は、単調に超モジュラーかつ凸であることを示す客観的関数の成分に焦点をあてることによって、この問題に対処する。
- 参考スコア（独自算出の注目度）: 6.123324869194196
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the assortment optimization problem under the mixed-logit customer choice model. While assortment optimization has been a major topic in revenue management for decades, the mixed-logit model is considered one of the most general and flexible approaches for modeling and predicting customer purchasing behavior. Existing exact methods have primarily relied on mixed-integer linear programming (MILP) or second-order cone (CONIC) reformulations, which allow for exact problem solving using off-the-shelf solvers. However, these approaches often suffer from weak continuous relaxations and are slow when solving large instances. Our work addresses the problem by focusing on components of the objective function that can be proven to be monotonically super-modular and convex. This allows us to derive valid cuts to outer-approximate the nonlinear objective functions. We then demonstrate that these valid cuts can be incorporated into Cutting Plane or Branch-and-Cut methods to solve the problem exactly. Extensive experiments show that our approaches consistently outperform previous methods in terms of both solution quality and computation time.
- Abstract（参考訳）: 本稿では,混合ロジット顧客選択モデルに基づくアソシエーション最適化問題について検討する。
アソシエーション最適化は、何十年にもわたって収益管理において主要なトピックとなっているが、混合ロジットモデルは、顧客の購買行動のモデリングと予測において、最も一般的で柔軟なアプローチの1つと考えられている。
既存の正確な手法は、主にMILP(mixed-integer linear programming)やCONIC(Second-order cone)の修正に頼っている。
しかし、これらのアプローチは、しばしば弱い連続緩和に悩まされ、大きなインスタンスを解く際には遅くなる。
我々の研究は、単調に超モジュラーかつ凸であることを示す客観的関数の成分に焦点をあてることによって、この問題に対処する。
これにより、非線形目的関数の外部近似に有効なカットを導出することができる。
次に、これらの有効なカットをカットプレーンやブランチ・アンド・カットの手法に組み込むことで、その問題を正確に解決できることを実証する。
大規模な実験により、我々のアプローチは、ソリューションの品質と計算時間の両方において、従来手法よりも一貫して優れていたことが示される。
関連論文リスト
- It's All in the Mix: Wasserstein Machine Learning with Mixed Features [5.739657897440173]
混合機能問題の解法として,実用的なアルゴリズムを提案する。
提案手法は, 個々の特徴が存在する場合の既存手法を著しく上回りうることを示す。
論文 参考訳（メタデータ） (2023-12-19T15:15:52Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。
本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
論文 参考訳（メタデータ） (2023-01-28T01:50:42Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。
本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。
本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-04T00:26:56Z) - Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
ノイズコントラスト法を用いて、サロゲート損失関数の族を動機付ける。
すべての予測と最適化アプローチのボトルネックに対処する。
非常に遅い成長率でさえ、最先端の手法の質に合わせるのに十分であることを示す。
論文 参考訳（メタデータ） (2020-11-10T19:09:12Z) - Memory Clustering using Persistent Homology for Multimodality- and
Discontinuity-Sensitive Learning of Optimal Control Warm-starts [24.576214898129823]
シューティング法は非線形最適制御問題の解法として効率的である。
最近の研究は、問題空間のオフライン探索中に生成されたサンプルに基づいてトレーニングされた学習モデルからの最初の推測を提供することに重点を置いている。
本研究では、代数的トポロジーからツールを適用し、解空間の基盤構造に関する情報を抽出する。
論文 参考訳（メタデータ） (2020-10-02T14:24:59Z) - Extracting Optimal Solution Manifolds using Constrained Neural
Optimization [6.800113407368289]
制約付き最適化解アルゴリズムは点ベース解に制限される。
最適集合を近似として抽出する手法を提案する。
論文 参考訳（メタデータ） (2020-09-13T15:37:44Z) - MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment [77.38594866794429]
非剛体形状マッチングのための凸混合整数プログラミングの定式化。
効率的な低次元離散モデルに基づく新しい形状変形モデルを提案する。
論文 参考訳（メタデータ） (2020-02-28T09:54:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。