KNOWLEDGE VAULT — TAG
タグ「組合せ最適化」
収蔵 17件
2026-11-16
エネルギー関数による推論の高速化:Loopedモデルを1,000倍凌駕するCRAMの衝撃
Classical Energies Learn to Reason 1,000x Faster than Looped Models
出典:arXiv cs.LG (Machine Learning)(Authors: Benjamin Hoover, Hugh Blayney, James C. R. Whittington | 2026-11-12)
- 推論タスクを「エネルギー関数の最小化」として定式化するCRAM(Hopfield & Tankの発展型)の提案。
- 従来のLoopedモデルと比較し、学習の安定性、推論速度(最大1,000倍)、FLOPsの劇的な削減を実現。
- SudokuやMazeといった制約条件の強い論理パズルにおいて、極めて高い精度と計算効率を両立。
2026-11-08
有理数混合整数計画問題(MIP)に対する厳密な計算状況の更新
A Computational Status Update for Exact Rational Mixed Integer Programming
出典:arXiv Core: Combinatorial MILP & Quantum Compilation(Authors: Leon Eifler, Ambros Gleixner | 2021-01-22)
- 有理数上の混合整数計画問題に対し、丸め誤差を排除した厳密な解法を提案。
- シンボリックな前処理、厳密な修復ステップ、高速な有理数LPソルバーを統合。
- MIPLIB 2017ベンチマークにおいて、従来手法より平均6.6倍の高速化と解決数の大幅な向上を達成。
2026-11-08
回路およびGraverウォークと線形・整数計画法
Circuit and Graver Walks and Linear and Integer Programming
出典:arXiv Core: Combinatorial MILP & Quantum Compilation(Authors: Shmuel Onn | 2024-10-01)
- 線形計画法(LP)において、実行可能点から最適点への「回路ウォーク」が、線形代数操作と単一のLP解のみを用いて多項式時間で計算可能であることを証明。
- 整数計画法(IP)における「Graverウォーク」は、IPオラクルがあれば多項式時間で計算可能だが、オラクルなしでは最適解が既知であっても計算困難であることを示した。
- 疎な整数計画法の最新知見を組み合わせ、木深さ(tree-depth)および部分行列式(subdeterminants)が制限された行列に対しては、Graverウォークが多項式時間で計算可能であることを立証。
2026-11-08
多様な経験と専門性を兼ね備えたグループ形成のためのハイパーグラフ・クラスタリング
Hypergraph Clustering for Finding Diverse and Experienced Groups
出典:arXiv Core: Ensemble Diversity & Empirical Bayes(Authors: Ilya Amburg, Nate Veldt, Austin R. Benson | 2020-06-10)
- チーム編成において「特定のタスクへの専門性(経験)」と「スキルの多様性」の両立を目的とする。
- 過去のグループ経験を複数のハイパーエッジ型を持つハイパーグラフとしてモデル化する。
- 多様性を保護属性ではなく、参加したハイパーエッジ型の種類の豊富さとして定義し、最適化を行う。
2026-11-08
意思決定依存型不確実性を伴う確率計画問題のためのL型法
The L-Shaped Method for Stochastic Programs with Decision-Dependent Uncertainty
出典:arXiv Core: Combinatorial MILP & Quantum Compilation(Authors: Giovanni Pantuso, Mike Hewitt | 2025-06-15)
- 意思決定依存型不確実性(Decision-Dependent Uncertainty)を含む二段階確率計画問題を解くためのL型法の拡張を提案。
- 線形および整数確率計画の両方に対応する、分布固有の最適性カットおよび実行可能カットを導入。
- 3つの生産計画問題を用いた大規模なテストにより、大規模インスタンスに対する極めて高い有効性を実証。
2026-11-08
量子アニーリングを用いたGraver基底の計算と非線形整数計画問題への応用
Graver Bases via Quantum Annealing with Application to Non-Linear Integer Programs
出典:arXiv Core: Combinatorial MILP & Quantum Compilation(Authors: Hedayat Alghassi, Raouf Dridi, Sridhar Tayur | 2019-02-12)
- Graver基底を計算するための、量子・古典ハイブリッドアプローチを提案。
- 古典コンピュータでは指数関数的に困難なGraver基底の計算を、量子アニーラ(D-Wave)を用いて実行可能にする。
- Graver基底を最適性証明(Test Set)として利用し、非線形整数計画問題を解くための実用性を検証。
2026-11-08
混合整数計画問題(MIP)のための学習ベースの近傍探索(LNS)アルゴリズム
Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs
出典:arXiv Core: Combinatorial MILP & Quantum Compilation(Authors: Nicolas Sonnerat, Pengming Wang, Ira Ktena et al. | 2021-07-21)
- 混合整数計画問題(MIP)を解くための、学習ベースのLarge Neighborhood Search(LNS)手法を提案。
- Neural Divingモデルを用いて初期解の確率分布を表現し、MIPソルバーと組み合わせて初期割当を生成。
- 探索プロセスをマルコフ決定過程(MDP)として定式化し、模倣学習を用いて最適な近傍を選択するNeural Neighborhood Selectionポリシーを構築。
2026-11-08
FMIP: 混合整数線形計画問題(MILP)のための連続・整数変数結合フロー
FMIP: Joint Continuous-Integer Flow For Mixed-Integer Linear Programming
出典:arXiv Core: Combinatorial MILP & Quantum Compilation(Authors: Hongpei Li, Hui Yuan, Han Zhang et al. | 2025-07-31)
- MILPにおける整数変数と連続変数の間の複雑な結合関係を捉えきれない従来の生成モデルの限界を指摘。
- 整数変数と連続変数の結合分布を同時にモデル化する初の生成フレームワーク「FMIP」を提案。
- 情報のボトルネックを解消することで、より最適に近い解の生成とダウンストリームソルバーの加速を実現。
2026-11-08
整数線形計画法を用いたサンドパイル構成の計算
Computing sandpile configurations using integer linear programming
出典:arXiv Core: Combinatorial MILP & Quantum Compilation(Authors: Carlos A. Alfaro, Carlos E. Valencia, Marcos C. Vargas | 2020-08-31)
- 再帰的サンドパイル構成を特定の最適化問題の最適解として特徴付ける手法を提示。
- 再帰的構成の算出およびその構成の次数(Order)を計算するための2つの新しい整数線形計画法(MILP)モデルを提案。
- 線形計画法の双対性を利用することで、正則グラフの錐(Cone)における単位構成(Identity configuration)を計算可能にした。
2026-11-08
オンライン3D箱詰め問題におけるSHORE: 安定性モデリングによる効率的な空間利用と学習速度向上
SHORE: Stability-Hybrid On-Policy Reinforcement Learning for Online Bin Packing
出典:arXiv 2026: Calibration, Conformal & Optimal Transport(Authors: Chang Shi, Ann Majewicz Fey | 2026-11-05)
- SHOREは、オンライン3D箱詰め問題における箱の配置順序、向き、位置を決定する手法であり、特に未知の箱の到着に対応する。
- SHOREは、安定性モデリングにより、既存手法と比較して空間利用率を向上させ、学習ステップ数を大幅に削減する(0.4Mステップ vs 1Mステップ)。
- SHOREは、シミュレーション環境(Isaac Gym)および実ロボット環境での検証を通じて、その有効性と実装の容易性を示している。
2026-11-08
線形計画法のためのシュリンク・ラッピング(Shrink-Wrapping)軌道の幾何学的解析
Shrink-Wrapping trajectories for Linear Programming
出典:arXiv Core: Combinatorial MILP & Quantum Compilation(Authors: Yuriy Zinchenko | 2010-05-30)
- 線形計画法(LP)を双曲幾何学(Hyperbolic Programming, HP)の緩和問題として捉え、Renegarが提案した「Shrink-Wrapping」手法を研究。
- Shrink-Wrapping軌道が内点法における「中心経路(Central Path)」を一般化した概念であることを幾何学的に分析。
- 中心線付近における軌道の挙動を解析し、特定の病的なLPインスタンスにおいて中心経路と比較した際の特性を明らかに。
2026-11-08
GP-NASを用いたスタッキングアンサンブルによるマルチタスクNAS性能予測
Predict NAS Multi-Task by Stacking Ensemble Models using GP-NAS
出典:arXiv Core: Ensemble Diversity & Empirical Bayes(Authors: Ke Zhang | 2023-05-02)
- 少数の学習サンプルからアーキテクチャの性能を正確に予測するための過学習抑制とマルチタスク相関の活用を追求。
- ViT-Baseをベースとした探索空間(深さ、ヘッド数、MLP比率、埋め込み次元)に対し、データの前処理で複雑性を削減。
- GP-NASを用いたクロスバリデーションによるスタッキングアンサンブルを採用し、CVPR 2022 Track 2 Challengeで1位を獲得。
2026-11-08
NISQ回路コンパイルのためのKnuth-Bendix補完アルゴリズムとシャッフル代数
Knuth-Bendix Completion Algorithm and Shuffle Algebras For Compiling NISQ Circuits
出典:arXiv Core: Combinatorial MILP & Quantum Compilation(Authors: Raouf Dridi, Hedayat Alghassi, Sridhar Tayur | 2019-04-30)
- 量子回路のコンパイルを、非可換多項式代数 $\mathbb Q\langle X\rangle$ 上の書き換えシステムとして定式化。
- ハードウェアの制約を書き換え規則 $\mathcal R$ として定義し、理想的なゲートをその正規形へ変換することでコンパイルを行う。
- 書き換えシステムの生成に、Knuth-Bendix補完アルゴリズムとシャッフル代数上のBuchbergerアルゴリズムの2つの手法を導入。
2026-11-08
ベイズ相関均衡、ベイズゲームにおけるノーレグレット動態、および無秩序の価格
Bayes correlated equilibria, no-regret dynamics in Bayesian games, and the price of anarchy
出典:arXiv Core: Ensemble Diversity & Empirical Bayes(Authors: Kaito Fujii | 2023-04-11)
- 不完全情報ゲーム(ベイズゲーム)における相関均衡の効率的な計算と、無秩序の価格(Price of Anarchy)の境界に関する研究。
- 従来のノーレグレット動態ではベイズゲームにおける相関均衡の定義が複数存在し、計算可能性や性能保証が不明確であった問題を特定。
- 「不誠実なスワップ・レグレット(untruthful swap regret)」という新しいレグレットの概念を導入し、効率的な計算と性能保証の両立を提案。
2026-11-08
N-Fold整数計画法の理論と応用
Theory and Applications of N-Fold Integer Programming
出典:arXiv Core: Combinatorial MILP & Quantum Compilation(Authors: Shmuel Onn | 2009-11-21)
- 変数次元において基本的な線形および非線形整数計画問題を多項式時間で解くことを可能にする「n-fold整数計画法」の理論を提示。
- 多商品フロー問題や統計データベースにおけるプライバシー保護など、複数の応用分野において初の多項式時間アルゴリズムを導出。
- 複雑な組合せ最適化問題を、構造的な性質(n-fold構造)を利用することで効率的に解決する枠組みを確立。
2026-11-08
非線形整数計画法
Nonlinear Integer Programming
出典:arXiv Core: Combinatorial MILP & Quantum Compilation(Authors: Raymond Hemmecke, Matthias Köppe, Jon Lee et al. | 2009-06-28)
- 線形整数計画法と比較して、非線形システムにおける整数制約問題は未だ成熟していない分野である。
- 制約条件が線形であり、目的関数のみが非線形である単純な非線形整数問題の計算複雑性を中心に調査する。
- 目的関数の種類と組合せ構造の組み合わせにより計算複雑性は大きく変動し、一部の境界ケースでは多項式時間アルゴリズムが可能になる。
2026-11-08
組み合わせ最適化におけるLSTM Encoderの順序バイアスとPointer Networkの有効性
Combinatorial Optimization with Pointer Networks: Theory, Benchmarks, and Limitations [P]
出典:Reddit r/MachineLearning(ML Research Community)
- 組み合わせ最適化問題(例:2D Euclidean TSP)に対するPointer Networkの有効性と、LSTM Encoderの順序バイアスがパフォーマンスを阻害する可能性を指摘。
- 既存の順序依存モデル(LSTM Encoder)は、問題の不変性(permutation invariance)とミスマッチを起こし、パフォーマンスを低下させる。
- 大規模な問題スケール(N=20〜200)において、Pointer NetworkはGoogle OR-Toolsに対しても競争力のある、高速な(ミリ秒単位)高品質な解を生成する。
このページの要約は、収集パイプラインが自動生成した digest(要約)です。内容の正確なところは、必ず各項目の出典リンク先の原文で確認してください。出典の本文そのものは掲載していません。ジャンル分けも自動分類のため、周辺の話題が混ざることがあります。