値変更コスト付き動的SATの定式化とその解法
スポンサーリンク
概要
- 論文の詳細を見る
We address a dynamic decision problem in which decision makers must pay some costs when they change their decisions along the way. We formalize this problem as Dynamic SAT (DynSAT) with decision change costs, whose goal is to find a sequence of models that minimize the aggregation of the costs for changing variables. We provide two solutions to solve a specific case of this problem. The first uses a Weighted Partial MaxSAT solver after we encode the entire problem as a Weighted Partial MaxSAT problem. The second solution, which we believe is novel, uses the Lagrangian decomposition technique that divides the entire problem into sub-problems, each of which can be separately solved by an exact Weighted Partial MaxSAT solver, and produces both lower and upper bounds on the optimal in an anytime manner. To compare the performance of these solvers, we experimented on the random problem and the target tracking problem. The experimental results show that a solver based on Lagrangian decomposition performs better for the random problem and competitively for the target tracking problem.
論文 | ランダム
- Alternative splicing by participation of the group 2 intron ORF in extremely halotolerant and alkaliphilic Oceanobacillus iheyensis
- Enrichment of a novel marine ammonia-oxidizing archaeon obtained from sand of an eelgrass zone
- Diversity of culturable chitinolytic bacteria from rhizospheres of agronomic plants in Japan
- Contribution of anammox bacteria to benthic nitrogen cycling in a mangrove forest and shrimp ponds, Haiphong, Vietnam
- 臨床心理学キーワード(第60回)第1世代の行動療法/第2世代の行動療法/第3世代の行動療法