論文の概要: Column Generation Using Domain-Independent Dynamic Programming

• arxiv url: http://arxiv.org/abs/2510.14317v1
• Date: Thu, 16 Oct 2025 05:23:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-17 21:15:14.735098
• Title: Column Generation Using Domain-Independent Dynamic Programming
• Title（参考訳）: ドメインに依存しない動的プログラミングを用いたカラム生成
• Authors: Ryo Kuroiwa, Edward Lam,
• Abstract要約: カラム生成とブランチ・アンド・プライスは大規模な正確な最適化のための主要な手法である。 本稿では,ドメインに依存しない動的プログラミングを汎用価格決定器として利用できることを示す。
• 参考スコア（独自算出の注目度）: 2.7071541526963805
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Column generation and branch-and-price are leading methods for large-scale exact optimization. Column generation iterates between solving a master problem and a pricing problem. The master problem is a linear program, which can be solved using a generic solver. The pricing problem is highly dependent on the application but is usually discrete. Due to the difficulty of discrete optimization, high-performance column generation often relies on a custom pricing algorithm built specifically to exploit the problem's structure. This bespoke nature of the pricing solver prevents the reuse of components for other applications. We show that domain-independent dynamic programming, a software package for modeling and solving arbitrary dynamic programs, can be used as a generic pricing solver. We develop basic implementations of branch-and-price with pricing by domain-independent dynamic programming and show that they outperform a world-leading solver on static mixed integer programming formulations for seven problem classes.
• Abstract（参考訳）: カラム生成とブランチ・アンド・プライスは大規模な正確な最適化のための主要な手法である。 列生成は、マスター問題と価格問題の解決を繰り返す。 マスター問題は線形プログラムであり、一般解法を用いて解くことができる。 価格問題はアプリケーションに大きく依存するが、通常は個別である。 離散最適化の難しさから、高性能カラム生成は、しばしば問題の構造を利用するために特別に構築されたカスタム価格アルゴリズムに依存している。 この価格解決器の性質は、他のアプリケーションに対するコンポーネントの再利用を妨げます。 本稿では、任意の動的プログラムをモデリングし、解決するためのソフトウェアパッケージであるドメイン非依存の動的プログラミングを、汎用的な価格決定器として利用できることを示す。 ドメインに依存しない動的プログラミングによる価格設定による分岐と価格の基本的な実装を開発し、7つの問題クラスに対する静的混合型整数プログラミングの解法よりも優れていることを示す。

関連論文リスト

• Inexact Column Generation for Bayesian Network Structure Learning via Difference-of-Submodular Optimization [8.09615396808421]
  最先端のBNSLIPの定式化は、指数関数的に多くの変数と制約に悩まされる。 このような課題に対処するためのIPの標準的なアプローチは、行と列の生成テクニックを採用することである。 我々の行と列の生成アプローチは、最先端のスコアベースアプローチよりも高い品質のソリューションが得られることを示す。
  論文  参考訳（メタデータ） (2025-05-16T10:23:19Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  我々はスムーズな(摂動された)ポリシーを解析し、線形オラクルが使用する方向に対して制御されたランダムな摂動を付加する。 我々の主な貢献は、過剰リスクを摂動バイアス、統計的推定誤差、最適化誤差に分解する一般化境界である。 車両のスケジューリングやスムーズ化がトラクタブルトレーニングと制御された一般化の両方を可能にしていることを示す。
  論文  参考訳（メタデータ） (2024-07-24T12:00:30Z)
• ACE, a generic constraint solver [1.550120821358415]
  制約プログラミング(CP)は制約された問題のモデリングと解決に有用な技術である。 本稿では,Javaで開発されたオープンソースの制約解決ツールACEについて述べる。
  論文  参考訳（メタデータ） (2023-01-06T12:15:18Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Budget-Aware Pruning for Multi-Domain Learning [45.84899283894373]
  この作業は、ユーザが定義した予算に従って複数のドメインを処理可能なモデルを立案することを目的としている。 これを実現するために、全てのドメインがベースラインモデルから同様のフィルタのサブセットを使用するように促します。 提案手法は、リソース制限されたデバイスへの適応性の向上によって革新される。
  論文  参考訳（メタデータ） (2022-10-14T20:48:12Z)
• Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring [5.278929511653199]
  カラム生成(CG)は,大規模最適化問題の解決に有効な手法である。 本稿では,高品質な列を効率的に生成できる機械学習価格ヒューリスティックを提案する。
  論文  参考訳（メタデータ） (2021-12-08T03:58:25Z)
• Competitive Mirror Descent [67.31015611281225]
  制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。 本稿では, 競合ミラー降下法(CMD)を提案する。 特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
  論文  参考訳（メタデータ） (2020-06-17T22:11:35Z)
• Physarum Powered Differentiable Linear Programming Layers and Applications [48.77235931652611]
  一般線形プログラミング問題に対する効率的かつ微分可能な解法を提案する。 本稿では,ビデオセグメンテーションタスクとメタラーニングにおける問題解決手法について述べる。
  論文  参考訳（メタデータ） (2020-04-30T01:50:37Z)
• Constrained Multiagent Rollout and Multidimensional Assignment with the Auction Algorithm [0.0]
  本稿では,制約付き決定論的動的プログラミングに適用可能なロールアウトアルゴリズムの拡張について考察する。 提案手法では,ベースが実現可能な解を生成する場合,ロールアウトアルゴリズムはコスト改善特性を有することを示す。 コスト改善特性は計算要求を大幅に削減した代替実装で維持されていることを示す。
  論文  参考訳（メタデータ） (2020-02-18T07:09:06Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。