論文の概要: Integer and Constraint Programming Revisited for Mutually Orthogonal
Latin Squares
- arxiv url: http://arxiv.org/abs/2103.11018v1
- Date: Fri, 19 Mar 2021 20:45:55 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-23 14:17:06.085803
- Title: Integer and Constraint Programming Revisited for Mutually Orthogonal
Latin Squares
- Title(参考訳): 直交ラテン方形に対する整数と制約プログラミングの再検討
- Authors: Noah Rubin, Curtis Bright, Kevin K. H. Cheung, Brett Stevens
- Abstract要約: 相互直交ラテン四角形(MOLS)の集合の探索に整数プログラミング(IP)と制約プログラミング(CP)を用いた結果を提供する。
最先端の解決器をブラックボックスとして使用することで、すべてのオーダーで最大10個のMOLSを素早く見つけることができました。
また,IPおよびCPソルバを用いたMOLSの三重探索の有効性を解析し,そのタイミングを以前に公表したものと比較し,この手法を用いた実行時間を推定し,順序10の三重のMOLSの存在を決定するという長年のオープンな問題を解決する。
- 参考スコア(独自算出の注目度): 8.793721044482613
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we provide results on using integer programming (IP) and
constraint programming (CP) to search for sets of mutually orthogonal latin
squares (MOLS). Both programming paradigms have previously successfully been
used to search for MOLS, but solvers for IP and CP solvers have significantly
improved in recent years and data on how modern IP and CP solvers perform on
the MOLS problem is lacking. Using state-of-the-art solvers as black boxes we
were able to quickly find pairs of MOLS (or prove their nonexistence) in all
orders up to ten. Moreover, we improve the effectiveness of the solvers by
formulating an extended symmetry breaking method as well as an improvement to
the straightforward CP encoding. We also analyze the effectiveness of using CP
and IP solvers to search for triples of MOLS, compare our timings to those
which have been previously published, and estimate the running time of using
this approach to resolve the longstanding open problem of determining the
existence of a triple of MOLS of order ten.
- Abstract(参考訳): 本稿では,整数プログラミング (IP) と制約プログラミング (CP) を用いて相互直交ラテン二乗 (MOLS) の集合を探索する。
どちらのプログラミングパラダイムも以前はMOLSの探索に使われてきたが、近年ではIPとCPの解法が大幅に改善され、MOLS問題における最新のIPとCPの解法がどのように機能するかのデータが不足している。
最先端の解決器をブラックボックスとして使用することで、すべての順序でMOLSのペア(あるいはその非存在を証明)を素早く見つけることができました。
さらに, 拡張対称性分割法を定式化し, 解法の有効性を向上させるとともに, 簡単なcp符号化も改善した。
また、CPとIPソルバを用いてMOLSの三重項を探索し、そのタイミングを以前に発表されたものと比較し、この手法を用いた実行時間を推定して、10のMOLSの三重項の存在を判断する長年の未解決問題の解決を図った。
関連論文リスト
- Domain-Independent Dynamic Programming [6.437469175415774]
ドメイン独立動的プログラミング(DIDP)は動的プログラミング(DP)に基づく新しいモデルベースパラダイムである
AI計画にインスパイアされた状態遷移システムに基づくDPモデルを定義するフォーマリズムである動的プログラミング記述言語(DyPDL)を導入する。
探索アルゴリズムを用いてDyPDLモデルの解法と7つのDIDP解法を提案する。
論文 参考訳(メタデータ) (2024-01-25T01:48:09Z) - Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳(メタデータ) (2023-07-01T18:35:21Z) - Twice Regularized Markov Decision Processes: The Equivalence between
Robustness and Regularization [64.60253456266872]
マルコフ決定プロセス(MDP)は、変化または部分的に知られているシステムのダイナミクスを扱うことを目的としている。
規則化されたMDPは、時間的複雑さを損なうことなく、ポリシー学習の安定性を高める。
ベルマン作用素は、収束と一般化を保証する計画と学習スキームを導出することができる。
論文 参考訳(メタデータ) (2023-03-12T13:03:28Z) - DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean
Optimization [10.513103815142731]
PBO(Pseudo-Boolean Optimization)の解法における局所探索アルゴリズムの改良法について検討する。
我々のアルゴリズムであるDeciLS-PBOは最先端のアルゴリズムと比較して有望な性能を持つ。
論文 参考訳(メタデータ) (2023-01-28T17:03:56Z) - Domain-Independent Dynamic Programming: Generic State Space Search for
Combinatorial Optimization [13.386517072025722]
動的プログラミング(DP)に基づく新しいモデルベースパラダイムであるドメイン非依存動的プログラミング(DIDP)を提案する。
DPモデルを定義するフォーマリズムである動的プログラミング記述言語(DyPDL)を提案し、DyP(CAASDy)のためのコスト代数型A*ソルバーを開発する。
論文 参考訳(メタデータ) (2022-11-26T00:15:45Z) - Learning Pseudo-Backdoors for Mixed Integer Programs [48.36587539004464]
そこで我々は,Mixed Programs (MIP) の解法として,擬似バックドア(擬似バックドア)と呼ばれる一連の決定変数の優先順位付けを学習し,解時間を短縮する機械学習手法を提案する。
我々のアプローチは、これらの変数の分岐のみが最適積分解と最適性の証明となるような、小さな変数の集合に対応する強いバックドアの概念から着想を得ている。
強力なバックドアに対する擬似バックドアの重要な利点は、データ駆動の識別や予測に非常に適している点である。
論文 参考訳(メタデータ) (2021-06-09T13:59:53Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - Solving Inverse Problems by Joint Posterior Maximization with
Autoencoding Prior [0.0]
JPal Autoencoder (VAE) が先行する画像における不適切な逆問題解決の問題に対処する。
本手法は,提案した目的関数を満たすのに十分であることを示す。
結果は、より堅牢な見積もりを提供するアプローチの堅牢性も示しています。
論文 参考訳(メタデータ) (2021-03-02T11:18:34Z) - Exact Optimization of Conformal Predictors via Incremental and
Decremental Learning [46.9970555048259]
Conformal Predictors (CP) はMLメソッドのラッパーであり、データ分散に対する弱い仮定の下でエラー保証を提供する。
分類や回帰から異常検出まで幅広い問題に適している。
本研究では,基礎となるML手法と組み合わせて学習し,漸進的・漸進的学習を活用することにより,CP分類器を著しく高速化できることを示す。
論文 参考訳(メタデータ) (2021-02-05T15:31:37Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。