Một Heuristic Cải Tiến cho Các Bài Toán Ba-lô 0-1 Đa chiều

Đối với bài toán ba-lô 0-1 đa chiều, có một phương pháp heuristic tồn tại, dựa trên các số nhân Lagrange, cũng cho phép xác định một giới hạn phía trên cho giá trị tiêu chí tối ưu. Phương pháp heuristic này được mở rộng theo hai cách: (1) trong mỗi bước, không chỉ một mà nhiều giá trị số nhân được tính toán đồng thời, và (2) vào cuối cùng, giới hạn phía trên được tinh chỉnh bằng cách thay đổi một số giá trị số nhân. Từ việc so sánh sử dụng một loạt lớn các bài toán thử nghiệm khác nhau, các mở rộng dường như tạo ra sự cải thiện, trung bình, với chỉ một lượng thời gian tính toán bổ sung khiêm tốn.