- Join over
**1.5M+ people** - Join over
**100K+ communities** - Free
**without limits** - Create
**your own community**

- 15:59mforets edited #190
- 15:55abduld starred JuliaReach/MathematicalSystems.jl
- Jan 18 23:14ueliwechsler synchronize #125
- Jan 18 23:14ueliwechsler synchronize #125
- Jan 18 23:14
ueliwechsler on 76

Apply suggestions from code revโฆ (compare)

- Jan 18 15:21imbsky starred JuliaReach/MathematicalSystems.jl
- Jan 18 11:02schillic labeled #1916
- Jan 18 11:02schillic labeled #1916
- Jan 18 11:02schillic commented #1916
- Jan 18 11:00schillic edited #1916
- Jan 17 22:44ueliwechsler opened #1916
- Jan 17 17:59schillic edited #190
- Jan 17 17:57
schillic on transmission_line

fix computation of X0 (compare)

- Jan 17 17:57schillic synchronize #190
- Jan 17 17:10schillic edited #190
- Jan 17 17:10schillic synchronize #190
- Jan 17 17:10
schillic on transmission_line

add temporary fix of matrix invโฆ (compare)

- Jan 17 17:07schillic edited #190
- Jan 17 16:45schillic edited #190

hmm this is related but not the same?

we didn't speak about passing the inverse matrix there

where you already know the inverse

this issue was some logic (my logic) broken

@ueliwechsler: it seems to me be that in your

however, your inputs are zonotopes,*some* bottleneck :P)

`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 howhowever, your inputs are zonotopes,

`minkowski_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 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)

so i'm not surprised that

`minkowski_difference`

is fast
Thanks for your help guys! :D

Yes, I followed (but then my supervisor interrupted me)

For my problem, I most likely need to work with

But enabling

Yes, I followed (but then my supervisor interrupted me)

For my problem, I most likely need to work with

`HPolytopes`

so even though the `Zonotopes`

option sounds really interesting, I cannot use it for my current issue.But enabling

`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.
they tend to do that :)

I see, so I have to be really careful with my conclusions since they depend heavily on the type ๐

yes, it is common that you can write a much more efficient algorithm if you know the type of set you are dealing with

and that's also why preserving more concrete types is beneficial

for instance in your first loop iteration you could work with zonotopes (assuming we have the efficient

`minkowski_difference`

) until the `intersection`

"for free"
but then in the second iteration you will have an

`HPolytope`

and have to use the slower methods
but that happens automatically

i can have a look at JuliaReach/LazySets.jl#1500 (the linear map) in the next days, but if you are eager, you can just add this option yourself and see if it helps (here)

this has a nasty tail, so you have to pass the option through several helper functions :)

basically make this line optional

The equality check can also be improved..? Save half the evaluations in the dual inclusion by checking approximate equality of the support functions

`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

@ueliwechsler: can you try out the variant of your algorithm with this change?

`๐ซโบ = intersection(overapproximate(linear_map(S_inv, minkowski_difference(๐ซ,๐ฒ)), Hyperrectangle), ๐)`

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

this is the LP

`(no objective) s.t. x <= 0`