Môi trường thử nghiệm quy hoạch nguyên
Giải bài toán quy hoạch tuyến tính nguyên nhỏ bằng phương pháp nhánh và cận chính xác, đồng thời xem mọi nút tìm kiếm. Điểm tốt nhất chỉ được báo cáo là tối ưu đã chứng minh khi toàn bộ cây tìm kiếm đã được duyệt.
Chương trình bị giới hạn ở 4.000 ký tự và 40 dòng, 8 biến và 8 ràng buộc có từ hai biến trở lên; giới hạn nút từ 1 đến 5.000 và quá trình tìm kiếm cũng dừng sau 3.000.000 bước số học chính xác. Mọi phép tính được thực hiện trên thiết bị của bạn trong tiến trình nền, giới hạn 15 giây. Tệp tải xuống gồm báo cáo JSON và CSV các nút. Dòng đầu tiên: maximize hoặc minimize và hàm mục tiêu. Sau đó viết mỗi ràng buộc trên một dòng. Tối đa 4.000 ký tự. Kiểm tra cài đặt trước khi chạy.
Kết quả của bạn
Môi trường thử nghiệm quy hoạch nguyên
- Viết hàm mục tiêu trên dòng đầu tiên, chẳng hạn maximize 5x + 4y.
- Thêm mỗi ràng buộc trên một dòng, các cận như x, y >= 0, và các dòng tùy chọn như integer x hoặc binary z, sử dụng biến trong chương trình.
- Đặt giới hạn số nút rồi chạy tìm kiếm.
- Đọc trạng thái, nghiệm khả thi tốt nhất hiện tại, cận tốt nhất và khoảng cách, sau đó tải báo cáo JSON hoặc CSV các nút.
Điều cần biết
Chương trình bị giới hạn ở 4.000 ký tự và 40 dòng, 8 biến và 8 ràng buộc có từ hai biến trở lên; giới hạn nút từ 1 đến 5.000 và quá trình tìm kiếm cũng dừng sau 3.000.000 bước số học chính xác. Mọi phép tính được thực hiện trên thiết bị của bạn trong tiến trình nền, giới hạn 15 giây. Tệp tải xuống gồm báo cáo JSON và CSV các nút.
Nhánh và cận
Mỗi nút giải chính xác bài toán thư giãn tuyến tính bằng phương pháp đơn hình. Biến nguyên có giá trị phân số được chia thành hai nhánh, x <= floor và x >= ceiling. Nút bị cắt bỏ nếu bài toán thư giãn không khả thi hoặc không thể tốt hơn điểm nguyên tốt nhất đã tìm thấy. Phương pháp: Wolsey, Integer Programming, ấn bản thứ 2, chương 7 (2020).
Ý nghĩa của “đã chứng minh”
Khi mọi nút đã được giải hoặc cắt bằng cận chính xác, nghiệm khả thi tốt nhất hiện tại được chứng minh là tối ưu hoặc bài toán được chứng minh là không khả thi. Nếu giới hạn số nút hoặc ngân sách bước làm dừng tìm kiếm sớm, nghiệm đó chỉ là điểm tốt nhất tìm được đến lúc ấy; báo cáo cho biết cận tốt nhất và khoảng cách giữa chúng.
Quy tắc nhập
Mặc định, mọi biến đều là số nguyên. Nếu liệt kê một số biến bằng cú pháp integer x, y, các biến được liệt kê vẫn là số nguyên còn các biến không được liệt kê là biến liên tục. Ràng buộc một biến trở thành cận. Nếu bài toán thư giãn không bị chặn, quá trình tìm kiếm sẽ dừng vì bài toán nguyên khi đó có thể không bị chặn hoặc không khả thi.