論文の概要: Solving 0-1 Integer Programs with Unknown Knapsack Constraints Using Membership Oracles

• arxiv url: http://arxiv.org/abs/2405.14090v4
• Date: Thu, 23 Oct 2025 14:10:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:01.888615
• Title: Solving 0-1 Integer Programs with Unknown Knapsack Constraints Using Membership Oracles
• Title（参考訳）: メンバシップオラクルを用いた未知のKnapsack制約による0-1整数プログラムの解決
• Authors: Rosario Messana, Rui Chen, Andrea Lodi, Alberto Ceselli,
• Abstract要約: 我々は、未知の制約に対して、メンバシップオラクルを用いて未知のknapsack制約で最適化問題を解くことを検討する。 意思決定者の目標は、オラクルの呼び出し数に関する予算の対象となる最善の解決策を見つけることである。 サポートベクトルマシン(SVM)に基づくバイナリ分類のためのアクティブラーニングに着想を得て,線形制約の学習と活用による問題解決のための枠組みを考案した。
• 参考スコア（独自算出の注目度）: 6.223797014768041
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider solving a combinatorial optimization problem with unknown knapsack constraints using a membership oracle for each unknown constraint such that, given a solution, the oracle determines whether the constraint is satisfied or not with absolute certainty. The goal of the decision maker is to find the best possible solution subject to a budget on the number of oracle calls. Inspired by active learning for binary classification based on Support Vector Machines (SVMs), we devise a framework to solve the problem by learning and exploiting surrogate linear constraints. The framework includes training linear separators on the labeled points and selecting new points to be labeled, which is achieved by applying a sampling strategy and solving a 0-1 integer linear program. Following the active learning literature, a natural choice would be SVM as a linear classifier and the information-based sampling strategy known as simple margin, for each unknown constraint. We improve on both sides: we propose an alternative sampling strategy based on mixed-integer quadratic programming and a linear separation method inspired by an algorithm for convex optimization in the oracle model. We conduct experiments on classical problems and variants inspired by realistic applications to show how different linear separation methods and sampling strategies influence the quality of the results in terms of several metrics including objective value, dual bound and running time.
• Abstract（参考訳）: 我々は、未知の制約ごとに会員オラクルを用いて未知のknapsack制約を用いて組合せ最適化問題を解くことを検討する。 意思決定者の目標は、オラクルの呼び出し数に関する予算の対象となる最善の解決策を見つけることである。 サポートベクトルマシン(SVM)に基づくバイナリ分類のためのアクティブラーニングに着想を得て,線形制約の学習と活用による問題解決のための枠組みを考案した。 本フレームワークは、ラベル付きポイント上で線形分離器を訓練し、サンプリング戦略を適用して0-1整数線形プログラムを解くことにより、ラベル付けすべき新しいポイントを選択する。 アクティブラーニングの文献に従えば、線形分類器としてのSVMと、未知の制約ごとに単純なマージンとして知られる情報に基づくサンプリング戦略が自然選択となる。 我々は,混合整数二次計画法に基づく別のサンプリング手法と,オラクルモデルにおける凸最適化アルゴリズムにインスパイアされた線形分離法を提案する。 現実的な応用から着想を得た古典的問題や変種に関する実験を行い、客観値、二重有界時間、走行時間を含むいくつかの指標を用いて、異なる線形分離法とサンプリング戦略が結果の質にどのように影響するかを示す。

関連論文リスト

• Learning-augmented smooth integer programs with PAC-learnable oracles [6.4126799144358975]
  予測オラクルを組み込んだフレームワークを導入し、目的の線形サロゲートを構築し、線形プログラミングによって解決する。 提案手法は,古典的な高密度政権から近距離政権へ効果的にトラクタブル近似を拡張できることを実証する。 帰納的アルゴリズムが有界擬似次元を持つことを証明し、ほぼ最適性能のオラクルを学習できるようにする。
  論文  参考訳（メタデータ） (2026-01-22T05:55:36Z)
• Randomized multi-class classification under system constraints: a unified approach via post-processing [8.354034992258482]
  ランダム化分類器上での線形汎関数として表現可能なシステムレベルの制約下でのマルチクラス分類の問題について検討する。 本稿では,与えられたベース分類器を調整し,再学習せずに一般制約を満たすポストプロセッシング手法を提案する。
  論文  参考訳（メタデータ） (2025-12-16T09:53:22Z)
• Online Inference of Constrained Optimization: Primal-Dual Optimality and Sequential Quadratic Programming [55.848340925419286]
  等式制約と不等式制約を持つ2次最適化問題の解に対するオンライン統計的推測について検討した。 これらの問題を解決するための逐次プログラミング(SSQP)手法を開発し、目的の近似と制約の線形近似を逐次実行することでステップ方向を計算する。 本手法は,Hjek と Le Cam の意味での最適原始双対制限行列を用いて局所正規性を示す。
  論文  参考訳（メタデータ） (2025-11-27T06:16:17Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
  本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。 数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
  論文  参考訳（メタデータ） (2024-09-02T12:55:27Z)
• Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization [1.1510009152620668]
  自己改善学習のための単純で問題に依存しないシーケンス復号法を提案する。 以前にサンプリングされたシーケンスを無視するためにポリシーを変更することで、目に見えない代替案のみを検討するように強制する。 本手法は,ジョブショップスケジューリング問題における従来のNCO手法よりも優れていた。
  論文  参考訳（メタデータ） (2024-07-24T12:06:09Z)
• Feature selection in linear SVMs via hard cardinality constraint: a scalable SDP decomposition approach [3.7876216422538485]
  線形支援ベクトルマシン(SVM)における組込み特徴選択問題について検討する。 濃度制約が適用され、完全に説明可能な選択モデルが導かれる。 問題は、濃度制約が存在するためNPハードである。
  論文  参考訳（メタデータ） (2024-04-15T19:15:32Z)
• Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving [73.58829980121767]
  本稿では,大域最適化に基づく二乗ジグソーパズルの解法を提案する。 この手法は完全に自動化されており、事前情報を前提とせず、未知または未知のピースオリエンテーションでパズルを扱うことができる。
  論文  参考訳（メタデータ） (2023-03-26T18:53:51Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Bilevel Optimization for Feature Selection in the Data-Driven Newsvendor Problem [8.281391209717105]
  本稿では、意思決定者が過去のデータにアクセス可能な機能ベースのニュースベンダー問題について検討する。 そこで本研究では,スパースモデル,説明可能なモデル,およびアウト・オブ・サンプル性能の改善を目的とした特徴選択について検討する。 本稿では,2レベルプログラムに対する混合整数線形プログラムの修正について述べる。
  論文  参考訳（メタデータ） (2022-09-12T08:52:26Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• A Lagrangian Duality Approach to Active Learning [119.36233726867992]
  トレーニングデータのサブセットのみをラベル付けするバッチアクティブな学習問題を考察する。 制約付き最適化を用いて学習問題を定式化し、各制約はラベル付きサンプルにモデルの性能を拘束する。 数値実験により,提案手法は最先端の能動学習法と同等かそれ以上に機能することを示した。
  論文  参考訳（メタデータ） (2022-02-08T19:18:49Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• On the Adversarial Robustness of LASSO Based Feature Selection [72.54211869067979]
  検討されたモデルでは、悪意のある敵がデータセット全体を観察し、レスポンス値やフィーチャーマトリックスを慎重に修正する。 両レベルの最適化問題として、敵の修正戦略を定式化する。 合成および実データを用いた数値的な例は,本手法が効率的かつ効果的であることを示している。
  論文  参考訳（メタデータ） (2020-10-20T05:51:26Z)
• Decomposition and Adaptive Sampling for Data-Driven Inverse Linear Optimization [12.610576072466895]
  この研究は、線形プログラムの未知のコストベクトルを推論することが目的である逆線形最適化に対処する。 本稿では,既存の手法と比較して,制約の少ない,一般的に許容可能なコスト見積の集合の回復を可能にする,新たな問題の定式化を導入する。
  論文  参考訳（メタデータ） (2020-09-16T22:25:31Z)
• Sparse Methods for Automatic Relevance Determination [0.0]
  まず、自動妥当性決定(ARD)について検討し、スパースモデルを実現するために、追加の正規化やしきい値設定の必要性を解析的に実証する。 次に、正規化ベースとしきい値ベースという2つの手法のクラスについて論じる。
  論文  参考訳（メタデータ） (2020-05-18T14:08:49Z)
• Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
  部分ラベル学習(Partial-label Learning, PLL)は、典型的な弱教師付き学習問題であり、各トレーニングインスタンスには、真のラベルである候補ラベルのセットが設けられている。 既存のほとんどの手法は、特定の方法で解決しなければならない制約付き最適化として精巧に設計されており、計算複雑性をビッグデータにスケールアップするボトルネックにしている。 本稿では,モデルと最適化アルゴリズムの柔軟性を備えた分類器の新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-02-19T08:35:15Z)

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

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