HUỲNH THÀNH TRUNG
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------
Huỳnh Thành Trung
HỆ THỐNG THÔNG TIN
KỸ THUẬT QUY HOẠCH RÀNG BUỘC, TÌM KIẾM CỤC
BỘ DỰA TRÊN RÀNG BUỘC VÀ PHÂN CỤM CÂN BẰNG
TRONG VIỆC GIẢI CÁC BÀI TOÁN TỐI ƯU TỔ HỢP
LUẬN VĂN THẠC SĨ KHOA HỌC
HỆ THỐNG THÔNG TIN
2016CLC
Hà Nội – 2017
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------
Huỳnh Thành Trung
KỸ THUẬT QUY HOẠCH RÀNG BUỘC, TÌM KIẾM CỤC BỘ DỰA
TRÊN RÀNG BUỘC VÀ PHÂN CỤM CÂN BẰNG TRONG VIỆC GIẢI
CÁC BÀI TOÁN TỐI ƯU TỔ HỢP
Chuyên ngành : Hệ thống thông tin
LUẬN VĂN THẠC SĨ KHOA HỌC
HỆ THỐNG THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC :
1. TS. Phạm Quang Dũng
2. GS. Katsumi Inoue
Hà Nội – 2017
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc
BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ
Họ và tên tác giả luận văn: Huỳnh Thành Trung
Đề tài luận văn: Kỹ thuật quy hoạch ràng buộc, tìm kiếm cục bộ dựa trên ràng
buộc và phân cụm cân bằng trong việc giải các bài toán tối ưu tổ hợp
Chuyên ngành: Hệ thống thông tin
Mã số SV: CBC16001
Tác giả, Người hướng dẫn khoa học và Hội đồng chấm luận văn xác
nhận tác giả đã sửa chữa, bổ sung luận văn theo biên bản họp Hội đồng ngày
24/03/2017 với các nội dung sau:
- Cấu trúc lại luận văn thành 4 chương (từ 7 chương trong bản luận văn ban
đầu). Cấu trúc của luận văn sau chỉnh sửa như sau:
Chương 1: Giới thiệu đề tài. Giới thiệu đề tài thực hiện
Chương 2: Cơ sở lý thuyết. Nêu lên các cơ sở lý thuyết về bài toán tối
ưu hóa tổ hợp, bài toán xếp lịch bảo vệ cao học, các hướng tiếp cận
giải bài toán tối ưu tổ hợp như tìm kiếm cục bộ, quy hoạch ràng buộc,
tìm kiếm cục bộ dựa trên ràng buộc và các kỹ thuật bổ trợ như Loại
bỏ đối xứng, Phân rã bài toán, Phân cụm.
Chương 3: Đề xuất thuật toán giải bài toán xếp lịch bảo vệ cao học.
Trình bày thuật toán đề xuất với các phương pháp sử dụng để cải thiện
mô hình hóa bài toán và các phương pháp sử dụng để tìm kiếm lời giải
cho bài toán, sau đó là thực nghiệm đánh giá so sánh kết quả của thuật
toán đề xuất.
Chương 4: Kết luận và các hướng phát triển. Tổng hợp các công việc
đã làm được và các hướng phát triển trong tương lai.
- Đánh số các trang bắt đầu từ phần nội dung chính của luận văn (thay vì từ
phần mục lục)
- Chỉnh sửa lại lỗi văn bản hình vẽ và tên hình vẽ bị nhảy (hình 20)
- Chỉnh sửa lại văn phong khoa học hơn (phần 2.3.2.1)
- Chỉnh sửa lại cách đánh số các định nghĩa cho không còn trùng lặp (phần
2.1.1 và 3.1.2.1)
- Chỉnh sửa lại phần tài liệu tham khảo cho thống nhất và chuẩn xác hơn
Ngày 29 tháng 03 năm 2017
Giáo viên hướng dẫn Tác giả luận văn
CHỦ TỊCH HỘI ĐỒNG
LỜI CẢM ƠN
Để hoàn thành luận văn tốt nghiệp này, lời đầu tiên tôi xin chân thành cảm ơn
các thầy giáo, cô giáo của Viện Công nghệ thông tin và Truyền thông Trường Đại học
Bách Khoa Hà Nội, những người đã dạy dỗ, trang bị những kíến thức bổ ích trong những
năm học vừa qua.
Tôi xin bày tỏ lòng biết ơn sâu sắc nhất tới thầy giáo Phạm Quang Dũng, người
đã tận tình hướng dẫn, chỉ bảo trong suốt thời gian học tập, thực tập và làm luận văn.
Tôi xin bày tỏ lòng biết ơn sâu sắc nhất tới giáo sư Katsumi Inoue cùng hai
nghiên cứu sinh Maxime Clement và Emir Demirovic, những người đã tận tình giúp đỡ
trong suốt thời gian thực tập nghiên cứu và làm luận văn tại National Institute of
Infomatics, Tokyo
Nhân dịp này tôi xin gửi lời cảm ơn chân thành tới gia đình, bạn bè, những người
thân đã cổ vũ, động viên tiếp thêm cho em nghị lực để tôi hoàn thành luận văn tốt
nghiệp.
Tôi xin chân thành cảm ơn!
Hà Nội, ngày 12 tháng 03 năm 2017
Học viên
Huỳnh Thành Trung
Danh mục các bảng biểu sử dụng trong đồ án
Bảng 1: Một số API tiêu biểu của thư viện OpenCBLS .................................. 40
Bảng 2: Bảng so sánh hiệu năng mô hình nQueen sử dụng Symmetry Breaking
......................................................................................................................... 43
Bảng 3: Bảng thực nghiệm đánh giá hiệu quả của kỹ thuật phân rã thu gọn 60
Bảng 4: Bảng thực nghiệm đánh giá hiệu quả của các kỹ thuật loại bỏ đối xứng
......................................................................................................................... 65
Bảng 5: Bảng thực nghiệm đánh giá hiệu quả của thuật toán KPBC ............ 74
Bảng 6: Bảng thực nghiệm đánh giá hiệu quả của Heuristic phân cụm ........ 75
Bảng 7: Bảng thực nghiệm đánh giá hiệu quả của Tìm kiếm lời giải tối ưu từng
phần với một phân hoạch ................................................................................ 83
Bảng 8: Bảng thực nghiệm đánh giá hiệu quả của Tìm kiếm cục bộ sử dụng lời
giải từng phần ................................................................................................. 88
Bảng 9: Bảng thực nghiệm đánh giá kết quả .................................................. 90
Danh mục các hình vẽ sử dụng trong đồ án
Hình 1: Minh họa cho bài toán TSP với 4 thành phố ..................................... 11
Hình 2: Ví dụ về chu trình con của bài toán TSP ........................................... 12
Hình 3: Minh họa Local search với bài toán 4-queen .................................... 20
Hình 4: Minh họa lời giải cực trị địa phương trong LS ................................. 21
Hình 5: Minh họa Backtracking Search với bài toán 4-queen ....................... 30
Hình 6: Tổng quan kiến trúc Constraint-based Local Search [7] ................. 32
Hình 7: Minh họa sự họat động của Dependency Graph ............................... 35
Hình 8: Minh họa Symmetry Breaking với bài toán N-queens ....................... 42
Hình 9: Sơ đồ khối thuật toán phân cụm K-means ......................................... 47
Hình 10: Ví dụ minh họa bài toán ghép cặp cực đại ...................................... 51
Hình 11: Ví dụ về ma trận biểu diễn hàm độ đo W ........................................ 51
Hình 12: Sơ đồ khối của thuật toán K-means balanced clustering ................ 56
Hình 13: Minh họa trường hợp không bảo toàn nghiệm khi phân rã kíp thời gian
......................................................................................................................... 59
Hình 14: Minh họa đối xứng giữa các cụm hội đồng – phòng ....................... 61
Hình 15: Minh họa đối xứng giữa chủ tịch – thư ký ....................................... 63
Hình 16: Mô hình pha 1-1 của bài toán MTDT .............................................. 67
Hình 17: Minh họa ghép cặp cực đại các hội đồng vào các cụm .................. 69
Hình 18: Ví dụ minh họa trường hợp kết quả phân cụm không sử dụng được70
Hình 19: Ví dụ minh họa thuật toán hậu xử lý kết quả phân cụm .................. 72
Hình 20: Mô hình pha 1-2 của bài toán ......................................................... 78
Hình 21: Minh họa phân hoạch láng giềng trong tìm kiếm cục bộ ................ 85
Danh mục các từ ngữ viết tắt và thuật ngữ
Chữ viết tắt
Tên đầy đủ
Ý nghĩa
NP
Non-determistic
polynomial
Lớp bài toán quyết định chưa có thuật
toán độ phức tạp đa thức để giải
LS
Local search
Tìm kiếm cục bộ
CP
Constraint
Programming
Quy hoạch ràng buộc
CBLS
Constraint-based
Local search
Tìm kiếm cục bộ dựa trên ràng buộc
MỤC LỤC
MỤC LỤC ...........................................................................................................
Chương 1: Giới thiệu đề tài............................................................................... 1
1.1. Giới thiệu chung ................................................................................... 1
1.2. Ngữ cảnh và lý do thực hiện ................................................................ 1
1.2.1. Bài toán tối ưu tổ hợp: tính cần thiết và các khó khăn ..................... 1
1.2.2. Các phương pháp giải quyết ............................................................. 2
1.2.3. Bài toán xếp lịch bảo vệ cao học ...................................................... 4
1.2.4. Lý do thực hiện ................................................................................. 4
1.3. Nội dung luận văn ................................................................................ 5
Chương 2: Cơ sở lý thuyết ................................................................................ 6
2.1. Bài toán tối ưu hóa tổ hợp .................................................................... 6
2.1.1. Một số khái niệm .............................................................................. 6
2.1.2. Phương pháp tổng trọng số trong bài toán tối ưu hóa tổ hợp đa mục tiêu
.................................................................................................................... 9
2.1.3. Ví dụ - Bài toán người du lịch (TSP) ............................................. 10
2.2. Bài toán xếp lịch bảo vệ cao học (MTDT) ......................................... 13
2.2.1. Mô tả bài toán ................................................................................. 13
2.2.2. Mô hình toán học của bài toán ....................................................... 14
2.2.3. Ví dụ minh họa ............................................................................... 16
2.3. Các hướng tiếp cận giải bài toán tối ưu tổ hợp .................................. 19
2.3.1. Tìm kiếm cục bộ ............................................................................. 19
2.3.2. Quy hoạch ràng buộc ...................................................................... 25
2.3.3. Tìm kiếm cục bộ dựa trên ràng buộc .............................................. 31
2.3.4. Các kỹ thuật bổ trợ ......................................................................... 40
Chương 3: Đề xuất thuật toán giải bài toán xếp lịch bảo vệ cao học ............. 57
3.1. Các phương pháp sử dụng cải thiện mô hình bài toán ....................... 57
3.1.1. Kỹ thuật phân rã thu gọn bài toán .................................................. 57
3.1.2. Kỹ thuật loại bỏ đối xứng ............................................................... 60
3.1.3. Đánh giá hiệu quả ........................................................................... 64
3.2. Các phương pháp sử dụng để tìm kiếm lời giải cho bài toán ............. 65
3.2.1. Heuristic phân cụm cân bằng .......................................................... 65
3.2.2. Tìm kiếm cục bộ sử dụng lời giải từng phần .................................. 76
Chương 4: Thực nghiệm đánh giá kết quả ...................................................... 89
4.1. Thực nghiệm ......................................................................................... 89
4.2. Đánh giá kết quả ................................................................................... 90
Chương 5: Kết luận và các hướng phát triển .................................................. 92
5.1. Kết luận ................................................................................................. 92
5.2. Các hướng phát triển ............................................................................. 93
CÔNG TRÌNH NGHIÊN CỨU CỦA TÁC GIẢ ........................................... 94
TÀI LIỆU THAM KHẢO .............................................................................. 95
Chương 1: Giới thiệu đề tài
1.1. Giới thiệu chung
Tên đề tài luận văn: Quy hoạch ràng buộc, tìm kiếm cục bộ dựa trên ràng buộc
và phân cụm cân bằng trong việc giải các bài toán tối ưu tổ hợp.
Sơ lược: Trong luận văn này, chúng tôi sẽ tìm hiểu chi tiết nền tảng kiến thức
về quy hoạch ràng buộc (constraint programming), tìm kiếm cục bộ dựa trên ràng
buộc (constraint-based local search) trong việc giải các bài toán tối ưu tổ hợp. Sau
đó, chúng tôi sẽ tiến hành triển khai các phương pháp nêu trên vào mô hình hóa và
thiết kế giải thuật cho bài toán xếp lịch bảo vệ cao học (Master thesis defense
timetabling), với đề xuất nổi bật là sử dụng phân cụm cân bằng (K-means balance
clustering) để phân rã bài toán thành các bài toán con để song song tìm các lời giải
tối ưu từng phần, giúp giảm thiểu đáng kể thời gian tính toán trong khi vẫn đảm bảo
được những phương án lịch đưa ra đạt chất lượng cao cho người quyết định (giáo vụ).
1.2. Ngữ cảnh và lý do thực hiện
1.2.1. Bài toán tối ưu tổ hợp: tính cần thiết và các khó khăn
Bài toán tối ưu tổ hợp là lớp bài toán trong đó chúng ta phải đưa ra lời giải quyết
định thỏa mãn một số những ràng buộc và đồng thời tối ưu hóa một hoặc nhiều những
mục tiêu có tính mâu thuẫn với nhau (ví dụ: trong bài toán lên kế hoạch sản xuất, chất
lượng sản phẩm, tốc độ sản xuất, hiệu quả sản xuất và chi phí sản xuất là những mục
tiêu có tính mâu thuẫn với nhau).
Trên thực tế hiện nay, các bài toán tối ưu hóa tổ hợp xuất hiện rất phổ biến trên
mọi khía cạnh của cuộc sống, từ sản xuất, năng lượng, vận chuyển hậu cần, giao
thông, tổ chức hành chính, y tế, etc … Việc giải quyết tốt các bài toán như vậy là rất
quan trọng, bởi chất lượng của các phương án đưa ra liên quan trực tiếp đến chất
2
lượng của cuộc sống chúng ta: công việc sản xuất được tối ưu hơn giúp đưa ra các
sản phẩm có chất lượng tốt mà giá thành hợp lý; năng lượng được sử dụng tối ưu nên
tiết kiệm hơn mà vẫn đảm bảo được hiệu năng; việc xếp lịch được tối ưu giúp cho
mọi người làm việc hiệu quả hơn và tránh được những rắc rối không mong muốn
(trùng thời gian, không cân đối, v.v…). Có rất, rất nhiều những ví dụ tương tự như
vậy, qua đó thể hiện mức độ phổ biến và nhu cầu giải quyết của các bài toán tối ưu
hóa tổ hợp trong cuộc sống là rất lớn.
Tuy rất phổ biến và cần thiết như vậy, việc giải các bài toán tối ưu hóa tổ hợp
nhìn chung gặp nhiều khó khăn. Các bài toán này thuộc lớp NP-đầy đủ, trong đó
chúng ta có thể kiểm chứng nhanh chóng bất kỳ một lời giải nào có phải là lời giải
thỏa mãn cho bài toán hay không (trong thời gian đa thức), nhưng hiện chưa có cách
nào tìm ra lời giải thỏa mãn một cách hiệu quả (độ phức tạp thuật toán vẫn là độ phức
tạp lũy thừa) [2, 6]. Nói cách khác, thời gian thực thi của tất cả các thuật toán hiện tại
cho những bài toán này đều tăng rất nhanh theo kích thước bài toán.
1.2.2. Các phương pháp giải quyết
Mặc dù các bài toán tối ưu hóa tổ hợp rất khó để giải quyết, các nhà nghiên
cứu về tối ưu hóa trong những năm qua vẫn cố gắng nghiên cứu tìm ra các phương
pháp để giải các bài toán này một cách tốt nhất có thể được. Có thể chia các phương
pháp thành hai dạng chính:
- Các phương pháp giải đúng: tiêu biểu có thể kể đến
o Constraint programming (Quy hoạch ràng buộc): là khuôn mẫu lập
trình trong đó mối quan hệ của các biến quyết định được biểu diễn bằng
các ràng buộc. Người dùng có thể sử dụng các ràng buộc và các biến
quyết định để mô hình hóa bài toán cần giải, sau đó sử dụng các phương
pháp cắt tỉa không gian tìm kiếm dựa vào sự lan truyền của các ràng
buộc để tìm ra lời giải cho bài toán. Phương pháp này đảm bảo đưa ra
3
được lời giải tốt nhất nhờ vào việc tìm kiếm quay lui, không gian lời
giải được vét cạn. Ưu điểm của quy hoạch ràng buộc là người dùng có
thể sử dụng các ràng buộc được định nghĩa trước hoặc tự mình định
nghĩa để mô hình hóa bài toán, các ràng buộc này khá tự nhiên với cách
hiểu của con người và linh hoạt cho việc mô hình hóa.
o Integer Linear Programming (Quy hoạch nguyên): là khuôn mẫu lập
trình trong đó sử dụng các biến nguyên và sử dụng các quan hệ tuyến
tính để biểu diễn mô hình bài toán cần giải, sau đó sử dụng các phương
pháp như cắt tỉa, đơn hình, v.v… để tìm ra lời giải của bài toán.
o Logic Programming (Quy hoạch logic): là khuôn mẫu lập trình trong
đó sử dụng các vị từ (có thể hiểu là các biến boolean, nhận giá trị true
hoặc false) để mô hình hóa bài toán thông qua các mệnh đề, sau đó sử
dụng các giải thuật để tìm kiếm lời giải của bài toán, phổ biến nhất là
tìm kiếm quay lui (backtracking search).
- Các phương pháp xấp xỉ: sử dụng các metaheuristic, có thể chia thành 2 loại
o Local search (Tìm kiếm cục bộ): là thuật toán xấp xỉ trong đó đòi hỏi
chúng ta phải mô hình hóa được không gian lời giải của bài toán và mối
quan hệ láng giềng giữa các lời giải. Trong quá trình tìm kiếm, giải
thuật sẽ di chuyển lần lượt qua các lời giải lân cận với lời giải hiện tại
tại mỗi bước với mong muốn tìm được lời giải tối ưu. Ưu điểm của tìm
kiếm cục bộ là có thể làm việc trong thời gian tùy ý, do đó có ích khi
giải quyết các bài toán tối ưu tổ hợp cần đưa ra một lời giải tốt trong
thời gian bị hạn chế. Tuy nhiên nhược điểm của tìm kiếm cục bộ là lời
giải tìm được có thể là không tối ưu nhất mà bị kẹt ở một tối ưu cục bộ.
Các metaheuristic là local search tiêu biểu có thể kể đến là hill-
climbing, tabu search, simulated annealing, v.v…
4
o Global search (Tìm kiếm toàn cục): trái với local search – thực hiện
việc tìm kiếm lời giải tối ưu thông qua thông tin cục bộ của một lời giải
với các lời giải láng giềng của nó, tìm kiếm toàn cục thường dựa vào
thông tin của một quần thể các lời giải để tìm kiếm lời giải tối ưu. Các
metaheuristic là global search tiêu biểu có thể kể đến là genetic
algorithm, ant colony optimization, evolutionary computation, v.v…
1.2.3. Bài toán xếp lịch bảo vệ cao học
Bài toán xếp lịch cao học là một bài toán tối ưu hóa tổ hợp xuất hiện ở các
trường đại học của Việt Nam hiện nay. Tại trường Bách Khoa Hà Nội nói riêng và
các trường đại học nói chung, nghiệp vụ quản lý xếp lịch bảo vệ của trường vẫn được
thực hiện một cách thủ công, bằng công sức và kinh nghiệm của con người. Phương
pháp này có nhiều nhược điểm, bởi nghiệp vụ xếp lịch bảo vệ cao học là một nghiệp
vụ phức tạp bởi nhiều các ràng buộc (các giáo viên của một hội đồng không trùng
nhau, các giáo viên không trùng kíp, các hội đồng không trùng kíp phòng, yêu cầu
giảng viên trong/ngoài trường cho các vị trí thành viên trong hội đồng, v.v…) mà
người xếp lịch thủ công rất khó khăn trong việc theo dõi và kiểm soát. Hơn nữa, kể
cả khi những ràng buộc chặt này được thỏa mãn, thì lịch bảo vệ được xếp bởi con
người khó lòng đạt được sự tối ưu với tổ hợp các mục tiêu phức tạp như: mức độ phù
hợp của các phản biện với đề tài, một giáo viên không ngồi quá nhiều hội đồng, v.v…
Do đó việc giải quyết bài toán xếp lịch cao học tự động bằng thuật toán là nhu cầu
cần thiết.
1.2.4. Lý do thực hiện
Xuất phát từ nhu cầu thực tiễn của các bài toán tối ưu hóa tổ hợp nói chung
(phần 1.2.1) và bài toán xếp lịch bảo vệ cao học nói riêng (phần 1.2.3), chúng tôi:
5
- Tìm hiểu việc sử dụng quy hoạch ràng buộc và tìm kiếm cục bộ trong việc giải
quyết các bài toán tối ưu hóa tổ hợp với mong muốn có nền tảng kiến thức
vững chắc trong việc giải quyết các bài toán này.
- Đề xuất một thuật toán hiệu quả giải quyết bài toán xếp lịch bảo vệ cao học,
sử dụng quy hoạch ràng buộc, tìm kiếm cục bộ dựa trên ràng buộc. Ngoài ra,
thuật toán đề xuất còn sử dụng phân cụm cân bằng để phân rã bài toán thành
các bài toán con và xử lý song song. Với thuật toán đề xuất, chúng tôi mong
muốn đây sẽ là một giải pháp được áp dụng vào thực tế để giảm thiểu công
sức của các giáo vụ và tăng chất lượng tối ưu của các lịch được xếp.
1.3. Nội dung luận văn
Luận văn gồm có 5 chương chính:
Chương 1: Giới thiệu đề tài. Giới thiệu đề tài thực hiện
Chương 2: Cơ sở lý thuyết. Nêu lên các cơ sở lý thuyết về bài toán tối ưu hóa tổ hợp,
bài toán xếp lịch bảo vệ cao học, các hướng tiếp cận giải bài toán tối ưu tổ hợp như
tìm kiếm cục bộ, quy hoạch ràng buộc, tìm kiếm cục bộ dựa trên ràng buộc và các kỹ
thuật bổ trợ như Loại bỏ đối xứng, Phân rã bài toán, Phân cụm.
Chương 3: Đề xuất thuật toán giải bài toán xếp lịch bảo vệ cao học. Trình bày thuật
toán đề xuất với các phương pháp sử dụng để cải thiện mô hình hóa bài toán và các
phương pháp sử dụng để tìm kiếm lời giải cho bài toán, sau đó là thực nghiệm đánh
giá so sánh kết quả của thuật toán đề xuất.
Chương 4: Kết luận và các hướng phát triển. Tổng hợp các công việc đã làm được
và các hướng phát triển trong tương lai.
6
Chương 2: Cơ sở lý thuyết
2.1. Bài toán tối ưu hóa tổ hợp
2.1.1. Một số khái niệm
Như phần 1.2.1 đã giới thiệu, bài toán tối ưu hóa tổ hợp là lớp bài toán trong
đó chúng ta phải đưa ra lời giải/ quyết định thỏa mãn một số những ràng buộc/ giới
hạn và đồng thời tối ưu hóa một hoặc nhiều những mục tiêu có tính mâu thuẫn với
nhau. Đây là những bài toán xuất hiện và có vai trò quan trọng trên mọi lĩnh vực của
cuộc sống, từ năng lượng, giao thông vận tải, tổ chức hành chính, sản xuất, v.v… Sau
đây là định nghĩa cụ thể hơn cho các khái niệm liên quan và cho bài toán tối ưu hóa
tổ hợp.
Định nghĩa 2.1: Biến quyết định của bài toán (Decision variable)
Biến quyết định của bài toán tối ưu hóa tổ hợp là một biến nằm trong mô hình
của bài toán mà người ra quyết định có thể kiểm soát được giá trị của biến đó và cần
xác định giá trị cho biến đó.
Biến quyết định có thể coi như những tế bào xây dựng nên bài toán tối ưu hóa tổ
hợp. Đó không phải là những biến ngẫu nhiên, người ra quyết định hoàn toàn có thể
kiểm soát và quyết định được giá trị của nó. Ví dụ: số lượng những chiếc xe sẽ được
sản xuất, giá thành của một chiếc xe, v.v…. Biến quyết định của bài toán thường
được ký hiệu là x, và tập hợp các biến quyết định của bài toán là X.
Định nghĩa 2.2: Miền xác định của biến quyết định (Domain)
Miền giá trị của biến quyết định là tập hợp các giá trị có thể gán tới các biến đó.
Miền quyết định của biến có thể là một tập hữu hạn hoặc vô hạn các giá trị, miền
đó có thể là liên tục và rời rạc. Trong khuôn khổ của luận văn, chúng tôi chỉ xét các
bài toán tối ưu hóa tổ hợp rời rạc, trong đó miền của tất cả các biến quyết định cấu
