論文の概要: IntSat: Integer Linear Programming by Conflict-Driven Constraint-Learning

• arxiv url: http://arxiv.org/abs/2402.15522v1
• Date: Fri, 16 Feb 2024 12:48:40 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-03 19:17:21.180167
• Title: IntSat: Integer Linear Programming by Conflict-Driven Constraint-Learning
• Title（参考訳）: IntSat: 競合駆動の制約学習による整数線形プログラミング
• Authors: Robert Nieuwenhuis, Albert Oliveras, Enric Rodriguez-Carbonell
• Abstract要約: いわゆる Conflict-Driven Clause-Learning スキームを線形プログラミングに拡張する。 本稿では,これらの手法を効率的に実装する方法を説明し,改善の可能性について論じる。 我々の研究は、非常に未成熟な段階でも、我々の技術はICP解決における最先端技術に対する有用な補完であることを示す基本的な実装で裏付けられている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: State-of-the-art SAT solvers are nowadays able to handle huge real-world instances. The key to this success is the so-called Conflict-Driven Clause-Learning (CDCL) scheme, which encompasses a number of techniques that exploit the conflicts that are encountered during the search for a solution. In this article we extend these techniques to Integer Linear Programming (ILP), where variables may take general integer values instead of purely binary ones, constraints are more expressive than just propositional clauses, and there may be an objective function to optimise. We explain how these methods can be implemented efficiently, and discuss possible improvements. Our work is backed with a basic implementation that shows that, even in this far less mature stage, our techniques are already a useful complement to the state of the art in ILP solving.
• Abstract（参考訳）: 最先端のSATソルバは今や巨大な現実世界のインスタンスを処理できる。 この成功の鍵は、ソリューションの探索中に遭遇する競合を利用する数多くのテクニックを含む、いわゆるConflict-Driven Clause-Learning(CDCL)スキームである。 本稿では、これらの手法を整数線形プログラミング(ilp)に拡張します。変数が純粋に二項ではなく一般の整数値を取る場合、制約は命題節よりも表現力が高く、最適化する目的関数が存在する場合があります。 これらの手法を効率的に実装する方法を説明し、改善の可能性について議論する。 我々の研究は、非常に未成熟な段階でも、我々の技術はICP解決における最先端技術に対する有用な補完であることを示す基本的な実装で裏付けられている。

関連論文リスト

• Learning Valid Dual Bounds in Constraint Programming: Boosted Lagrangian Decomposition with Self-Supervised Learning [2.8425837800129696]
  ラグランジアン分解(LD)は、制約付き最適化問題に対して二重境界を与える緩和法である。 この研究は、制約プログラミングにおいて有効な双対境界を学習するための最初の一般的な方法を示す。
  論文  参考訳（メタデータ） (2024-08-22T19:26:29Z)
• Near-Optimal Solutions of Constrained Learning Problems [85.48853063302764]
  機械学習システムでは、振る舞いを縮小する必要性がますます顕在化している。 これは、双対ロバスト性変数を満たすモデルの開発に向けた最近の進歩によって証明されている。 この結果から, 豊富なパラメトリゼーションは非次元的, 有限な学習問題を効果的に緩和することが示された。
  論文  参考訳（メタデータ） (2024-03-18T14:55:45Z)
• Evaluating and Improving Tool-Augmented Computation-Intensive Math Reasoning [75.74103236299477]
  CoT(Chain-of- Thought prompting)とツール拡張は、大きな言語モデルを改善するための効果的なプラクティスとして検証されている。 ツールインターフェース,すなわち textbfDELI を用いた推論ステップを考慮に入れた新しい手法を提案する。 CARPと他の6つのデータセットの実験結果から、提案されたDELIは、主に競合ベースラインを上回っていることが示された。
  論文  参考訳（メタデータ） (2023-06-04T17:02:59Z)
• Object Representations as Fixed Points: Training Iterative Refinement Algorithms with Implicit Differentiation [88.14365009076907]
  反復的洗練は表現学習に有用なパラダイムである。 トレーニングの安定性とトラクタビリティを向上させる暗黙の差別化アプローチを開発する。
  論文  参考訳（メタデータ） (2022-07-02T10:00:35Z)
• Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias [27.06618125828978]
  本稿では,潜伏変数と選択バイアスの存在下での観測データからシステムの因果MAGを学習する問題を考察する。 本稿では,音と完全性を備えた計算効率のよい制約ベースの新しい手法を提案する。 提案手法と人工と実世界の両方の構造に関する技術の現状を比較した実験結果を提供する。
  論文  参考訳（メタデータ） (2021-10-22T19:49:59Z)
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning [85.50033812217254]
  アクター批判法はオフラインの強化学習に広く用いられているが、理論的にはそれほどよく理解されていない。 ペシミズムの原理を自然に取り入れた新しいオフラインアクター批判アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-08-19T17:27:29Z)
• Learning Implicitly with Noisy Data in Linear Arithmetic [94.66549436482306]
  PAC-セマンティックスにおける暗黙学習を拡張し、線形算術の言語における間隔としきい値の不確実性を扱う。 最適線形プログラミング対象制約の学習に対する我々の暗黙的アプローチは、実際的な明示的アプローチよりも著しく優れていることを示す。
  論文  参考訳（メタデータ） (2020-10-23T19:08:46Z)
• Inexact Derivative-Free Optimization for Bilevel Learning [0.27074235008521236]
  変分正則化技術は数理イメージングの分野で支配的である。 この問題を解決するための一般的な戦略は、これらのパラメータをデータから学習することだ。 上層問題の解法では、下層問題の正確な解にアクセスできると仮定することが一般的であり、実際は不可能である。 本稿では, 厳密な低レベル問題解を必要としない不正確な微分自由最適化アルゴリズムを用いて, これらの問題を解くことを提案する。
  論文  参考訳（メタデータ） (2020-06-23T00:17:32Z)
• A General Large Neighborhood Search Framework for Solving Integer Linear Programs [46.62993477453986]
  我々は整数プログラムの解法に重点を置いており、我々のアプローチは大規模近傍探索(SLN)パラダイムに根ざしている。 我々のLSSフレームワークは、Gurobiのような最先端の商用解法と比較して、大幅に性能が向上することを示した。
  論文  参考訳（メタデータ） (2020-03-29T23:08:14Z)

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

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