组合 z3 中给定项目集的元素

Question

以下 z3 代码从 {x1..x6} 中选取元素以最大化总重量，同时满足总长度小于 10。

(declare-datatypes () ((Item (mk-item (size Int) (weight Int)))))

(define-fun ee () Item (mk-item 0 0)); empty item
(define-fun i1 () Item (mk-item 4 2))
(define-fun i2 () Item (mk-item 4 2))
(define-fun i3 () Item (mk-item 1 4))
(define-fun i4 () Item (mk-item 5 5))
(define-fun i5 () Item (mk-item 3 2))
(define-fun i6 () Item (mk-item 1 9))

(define-fun x_props ((x Bool) (i Item)) Item (ite x i ee))

; each x defines whether an item is selected or not
(declare-const x1 Bool)
(declare-const x2 Bool)
(declare-const x3 Bool)
(declare-const x4 Bool)
(declare-const x5 Bool)
(declare-const x6 Bool)

(define-fun total_size () Int
  (+
    (size (x_props x1 i1))
    (size (x_props x2 i2))
    (size (x_props x3 i3))
    (size (x_props x4 i4))
    (size (x_props x5 i5))
    (size (x_props x6 i6))
  ))

(define-fun total_weight () Int
  (+
    (weight (x_props x1 i1))
    (weight (x_props x2 i2))
    (weight (x_props x3 i3))
    (weight (x_props x4 i4))
    (weight (x_props x5 i5))
    (weight (x_props x6 i6))
  ))

(assert (< total_size 10))
(maximize total_weight)

(check-sat)
(get-model)

但是，我可以想象这种缩放非常糟糕，因为项目属性的数量激增，项目的数量也是如此。

是否会有不同的、更简洁的方法？特别是，你能想出一种分解 total_size 和 total_weight 函数的方法，因为那里有很多重复吗？

Answer 1

你的编码确实没有问题。由于您需要对多个元素求和，因此唯一的方法是明确说明它们，或者使用递归函数。虽然 SMT-Lib 和 Z3 都支持递归函数，但实现还不是很强大，你最好坚持显式风格。

这里的问题实际上是在尝试使用 SMT-Lib 作为一种编程语言，这并不是它真正的目的。我建议改为研究高级语言接口，例如来自 Python、Scala 或 Haskell 的接口；这将负责重复编码。这是一个很好的网站，用于描述如何在 Python 中对此类事物进行建模：https://ericpony.github.io/z3py-tutorial/guide-examples.htm and here's an example of a similar problem in Haskell: https://hackage.haskell.org/package/sbv-7.4/docs/src/Data.SBV.Examples.Optimization.VM.html

组合 z3 中给定项目集的元素

Combining elements of a given set of items in z3

z3

linear-programming

smt