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!
1 Like
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.
1 Like
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.
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 VectorizeBridge and ScalarizeBridge · Issue #614 · jump-dev/MathOptInterface.jl · GitHub, Slack and Unslack bridge · Issue #528 · jump-dev/MathOptInterface.jl · GitHub and nonpositives to nonnegatives bridge · Issue #516 · jump-dev/MathOptInterface.jl · GitHub).
3 Likes
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.
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.
2 Likes
I am also looking to convert a General LP to Standard LP - @ianfiske do you have any code or insights that you can share from what you found? (My use case requires manipulating the coefficient matrix of the equality constraints in the Standard form, i.e. A in Ax=b.)
Will JuMP.set_normalized_coefficient work for you?
More here: https://jump.dev/JuMP.jl/stable/constraints/#Modifying-a-variable-coefficient
1 Like
There’s also this code in JuMP to get the standard form:
https://github.com/jump-dev/JuMP.jl/blob/b6d9ddfc1f190986834eaef1c729098fb16ddf32/src/lp_sensitivity2.jl#L301-L410
although it’s not public, so it may change in any future release.
5 Likes
Thanks! That is what I need to manipulate A once it is defined in the Model.
Thank you! This is the solution that I was looking for.