Existing package to convert LP to standard form?


#1

I’m working towards implementing a new type of solver for MILPs based on ADMM. This solver requires that the problem be specified as an LP in standard form (+ MI constraints). Before I go re-inventing the wheel, are there any existing packages that perform this conversion (raw LP spec to standard form)? I haven’t found anything so far since most solvers are wrappers around C libraries and that conversion to standard form happens at the C-library level. However, I’d like to write the solver itself in Julia. I didn’t see anything like this in MathProgBase or MathOptInterface, but I might have missed something. Thanks for any tips!


#2

NLPModels.jl will let you specify continuous optimization problems and convert them by adding slack variables. Currently, inequality constraints of the form \ell \leq c(x) \leq u are transformed to c(x) - s = 0 and \ell \leq s \leq u, where s are the slack variables. That should be ok for most solvers, but it wouldn’t be hard to actually perform the conversion to standard form. For example, you could read an LP in MPS format using QPSReader.jl, turn the result into a QuadraticModel (a subtype of NLPModel), and then add slack variables to the result. The metadata contained in an NLPModel lets you specify which variables have integrality constraints on them, though we haven’t really exercised that facility much. So feedback there would be very welcome.


#3

I think this should be relatively easy to do on the basis of MathOptInterface, which also give JuMP support to your solver.

There’s also the LinQuadOptInterface intermediate layer that is more high-level used by several MIP solver wrappers.

But I did not find exactly the function to extract the LP data in matrix/vector form.


#4

With MathOptInterface, a solver should only support the type of constraints for which he actually exploits the structure and not support any constraint types that are transformed internally into equivalent ones.
The transformations are all done automatically using bridges.
If your optimizer only support MOI.SingleVariable-in-MOI.GreaterThan{Float64} and MOI.ScalarAffineFunction{Float64}-in-MOI.EqualTo{Float64} (standard LP form), then the user will be able to use any LP form with JuMP.
Slack variables, and so on will be automatically created by the bridges (note that a few bridges are currently missing but they are planning to be done in the coming days, see https://github.com/JuliaOpt/MathOptInterface.jl/issues/614, https://github.com/JuliaOpt/MathOptInterface.jl/issues/528 and https://github.com/JuliaOpt/MathOptInterface.jl/issues/516).


#5

Thank you for the tip. I didn’t really know about NLPModels.jl. I will come back to this solution if the JuMP/MathOptInterface solutions don’t work out.


#6

Wow! I had hoped that this type of thing was supported in MathOptInterface, just didn’t quite know where to find it. Bridges look amazing. I’ll start testing with those that are already available. Looking forward to the rest of them coming as you’ve mentioned for slack variables since the method I’m looking at only supports equality constraints.