I was playing with a small multi-objective integer programming problem:
In Z3 (using the Python bindings) we can state this very elegantly:
from z3 import *
x1,x2 = Ints('x1 x2')
z1,z2 = Reals('z1 z2')
opt = Optimize()
opt.set(priority='pareto')
opt.add(x1 >= 0, x2 >=0, x1 <= 2, x2 <= 2)
opt.add(x1 <= 2*x2)
# this version is ok:
# opt.add(z1 == x1 - 2*x2, z2 == -x1 + 3*x2)
# this truncates coefficients (round down to integer):
# opt.add(z1 == 0.5*x1 - 1.0*x2, z2 == -0.5*x1 + 1.5*x2)
# this one seems to work:
# opt.add(z1 == 0.5*ToReal(x1) - 1.0*ToReal(x2), z2 == -0.5*ToReal(x1) + 1.5*ToReal(x2))
opt.add(z1 == x1 - 2*x2, z2 == -x1 + 3*x2)
f1 = opt.maximize(z1)
f2 = opt.maximize(z2)
while opt.check() == sat:
print(opt.model())
This solves correctly and gives:
[x1 = 2, x2 = 1, z2 = 1, z1 = 0]
[x1 = 0, x2 = 2, z2 = 6, z1 = -4]
[x1 = 2, x2 = 2, z2 = 4, z1 = -2]
[x1 = 1, x2 = 1, z2 = 2, z1 = -1]
[x1 = 1, x2 = 2, z2 = 5, z1 = -3]
As my real problem has floating point coefficients for the objectives, I divided the objectives by 2:
opt.add(z1 == 0.5*x1 - 1.0*x2, z2 == -0.5*x1 + 1.5*x2)
This model should give the same five solutions for the x variables. However, when we run it, we see some wrong results:
[x1 = 0, x2 = 0, z2 = 0, z1 = 0]
[x1 = 0, x2 = 2, z2 = 2, z1 = -2]
[x1 = 0, x2 = 1, z2 = 1, z1 = -1]
When I print opt
I can see where things go wrong:
(assert (= z1 (to_real (- (* 0 x1) (* 1 x2)))))
(assert (= z2 (to_real (+ (* 0 x1) (* 1 x2)))))
The coefficients are silently truncated and converted to integers: 0.5 arrived as 0 and 1.5 became 1.
A workaround seems to be:
opt.add(z1 == 0.5*ToReal(x1) - 1.0*ToReal(x2), z2 == -0.5*ToReal(x1) + 1.5*ToReal(x2))
This converts the floating point coefficient to their rational equivalents:
(assert (= z1 (- (* (/ 1.0 2.0) (to_real x1)) (* 1.0 (to_real x2)))))
(assert (= z2 (+ (* (- (/ 1.0 2.0)) (to_real x1)) (* (/ 3.0 2.0) (to_real x2)))))
Now 0.5 becomes (/ 1.0 2.0)
and 1.5 is represented by (/ 3.0 2.0)
.
My questions are:
- Is this truncation "as designed"?
- Is my workaround the correct way to go about this? Or should I avoid floating point coefficients altogether?
- The printed rational number
(/ 1.0 2.0)
seems to hint there are still floating point numbers involved. Is this really(/ 1 2)
? (I assume these are actually bigints).