値推移コスト付き動的制約充足問題とその解法

DOI HANDLE Web Site BIBCODE 参考文献6件 オープンアクセス

書誌事項

タイトル別名
  • Dynamic CSP with Decision Transition Costs and its Solutions

抄録

The dynamic constraint satisfaction problem (DynCSP) is a sequence of CSP instances. By introducing a notion of decision transition costs, one natural optimization problem results, where we search for a sequence of solutions that minimizes a total sum of decision transition costs. We will refer to this problem as the dynamic constraint satisfaction problem with decision transition costs (DynCSP-DTC). Previously, Hatano and Hirayama have presented an integer linear programming formulation to apply Lagrangian decomposition to the SAT-version of the problem called Dynamic SAT with decision change costs(DynSAT-DCC). However, since their linear encoding of decision change costs was specially designed for DynSAT, a new encoding method is required when we try to extend Lagrangian decomposition to solve general DynCSP-DTC. In this paper, we will introduce the quadratic encoding of decision transition costs that enables Lagrangian decomposition to work on general DynCSP-DTC including DynSAT-DCC. Furthermore, we empirically show that, even on DynSAT-DCC, Lagrangian decomposition with quadratic encoding performs more efficiently than other methods.

収録刊行物

参考文献 (6)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ