Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Solution attr "status" VS solution not found #105

Closed
magalicombes opened this Issue Feb 13, 2019 · 4 comments

Comments

Projects
None yet
2 participants
@magalicombes
Copy link

magalicombes commented Feb 13, 2019

Hi,
I plan to run about 100 solutions for each of my conservation problems and get the selection frequencies. I do not use Gurobi yet and did some tests on Rsymphony with add_cuts_portfolio and add_shuffle_portfolio, to see what it does. For my problem the shuffle portfolio is not useful because returning always the same solution with +- a few planning units.
On all my solutions, I get the attr(s,"status") as a code, like "231" when the solution met the Rsymphony gap, or "228" when it did not.

I identified a problem when I imposed a time limit to Rsymphony with add_cuts_portfolio: when none solution was found when the time limit was reached, I got in my solution list:

  • "status" = "228", like when solution is found but outside the gap
  • sometimes weird solution values, for instance one was ranging between 0 and 658 (it should be 0 on 1 for a binary solution)

So I looked at the solving display and identified the “solutions not found” to exclude them manually from my selection frequencies. But this can be a bit tedious work if you have, let’s say, 50 scenarios with 100 solutions for each.
My questions and suggestions are:

  • Is there an explanation for the “status” codes? Are they the same on Gurobi?
  • Is there a way to measure the distance to the gap when a solution did not meet the gap? Do you recommend to ignore these solutions and only work with the solutions being within the gap? The limitation that I see here, is that it will be difficult to get 100 solutions meeting the gap in a reasonable amount of time (with Rsymphony), that’s why I consider including the solutions that are out of the gap.
  • I recommend to differentiate the “status” codes of “solution not found” and “solution found out of the gap” so we can filter them with the attr(s,”status”) command. It would be even better to remove the concerned solving output when no solution is found, either by returning all values as NA for that solution, either by removing the solution from the solutions list.

Thank you,
Magali

@jeffreyhanson

This comment has been minimized.

Copy link
Contributor

jeffreyhanson commented Feb 14, 2019

Hi,

Thanks for reaching out. I've tried to respond to each of your points/questions below, but please let me know if I've missed anything.

Yeah, the current portfolio methods tend to produce very similar solutions, and so you need a lot of solutions to compute "meaningful" selection frequencies. That said, in my opinion, selection frequencies don't provide much useful information. They don't tell you which planning units are more or less irreplaceable (since they don't include cost data, instead replacement cost values would be more useful, see
https://doi.org/10.1016/j.biocon.2008.11.011), and they don't tell you which planning units in the solution should be protected sooner rather then later (since they aren't calculated using any vulnerability data, e.g. which planning units are most likely to be subject to land clearing over the next 10 years). I think prioritizr really needs a "replacement cost"-like functionality, but I haven't got around to this yet (partly because I suspect that it won't be feasible for problems with 10k+ planning units). I'm sorry, other than increasing the number of suboptimal solutions, I don't really have any advice for this issue.

Yeah, the status codes are different between Gurobi and SYMPHONY. I refer to the ROI.plugin.symphony R package for descriptions of the SYMPHONY status codes (i.e. https://github.com/cran/ROI.plugin.symphony/blob/master/R/plugin.R#L79-L193). I'm sure there's an official write-up somewhere, but I haven't found it yet (so please let me know if you do find it).

Yeah, planning unit values should only be zero or one when you've specified binary decisions (the default), so getting a value of 658 is a bug. Could you please share a reproducible example, either with your data or the example data, that results in this bug?

I would (generally) recommend setting the gap instead of a maximum time limit. For reproducibility (e.g. if you run the same code on a better system, you might get different results when using time limits) and quality assurance (e.g. knowing how good the solutions are without removing highly suboptimal solutions afterwards), I think it's better to set a minimum level of performance rather then a maximum run time. If you only need solutions that are within a certain threshold of optimality (e.g. with the SYMHPONY solvers, a gap of 50 means that solution(s) need to be within 50 cost units of the optimal solution), then I would recommend setting the gap accordingly. If you set a higher gap, then this will generally reduce the run time considerably (e.g. see Figure 1 in https://doi.org/10.1016/S0006-3207(02)00042-3).

In terms of filtering out solutions using status codes, would something like this work?

# load package
library(prioritizr)

# load data
data(sim_pu_raster, sim_features, sim_pu_zones_stack, sim_features_zones)

# create minimal problem with minimum set objective
p1 <- problem(sim_pu_raster, sim_features) %>%
     add_min_set_objective() %>%
     add_relative_targets(0.1) %>%
     add_binary_decisions() %>%
     add_rsymphony_solver(gap = 2, time_limit = 1) %>%
     add_cuts_portfolio(number_solutions = 10)

# solve problem
s1 <- solve(p1)
length(s1) # yields 10 solutions on my computer

# extract solutions where status code is "231",
# i.e. target gap achieved
s2 <- s1[which(attr(s1, "status") == "231")]
length(s2) # yields 4 solutions on my computer

Also, if there's any way that you can get access to Gurobi, I'd strongly recommend it. It's much, much faster and the pool search portfolio methods also return multiple solutions in a much shorter period of time.

Cheers,

Jeff

@jeffreyhanson jeffreyhanson added the bug label Feb 14, 2019

@magalicombes

This comment has been minimized.

Copy link
Author

magalicombes commented Feb 14, 2019

Thank you Jeffrey for your really quick and useful answer,
We thought of using selection frequencies because we considered that several different solutions (not one or two planning units different, but really different) could meet our targets with a similar cost, so we can provide a more flexible spatial plan, or different planning options, to stakeholders. But you're right, the irreplaceability issue stays... Thanks for the reference.
I sent you the R console display of my code, leading to the bug. The bug seems to be inherent to Rsymphony and not PrioritizR:
when solving displays :

****************************************************
* Time Limit Reached                               *
****************************************************

No Solution Found

sym_get_col_solution(): No solution has been stored!

It actually stores a “fake” solution (with sometimes weird values) and its status code is “228”. So I recommend, as you said, to advise prioritizr users to use only the "231" solutions to be sure.
I will run my problems with and increased gap instead of a time limit. My mistake was also to give Rsymphony a relative gap whereas it should be in cost unit, thus my gap was really to small.
I will also install Gurobi to fix the processing time issue.
Thanks a lot,
Magali

@jeffreyhanson

This comment has been minimized.

Copy link
Contributor

jeffreyhanson commented Feb 22, 2019

Ok - thank you so much for looking into this. I'll patch prioritizr so that if any solutions with values are greater than one or less than zero are returned by Rsymphony, then prioritizr will throw an error.

@jeffreyhanson

This comment has been minimized.

Copy link
Contributor

jeffreyhanson commented Feb 22, 2019

I'm just about to upload a patch which will mean that prioritizr throws an error instead of returning invalid solutions from Rsymphony which should address this issue, so I'll close this issue in a minute or so. If you have any further questions, or if you find that the new version doesn't fix this problem, please feel free to reopen this issue.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.