Modeling and Algorithm for Dynamic Multi-objective Weighted Constraint Satisfaction Problem

Tenda Okimoto, Tony Ribeiro, Maxime Clement, Katsumi Inoue

2014

Abstract

A Constraint Satisfaction Problem (CSP) is a fundamental problem that can formalize various applications related to Artificial Intelligence problems. A Weighted Constraint Satisfaction Problem (WCSP) is a CSP where constraints can be violated, and the aim of this problem is to find an assignment that minimizes the sum of weights of the violated constraints. Most researches have focused on developing algorithms for solving static mono-objective problems. However, many real world satisfaction/optimization problems involve multiple criteria that should be considered separately and satisfied/optimized simultaneously. Additionally, they are often dynamic, i.e., the problem hanges at runtime. In this paper, we introduce a Multi-Objective WCSP (MO-WCSP) and develop a novel MO-WCSP algorithm called Multi-Objective Branch and Bound (MO-BnB), which is based on a new solution criterion called (l, s)-Pareto solution. Furthermore, we first formalize a DynamicMO-WCSP (DMO-WCSP). As an initial step towards developing an algorithm for solving a DMO-WCSP, we focus on the change of weights of constraints and develop the first algorithm called Dynamic Multi-Objective Branch and Bound (DMO-BnB) for solving a DMO-WCSPs, which is based on MO-BnB. Finally, we provide the complexity of our algorithms and evaluate DMO-BnB with different problem settings.

Paper Citation

in Harvard Style

Okimoto T., Ribeiro T., Clement M. and Inoue K. (2014). Modeling and Algorithm for Dynamic Multi-objective Weighted Constraint Satisfaction Problem . In Proceedings of the 6th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART, ISBN 978-989-758-015-4, pages 420-427. DOI: 10.5220/0004816704200427

in Bibtex Style

@conference{icaart14,
author={Tenda Okimoto and Tony Ribeiro and Maxime Clement and Katsumi Inoue},
title={Modeling and Algorithm for Dynamic Multi-objective Weighted Constraint Satisfaction Problem},
booktitle={Proceedings of the 6th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,},
year={2014},
pages={420-427},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004816704200427},
isbn={978-989-758-015-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 6th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,
TI - Modeling and Algorithm for Dynamic Multi-objective Weighted Constraint Satisfaction Problem
SN - 978-989-758-015-4
AU - Okimoto T.
AU - Ribeiro T.
AU - Clement M.
AU - Inoue K.
PY - 2014
SP - 420
EP - 427
DO - 10.5220/0004816704200427