論文の概要: 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と、未知の制約ごとに単純なマージンとして知られる情報に基づくサンプリング戦略が自然選択となる。
我々は,混合整数二次計画法に基づく別のサンプリング手法と,オラクルモデルにおける凸最適化アルゴリズムにインスパイアされた線形分離法を提案する。
現実的な応用から着想を得た古典的問題や変種に関する実験を行い、客観値、二重有界時間、走行時間を含むいくつかの指標を用いて、異なる線形分離法とサンプリング戦略が結果の質にどのように影響するかを示す。
関連論文リスト
- 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) - A Lagrangian Duality Approach to Active Learning [119.36233726867992]
トレーニングデータのサブセットのみをラベル付けするバッチアクティブな学習問題を考察する。
制約付き最適化を用いて学習問題を定式化し、各制約はラベル付きサンプルにモデルの性能を拘束する。
数値実験により,提案手法は最先端の能動学習法と同等かそれ以上に機能することを示した。
論文 参考訳（メタデータ） (2022-02-08T19:18:49Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。