Cách tối ưu hóa cơ bản bằng cách sử dụng loco

Question

Tôi đang cố gắng làm một ví dụ cơ bản về tối ưu hóa bằng cách sử dụng loco.

Tôi có vectơ chi phí chỉ mục tương ứng với giá trị số nguyên của một số vị trí và muốn giảm thiểu tổng chi phí cho một tập con riêng biệt của các vị trí.

Hãy xem nỗ lực của tôi bên dưới, không hoạt động do không có "liên kết" giữa các vị trí đã chọn và chi phí.

(def costs [10 10 20 20 30 30 40 40 10 10]) 

(let [slot-vars (for [i (range 5)] ($in [:slot i] 1 10)) 
     cost-vars (for [i (range 10)] ($in [:cost i] 10 40))] 
    (solution 
    (concat 
    slot-vars 
    cost-vars 
    [($distinct (for [i (range 5)] [:slot i]))] 
    (for [i (range 5)] 
     ($= [:cost i] (get costs i)))) 
    :minimize (apply $+ (for [i (range 5)] [:slot i])))) 

Answer 1

Trước tiên, tôi không hoàn toàn chắc chắn rằng tôi hiểu được vấn đề này, bởi vì rõ ràng giải pháp là chỉ lấy 5 giá trị nhỏ nhất trong danh sách. Nhưng nếu bạn muốn làm cho loco làm điều đó, tôi đồng ý rằng ràng buộc ba lô là một công cụ hữu ích cho việc này. Trái với những gì Mike nói trong bình luận của mình, tôi không thấy bất kỳ trở ngại nào khi sử dụng ba lô để giảm thiểu. Hãy để cho tất cả các trọng số là 1 và thực thi rằng trọng số thêm tối đa 5 để chọn 5 trong số 10 vị trí. Tôi đã sử dụng biến số [:include i] để cho biết liệu vị trí tôi có nên được bao gồm trong tập hợp con (1 cho giá trị true và 0 cho sai). Chúng tôi muốn giảm thiểu sản phẩm dấu chấm của vecto: gồm các biến và vector chi phí.

(def costs [10 10 20 20 30 30 40 40 10 10]) 
(def weights (repeat 10 1)) 

(def include-vars (for [i (range 10)] [:include i])) 
(def include-constraints (for [i (range 10)] ($in [:include i] 0 1))) 

(def model 
    (concat 
    include-constraints 
    [($knapsack weights costs include-vars 5 :total) 
    ($in :total 0 (apply + costs))])) 

(solution model :minimize :total) 

Kết quả là:

{[:include 4] 0, [:include 6] 0, [:include 9] 1, [:include 1] 1, [:include 3] 0, [:include 8] 1, :total 60, [:include 0] 1, [:include 7] 0, [:include 2] 1, [:include 5] 0} 

Answer 2

Đây không phải là câu trả lời, nhưng tôi hy vọng nó có thể giúp điểm theo hướng có thể hữu ích. Nghe có vẻ giống như một vấn đề ba lô?

Bạn có thể tìm tối đa với:

(def slots (for [i (range 10)] (keyword (str "slot-" i)))) 

(solution 
    (concat 
    (for [s slots] ($in s 0 1)) 
    [($in :total-weight 10 60) 
    ($in :total-value 5 5) 
    ($knapsack [10 10 20 20 30 30 40 40 10 10] 
       (repeat 10 1) 
       slots :total-weight :total-value)])) 

Giả sử bạn chỉ có thể có 5 khe.

Có thể viết phiên bản thu nhỏ bằng cách xem mã nguồn và làm việc trực tiếp với thư viện Choco?

Kiểm tra nguồn của chức năng Loco knapsack.