論文の概要: Towards Bound Consistency for the No-Overlap Constraint Using MDDs

• arxiv url: http://arxiv.org/abs/2601.14784v1
• Date: Wed, 21 Jan 2026 09:06:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-22 21:27:50.302225
• Title: Towards Bound Consistency for the No-Overlap Constraint Using MDDs
• Title（参考訳）: MDDを用いた非オーバーラップ制約の境界整合性に向けて
• Authors: Amaury Guichard, Laurent Michel, Hélène Verhaeghe, Pierre Schaus,
• Abstract要約: オーバラップ制約に対する最初のバウンダリ一貫性アルゴリズムを導出する。 新しいフィルタリングは、非オーバーラップ制約に対する古典的伝搬法を補完しているように見える。
• 参考スコア（独自算出の注目度）: 2.771897351607068
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Achieving bound consistency for the no-overlap constraint is known to be NP-complete. Therefore, several polynomial-time tightening techniques, such as edge finding, not-first-not-last reasoning, and energetic reasoning, have been introduced for this constraint. In this work, we derive the first bound-consistent algorithm for the no-overlap constraint. By building on the no-overlap MDD defined by Ciré and van Hoeve, we extract bounds of the time window of the jobs, allowing us to tighten start and end times in time polynomial in the number of nodes of the MDD. Similarly, to bound the size and time-complexity, we limit the width of the MDD to a threshold, creating a relaxed MDD that can also be used to relax the bound-consistent filtering. Through experiments on a sequencing problem with time windows and a just-in-time objective ($1 \mid r_j, d_j, \bar{d}_j \mid \sum E_j + \sum T_j$), we observe that the proposed filtering, even with a threshold on the width, achieves a stronger reduction in the number of nodes visited in the search tree compared to the previously proposed precedence-detection algorithm of Ciré and van Hoeve. The new filtering also appears to be complementary to classical propagation methods for the no-overlap constraint, allowing a substantial reduction in both the number of nodes and the solving time on several instances.
• Abstract（参考訳）: ノーオーバーラップ制約に対する有界一貫性を達成することはNP完全であることが知られている。 したがって、この制約に対してエッジ探索、No-first-not-last推論、エネルギティック推論などの多項式時間締め付け技術が導入された。 本研究では,ノンオーバーラップ制約に対する最初の有界整合アルゴリズムを導出する。 Ciré と van Hoeve が定義した非オーバーラップ MDD 上に構築することにより、ジョブの時間窓の境界を抽出し、MDD のノード数において、時間多項式の開始時間と終了時間を締め付けることができる。 同様に、サイズと時間複雑度を束縛するために、MDDの幅をしきい値に制限し、リラクテッドMDDを作成する。 時間ウィンドウとジャスト・イン・タイムの目的 (1 \mid r_j, d_j, \bar{d}_j \mid \sum E_j + \sum T_j$) を用いたシークエンシング実験により,提案したフィルタリングは,幅のしきい値であっても探索木に訪れるノードの数を,Ciré と van Hoeve が提案した先行検出アルゴリズムと比較してより小さくすることを示した。 新たなフィルタリングは、ノーオーバーラップ制約に対する古典的伝搬法を補完するものでもあり、ノード数と複数のインスタンスの解決時間の両方を大幅に削減できる。

関連論文リスト

• Finite-Time Information-Theoretic Bounds in Queueing Control [54.11376591632282]
  本稿では, 待ち行列の待ち行列を, 待ち行列と待ち行列の双方で処理するネットワーク上のスケジューリング問題において, 待ち行列の総長を求める新しいポリシーを導出する。 これらの結果は「ドリフトオンリー」な手法の基本的な制限を明らかにし、待ち行列制御における原則的、非漸近的最適性への道を示す。
  論文  参考訳（メタデータ） (2025-06-23T04:14:40Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• Large data limits and scaling laws for tSNE [1.2085509610251701]
  元の tSNE アルゴリズムの埋め込みは、$n から in$ への一貫した極限を持たないことを示す。 本稿では、魅力的なエネルギーの減衰を緩和し、一貫した極限を持つ再スケールモデルを提案する。
  論文  参考訳（メタデータ） (2024-10-16T21:43:02Z)
• Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine Constraints [21.38692458445459]
  ブラックボックス制約と既知のアフィン制約を結合した分散マルチエージェントベイズ最適化の問題について検討する。 単一エージェントの場合と同様の後悔/違反境界を実現するアルゴリズムが提案されている。
  論文  参考訳（メタデータ） (2023-10-02T08:07:36Z)
• Solving Projected Model Counting by Utilizing Treewidth and its Limits [23.81311815698799]
  予測モデルカウント(PMC)を解く新しいアルゴリズムを提案する。 いわゆる「ツリー幅」が最も顕著な構造パラメータの1つであるという観測から着想を得て,本アルゴリズムは入力インスタンスの一次グラフの小さなツリー幅を利用する。
  論文  参考訳（メタデータ） (2023-05-30T17:02:07Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  断片的な離散化は既存の離散化問題と矛盾しないことを示す。 この理論を2つの画像のマッチング問題に適用する。
  論文  参考訳（メタデータ） (2021-07-13T12:31:06Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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