Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Các vấn đề ràng buộc mềm với giá trị khoảng
Tóm tắt
Các ràng buộc và sở thích định lượng, hay chi phí, rất hữu ích trong việc mô hình hóa nhiều vấn đề thực tế. Tuy nhiên, trong nhiều bối cảnh, việc xác định giá trị sở thích chính xác là rất khó khăn, và hợp lý hơn khi cho phép sử dụng các khoảng sở thích. Chúng tôi định nghĩa vài khái niệm về giải pháp tối ưu cho các vấn đề như vậy, cung cấp các thuật toán để tìm giải pháp tối ưu và cũng để kiểm tra xem một giải pháp có phải là tối ưu hay không. Hầu hết thời gian, các thuật toán này chỉ yêu cầu giải quyết các vấn đề ràng buộc mềm, điều này gợi ý rằng có thể xử lý hình thức không chắc chắn này trong các ràng buộc mềm mà không làm tăng đáng kể công sức tính toán cần thiết để lý luận với những vấn đề như vậy. Điều này cũng được hỗ trợ bởi các kết quả thực nghiệm. Chúng tôi cũng xác định các lớp vấn đề mà ở đó các kết quả tương tự vẫn giữ nguyên nếu người dùng được phép sử dụng nhiều khoảng không đoạn rời thay vì chỉ một khoảng duy nhất.
Từ khóa
Tài liệu tham khảo
Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based constraint solving and optimization. JACM 44(2):201–236 (1997)
Bistarelli, S., Montanari, U., Rossi, F., Schiex, T., Verfaillie, G., Fargier, H.: Semiring-based CSPs and valued CSPs: frameworks, properties, and comparison. Constraints 4(3), 199–240 (1999)
Ceberio, M., Modave, F.: An interval-valued, 2-additive Choquet integral for multi-criteria decision making. In: IPMU’04 (2004)
Faltings, B., Macho-Gonzalez, S.: Open constraint programming. AI J. 161(1–2):181–208 (2005)
Fargier, H., Schiex, T., Verfaille, G.: Valued constraint satisfaction problems: hard and easy problems. In: IJCAI-95, pp. 631–637. Morgan Kaufmann, San Mateo (1995)
Gelain, M., Pini, M.S., Rossi, F., Venable, K.B.: Dealing with incomplete preferences in soft constraint problems. In: Proc. CP’07, volume 4741 of LNCS, pp. 286–300. Springer, New York (2007)
Gelain, M., Pini, M.S., Rossi, F., Venable, K.B., Walsh, T.: Dealing with incomplete preferences in soft constraint problems. In: Proc. CP’08, volume 5202 of LNCS, pp. 402–417. Springer, New York (2008)
Macho González, S., Ansótegui, C., Meseguer, P.: On the relation among open, interactive and dynamic CSP. In: The Fifth Workshop on Modelling and Solving Problems with Constraints (IJCAI’05) (2005)
Meseguer, P., Rossi, F., Schiex, T.: Soft constraints. In: Rossi F., Van Beek P, Walsh T. (eds.) Handbook of Constraint Programming. Elsevier, Amsterdam (2006)
Pini, M.S., Rossi, F., Venable, K.B., Dechter, R.: Robust solutions in unstable optimization problems. In: Proc. Recent Advances in Constraints, LNAI. Springer, New York (2009)
Rossi, F., Van Beek, P., Walsh, T. (eds.): Handbook of Constraint Programming. Elsevier, Amsterdam (2006)
Ruttkay, Z.: Fuzzy constraint satisfaction. In: Proceedings 1st IEEE Conference on Evolutionary Computing, pp. 542–547. Orlando (1994)
Zivan, R., Shapen, U., Meisels, A.: Meeting scheduling problem (MSP). Available at http://www.cs.st-andrews.ac.uk/~ianm/CSPLib/prob/prob046/index.html (2010)
Wilson, N., Grimes, D., Freuder, E.C.: A cost-based model and algorithms for interleaving solving and elicitation of CSPS. In: Proc. CP’07, volume 4741 of LNCS, pp. 666–680. Springer, New York (2007)
Yorke-Smith, N., Gervet, C.: Certainty closure: A framework for reliable constraint reasoning with uncertainty. In: Proc. CP’03, volume 2833 of LNCS, pp. 769–783. Springer, New York (2003)