如何使用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进行基本优化

回答

相关问题