論文の概要: Teaching LLMs to Generate Challenging MILP Instances via Solver Feedback

• arxiv url: http://arxiv.org/abs/2609.37356v1
• Date: Tue, 29 Sep 2026 12:19:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-30 21:28:47.477185
• Title: Teaching LLMs to Generate Challenging MILP Instances via Solver Feedback
• Title（参考訳）: LLMs to Generate Challenging MILP Instances through Solver Feedback
• Abstract要約: そこで我々は,学習アルゴリズムのベンチマークや学習アルゴリズムの学習を行うための,チャレンジャー・ソルバ非対称なセルフプレイ手法を開発した。 我々は Gemma-4-12B と Qwen3.5-4B を GRPO と OptiScribe-12B と OptiScribe-4B に微調整する。 問題は、同じサイズの公開ベンチマークよりも幅広い難易度の範囲をカバーし、密度と難易度に関する指示に従うとともに、公立図書館に欠けている家族の問題解決設定を調整できる。
• 参考スコア（独自算出の注目度）: 10.06624844066029
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Generating optimization instances that are both feasible and computationally challenging is crucial for benchmarking solvers and training learning-based optimization algorithms. Existing non-LLM generators rely on seed instances or parameter tuning, resulting in high test-time computational cost, while existing LLM generators lack explicit hardness measures. Recent reinforcement learning methods with verifier feedback evaluate only binary correctness, which is misaligned with generating challenging problems. We note that an optimization solver reports the cost of solving at several stages of its pipeline, and leverage this to design a reward that scores both the solvability and the hardness of generated problems, measured by branch-and-bound nodes and post-cut relaxation gaps. Our key idea is a challenger-solver asymmetric self-play approach, where an LLM challenger generates progressively harder instances and the solver verifies feasibility and hardness, so no seed or training MILP instances are required. We fine-tune Gemma-4-12B and Qwen3.5-4B with GRPO and a size curriculum into OptiScribe-12B and OptiScribe-4B, which generate feasible yet challenging MILP problems from natural language instructions. On capacitated facility location and max-cut, OptiScribe-12B raises median SCIP search nodes by 1.7-5x and post-cut gaps by 1.1-1.7x over its base model and improves the feasibility rate on facility location by 9-19 points, while OptiScribe-4B raises median nodes by up to 15.6x. The problems cover a wider difficulty range than public benchmarks of the same size, follow instructions on density and difficulty, and can tune solver settings for families that public libraries lack. These results indicate that optimization-specific rewards, used in self-play mode, can teach LLMs to generate high-difficulty optimization benchmarks. We will release our code and models publicly on acceptance.
• Abstract（参考訳）: 実現可能かつ計算的に困難な最適化インスタンスの生成は、ソルバのベンチマークや学習ベースの最適化アルゴリズムのトレーニングに不可欠である。 既存のLLMジェネレータはシードインスタンスやパラメータチューニングに依存しており、既存のLCMジェネレータは明示的な硬度測定をしていないが、テストタイムの計算コストが高い。 検証器フィードバックを用いた最近の強化学習手法は二項正当性のみを評価するが、これは難解な問題の発生と不一致である。 最適化ソルバはパイプラインの複数段階での解法コストを報告し、これを利用して、分岐ノードと切断後緩和ギャップによって測定された、発生した問題の可解性と硬度の両方をスコアする報酬を設計する。 我々のキーとなるアイデアは、挑戦者-解決者非対称な自己再生アプローチであり、LLMチャレンジャーが徐々に難しいインスタンスを生成し、解決者が実現可能性と硬さを検証するため、MILPインスタンスのシードやトレーニングは不要である。 我々は Gemma-4-12B と Qwen3.5-4B を GRPO と OptiScribe-12B と OptiScribe-4B に微調整する。 容量制限された施設位置と最大カットでは、OptiScribe-12Bは中央値のSCIPサーチノードを1.7-5x、ポストカットギャップを1.1-1.7x、施設位置のフィージビリティ率を9-19ポイント、OptiScribe-4Bは15.6倍に向上する。 問題は、同じサイズの公開ベンチマークよりも幅広い難易度の範囲をカバーし、密度と難易度に関する指示に従うとともに、公立図書館に欠けている家族の問題解決設定を調整できる。 これらの結果は、自己再生モードで使用される最適化固有の報酬は、LLMに高次最適化ベンチマークを生成することができることを示している。 受け入れ次第、コードとモデルを公開します。

関連論文リスト

• OptiVerse: A Comprehensive Benchmark towards Optimization Problem Solving [16.7333612841671]
  我々は、無視されたドメインにまたがる1,000のキュレートされた問題の総合ベンチマークであるOptiVerseを紹介する。 GPT-5.2 や Gemini-3 のような先進モデルでさえ27% を超える精度で苦戦している。 本稿では,時間的オーバーヘッドを伴わずにモデリングプロセスの精度を向上させるデュアルビュー監査エージェントを提案する。
  論文  参考訳（メタデータ） (2026-04-23T10:12:32Z)
• SolverLLM: Leveraging Test-Time Scaling for Optimization Problem via LLM-Guided Search [58.116954449750544]
  多様な最適化問題を解決するために,テスト時間スケーリングを活用したトレーニング不要のフレームワークを導入する。 直接的に解くのではなく、数学的定式化を生成し、新しいモンテカルロ木探索戦略によって導かれる解法対応のコードに変換する。
  論文  参考訳（メタデータ） (2025-10-19T16:21:19Z)
• OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization Modeling [62.19438812624467]
  大規模言語モデル (LLM) は数学的推論における問題解決能力を示した。 本稿では,人間可読入力と出力を用いたエンドツーエンド最適化問題のベンチマークであるOptiBenchを提案する。
  論文  参考訳（メタデータ） (2024-07-13T13:27:57Z)
• Navigating the Labyrinth: Evaluating LLMs' Ability to Reason About Search Problems [62.76627483915117]
  大規模言語モデル(LLM)は、最近、数学と推論ベンチマークで印象的なパフォーマンスを達成した。 直感的なパズルにインスパイアされた11のユニークな検索問題を含む新しいベンチマークであるSearchBenchを紹介した。 ステップバイステップで言語のみの推論を用いることで、最も先進的なLLMでさえ、SearchBenchの解決に失敗することを示します。
  論文  参考訳（メタデータ） (2024-06-18T00:44:58Z)

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

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