jump-dev / mathoptinterface.jl Goto Github PK
View Code? Open in Web Editor NEWAn abstraction layer for mathematical optimization solvers
Home Page: http://jump.dev/MathOptInterface.jl/
License: Other
An abstraction layer for mathematical optimization solvers
Home Page: http://jump.dev/MathOptInterface.jl/
License: Other
We're missing this interface, and it needs some thought to fit in with the current design.
from discussion with @mlubin, and following the fix to #6.
define an interface for asking a solver
Came across another use of MOI in a related context...
Bjarni V. Halldórsson , Erlendur S. Thorsteinsson , and Bjarni Kristjánsson (2000). A Modeling Interface to Non-Linear Programming Solvers - An instance: xMPS, the extended MPS format
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.9202
Many solvers allow us to change the constraint from equality to inequality. The first idea was not to support it f245a6a , one had to delete a constraint and add a new one, however some solver might be able to modify the sign and not be able to delete. Moreover modifying looks simpler.
The idea is to have something along the lines:
c_new = modifyconstraint(m::SolverInstance, ::MOI.ConstraintSet,
c::MOI.ConstraintReference{F, MOI.LessThan{T}},
newset::MOI.EquaTo{T})::MOI.ConstraintReference{F, MOI.EqualTo{T}}
There are a few inconsistencies in the naming of various fields within sets
dim
instead of dimension
: most of the time, long names are preferred (i.e. lower
). However, dim
is used in place of `dimension.a
is not descriptive in the PowerCone
: should it be exponent
or something similar?l
and u
in Semicontinuous
instead of lower
and upper
Are we happy with these or do we want to change?
Requires a documentation update.
see issues : #40 and JuliaOpt/MathProgBase.jl#186
Some functions like converting Matrices to MOI VectorAffineFunction format might be very useful for users, for instance this sketch:
function triplets(A::SparseMatrixCSC, cols::Vector{MOI.VariableReference}, rows::Vector{I})
@assert A.m == length(rows)
@assert A.n == length(cols)
colval = colval(A.colptr, length(A.rowval))
return rows[A.rowval], cols[colval], A.nzvals
end
function colval(colptr::Vector{I}, n::Integer)
colval = zeros(I, n)
c = 1
for i in 1:length(colptr)-1
for j in colptr[i]:(colptr[i+1]-1)
colval[c] = I(i)
c+=1
end
end
return colval
end
Would it be good to have a MOIExtras.jl?
Maybe solver APIs have similar functions that could also go into MOIExtras.jl ...
I am still processing the details, but after talking to @mlubin I think a name change from ConstraintDual
to ConicDual
may be important to allow the correct generic dual convention in the future.
The current dual conventions are based on Conic duality, but to me a more generic dual convention includes:
Point 1. also works for functions and sets, and probably the function and set duals can be combined into a dual for the associated constraint (e.g. if the function is affine and the set is a cone, we know how to get the constraint dual). Points 2. and 3. are the same up to the relative scaling between the duals required by Point 3. You also may be able to get the duals for 3. even if 4. does not exist. Probably a lot more to discuss about this (e.g. infeasibility and unboundedness) and so too early to resolve.
In the mean time I propose changing ConstraintDual
to ConicDual
so we can reserve FunctionDual
, SetDual
and ConstraintDual
for the future. ConicDual
would be a special case of SetDual
whose feasibility/optimality is w/r to 4. In particular, this would allow us to later have a ConeDual
in between SetDual
and ConicDual
whose feasibility/optimality could be w/r to 1.-3. (e.g. in a conic problem the ConeDual
s in an optimal set from 3. would be any non-zero scalings of the optimal ConicDual
s)
Most important for LP blocks, e.g., groups of bounds and groups of linear constraints.
#101 (comment)
It seems very fragile to depend on an interrelated package for testing MOI.
Discuss in the manual that it's reasonable for solvers to reject multiple variable-wise lower bounds on the same variable. See, e.g., #53.
Is a detailed documentation enough or should we have something like the following?
abstract type AbstractSolverInstanceAttribute{T} end
...
and
function getattribute(m, attr::AnyAttribute{T}, args...)::T
We can have shortcuts like NumberOfVariables <: AbstractSolverInstanceAttribute{Int}
There are references to VariableResult
which is now called VariablePrimal
.
These should be renamed without the prog
and perhaps moved to a separate package. I don't see a good reason why these three particular functions should be in MOI itself.
@joaquimg proposed a performance hint to tell the MOI wrapper to load the problem into the solver. I expect that we may decide that we want other performance hints as we start implementing things, so opening this for general discussion.
It would be nice if we had a data type to store all the data for an instance in MOI format independent of a solver API. This will make it more natural to talk about performing transformations, and we could also revive loadproblem!
which could be more efficient for throwing everything to a SolverInstance
at once.
Should the data structure just be a dictionary with vectors of variablewise, affine, and quadratic constraints (by type)? Do we care about type stability?
Related to JuliaOpt/SemidefiniteOptInterface.jl#1
I'm going to use this issue as a collection place for a range of questions I have implementing the CPLEX solver wrapper:
On the purpose of low-level interface
On variable bounds
addconstraint!(m, v::VectorOfVariables, set::LessThan{Float64})
a valid constraint? oOaddconstraint!(m, v::VectorOfVariables, set::Vector{Union{LessThan{Float64}, GreaterThan{Float64}, EqualsTo{Float64}, Interval{Float64}}})
be a valid constraint so users can set bounds all at once? No. Define what should happen when you ask a solver to do something that it can't do. Most of this is covered by cansetattribute
, cangetattribute
, and supportsproblem
, but not everything (like adding a certain constraint after solving: #8). We have the InvalidInstance
termination status code, although you would normally test that only after calling optimize!
.
We should probably define a standard exception that solvers should throw which can be intercepted by JuMP to infer that a solver won't allow a certain action. For other exceptions JuMP might decide to let them pass through to the user.
... haven't been ported to MOI yet. Are they Solver
attributes? SolverInstance
attributes? Both? Something else?
Currently, in intlinear.jl it receives a number.
but more functions/types are still being added to MOI/MOA
Here's a potentially naive question (considering I know nothing about conic):
Is it possible to save any problem (based on the current standard form with linear-quadratic functions, and the current sets) in the CBF format?
Because I was reading through the specification (incl. the new one http://cblib.zib.de/doc/format2.pdf) and it wasn't obvious to me how to have quadratic objectives/quadratic terms in the constraints.
It seems like if this is to be the standard form that unifies linear/conic etc, it would be nice to have one simple, easy to parse file-format that everybody agrees upon (unlike LP and MPS where nobody agrees on a canonical format and each reader/writer has weird limitations).
Should we have a minimally standardized way to return more info about the status?
Some output info of Xpress and CPLEX do not match any existing status (and probably should not match at all) but we could have a default way to return a string/symbol/error/warning with that extra info.
The attribute name Sense
seems inconsistently short for MOI. I keep thinking it should be ObjectiveSense
. Opinions?
In order to avoid some level of redundancy and extra work for the solver wrappers, I'm thinking that it would be a good idea to disallow (by convention) constraints of the form: ScalarAffineFunction
in Nonnegative(1)
, Nonpositve(1)
, or Zeros(1)
. These are already covered by the one-dimensional sets GreaterThan
, LessThan
, and EqualTo
.
https://github.com/JuliaOpt/MathOptInterface.jl/blob/master/test/function_utilities.jl
is there anything else we want to redefine Base.isapprox
for? may want to rename the file.
any preference where it goes?
see #122 (comment)
Should we parameterize the solver and interface types with number types? For instance replace CSDPSolver
by CSDPSolver{Float64}
and CSDPSolverInstance
by CSDPSolverInstance{Float64}
.
I think this is necessary, for instance, to make SemidefiniteOptInterface work with high precision solvers.
The parameters are currently missing in lots of places:
http://www.juliaopt.org/MathOptInterface.jl/latest/apireference.html#MathOptInterface.GreaterThan
http://www.juliaopt.org/MathOptInterface.jl/latest/apireference.html#MathOptInterface.EqualTo
http://www.juliaopt.org/MathOptInterface.jl/latest/apireference.html#MathOptInterface.supportsproblem
Currently we haven't defined what happens when the Sense
attribute is never set. Should we define it to be minimization by default or make it required to provide a sense? I'm leaning towards the latter.
Why do we need Reals
, Zeros
, Nonnegatives
, Nonpositives
, GreaterThan
, LessThan
, EqualTo
, and Interval
?
struct Interval{T}
lower::T
upper::T
end
struct Intervals{T}
lower::Vector{T}
upper:Vector{T}
end
# or just riffing here...
struct VectorOfIntervals{T}
intervals::Vector{Interval{T}}
end
# variable bounds
addconstraint!(m, ::SingleVariable, ::Interval)
addconstraint!(m, ::SingleVariable, ::Intervals) # error. Not valid
addconstraints!(m, ::VectorOfVariables, ::Interval) # every variable has the same bound
addconstraints!(m, ::VectorOfVariables, ::Intervals) # every variable has different bound
# constraints
addconstraints!(m, ::ScalarAffineFunction, ::Interval)
addconstraints!(m, ::ScalarAffineFunction, ::Intervals) # error not valid
addconstraints!(m, ::VectorAffineFunction, ::Interval) # every constraint has same set
addconstraints!(m, ::VectorAffineFunction, ::Intervals) # every constraint has different set
addconstraints!(m, ::ScalarQuadraticFunction, ::Interval)
addconstraints!(m, ::ScalarQuadraticFunction, ::Intervals) # error not valid
addconstraints!(m, ::VectorQuadraticFunction, ::Interval) # every constraint has same set
addconstraints!(m, ::VectorQuadraticFunction, ::Intervals) # every constraint has different set
You can have Nonpositives(dim) = Intervals(fill(-Inf, dim), fill(0.0, dim))
if you really want.
Since we're about to write a bunch of MOI wrappers, now would be a good time to reconsider the current structure of the solver wrappers. I propose that we move all of the MOI wrappers into separate packages, like GurobiMOI MathOptInterfaceGurobi, CPLEXMOI MathOptInterfaceCPLEX, CbcMOI MathOptInterfaceCbc, etc. The reasons are:
It's a bit uglier to say using MathOptInterfaceGurobi
versus using Gurobi
. JuMP can get around this by providing a @usingsolver
macro that translates @usingsolver Gurobi, Mosek
into using MathOptInterfaceGurobi, MathOptInterfaceMosek
.
CC's for those not watching this repo: @ulfworsoe @tkelman @odow
Currently there is only one basis status per variable and constraint, but if there are multiple results, then they could have different bases
We have the following table in the manual:
Mathematical Constraint | MOI Function | MOI Set |
---|---|---|
a^Tx \le u |
ScalarAffineFunction |
LessThan |
a^Tx \ge l |
ScalarAffineFunction |
GreaterThan |
a^Tx = b |
ScalarAffineFunction |
EqualTo |
l \le a^Tx \le u |
ScalarAffineFunction |
Interval |
... | ... | ... |
In the first four lines we use a^Tx
in the first column and we say ScalarAffineFunction
, should we say/use ScalarLinearFunction
? This could avoid multiple representations of the same constraint. Since a^Tx - b = 0
is equivalent to a^Tx = b
Right now we have a few different ways of deciding whether to run a particular test or subtest:
Example 1 Example 2.
I wanted to get rid of the duals
keyword and replace it with the assumption that the solver wants us to test duals if the SupportsDuals
attribute returns true, but that doesn't quite work since some solvers (ahem) do duals for linear and quadratic but not cones.
We should think up a nicer way to handle this.
I agree that the current strategy of JuMP is useful but I don't like the idea of cache being only in JuMP... I understand and accept the argument of having MOI a pure API but It would be nice to have the MOIU instance shared by JuMP and the solver wrapper. Example: if a solver wrapper wants to answer the query about MOI.ConstraintSet it will need to store it's own copy or build the set on the fly which would be a waste since the set exists and is stored in JuMP.
The problem with sharing is that I don't know if it is possible with julia to deny the solvers from modifying the instance once it is shared.
One possible solution: given a valid MOIU instance there are queries that do not need a solver to be answered. so wrappers do not implement those methods and we move them to MOIU. Everything using MOIU instance goes to MOIU to keep it separated from what solvers should implement. Then I see methods in MOIU like
MOIU.addconstraint!(m::MOI.AbstractSolverInstance, func::F, set::S, <:MOIU.AbstractInstance{T}, updateform::Bool)
#MOIU update its instance and if updateform == false
#MOIU keeps track of what is not yet passed through vectors for each combination F,S as discussed
#here https://github.com/JuliaOpt/MathOptInterface.jl/issues/63#issuecomment-317526848
MOIU.update_solver_instance()
#calls MOI.addconstraints! and deletes the vectors but keeps the instance.
MOIU.getattribute(m::MOIU.AbstractInstance{T}, ::MOI.ConstraintSet}, ref)
#replacing what was before in MOI and implemented by the solvers
#MOI.getattribute(m::MOI.SolverInstance{T}, ::MOI.ConstraintSet}, ref)
As @blegat mentioned, this will not work in the following case:
if the solver wrapper wants to have a mode on the fly where every info required for a single constraint is added and deleted right afterwards (being only kept inside the solver).
Such solver wrappers will be denied to have an answer to the following query since now it s the responsability of MOIU instance.
MOI.getattribute(m::MOI.SolverInstance{T}, ::MOI.ConstraintSet}, ref)
To solve this issue, solvers need to have access to the instance (bad thing). and all those methods will not be replaced but only get a default implementation that uses MOIU instance (when available):
So Instead of this
MOIU.getattribute(m::MOIU.AbstractInstance{T}, ::MOI.ConstraintSet, ref)
# replacing what was before in MOI and implemented by the solvers
# MOI.getattribute(m::MOI.SolverInstance{T}, ::MOI.ConstraintSet, ref)
We can have this
MOIU.getattribute(m::MOIU.AbstractInstance{T}, ::MOI.ConstraintSet, ref)
# helps providing default implementation to
# MOI.getattribute(m::MOI.SolverInstance{T}, ::MOI.ConstraintSet}, ref)
function MOI.getattribute(m::MOI.AbstractSolverInstance{T}, s::MOI.ConstraintSet, ref)
if has_instance(m)
MOIU.getattribute(instance(m), s, ref)
else
throw MethodError()
end
end
With JuMP being now only one among other possible users of MOI / MOIU doing instead of this :
functions1 = Vector{FunctionSetA}()
sets1 = Vector{ConstraintSetA}()
# fill the vectors
functions2 = Vector{FunctionSetA}()
sets2 = Vector{ConstraintSetB}()
# fill the vectors
# ...continue for each F,S type combination
MOI.addconstraints!(m,functions1, sets1)
MOI.addconstraints!(m,functions2, sets2)
#...continue for each F,S type combination
the follwing:
MOIU.addconstraint!(m, f, s, false) # assuming instance(m) returns an MOIU instance
#...continue adding the other constraints
MOIU.update_solver_instance(m)
List of tests to be ported from MPB
linproginterface.jl
linprog.jl
mixintprog.jl
quadprog.jl
conicinterface.jl
PositiveSemidefinteConeScaled
What if...
References were pointers instead of UInt
´s?
With UInt
s we can have simple vector as mappings IF the solver does not support deletions. However, if the solver supports deletions we need some mapping. This mapping could be a vector, which would grow a lot with lots of deletions; could be a linked list which is fast to delete but not fast to access; could be a Dict which is easy to delete but not so fast to access.
Given that we usually do a lot more additions than deletions, may we should not be much worried of the time it takes to delete, but with the time it takes to add.
My proposal goes as follows, instead of giving the user a unique UInt
everytime a variable/constraint is added we could give a pointer to an Int
that directly matches the solver´s index, the SolverInstance
would also hold a list of those pointers. In case of adding a constraint there would be no need for a lookup to get the solver´s corresponding index. In case of a deletion we can set that pointer to a zero value and fix all the other pointers since the SolverInstance
has a list of them, then the user´s reference are fixed.
List of LP and conic solver wrappers to be implemented.
We can mark whoever is currently working on it and which ones are basically done.
only 3 overlap, and they don't really make sense (per discussion with @mlubin). so separate these attributes.
also from discussion with @mlubin: define an interface for asking a solver whether a group of "types" of constraints is supported together. and also a way to ask the solver, given an existing model that has already been solved, what types of constraints can be added to it. EDIT moved to #8
there is confusion on my part on what a model is and what a solver is. I think perhaps the terminology could be revisited to make it clearer.
The name "variablewise function" is a holdover from variablewise constraint, which made a bit more sense.
To replace ScalarVariablewiseFunction
and VectorVariablewiseFunction
, what about ScalarComponentProjection
and VectorComponentProjection
?
Let the bikeshedding begin. @blegat @joehuchette @chriscoey @odow @joaquimg @IssamT
Thanks to @edljk for pointing this out.
A bound constraint can be given either as a constraint or as a bound. With the current MOI interface are we able to distinguish those?
The discussion at #67 needs to result in changes to the manual.
ObjectiveSense
is an attribute but it is also set in setobjective!
.
It looks like ObjectiveSense
belongs to the objective and thus could be modified by modifyobjective!
instead of setattribute
.
Where it belongs? Both places?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.