論文の概要: Virtual Arc Consistency for Linear Constraints inCost Function Networks
- arxiv url: http://arxiv.org/abs/2509.17706v1
- Date: Mon, 22 Sep 2025 12:44:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-23 18:58:16.383995
- Title: Virtual Arc Consistency for Linear Constraints inCost Function Networks
- Title（参考訳）: コースト関数ネットワークにおける線形制約に対する仮想アーク整合性
- Authors: Pierre Montalbano, Simon de Givry, George Katsirelos,
- Abstract要約: 我々は線形制約を扱うために既存のSACアルゴリズムを適用した。
提案アルゴリズムは,複数のベンチマークにおいて,元のアルゴリズムと比較して下位境界を著しく改善することを示す。
- 参考スコア（独自算出の注目度）: 2.8675177318965037
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In Constraint Programming, solving discrete minimization problems with hard and soft constraints can be done either using (i) soft global constraints, (ii) a reformulation into a linear program, or (iii) a reformulation into local cost functions. Approach (i) benefits from a vast catalog of constraints. Each soft constraint propagator communicates with other soft constraints only through the variable domains, resulting in weak lower bounds. Conversely, the approach (ii) provides a global view with strong bounds, but the size of the reformulation can be problematic. We focus on approach (iii) in which soft arc consistency (SAC) algorithms produce bounds of intermediate quality. Recently, the introduction of linear constraints as local cost functions increases their modeling expressiveness. We adapt an existing SAC algorithm to handle linear constraints. We show that our algorithm significantly improves the lower bounds compared to the original algorithm on several benchmarks, reducing solving time in some cases.
- Abstract（参考訳）: 制約プログラミングでは、ハードとソフトの制約で離散最小化問題を解決することができる。
(i)ソフトグローバルな制約
二 線形プログラムに改定すること、又は
三 地方費用関数の改正
アプローチ
(i)制約の膨大なカタログの恩恵。
それぞれのソフト制約プロパゲータは、変数領域を通してのみ他のソフト制約と通信し、弱い下界をもたらす。
逆にアプローチは
(二) 強い境界を持った世界観を提供するが、改革の規模は問題となることがある。
アプローチに焦点をあてる
三 ソフトアーク整合(SAC)アルゴリズムが中間品質のバウンダリを生成する場合。
近年,局所的コスト関数として線形制約を導入することで,モデリング表現性が向上している。
我々は線形制約を扱うために既存のSACアルゴリズムを適用した。
提案アルゴリズムは,いくつかのベンチマークにおいて,元のアルゴリズムと比較して下位境界を著しく改善し,いくつかのケースでは解時間を削減する。
関連論文リスト
- Adaptive Graph Shrinking for Quantum Optimization of Constrained Combinatorial Problems [4.266376725904727]
最適化問題のQUBO定式化における変数数と制約を減らすために,グラフ縮小に基づく古典量子ハイブリッドフレームワークを提案する。
提案手法は, ソリューションの実現性の向上, 修理の複雑さの低減, ハードウェア限定インスタンスの量子最適化品質の向上を実現する。
論文 参考訳（メタデータ） (2025-06-17T07:11:48Z) - Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。
既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。
これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-04-21T17:15:48Z) - A Penalty-Based Guardrail Algorithm for Non-Decreasing Optimization with Inequality Constraints [1.5498250598583487]
伝統的な数学的プログラミングの解法は制約付き最小化問題を解くのに長い計算時間を必要とする。
ペナルティに基づくガードレールアルゴリズム(PGA)を提案する。
論文 参考訳（メタデータ） (2024-05-03T10:37:34Z) - Constrained Bi-Level Optimization: Proximal Lagrangian Value function
Approach and Hessian-free Algorithm [8.479947546216131]
We developed a Hessian-free gradient-based algorithm-termed proximal Lagrangian Value function-based Hessian-free Bi-level Algorithm (LV-HBA)
LV-HBAは特に機械学習アプリケーションに適している。
論文 参考訳（メタデータ） (2024-01-29T13:50:56Z) - Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。