Add parameter to cbc_solve to specify initial solutions

[jeffreyhanson]

Hi,

Thanks again for creating this R package @dirkschumacher! I've been using it to solve a bunch of optimization problems, and I'm now applying it to some multi-objective optimization problems. Specifically, the multi-objective optimization process involves (i) formulating a problem using an objective, (ii) solving it to obtain a solution, (ii) updating the problem formulation with a second objective (replacing the first objective), (iv) adding a constraint to the problem formulation based on first objective and first solution (e.g. ensure performance based on first objective is within 10% of optimality based on first optimization run), and (v) solving it to generate a second solution. This works really well, and I was thinking it might be possible to improve performance by using first solution as the starting/initial solution when generating the second solution.

So, this PR adds functionality so that users can supply a starting solution for the CBC solver. To acheive this, a new parameter (i.e. initial_solution) is added to the cbc_solve function where users can supply a numeric vector containing the initial solution values. Missing (NA) values can be used when initial values do not need to be supplied for certain variables. We can see that the CBC does indeed use the supplied starting solution values because it prints MIPStart solution provided values for [....] when using the initial_solution to supply starting values (e.g. see example below). Additionally, to maintain test coverage, this PR also includes a test for the initial solutions in tests/testthat/test-cbc-solver.R. Also, although CBC can take longer to solve problems when initial solution are supplied (even when the initial solution is an optimal solution), it seems that this only the case for small/simple problems.

Let me know what you think?

---

Example using intial solution:

# load pacakge
library(rcbc)

# run optimization
A <- as(matrix(c(1, 2, 3, 4), ncol = 2, nrow = 2), "dgTMatrix")
result <- cbc_solve(
          obj = c(1, 2),
          is_integer = c(TRUE, TRUE),
          mat = A,
          row_lb = c(0, 0),
          row_ub = c(1, 2),
          max = TRUE,
          cbc_args = list("logLevel" = 3),
          initial_solution = c(0, NA_real_))

[dirkschumacher]

Thanks for the PR. Exciting! Sorry I totally missed that. Will try to review it until end of month.

[jeffreyhanson]

Awesome - thanks - no worries! Let me know if there's anything I can do to help.

[jeffreyhanson]

Thank you very much for taking a look at this! I'll try and respond to your comments/questions and update the PR by the end of the week.

[jeffreyhanson]

@dirkschumacher, I think I've responded to and addressed all your comments - but please let me know if I missed anything or if anything I've written isn't clear?

[dirkschumacher]

Thanks a lot. Initial values are extremely useful. Often you would write a custom heuristic that finds a good first feasible solution and then start the search process. Because without a feasible solution you are missing a bound that can be used to prune the search tree.

[dirkschumacher]

PS: I cannot test it as CBC fails to install on my new m1 Mac 🙈 But I trust the CI

[jeffreyhanson]

Thanks a lot. Initial values are extremely useful. Often you would write a custom heuristic that finds a good first feasible solution and then start the search process. Because without a feasible solution you are missing a bound that can be used to prune the search tree.

No worries! Yeah, that's basically the use case that motivated this PR.

[jeffreyhanson]

PS: I cannot test it as CBC fails to install on my new m1 Mac see_no_evil But I trust the CI

Ah - that must be a bit annoying. Let me know if there's any tests I can run on my computer that would be helpful? E.g., I could post the logs from running checks on my computer (Ubuntu 21.4)?

[dirkschumacher]

I seems the checks have not been triggered. Can you make another commit to see if they work now?

[jeffreyhanson]

Sure

[jeffreyhanson]

Just pushed a small doc tweak - that seems to have done it.

[jeffreyhanson]

I'll add you to my fork so you can make any further changes if needed.

[jeffreyhanson]

Looks like the Ubuntu builds failed because curl needs to be installed:

2021-10-19T08:56:57.7176177Z * installing *source* package ‘curl’ ...
2021-10-19T08:56:57.7268232Z ** package ‘curl’ successfully unpacked and MD5 sums checked
2021-10-19T08:56:57.7269637Z ** using staged installation
2021-10-19T08:56:57.7323088Z Package libcurl was not found in the pkg-config search path.
2021-10-19T08:56:57.7325022Z Perhaps you should add the directory containing `libcurl.pc'
2021-10-19T08:56:57.7326234Z to the PKG_CONFIG_PATH environment variable
2021-10-19T08:56:57.7327383Z No package 'libcurl' found
2021-10-19T08:56:57.7340117Z Package libcurl was not found in the pkg-config search path.
2021-10-19T08:56:57.7341545Z Perhaps you should add the directory containing `libcurl.pc'
2021-10-19T08:56:57.7342617Z to the PKG_CONFIG_PATH environment variable
2021-10-19T08:56:57.7343605Z No package 'libcurl' found
2021-10-19T08:56:57.8366606Z Using PKG_CFLAGS=
2021-10-19T08:56:57.8368303Z Using PKG_LIBS=-lcurl

[jeffreyhanson]

I'll update the GitHub actions file to manually install it

[jeffreyhanson]

Awesome - thanks for merging this!