mforets on 2219_setops
Update src/LazyOperations/Minko… (compare)
github-actions[bot] on v0.9.1
mforets on gh-pages
build based on 5b4c01a (compare)
mforets on 2219_setops
Update Intersection.jl (compare)
mforets on 2219_setops
Update MinkowskiSum.jl (compare)
mforets on 2219_setops
Update Intersection.jl (compare)
mforets on 2219_setops
Update CartesianProduct.jl (compare)
mforets on master
Update Project.toml (compare)
minkowski_difference
the second argument is a (again: constant) BallInf
. maybe that can be exploited, but from the code for minkowski_difference
i don't see howminkowski_difference
of two zonotopes is again a zonotope (not in our current implementation, but it should be easy to add a method for that; this is JuliaReach/LazySets.jl#586), and the linear map of a zonotope is again a zonotope. the "problematic" operation here is the intersection with a BallInf
, which does not preserve "being a zonotope." if you are willing to pay the price of an overapproximation to a zonotope at this point, you would get rid of the remove_redundant_constraints
and the linear_map
would be cheap as well. but the intersection
then becomes more complicated (i think there is no way around some bottleneck :P)
for the
minkowski_difference
I know that I solve #constraint linear programs (therefore, it is linear in the number of constraints)
no, the implementation of minkowski_difference
performs m
support-function queries, which in your case are applied to a BallInf
(which is very cheap)
minkowski_difference
is fast
HPolytopes
so even though the Zonotopes
option sounds really interesting, I cannot use it for my current issue.linear_map
to pass the matrix S
directly would be exactly what I was looking for since if I can get rid of the performance penalty of computing the inverse every iteration.
minkowski_difference
) until the intersection
"for free"
HPolytope
and have to use the slower methods
minkowski_difference
for hyperrectangular sets can be specialized as well or not?
maybe, but the hyperrectangle will definitely be destroyed by the linear_map
but that would be an alternative to my other suggestion: overapproximate the result of linear_map
by a hyperrectangle. hyperrectangles are closed under intersection, so this would give you a "stable" loop. and all of these operations are cheap, so i would really give it a try, just to see the potential performance boost
𝒫⁺ = intersection(overapproximate(linear_map(S_inv, minkowski_difference(𝒫,𝒲)), Hyperrectangle), 𝒟)
The equality check can also be improved..? Save half the evaluations in the dual inclusion by checking approximate equality of the support functions
i didn't understand this proposal. but yeah, if typically one of the two inclusions fails, it is more efficient to do that check first (because it usually avoids the second check). and again for hyperrectangles this equality check can be made very efficient
@blegat while you are here: i cannot get MOI
to work with Rational
s. what is wrong here?
using GLPK, MathOptInterface
const MOI = MathOptInterface
N = Rational{Int}
solver = GLPK.Optimizer(method=GLPK.EXACT)
x = MOI.add_variables(solver, 1)
MOI.set(solver, MOI.ObjectiveSense(), MOI.FEASIBILITY_SENSE)
a = MOI.ScalarAffineFunction(MOI.ScalarAffineTerm.(N[1], x), N(0))
b = MOI.LessThan(N(0))
MOI.add_constraint(solver, a, b)
this throws an error:
ERROR: MathOptInterface.UnsupportedConstraint{MathOptInterface.ScalarAffineFunction{Rational{Int64}},MathOptInterface.LessThan{Rational{Int64}}}: `MathOptInterface.ScalarAffineFunction{Rational{Int64}}`-in-`MathOptInterface.LessThan{Rational{Int64}}` constraint is not supported by the model.
note that for N = Float64
this works
(no objective) s.t. x <= 0
Float64
, but there is no method for other types
Float64
(i updated my comment JuliaReach/LazySets.jl#1701). we should discuss how to proceed. one way is to convert from N
to Float64
, solve the LP
, then convert back to N
(which obviously has soundness issues, but it may be better than crashing; maybe there should be an option to print a warning or error)