論文の概要: Efficient Implementation of the Global Cardinality Constraint with Costs
- arxiv url: http://arxiv.org/abs/2502.02688v1
- Date: Tue, 04 Feb 2025 20:03:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-06 14:26:47.684587
- Title: Efficient Implementation of the Global Cardinality Constraint with Costs
- Title（参考訳）: コストを考慮したグローバルカルチナリティ制約の効率的な実装
- Authors: Margaux Schmied, Jean-Charles Regin,
- Abstract要約: 我々は、コストに対する基数制約を考慮に入れている。
これは、全ての異なる制約の一般化であり、それぞれの値が与えられた変数の集合によって解において取らなければならない回数を指定する。
ランドマークに基づく最短経路上の上限を扱う新しい手法を提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: The success of Constraint Programming relies partly on the global constraints and implementation of the associated filtering algorithms. Recently, new ideas emerged to improve these implementations in practice, especially regarding the all different constraint. In this paper, we consider the cardinality constraint with costs. The cardinality constraint is a generalization of the all different constraint that specifies the number of times each value must be taken by a given set of variables in a solution. The version with costs introduces an assignment cost and bounds the total sum of assignment costs. The arc consistency filtering algorithm of this constraint is difficult to use in practice, as it systematically searches for many shortest paths. We propose a new approach that works with upper bounds on shortest paths based on landmarks. This approach can be seen as a preprocessing. It is fast and avoids, in practice, a large number of explicit computations of shortest paths.
- Abstract（参考訳）: 制約プログラミングの成功は、部分的には関連するフィルタリングアルゴリズムのグローバルな制約と実装に依存している。
最近、これらの実装を実践的に改善する新しいアイデアが登場し、特に全ての異なる制約についてである。
本稿では,コストに対する基数制約について考察する。
濃度制約は、全ての異なる制約の一般化であり、それぞれの値が解の与えられた変数の集合によって取らなければならない回数を特定するものである。
コストのかかるバージョンは、割り当てコストを導入し、割り当てコストの合計を制限します。
この制約のアーク一貫性フィルタリングアルゴリズムは、多くの最短経路を体系的に検索するので、実際に使用するのは難しい。
ランドマークに基づく最短経路上の上限を扱う新しい手法を提案する。
このアプローチは前処理と見なすことができます。
高速で、実際には、最短経路の多くの明示的な計算を回避している。
関連論文リスト
- A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization [17.25924791071807]
複雑な制約に対する新しい種類の下次アルゴリズムを提案する。
提案手法は, 2-of-the-artアルゴリズムよりもはるかに高速であることを示す。
論文 参考訳（メタデータ） (2025-01-31T15:18:52Z) - Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints [10.047668792033033]
本稿では,オンライン凸最適化(OCO)フレームワークの時間的逆制約による一般化について検討する。
この問題では、凸判定セットから実行可能な動作を選択した後、各ラウンドのコスト関数とともに凸制約関数を$X,$とする。
我々は,一ラウンドに1回,線形プログラム(LP)ソルバに1回コールする*プロジェクションフリー*オンラインポリシーを提案する。
論文 参考訳（メタデータ） (2025-01-28T13:04:32Z) - Projection-Free Online Convex Optimization with Time-Varying Constraints [19.993839085310643]
逆時間制約によるオンライン凸最適化の設定について検討する。
固定可能な集合を投影することが難しいシナリオによって動機付けられ、線形最適化オラクル(LOO)を通してのみこの集合にアクセスするプロジェクションフリーアルゴリズムを考える。
我々は、長さ$T$のシーケンスで、全体$T$をLOOに呼び出し、$tildeO(T3/4)$ regret w.r.t.の損失と$O(T7/8)$制約違反を保証します。
論文 参考訳（メタデータ） (2024-02-13T21:13:29Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - Algorithm for Constrained Markov Decision Process with Linear
Convergence [55.41644538483948]
エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。
エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。
提案手法は(線形速度で)大域的最適値に収束することが示されている。
論文 参考訳（メタデータ） (2022-06-03T16:26:38Z) - Refined approachability algorithms and application to regret
minimization with global costs [0.38073142980732994]
ブラックウェルのアプローチ可能性 (Blackwell's approachability) は、2人のプレイヤー、すなわち意思決定者(Decision Maker)と環境(Environment)がベクター価値のペイオフで繰り返しゲームをする枠組みである。
我々は、ブラックウェルのアプローチ可能性のために、正規化リーダアルゴリズム(FTRL)のクラスを構築し、分析する。
この柔軟性により、これらのアルゴリズムを適用して、様々なオンライン学習問題への関心度を極力最小化することができる。
論文 参考訳（メタデータ） (2020-09-08T15:54:08Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z) - Beyond Worst-Case Analysis in Stochastic Approximation: Moment
Estimation Improves Instance Complexity [58.70807593332932]
近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。
最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。
提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
論文 参考訳（メタデータ） (2020-06-08T09:25:47Z) - Constrained Multiagent Rollout and Multidimensional Assignment with the
Auction Algorithm [0.0]
本稿では,制約付き決定論的動的プログラミングに適用可能なロールアウトアルゴリズムの拡張について考察する。
提案手法では,ベースが実現可能な解を生成する場合,ロールアウトアルゴリズムはコスト改善特性を有することを示す。
コスト改善特性は計算要求を大幅に削減した代替実装で維持されていることを示す。
論文 参考訳（メタデータ） (2020-02-18T07:09:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。