separate model types

[mlubin]

The abstraction is a getting a bit crowded with methods overloaded to mean different things depending on the sequence of operations you perform on a model object. E.g., if you load a nonlinear problem, then getconstrduals returns the multipliers for all constraints, while if you load a linear problem, it returns the multipliers for the linear constraints. A similar issue leads to jump-dev/JuMP.jl#472 where you're only allowed to call setquadobj! after loadproblem! but not after loadnonlinearproblem!. I think we should be a bit more careful about solver features (jump-dev/JuMP.jl#83).

Concrete proposal:
Define a finite list of problem classes which a solver might support, and force users to request the features that they need as arguments to model(). Example:

m = model(IpoptSolver(), Nonlinear)

or

m = model(IpoptSolver(), LP)

Having these as arguments to model lets the solver wrapper potentially return different types depending on the input. The major problem classes might be LP, Conic, and Nonlinear. These are meant to be very broad but capture the different styles of input that we currently support. Further distinctions can be made by using applicable as we do now. (Extra bonus if we can resolve the GLPKSolverMIP/GLPKSolverLP split.) These changes would most directly affect JuMP; Convex.jl shouldn't need more than a couple lines of code tweaked.

CC @carlobaldassi @tkelman @madeleineudell

[tkelman]

Just so I have this straight, this is the MathProgBase lower-case model that only the modeling interfaces would need to deal with, not the JuMP Model that users interact with?

Somewhat related, in putting QP/QCQP support into CoinOptServices it was pretty apparent that quadratic objectives and constraints are sort of tacked onto the LP API in a not-so-elegant way, a dedicated loadquadraticproblem! would be cleaner in cases that aren't doing any problem modification.

[mlubin]

Yes, this is MathProgBase.model. Would loadquadraticproblem! also take quadratic constraints? If so, do we also need a QP-specific loadproblem? Should these methods take in a list of integer variables as well to fully specify the problem with a single call?
I think the original intention was to avoid the combinatorial number of cases to have a special loadproblem for each problem class, but it's probably not as bad as we had worried if we just want LP, QP, and QCQP, given that we already have specialized loadproblems for conic and nonlinear. At the same time, the LP interface basically just follows what most existing solvers like CPLEX and Gurobi do, so I'm split.

[tkelman]

At least for LP, QP, and QCQP there's an obvious hierarchy where there's one obvious choice for an MIQCQP data structure which could represent all 6 combinations with either #undef or empty for the subclasses. Not so obvious that you'd use the same data structure for conic (you could, and would for Convex.jl [edit: by which I mean you'd represent LP's, QP's, etc within the same conic format as SOCP's and SDP's], but might also lose information in the reformulation like constant Hessian for QP's), and nonlinear is entirely different.

I found myself doing a lot of checking whether quadratic objectives and/or quadratic constraints were empty and was never really happy with it - kind of a code smell that feels against the spirit of multiple dispatch (and might make LP's slower), but we also don't have an easy way of inheriting and extending from concrete types. The objective and linear part of a QCQP could be put in a QP data structure as a subfield of the QCQP type, and the linear part of a QP could be put in an LP data structure as a subfield of the QP type, but this also feels wrong.

[mlubin]

At the same time, I don't think a pure LP solver should have to deal with or worry about data structures which have quadratic terms. It doesn't feel right to say that LP and MIP are special cases of MIQCQP.

[mlubin]

I'd like to revisit this. I propose to separate out into LP, Conic, and Nonlinear with minimal changes to the existing method structure, just a better categorization of which methods are expected to be implemented for which solvers. It will be a lot of work to push this through to all the solvers, JuMP, Convex.jl etc and coordinate releases of the packages. After that we can consider further refining the LP category.

Regarding the name of the LP category, I used "LP++" in my ISMP talk to indicate that it's LP with lots of things tacked on top, but we cant use that as a symbol in Julia. What about LPStyle or LPFamily or just LP if it's not too misleading.

[tkelman]

I have to disagree with

It doesn't feel right to say that LP and MIP are special cases of MIQCQP

I think that's far more accurate than putting "linear" in the name for a data structure that you're using for MIQCQP.

[mlubin]

Fair enough, but let's leave the MIQCQP category for when we have a proper, native, MIQCQP loadproblem. For now we just need a name that describes the family of solvers which implements loadproblem! as it is now.

[mlubin]

It could be LPthruMIQCQP :)

[mlubin]

Which is only slightly a misnomer because you can pass SOCP constraints through the interface.

[tkelman]

Maybe instead of trying to name them based on problem classes, name them based on the data structures they're using? MatrixProblem, ConeProblem, ExprProblem? ConeProblem is a bit of a generalization of MatrixProblem with additional data and classes of constraints that it can cover.

[mlubin]

I like the idea, needs a bit more bikeshedding. ExprProblem seems a bit off for derivative-based NLP solvers though, and MatrixProblem isn't really self explanatory.

[madeleineudell]

To me, it seems conceptually simpler to think about types of problem
components rather than types of problems: linear constraints, conic
constraints, integer constraints, QP constraints, linear objectives,
nonlinear objectives, etc etc. I'd add them to a model instance as I go
along.

The model instance might have a distinct type for every solver, and would
issue an error whenever I try to add a problem component unsupported by
that model instance. We'd also offer a handy table to users to help them
figure out which problem components can be accepted by which solvers.

Other functions, like getconstrduals, would be renamed to refer to
particular problem components. Or perhaps something like
getduals(model.LinearConstraints) as distinguished from
getduals(model.ConicConstraints). (This aspect is the least clear to me.)

This allows for a more complex world of models with non-hierarchical
(LP->SOCP->SDP <-?-> nonlinear) capabilities.

On Thu, Nov 19, 2015 at 12:38 PM, Miles Lubin [email protected]
wrote:

I like the idea, needs a bit more bikeshedding. ExprProblem seems a bit
off for derivative-based NLP solvers though, and MatrixProblem isn't really
self explanatory.

—
Reply to this email directly or view it on GitHub
#73 (comment)
.

Madeleine Udell
Postdoctoral Fellow at the Center for the Mathematics of Information
California Institute of Technology
https://courses2.cit.cornell.edu/mru8
https://courses2.cit.cornell.edu/mru8
(415) 729-4115

[tkelman]

I agree that keeping track of quadratic, conic, etc constraints separately from linear makes a lot of sense in giving a cleaner internal implementation. The current MPB design for quadratic problems seems a bit overly driven by the CPLEX/Gurobi API.

[mlubin]

We've been tailoring the interface in MPB for solvers as they are and not as we'd like them to be :). I'm all in favor of smashing the hierarchy, but I'm very hesitant to design an abstraction for solvers that don't exist yet. We just don't know what input format might be ideal for a conic+NLP solver.

I could see splitting out linear/QP/conic constraints (we already split linear and quadratic), and leaving NLP on its own for now. The more concrete problem is that we need a design for how to deal with transformations when the solver itself doesn't directly support the input format, e.g. Gurobi/CPLEX don't accept conic constraints in natural conic format, and ECOS/SCS don't support variable bounds directly. There are no solvers which support conic+quadratic constraints in the same problem without some transformation. These transformations are annoying to write, and we shouldn't force each solver wrapper to implement them from scratch. My proposal was to categorize the solvers according to the input format that they do accept (e.g. Gurobi/CPLEX LP++ style versus conic form) and then have some standard transformation code that can take any conic solver and turn it into an LP solver, for example. Another example is NLP solvers, which can act as LP or QCQP solvers after some transformation. The motivation for these three problem classes is really just to make this transformation process tractable and not to provide an ideal interface for mathematical programming, which can be done on top of this plumbing code.

[tkelman]

We don't have PENNON http://www.penopt.com hooked up, but it certainly exists and straddles the divisions here.

[mlubin]

Does PENNON have any publicly available documentation? Can't find it.

[madeleineudell]

Smash the hierarchy!

(Oh sorry; wrong internet forum.)

I'd want to use two levels of abstraction to do what Miles suggests. The
first is an AbstractModel, with fields for all sorts of components: linear
constraints, conic constraints, integer constraints, QP constraints, linear
objectives, nonlinear objectives, etc etc. The second is a SolverModel,
with fields for only the sorts of components a solver understands.

Then we'd have a bunch of translator functions for mapping between sorts of
components. When you try to smash an AbstractModel into a
particularSolverModel, we'd call the appropriate translation methods if
they exist and throw an error otherwise.

On Thu, Nov 19, 2015 at 1:49 PM, Miles Lubin [email protected]
wrote:

We've been tailoring the interface in MPB for solvers as they are and not
as we'd like them to be :). I'm all in favor of smashing the hierarchy, but
I'm very hesitant to design an abstraction for solvers that don't exist
yet. We just don't know what input format might be ideal for a conic+NLP
solver.

I could see splitting out linear/QP/conic constraints (we already split
linear and quadratic), and leaving NLP on its own for now. The more
concrete problem is that we need a design for how to deal with
transformations when the solver itself doesn't directly support the input
format, e.g. Gurobi/CPLEX don't accept conic constraints in natural conic
format, and ECOS/SCS don't support variable bounds directly. There are no
solvers which support conic+quadratic constraints in the same problem
without some transformation. These transformations are annoying to write,
and we shouldn't force each solver wrapper to implement them from scratch.
My proposal was to categorize the solvers according to the input format
that they do accept (e.g. Gurobi/CPLEX LP++ style versus conic form)
and then have some standard transformation code that can take any conic
solver and turn it into an LP solver, for example. Another example is NLP
solvers, which can act as LP or QCQP solvers after some transformation. The
motivation for these three problem classes is really just to make this
transformation process tractable and not to provide an ideal interface for
mathematical programming, which can be done on top of this plumbing code.

—
Reply to this email directly or view it on GitHub
#73 (comment)
.

Madeleine Udell
Postdoctoral Fellow at the Center for the Mathematics of Information
California Institute of Technology
https://courses2.cit.cornell.edu/mru8
https://courses2.cit.cornell.edu/mru8
(415) 729-4115

[tkelman]

You apparently have to fill out a form to get the code, but

a free open source Matlab based code PENLAB can do (almost) everything that PENNON can.

says it's GPL - http://web.mat.bham.ac.uk/kocvara/penlab. Have not looked at it in any depth though, so don't know how much is done in Matlab code vs mex files that we could maybe adapt more easily. I think I skimmed some of the associated papers at some point.

[mlubin]

The first is an AbstractModel, with fields for all sorts of components: linear
constraints, conic constraints, integer constraints, QP constraints, linear
objectives, nonlinear objectives, etc etc.

That's almost what a JuMP model is right now.

Then we'd have a bunch of translator functions for mapping between sorts of
components. When you try to smash an AbstractModel into a
particularSolverModel, we'd call the appropriate translation methods if
they exist and throw an error otherwise.

That logic is in JuMP already.

[madeleineudell]

One possible conclusion, then, is that JuMP is an abstraction sitting on
top of MathProgBase and Convex.jl and other modeling languages should be
abstractions sitting on top of JuMP.

On Thu, Nov 19, 2015 at 5:48 PM, Miles Lubin [email protected]
wrote:

The first is an AbstractModel, with fields for all sorts of components:
linear
constraints, conic constraints, integer constraints, QP constraints, linear
objectives, nonlinear objectives, etc etc.

That's almost what a JuMP model is right now.

Then we'd have a bunch of translator functions for mapping between sorts of
components. When you try to smash an AbstractModel into a
particularSolverModel, we'd call the appropriate translation methods if
they exist and throw an error otherwise.

That logic is in JuMP already.

—
Reply to this email directly or view it on GitHub
#73 (comment)
.

Madeleine Udell
Postdoctoral Fellow at the Center for the Mathematics of Information
California Institute of Technology
https://courses2.cit.cornell.edu/mru8
https://courses2.cit.cornell.edu/mru8
(415) 729-4115

[mlubin]

Quite possibly, unless they only care exclusively about LPs or conic problems.

[mlubin]

Closed by #91