Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Order-maintaining copy_to #2236

Closed
matbesancon opened this issue Jul 5, 2023 · 14 comments
Closed

Order-maintaining copy_to #2236

matbesancon opened this issue Jul 5, 2023 · 14 comments

Comments

@matbesancon
Copy link
Contributor

It would be handy in some cases to have a second implementation of copy_to that adds variables (and constraints) in the order of increasing index instead of constrained and then free.

That way one can get rid of the index_map. Concretely, I'm working on non-linear on top of MOI with a function f(x) that takes the vector of variables in order of variable index. When copying the model, this would be handy to keep the same order to avoid having to call f(permutation_matrix * x) all the time

@blegat
Copy link
Member

blegat commented Jul 5, 2023

I agree, when there is an NLP block then we simply disable constrained variables.
For JuliaManifolds/Manopt.jl#273, we would need to maintain the order of variables but still use constrained variables.
So I think we should, if any part of the model is a black-box function, add constrained variables but without reordering.
We could also do like MIP callbacks and have a variable attribute to get the values so that it goes through the index map but for it to be efficient enough for NLP we might need the CleverDictt o have a special case when the order is the same

@matbesancon
Copy link
Contributor Author

we could add a keyword argument always_maintain_variable_order=false to default_copy_to, and then:

maintain_variable_order = always_maintain_variable_order || has_nlp

@blegat
Copy link
Member

blegat commented Jul 5, 2023

We probably want to stop adding keyword arguments to copy_to since we removed them all for MOI v1.
Probably we can query MOI.get(src, SupportsVariableReordering()) which falls back to checking if all attributes and constraint types support it.

@matbesancon
Copy link
Contributor Author

The problem is if you want to set that as the caller of copy_to, and not at the Optimizer level

@blegat
Copy link
Member

blegat commented Jul 5, 2023

The approach then is to use a layer like here:

"""
ModelFilter(filter::Function, model::MOI.ModelLike)
A layer to filter out various components of `model`.
The filter function takes a single argument, which is each element from the list
returned by the attributes below. It returns `true` if the element should be
visible in the filtered model and `false` otherwise.
The components that are filtered are:
* Entire constraint types via:
* `MOI.ListOfConstraintTypesPresent`
* Individual constraints via:
* `MOI.ListOfConstraintIndices{F,S}`
* Specific attributes via:
* `MOI.ListOfModelAttributesSet`
* `MOI.ListOfConstraintAttributesSet`
* `MOI.ListOfVariableAttributesSet`
!!! warning
The list of attributes filtered may change in a future release. You should
write functions that are generic and not limited to the five types listed
above. Thus, you should probably define a fallback `filter(::Any) = true`.
See below for examples of how this works.
!!! note
This layer has a limited scope. It is intended by be used in conjunction
with `MOI.copy_to`.
## Example: copy model excluding integer constraints
Use the `do` syntax to provide a single function.
```julia
filtered_src = MOI.Utilities.ModelFilter(src) do item
return item != (MOI.VariableIndex, MOI.Integer)
end
MOI.copy_to(dest, filtered_src)
```
## Example: copy model excluding names
Use type dispatch to simplify the implementation:
```julia
my_filter(::Any) = true # Note the generic fallback!
my_filter(::MOI.VariableName) = false
my_filter(::MOI.ConstraintName) = false
filtered_src = MOI.Utilities.ModelFilter(my_filter, src)
MOI.copy_to(dest, filtered_src)
```
## Example: copy irreducible infeasible subsystem
```julia
my_filter(::Any) = true # Note the generic fallback!
function my_filter(ci::MOI.ConstraintIndex)
status = MOI.get(dest, MOI.ConstraintConflictStatus(), ci)
return status != MOI.NOT_IN_CONFLICT
end
filtered_src = MOI.Utilities.ModelFilter(my_filter, src)
MOI.copy_to(dest, filtered_src)
```
"""
struct ModelFilter{T,F} <: MOI.ModelLike
inner::T
filter::F
function ModelFilter(filter::Function, model::MOI.ModelLike)
return new{typeof(model),typeof(filter)}(model, filter)
end
end
function MOI.get(
model::ModelFilter,
attr::Union{
MOI.ListOfConstraintAttributesSet,
MOI.ListOfConstraintIndices,
MOI.ListOfConstraintTypesPresent,
MOI.ListOfModelAttributesSet,
MOI.ListOfVariableAttributesSet,
},
)
return filter(model.filter, MOI.get(model.inner, attr))
end
function MOI.get(model::ModelFilter, attr::MOI.AbstractModelAttribute)
return MOI.get(model.inner, attr)
end
# !!! warning
# Slow implementations, but we need to report the number of constraints in
# the filtered model, not in the `.inner`.
function MOI.get(model::ModelFilter, ::MOI.NumberOfConstraints{F,S}) where {F,S}
return length(MOI.get(model, MOI.ListOfConstraintIndices{F,S}()))
end
# These just forward the attributes into the inner model.
function MOI.get(
model::ModelFilter,
attr::MOI.AbstractVariableAttribute,
x::MOI.VariableIndex,
)
return MOI.get(model.inner, attr, x)
end
function MOI.get(
model::ModelFilter,
attr::MOI.AbstractConstraintAttribute,
ci::MOI.ConstraintIndex,
)
return MOI.get(model.inner, attr, ci)
end
# !!! warning
# This is a slow implementation. But we need to check if we filtered
# everything.
function MOI.is_empty(model::ModelFilter)
if MOI.is_empty(model.inner)
return true
elseif MOI.get(model.inner, MOI.NumberOfVariables()) > 0
return false
elseif length(MOI.get(model, MOI.ListOfModelAttributesSet())) > 0
return false
end
return true
end
MOI.empty!(model::ModelFilter) = MOI.empty!(model.inner)

@odow
Copy link
Member

odow commented Jul 7, 2023

This actually hints at a deeper problem: the order of MOI constraints in a copy is not the same between solvers. One places this crops up is writing files like MPS. Most copies end up grouping by constraint type and then construction order, but I do wonder if there should instead be a global order of constraints. i.e., all ConstraintIndex must have a unique .value::Int64 field, not just unique within their constraint type. That's a MOI 2.0 problem though.

@odow
Copy link
Member

odow commented Aug 7, 2023

@blegat and I discussed this without much of a conclusion. Do we have a reproducible example of the current problem? Is it necessary to use a permutation matrix? Couldn't we just pass a (permuted) view of the vector to the function x?

Here's the bit where we disable constrained variables:

has_nlp = MOI.NLPBlock() in MOI.get(src, MOI.ListOfModelAttributesSet())
constraints_not_added = if has_nlp
Any[
MOI.get(src, MOI.ListOfConstraintIndices{F,S}()) for
(F, S) in MOI.get(src, MOI.ListOfConstraintTypesPresent()) if
_is_variable_function(F)
]
else
Any[
_try_constrain_variables_on_creation(dest, src, index_map, S)
for S in sorted_variable_sets_by_cost(dest, src)
]
end

So maybe we do need a way for dest to opt-in to this. I think this is probably the only place where it matters? Because solver wrappers implementing copy_to have control over the order.

@matbesancon
Copy link
Contributor Author

one solution would be a three-argument copy_to with default doing whatever the solver wants, and then other copy_to methods which add constraints, like keep variable / constraint order

@odow
Copy link
Member

odow commented Aug 8, 2023

Keeping constraint order would require a big change to MOI. We're really just not set up to record or communicate that information. (It'd likely mean requiring implementations to use a non-decreasing UUID for .value, and plenty of implementations (ab)use the value field for all sorts of things.

Can you point to a concrete example where this is necessary?

This line in Boscia is worrying:
https://github.com/ZIB-IOL/Boscia.jl/blob/f47ce9c0c93081de3dc468ef2648401cedfa73f8/src/interface.jl#L101-L103
Nothing in MOI guarantees that variable .values should be contiguous or 1 to n.

Can't you just work-around this with a permutation vector? Or ask your oracle to accept a view?

julia> x = [0.1, 0.2, 0.3, 0.4]
4-element Vector{Float64}:
 0.1
 0.2
 0.3
 0.4

julia> p = [4, 2, 1, 3]
4-element Vector{Int64}:
 4
 2
 1
 3

julia> x[p]
4-element Vector{Float64}:
 0.4
 0.2
 0.1
 0.3

julia> view(x, p)
4-element view(::Vector{Float64}, [4, 2, 1, 3]) with eltype Float64:
 0.4
 0.2
 0.1
 0.3

@blegat
Copy link
Member

blegat commented Aug 8, 2023

If you want indices to be from 1 to n you can use a MatrixOfConstraints. See Zaphod.jl for an example of how to use it

@odow
Copy link
Member

odow commented Sep 12, 2023

I'd propose we close this. I don't think we need to add more complexity to MOI.

@odow
Copy link
Member

odow commented Sep 12, 2023

Maybe we could add all constraints required a shared non-decreasing UUID as one of the MOI 2.0 decisions.

Added to #2180

@odow
Copy link
Member

odow commented Sep 13, 2023

Thoughts @matbesancon?

@matbesancon
Copy link
Contributor Author

If you want indices to be from 1 to n you can use a MatrixOfConstraints. See Zaphod.jl for an example of how to use it

I'll do that as a temporary solution, but the fact that the order-preserving implementation is right there in copy-to without being accessible is a bit frustrating

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Development

No branches or pull requests

3 participants