論文の概要: Logic-Based Benders Decomposition in Answer Set Programming for Chronic Outpatients Scheduling

• arxiv url: http://arxiv.org/abs/2305.11969v1
• Date: Fri, 19 May 2023 19:34:47 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-24 01:44:50.808968
• Title: Logic-Based Benders Decomposition in Answer Set Programming for Chronic Outpatients Scheduling
• Title（参考訳）: 慢性退院者スケジューリングのための解集合プログラミングにおける論理型ベンダ分解
• Authors: Paola Cappanera, Marco Gavanelli, Maddalena Nonato, Marco Roma
• Abstract要約: Answer Set Programming (ASP)では、ユーザーは宣言的に問題を定義でき、効率的な解法でそれを解決できる。 他の研究領域では、論理ベースのベンダー分解(LBBD)が有効であることが証明された。 本稿では, 医療分野の応用を事例として, LBBD を ASP に適用する。
• 参考スコア（独自算出の注目度）: 2.370481325034443
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In Answer Set Programming (ASP), the user can define declaratively a problem and solve it with efficient solvers; practical applications of ASP are countless and several constraint problems have been successfully solved with ASP. On the other hand, solution time usually grows in a superlinear way (often, exponential) with respect to the size of the instance, which is impractical for large instances. A widely used approach is to split the optimization problem into sub-problems that are solved in sequence, some committing to the values assigned by others, and reconstructing a valid assignment for the whole problem by juxtaposing the solutions of the single sub-problems. On the one hand this approach is much faster, due to the superlinear behavior; on the other hand, it does not provide any guarantee of optimality: committing to the assignment of one sub-problem can rule out the optimal solution from the search space. In other research areas, Logic-Based Benders Decomposition (LBBD) proved effective; in LBBD, the problem is decomposed into a Master Problem (MP) and one or several Sub-Problems (SP). The solution of the MP is passed to the SPs, that can possibly fail. In case of failure, a no-good is returned to the MP, that is solved again with the addition of the new constraint. The solution process is iterated until a valid solution is obtained for all the sub-problems or the MP is proven infeasible. The obtained solution is provably optimal under very mild conditions. In this paper, we apply for the first time LBBD to ASP, exploiting an application in health care as case study. Experimental results show the effectiveness of the approach. We believe that the availability of LBBD can further increase the practical applicability of ASP technologies.
• Abstract（参考訳）: Answer Set Programming (ASP)では、ユーザーは宣言的に問題を定義でき、効率的な解決器で解決することができる。 一方、解時間は通常、インスタンスのサイズに関して超線形(しばしば指数関数的)に成長するが、大規模なインスタンスでは実用的ではない。 広く使われているアプローチは、最適化問題を逐次解決された部分問題に分割し、ある者は他の方法で割り当てられた値にコミットし、ある部分問題の解をジャクスタポスすることで、問題全体の有効な割り当てを再構築する。 一方、このアプローチは超線型的な振る舞いのため、はるかに高速であり、一方、最適性の保証は提供されない: 1つのサブプロブレムの割り当てにコミットすることは、探索空間から最適解を除外することができる。 他の研究領域では、論理ベースのベンダー分解(LBBD)が有効であることが証明され、LBBDでは、問題はマスター問題(MP)と1つまたは複数のサブプロブレム(SP)に分解される。 MPの解はSPに渡され、おそらく失敗する可能性がある。 障害が発生した場合、mpにno-goodが返され、新たな制約を追加することで再び解決される。 解過程は、すべてのサブ問題に対して有効な解が得られ、あるいはmpが実現不可能であることが証明されるまで反復される。 得られた溶液は、非常に穏やかな条件下で確実に最適である。 本稿では, 医療におけるlbbdの応用をケーススタディとして活用し, lbbdをaspに初めて適用する。 実験の結果,アプローチの有効性が示された。 LBBDが利用可能になったことで、ASP技術の実用性はさらに向上すると考えています。

関連論文リスト

• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。 本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。 提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
  論文  参考訳（メタデータ） (2024-11-04T15:17:19Z)
• Continuous Tensor Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems [0.6906005491572401]
  本研究では、教師なし学習(UL)に基づくCOソルバのための連続的アン緩和(CTRA)を提案する。 CTRAは、単一のトレーニング実行で多様なソリューションを見つけるための計算効率のよいフレームワークである。 数値実験により、CTRAにより、ULベースの解法は、既存の解法を繰り返すよりもはるかに高速にこれらの多様な解を見つけることができることが示された。
  論文  参考訳（メタデータ） (2024-02-03T15:31:05Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• Discovering Many Diverse Solutions with Bayesian Optimization [7.136022698519586]
  信頼領域を用いたランク順ベイズ最適化(ROBOT)を提案する。 ROBOTは、ユーザが特定した多様性基準に従って、多様なハイパフォーマンスソリューションのポートフォリオを見つけることを目的としている。 そこで本研究では,機能評価をほとんど必要とせず,高い性能の多様な解を多数発見できることを示す。
  論文  参考訳（メタデータ） (2022-10-20T01:56:38Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• A Mutual Information Maximization Approach for the Spurious Solution Problem in Weakly Supervised Question Answering [60.768146126094955]
  弱々しい教師付き質問応答は通常、最終的な答えのみを監督信号として持つ。 偶然に正解を導出する刺激的な解が多数存在するかもしれないが、そのような解の訓練はモデルの性能を損なう可能性がある。 本稿では,質問応答対と予測解間の相互情報の最大化により,このような意味的相関を明示的に活用することを提案する。
  論文  参考訳（メタデータ） (2021-06-14T05:47:41Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization [5.669790037378094]
  目標は、有限個の可能性の集合の中で最適解を見つけることである。 深部強化学習(DRL)はNP-ハード最適化問題を解くことを約束している。 制約プログラミング(CP)は最適化問題を解決する汎用ツールである。 本研究では,最適化問題の解法としてDRLとCPを用いた汎用ハイブリッド手法を提案する。
  論文  参考訳（メタデータ） (2020-06-02T13:54:27Z)
• sKPNSGA-II: Knee point based MOEA with self-adaptive angle for Mission Planning Problems [2.191505742658975]
  いくつかの問題には、多くの非支配的な解をもたらす多くの目的がある。 本稿では,最も重要な解を得るために設計された新しいアルゴリズムを提案する。 このアルゴリズムは無人航空機(UAV)ミッション計画問題における実世界の応用に応用されている。
  論文  参考訳（メタデータ） (2020-02-20T17:07:08Z)

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

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