Một số kỹ thuật ước lượng cận trong việc giải bài toán quy hoạch toàn phương với biến nhị phân

Tóm tắt báo cáo

Bài toán quy hoạch toàn phương với biến nhị phân là bài toán NP-khó. Tuy nhiên đây là bài toán có rất nhiều ứng dụng trong nhiều lĩnh vực khác nhau. Do tính chất nhị phân của biến phương pháp nhánh cận là một sự lựa chọn hợp lý. Trong cách tiếp cận này kỹ thuật tính cận thu được dựa vào phân tích ma trận hàm mục tiêu rồi từ đó xây dựng bài toán nới lỏng. Tuy nhiên trong nhiều trường hợp cách làm này là không đủ. Với cách phân tích tính chất các bài toán con tại mỗi bước của thuật toán nhánh cận, chúng tôi đề xuất một cách ước lượng cận tốt hơn từ đó tăng tốc thuật toán.