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

- 12:26
schillic on spaceNLN

- 12:18
schillic on links

- 12:18
mforets on gh-pages

build based on 07a2b148 (compare)

- 12:01mforets edited #1780
- 12:01mforets labeled #1780
- 12:00mforets opened #1780
- 12:00mforets labeled #1780
- 11:46mforets labeled #702
- 11:46mforets opened #702
- 11:41
schillic on 622

- 11:41
schillic on master

add Bloating operation Merge pull request #1778 from Jโฆ (compare)

- 11:41schillic closed #1778
- 11:41schillic closed #622
- 11:41schillic commented #1778
- 11:41schillic commented #1778
- 11:33mforets commented #1778
- 11:21
mforets on update_arch

update arch models (compare)

- 11:11
mforets on gh-pages

build based on abaa2f8 (compare)

- 11:00
schillic on 700

they tend to do that :)

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`

this is the method for

`Float64`

, but there is no method for other types
@mforets: i think the LP solvers only support

`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)
Doesnt work

In verimag some people used PPL, a library for polyhedra with exact coordinates

but ok

but are you fine with conversion to

`Float64`

before calling the solver?
or should we just crash and say that we only support

`Float64`

?
i'm fine with either choice because we anyway always used

`Float64`

so far
and it is somewhat cleaner to not do conversions

I recall some threads about numeric types in MOI

yes,

`MOI`

is ready for that. it only crashes when i pass the model to a solver
just to say

i agree with you :+1:

can you confirm?

i think the code should work if the solver supported it

should we print a warning whenever a user tries to set up an LP with non-

`Float64`

? because the error is quite cryptic. the downside is that if the user employs a solver that supports the type, then the warning is "wrong"