Báo Cáo Tổng quan về một số phương pháp giải hệ ràng buộc quá mức

AN OVERVIEW OF CURRENT APPROACHES FOR SOLVING OVER-CONSTRAINED PROBLEMS

BẢN TÓM TẮT
​

Bài viết này trình bày khái quát những cách tiếp cận hiện hành để mô hình hóa và giải những
hệ ràng buộc quá mức. Những bài tóan này thường được thiết lập như là những bài tóan tối ưu tổ
hợp và có tồn tại nhiều cách hình thức hóa khác nhau để mô hình chúng. Về phương pháp giải, bài
viết sẽ khảo sát cả hai cách tiếp cận: tìm kiếm có hệ thống và tìm kiếm cục bộ. Cuối cùng bài viết
sẽ nói về một xu hướng mới trong phương pháp giải hệ ràng buộc quá mức: sự lai ghép giữa tìm
kiếm có hệ thống và tìm kiếm cục bộ.

ABSTRACT
​

This paper reviews existing approaches to model and solve over-constrained problems. These
problems are usually formulated as combinatorial optimization problems, and there exist different
formalisms to model them. Regarding solving methods, both systematic search and local search
approaches are considered.Finally, we discuss a new trend in solving approaches for over-constrained
systems: hybridization of these two above-mentioned paradigms.