Write incumbent soln at out-of-memory

[ghauser8]

In limited testing with the command line interface, I've found that if in the process of solving HiGHS is killed due to memory limitations, HiGHS currently does not write an incumbent solution to a specified solution file (--solution _file solution.sol).

Is it (as of v1.5.0) possible to recover an incumbent solution if the solver is killed because of insufficient memory? If not, are there plans to incorporate something like this?

For context, I'm testing via Docker containers (alpine:latest as base container, layered with necessary bits for cmake to build HiGHS) on a linux host.

This is a super cool project, I'm very excited to see a new version! Thanks for everything y'all are doing!

[jajhall]

HiGHS being killed by memory limitations is a very rare occurrence, so we don't do anything when this happens. When you mention "an incumbent solution", I'm guessing that you're solving a mixed-integer problem, and know that an integer feasible solution has been found. Is this the case? If you're only solving an LP, it's unlikely that there is any useful incumbent solution to be recovered.

Do you have an example of a problem where HiGHS is killed in this way?

Sorry for not replying sooner: I don't get notifications of discussion items.

[ghauser8]

Yes, I'm working with MIPs, sorry for not clarifying that earlier! I see your point about LPs. The example MIP I'm working with is here: bin.txt (originally .lp, I changed it to .txt to upload here). It's a bin packing problem with 500 items and 500 bins, where all item sizes are between 0 and 1 and all bin sizes are 1 with the objective of minimizing the number of bins used to pack all items (I randomly generated item sizes if you'd like to develop your own version of this model).

HiGHS steadily consumes memory as more and more of the branch/cut tree is explored. This is of course expected behavior for large MIPs, which is where I think returning incumbent solutions (if one exists) upon running out of memory would be useful. Especially as those incumbent solutions could be used for warm-starting subsequent runs of the same problem, thereby "recovering" some of the work that has already been done.

To see this behavior most clearly, solving the above problem with HiGHS (with presolve off) in a container with memory limited to 300Mb will result in HiGHS identifying an incumbent solution, but then being killed so as not to exceed the memory limit. Presolve will produce a large spike in memory usage, violating memory limits before identifying an incumbent solution. Other memory limits will also produce the same behavior, but 300Mb seems to do it in a reasonable amount of time.

Hopefully this small example makes the more general point.

As an aside, if an LP did run out of memory, perhaps returning the latest basis (if primal/dual simplex method is being used) could be useful, but to be honest I've never needed this in practice. On the contrary, I've found that (the most interesting) large scale MIPs almost always chew through whatever memory is available.

[jajhall]

Thanks for this. I think I see how to limit the memory available to a simple Linux process, allowing me to experiment. Of course I have to cover all possible places where the memory limit might be reached.

An alternative, simple fix is to have an option that, when set, writes any integer feasible solution to a file if it's the best so far. This would also be a fix for people who want a pool of integer feasible solutions - something that we'll not be implementing internally any time soon.

In the case of solving an LP using simplex, if you re-started from the saved basis, you'd probably hit the memory limit again very soon.

[ghauser8]

I think your alternative makes a lot of sense.

Glad I could help, thanks again!

[jajhall]

I've started implementing code to save and report improving solutions found by the MIP solver.

[jajhall]

The code to save and report improving solutions found by the MIP solver will be pushed to the latest branch by #1254. This will also lead to the documentation of the three associated options being available from https://ergo-code.github.io/HiGHS/dev/options/definitions/