Làm thế nào để chuyển đổi chương trình bậc hai sang tuyến tính?

Question

Tôi có một vấn đề tối ưu hóa có trong hàm mục tiêu 2 nhân các biến, làm cho mô hình bậc hai.

Tôi hiện đang sử dụng zimpl, để phân tích mẫu và glpk để giải quyết. Vì chúng không hỗ trợ lập trình bậc hai, tôi sẽ cần phải chuyển đổi nó thành MILP.

. Biến đầu tiên là có thật, trong phạm vi [0, 1], biến thứ hai là có thật, từ phạm vi 0 đến inf. Điều này có thể mà không có một vấn đề là số nguyên.

Phần quan trọng trong hàm mục tiêu trông như thế này:

max ... + var1 * var2 + ... 

Tôi đã có vấn đề tương tự trong những hạn chế, nhưng họ đã dễ dàng giải quyết được.

Làm cách nào để giải quyết loại sự cố này trong chức năng khách quan?

Answer 1

Các mô hình trong biểu mẫu này thực sự được gọi là các vấn đề tối ưu hóa song tuyến. Cách tiếp cận điển hình cho các thuật ngữ tuyến tính bilinear là thông qua một cái gì đó gọi là phong bì McCormick.

Xem xét các biến x và y, trong đó bạn muốn x*y trong mục tiêu của vấn đề tối đa hóa của bạn. Nếu chúng ta giả sử x và y được bao bọc bởi xL <= x <= xU và yL <= y <= yU, sau đó chúng ta có thể thay thế x*y với w, một giới hạn trên cho số lượng, với những hạn chế sau đây (bạn sẽ nhìn thấy nguồn gốc here):

w <= xU*y + x*yL - xU*yL 
w <= x*yU + xL*y - xL*yU 
xL <= x <= xU 
yL <= y <= yL 

Lưu ý rằng những ràng buộc này là tất cả tuyến tính trong các biến quyết định. Có giới hạn dưới tương ứng trong phong bì McCormick, nhưng vì bạn đang tối đa hóa chúng không quan trọng trong trường hợp của bạn.

Nếu bạn muốn giới hạn chặt chẽ hơn trên x*y, bạn có thể chia khoảng thời gian trên một trong các biến (tôi sẽ sử dụng x ở đây) thành các phạm vi [xL1, xU1], [xL2, xU2], ..., [xLn, xUn], giới thiệu các biến liên tục phụ trợ {x1, x2, ..., xn} và {w1, w2, ..., wn} cũng như các biến nhị phân phụ trợ {z1, z2, ..., zn} , sẽ cho biết phạm vi giá trị x nào đã được chọn. Những hạn chế trên có thể được thay thế bằng (Tôi sẽ chỉ cho trường hợp chỉ số 1, nhưng bạn sẽ cần những cho tất cả các chỉ số n):

w1 <= xU1*y + x1*yL - xU1*yL*z1 
w1 <= x1*yU + xL1*y - xL1*yU*z1 
xL*z1 <= x1 <= xU*z1 

Về cơ bản, bạn sẽ có x1 = 0 và W1 < = 0 khi z1 = 0 (hay còn gọi là phần này không được chọn), và bạn sẽ có phong bì McCormick bình thường nếu z1 = 1 (hay còn gọi là phần này của phạm vi được chọn).

Bước cuối cùng là tạo x và w trong số các phiên bản cụ thể theo phạm vi của các biến này. Điều này có thể được thực hiện với:

x = x1 + x2 + ... + xn 
w = w1 + w2 + ... + wn 

Lớn hơn bạn thực hiện n, chính xác hơn ước tính bạn sẽ có cho thuật ngữ song tuyến. Tuy nhiên giá trị lớn của n sẽ ảnh hưởng đến khả năng giải quyết của mô hình của bạn.

Một lưu ý cuối cùng - bạn chỉ ra rằng một trong các biến của bạn không bị chặn, nhưng phong bì McCormick yêu cầu giới hạn trên cả hai biến. Bạn nên sửa các giới hạn, giải quyết và nếu giá trị tối ưu của bạn ở ranh giới thì bạn nên giải quyết lại với một ranh giới khác.