Hỗn hợp-Integer Giải pháp tối ưu gần nhất trong Matlab

Question

Có thể tìm giải pháp gần nhất để tối ưu cho một vấn đề hỗn hợp số nguyên không? Ví dụ tôi muốn vấn đề đơn giản dưới đây:

f = [1;1;1]; 
intcon = 1:3; 

Aeq = [0.99,0.97,0.15]; 
beq = 0.16; 
lb = zeros(3,1); 
ub = [1;1;1]; 

x = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub) 

trở x=[0;0;1] vì đây là giải pháp số nguyên gần nhất với giá trị khách quan của 0.16. Thay vào đó hiện tại nó trả về

Intlinprog dừng vì không có điểm nào đáp ứng các ràng buộc.

Không nhất thiết phải chạy intlinprog. Lý tưởng cũng cần phải hoạt động nếu beq thấp, ví dụ: 0.14.

Answer 1

Bạn có thể giới thiệu một số biến slack cho phép một số vi phạm hạn chế khi cần thiết như sau:

largeValue = 100; % choose some large value to penalise the constraint violation 
f_ = [f; largeValue; largeValue]; % penalise both slack variables 
Aeq_ = [Aeq, 1, -1]; % add a positive and negative slack variable to the constraint 
beq_ = beq; 
lb_ = [lb; 0; 0]; % limit the constraint to a positive number 
ub_ = [ub; inf; inf]; 

x_ = intlinprog(f_,intcon,[],[],Aeq_,beq_,lb_,ub_); % solve the adapted problem 
x = x_(1:3) % extract the solution of the original problem 

chú

• tôi bổ sung thêm hai (dương) biến slack, một cho một tích cực ràng buộc vi phạm và một hành vi vi phạm ràng buộc tiêu cực khác.

• Bạn nên phạt các biến slack với giá trị lớn, nếu không sẽ có lợi khi vi phạm các ràng buộc của bạn nhiều hơn mức cần thiết. Một cách tiếp cận tổng quát hơn sẽ được xác định một giá trị penalisation tốt dựa trên các giá trị trong f và Aeq, ví dụ

  largeValue = 2*max(abs(f))/min(abs(Aeq(Aeq ~= 0)))