Thực hiện phân nhánh cục bộ
Gần đây tôi đã đọc một số bài báo trong đó các tác giả sử dụng phân nhánh cục bộ cụ thể trong Benders Decomposition ( xem để tham khảo). Mặc dù tôi hiểu được phần nào cách hoạt động của thuật toán, nhưng tôi vẫn gặp khó khăn để hiểu cách nó được triển khai trong thực tế.
Ví dụ, có tuyên bố rằng chúng ta có thể chia vùng khả thi thành hai phần bằng cách sử dụng $\Delta(x_o,x) \leq \kappa$ và $\Delta(x_o,x) \geq \kappa+1$ được xác định lần lượt là các nhánh bên trái và bên phải.
Tôi đã tự hỏi nếu ai đó có thể giải thích ngắn gọn cách hoạt động này có thể được thực hiện từ góc độ mã hóa khi sử dụng trong Java API bằng cách sử dụng CPLEX.
Một số tài liệu tham khảo học thuật là:
Rei, W., Cordeau, JF, Gendreau, M., & Soriano, P. (2009). Tăng tốc độ phân hủy Benders bằng cách phân nhánh cục bộ . Tạp chí INFORMS về Máy tính, 21 (2), 333-345.
Baena, D., Castro, J., & Frangioni, A. (2020). Các phương pháp uốn cong ổn định để tối ưu hóa tổ hợp quy mô lớn, ứng dụng vào quyền riêng tư của dữ liệu . Khoa học Quản lý.
Trả lời
Bạn cần sử dụng lệnh gọi lại và CPLEX đã giới thiệu hệ thống gọi lại mới ("lệnh gọi lại chung") trong phiên bản 12.8 (tôi nghĩ) trong khi vẫn duy trì hỗ trợ, ít nhất là vào lúc này, cho hệ thống gọi lại ban đầu ("lệnh gọi lại kế thừa"). Chi tiết của việc phân nhánh phụ thuộc một phần vào hệ thống bạn sử dụng.
Với các lệnh gọi lại kế thừa, bạn tạo một lớp mở rộng IloCplex.BranchCallback và đính kèm nó vào mô hình của bạn bằng IloCplex.use (). Bên trong phương thức main (), bạn sử dụng một trong các quá tải của makeBranch () để tạo mỗi nhánh. Để tạo hai nút con, bạn gọi makeBranch () hai lần.
Với các lệnh gọi lại chung chung, bạn tạo một lớp triển khai giao diện IloCplex.Callback.Function và đính kèm nó vào mô hình của bạn bằng cách sử dụng quá tải khác của IloCplex.use (). Trong quá trình sử dụng () này, bạn phải chỉ định một mặt nạ cho các ngữ cảnh trong đó lệnh gọi lại được gọi, và cụ thể là bạn sẽ cần bao gồm ngữ cảnh "phân nhánh" trong mặt nạ. Lớp thực thi IloCplex.Callback.Function sẽ có một phương thức invoke (), mà CPLEX sẽ gọi, truyền vào một đối số kiểu IloCplex.Callback.Context. Trong quá trình triển khai của bạn invoke (), sau khi kiểm tra nếu cần thiết để chắc chắn rằng bạn đang ở trong ngữ cảnh phân nhánh, bạn sẽ gọi phương thức makeBranch () của đối tượng ngữ cảnh một lần cho mỗi nút con.
Trong cả hai cách tiếp cận, việc cố gắng tạo nhiều hơn hai nút con tại một nút sẽ khiến liên tục không-thời gian tự thu gọn lại.