Methods for editing few coefficients in the problem

[joaquimg]

MathProgBase currently does not have methods to change few Bounds, RHS´s, Objective Coefficients and A matrix coefficients.

The existing methods (as far as I know) only change the entire b, c and lb/ub vectors.

Changing A matrix is not even possible.

I have a code on Stochastic Dual Dynamic Programming as in #125 . I have benchmarked the code and building the problems is a bottleneck (40%) of the overall running time. So being able to modify coeffs of the A matrix would give a significant speedup.

The speedup for the sparse coefficients modification (LB, UB, RHS etc) would not be that huge, thus it would be ok to leave them as they are in JuMP. I just like the idea of having the lower level feature in MathProgBase.

I am willing to prepare a PR here and add the method in Xpress (and possibly Gurobi).

Are there any objections?

Even deleting constraints in the MathProgBase level would be ok if the solver is ready for it (I think the problem is handling that on JuMP).

[mlubin]

If you modify LB, UB, RHS, etc at most once between solves, then there's no real speedup to be gained from exploiting sparsity because the solver has to do a full pass through the vectors anyway.

If we add support for modifying coefficients in A, it would be nice to have it supported in at least one open source solver so that we can test it on travis. Other than that I have no objections, and we can defer the question of how to expose this in JuMP for a later point.

[joaquimg]

Ok, good point on sparsity of LB, UB, RHS.

I will focus on A matrix, which of the open source solvers would be easier for me to do it, in other words which one has the interface more similar to Gurobi? GLPK or Clp?

[mlubin]

I don't think the Clp C interface supports modifying coefficients, so GLPK would be a better bet.

[joaquimg]

Just looked at GLPK's manual and I could not find a routine to change specific coeffients in the A matrix (but I did find it in Gurobi and Xpress).

The closest I found are glp_set_mat_row and glp_set_mat_col, but both modify entire rows or columns.

Have you seen something? Who could know something about it?

[mlubin]

The GLPK manual is complete, so if it's not there it likely doesn't exist.

[mlubin]

Have you experimented with changing coefficients with Xpress? How much of the 40% bottleneck does it eliminate?

[joaquimg]

Changing coeffs together with delconstraints remove complete 40%, because I no longer have to rebuild (or rewrite) the models.

Joaquim

On 23 Dec 2016, at 01:25, Miles Lubin notifications@github.com wrote:

Have you experimented with changing coefficients with Xpress? How much of the 40% bottleneck does it eliminate?

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or mute the thread.

[mlubin]

Would it perhaps make sense to focus on removing constraints over modifying coefficients, since to update the constraint matrix you could also delete and add in the modified row?

[joaquimg]

Both are changing coeffs and deleting rows are, done in JuliaOpt/Xpress.jl@46c1eaf453535730c3b72367027c71bcda652a1b , PR in JuliaOpt/Gurobi.jl#78 and ready to be pushed in joaquimg/MathProgBase@7997b28baec3900c79f3e8994ea578f60b951044

I really like the idea of having both.

And I am not opposed to have a replaceconstr method, I could do it myself.

[joaquimg]

ops closed by accident

[joaquimg]

I implemented copy, delete constraints, delete variables in joaquimg/GLPKMathProgInterface@7337e2d23a51d0465da105db3fae855c333f57c3 but

m = LinearQuadraticModel(GLPKSolverLP())
loadproblem!(m, [ 2.0 1.0 ; 1.0 2.0 ], [0.0,0.0], [Inf,Inf], [1.0, 1.0], [-Inf, -Inf], [4.0,4.0], :Max)
optimize!(m)

delconstrs!(m, [1])
optimize!(m)

returns

glp_simplex: initial basis is invalid

Xpress and Gurobi run smoothly, any suggestions?

[mlubin]

There's probably some method in GLPK to reset the basis.

[odow]

I don't have any proper benchmarks, but I have anecdotal evidence that modifying the coefficients in place can have significant benefits. I'm in favour of having a change coefficients method.

@joaquimg is PSR moving to Julia?

[joaquimg]

@odow Yes, we are moving to julia!

@mlubin I found that function and added it in: joaquimg/GLPKMathProgInterface.jl@ab0a0185884d0ef1223d04494f28beee3c07b8ad

[mlubin]

Closed by https://github.com/JuliaOpt/MathProgBase.jl/pull/141