如何使用loco進行基本優化

我有一個成本向量，它的索引對應於多個時隙的整數值，並且希望最小化不同子集的時隙的總和。

請參閱下面的我的嘗試，因爲沒有選擇的插槽和成本之間的「鏈接」，這失敗了。

(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]))))

來源

2017-07-06 mac

這聽起來像一個減少揹包問題。你可以做一個最大化，但不是最小化。可能需要直接處理choco庫才能做到這一點。 – Mike

首先，我並不完全確定我明白這個問題的重點，因爲顯然解決方案是隻取列表中的5個最小值。但是如果你想讓loco這樣做，我同意揹包約束是一個方便的工具。與Mike在評論中所說的相反，我沒有發現使用揹包進行最小化的障礙。讓權重全部爲1，並強制權重總和爲5，以便從10個槽中選擇5個。我已經使用變量[:include i]來指示槽i是否應該包含在子集中（1爲真，0爲假）。我們想要最小化包含變量和成本向量的向量的點積。

(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)

結果是：

{[: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}

來源

2017-07-15 06:07:19 puzzler

感謝您的回答。這個例子只是說明性的，在我的實際使用情況下，變量會受到許多其他限制。 – mac

這是不是問題的答案，但我希望它可以幫助點，可以幫助一個方向。這聽起來像揹包問題？

你可以找到最大：

(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)]))

假設你只能有5個插槽。

可能通過查看源代碼並直接使用Choco庫來編寫最小化版本？

檢查本地knapsack函數的來源。

來源

2017-07-10 01:30:41 Mike

如何使用loco進行基本優化

回答

相關問題