如何使用 loco 进行基本优化

Question

我正在尝试使用 loco 来做一个基本的优化示例。

我有一个成本向量，其索引对应于多个槽的整数值，并希望最小化槽的不同子集的成本总和。

请看下面我的尝试，它失败了，因为在选择的插槽和成本之间没有 "link"。

(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

这不是答案，但我希望它能帮助指出可能有用的方向。听起来像是背包问题？

您可以找到最大值：

(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 库来编写一个最小化版本？

检查 loco knapsack 函数的来源。

Answer 2

首先，我不完全确定我理解这个问题的要点，因为显然解决方案是只取列表中的 5 个最小值。但是如果你想让机车去做，我同意背包约束是一个方便的工具。与 Mike 在他的评论中所说的相反，我认为使用背包进行最小化没有任何障碍。让权重全部为 1，并强制权重加起来为 5，以便 select 5 从 10 个插槽中。我使用变量 [:include i] 来指示插槽 i 是否应包含在子集中（1 表示真，0 表示假）。我们希望最小化 :include 变量的向量与成本向量的点积。

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

如何使用 loco 进行基本优化

How to do basic optimisation using loco

optimization

clojure

constraint-programming