論文の概要: Sequence-Structured Decision Learning for Branch-and-Bound in Mixed-Integer Linear Programming

• arxiv url: http://arxiv.org/abs/2610.14835v1
• Date: Sat, 10 Oct 2026 11:52:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-20 11:35:53.556454
• Title: Sequence-Structured Decision Learning for Branch-and-Bound in Mixed-Integer Linear Programming
• Title（参考訳）: 混合整数線形計画法における分岐境界の列構造決定学習
• Abstract要約: ブランチ・アンド・バウンド(BnB)は,探索木の構築と探索によって混合整数線形プログラムを解く。 本稿では,共有グローバル表現から分岐とノード選択を学習するシーケンス構造化フレームワークSeq-BnBを提案する。 自己注意エンコーダは、このグローバル検索履歴を要約し、二部グラフニューラルネットワークは現在のLP緩和を符号化し、コンテキスト条件決定ヘッドは分岐変数とオープンノードをスコアする。
• 参考スコア（独自算出の注目度）: 17.826714773828886
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Branch-and-bound (BnB) solves mixed-integer linear programs by constructing and exploring a search tree. Node selection and branching are two recurrent decisions that directly determine the tree. Learning-based approaches typically optimize either decision in isolation and condition on a mostly local view, leaving the coupled evolution of the search tree insufficiently modeled. This paper proposes Seq-BnB, a sequence-structured framework that learns branching and node selection from a shared global representation of the evolving BnB process. Seq-BnB serializes node creations, node updates, node-selection events, and branching events into typed tokens, producing a causal event sequence of the search trajectory. A self-attention encoder summarizes this global search history, a bipartite graph neural network encodes the current LP relaxation, and context-conditioned decision heads score branching variables and open nodes. To reduce distribution shift between expert demonstrations and learned policies, Seq-BnB is trained with DAgger-style data aggregation. On four MILP benchmark families, Seq-BnB consistently processes fewer BnB nodes than heuristic and learning-based baselines, with strong solution times on both standard and larger transfer instances. While this paper evaluates Seq-BnB instantiation for branching and node selection, it accommodates additional solver decisions, such as cut selection, by introducing new action tokens and decision heads.
• Abstract（参考訳）: ブランチ・アンド・バウンド(BnB)は,探索木の構築と探索によって混合整数線形プログラムを解く。 ノードの選択と分岐は、ツリーを直接決定する2つの繰り返し決定である。 学習ベースのアプローチは通常、決定の分離と条件を主に局所的な視点で最適化し、探索木の進化を十分にモデル化したままにしておく。 本稿では,BnBプロセスのグローバルな共有表現から分岐とノードの選択を学習するシーケンス構造化フレームワークSeq-BnBを提案する。 Seq-BnBは、ノード生成、ノード更新、ノード選択イベント、型付きトークンへのイベントの分岐をシリアライズし、検索トラジェクトリの因果イベントシーケンスを生成する。 自己注意エンコーダは、このグローバル検索履歴を要約し、二部グラフニューラルネットワークは現在のLP緩和を符号化し、コンテキスト条件決定ヘッドは分岐変数とオープンノードをスコアする。 専門家によるデモンストレーションと学習ポリシの分散シフトを低減するため、Seq-BnBはDAggerスタイルのデータアグリゲーションでトレーニングされている。 4つのMILPベンチマークファミリでは、Seq-BnBはヒューリスティックなベースラインや学習ベースのベースラインよりもBnBノードを一貫して処理し、標準インスタンスと大きな転送インスタンスの両方で強い解時間を持つ。 本稿では、分岐とノード選択のためのSeq-BnBインスタンスの評価を行うが、新しいアクショントークンと決定ヘッドを導入することで、カットセレクションなどの問題解決に役立てる。

関連論文リスト

• Efficient and Trainable Language Model Test-Time Scaling via Local Branch Routing [65.59464371673623]
  Local Branch Routing (LBR)はトークンレベルのテストタイムスケーリングフレームワークである。 小さなローカルなルックアヘッドツリーを拡張し、言語モデルを通じてすべてのサンプルブランチを転送し、軽量ルータを使用してコミットするdeep-1サブツリーを選択する。 LBRにより、各トークン決定は、完全なソリューションレベルの検索を避けながら、ルート次トーケン分布を超えるエビデンスを使用することができる。
  論文  参考訳（メタデータ） (2026-06-24T03:42:44Z)
• Reinforcement Learning for Node Selection in Branch-and-Bound [52.2648997215667]
  現在の最先端セレクタは手作りのアンサンブルを使用して、ナイーブなサブノードセレクタと、個々のノードデータに依存する学習ノードセレクタを自動的に切り替える。 孤立ノードではなく木の状態全体を考慮しながら強化学習(RL)を用いる新しいシミュレーション手法を提案する。
  論文  参考訳（メタデータ） (2023-09-29T19:55:56Z)
• Des-q: a quantum algorithm to provably speedup retraining of decision trees [2.7262923206583136]
  Des-qは、回帰および二分分類タスクのための決定木を構築し、再訓練するための新しい量子アルゴリズムである。 我々は,複数のデータセット上での最先端の古典的手法に対して,Des-qのシミュレーションバージョンをベンチマークする。 提案アルゴリズムは,最新の決定木に類似した性能を示しながら,周期木再学習を著しく高速化する。
  論文  参考訳（メタデータ） (2023-09-18T17:56:08Z)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。 解法の効率は、分割する変数を選択するのに使用される分岐に依存する。 分岐を効率的に学習できる強化学習法を提案する。
  論文  参考訳（メタデータ） (2023-06-09T14:01:26Z)
• Learning to Compare Nodes in Branch and Bound with Graph Neural Networks [5.08128537391027]
  整数プログラミングにおける分岐とバウンドのアプローチは、次の探索のために空間の一部を順序付けする必要がある。 本稿では,この問題に対処する新たなシアムグラフニューラルネットワークモデルを提案し,ノードを属性付き二部グラフとして表現する。 本手法は,ノードがランクに応じて探索される平易なフレームワークのインスタンスを解くことで評価する。
  論文  参考訳（メタデータ） (2022-10-30T19:38:23Z)
• Lookback for Learning to Branch [77.32867454769936]
  Bipartite Graph Neural Networks (GNN) は、ディープラーニングに基づくMixed-Integer Linear Program (MILP) の重要コンポーネントであることが示されている。 近年の研究では、分岐とバウンド(B&B)の解法における分岐(可変選択)を置き換える上で、そのようなGNNの有効性が実証されている。
  論文  参考訳（メタデータ） (2022-06-30T02:33:32Z)

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

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