LP Solver with continuous constraint matrix

[mpadge]

You've got everything set up as binary, but extension to continuous/integer problems is obvious and would be needed to consider more complicated coverage issues like differential importance of proposed facilities. An archetypal consideration is population density - coverage ought to be related to this, and max coverage ought to consider coverage of the maximum area scaled to population density.

The Rglpk::Rglpk_solve_LP routine at least accepts additional types values of "I" and "C" for integer and continuous. It's easy to re-formulate your code to accept continuous input, and the solver is still surprisingly efficient, but ... I don't really know what the output means, nor do i understand how it maps on to your reference formulation of the problem from Church? Do you happen to have a document expressing your matrix construction, and the solution you're seeking in matrix algebra terms? Or anything else that might help?

[njtierney]

Continuous constraints would be fantastic.

I remember the output for the integer problem was a nightmare to interpret, so I imagine something similar for the other output.

I remember a lot of it was sitting down and doing small examples to imagine what the vector b was referring to. It ended up galvanised my motivation to make this package - this is analysis pain that the user should not need to experience.

[njtierney]

nor do i understand how it maps on to your reference formulation of the problem from Church? Do you happen to have a document expressing your matrix construction, and the solution you're seeking in matrix algebra terms? Or anything else that might help?

I've got a paper that is in press that has a bit of more detail, otherwise in my PhD thesis (never thought I would reference it!) - pages 50-52.

Let me know if that helps, otherwise I can revisit the code that builds the matrix and explain it better :)

[mpadge]

ah, okay, I think I'm starting to get it, and it looks like it should work. The LP is just maxmising the first expression subject to those constraints, which i think means it can be directly reformulated so that y_i remains the same binary variable, yet x_i becomes continuous, and by default scaled to 1/d. The maximisation remains identical, while the key is in your 3rd constraint (2.30):

You've got the a_i as binary, so it all adds up easy, but they could just as easily be continuous, in which case inverse distances would be my best guess. The x_i are then constrained to be ≤ the sum of inverse distances of a given set of candidate locations, and you're then trying to maximise that. The mechanics of maximisation then remain the same, and so it should all work ...

Obviously the interpretation will become different, and that'll be the next task to figure that out ...