Avoid copies on model construction from pre-existing C arrays

[mckib2]

This may be more of a discussion item, but starting here.

We encountered an interesting case of out-of-memory exception when constructing large problems in scipy/scipy#15888. I think while there's not necessarily anything to do about it (sometimes problems are large and you need more memory), in this case it appears it could be helped by not requiring a double allocation of memory (once for the Python C array copies and once for the HiGHS std::vector copies).

As I observed in the SciPy issue:

Looking into this a little more, HiGHS underneath relies on std::vector which does not support copy-less assignment from C arrays. Even the C interface incurs copies when initializing.

The stack overflow answer above suggests that a custom allocator could be used that simply "reuses" the array allocation for the vector, but it's not clear to me currently how well Cython supports custom C++ allocators/deleters.

EDIT: followup: without C++17 features and a big rewrite of the HiGHS C++ interfaces, achieving this with custom allocators is probably not possible

I'm curious if there's a possible refactor from using std::vector to something able to take ownership of existing memory allocations, most importantly, C arrays. Most interactions between HiGHS and other programming languages (Python, Julia, Fortran, etc.) are usually going to be facilitated through C interfaces. In these use cases, HiGHS will require at least double the amount of memory for a single problem unless another internal container is used which supports copy-less assignment.

I'm happy to try a few things if there's an appetite for this kind of overhaul, also wanting to know if you consider this model-creation "optimization" worth the effort

[mingodad]

I do consider this worth because as you said "sometimes problems are large and you need more memory" but till that point with the same amount of memory we can do a lot of work id we do not use memory naively.

[mingodad]

See also this comment #855 (comment)

[jajhall]

Once we've finished the thin Python wrapper around the C++ class, so that use of HiGHS from Python will not involve the C interface, this situation will probably ease. However, it has to be stressed that if a model is so large that this extra copy is significant, then HiGHS probably won't be able to solve it (a) because it's so large and (b) because a couple of partial copies of the constraint matrix are made internally as part of the LP solution process. If you really want to cut down on memory use, pass the model to HiGHS and then deallocate the memory at the Python level before calling Highs_run(). If you want the model back, then extract it with Highs_getLp().

The work of moving away from std::vector just to address this issue is certainly not worthwhile.

[mingodad]

I'm not saying to "move away from std::vector" I'm saying to preallocate the user specified size and allow it to be populated by the user piece by piece without need to build an array just to pass to HiGHS that will make another copy.

[jajhall]

HiGHS already has the functionality you require.

Define a bunch of variables with Highs_addVars (or Highs_addCols), and then define constraints as you wish using Highs_addRows (or Highs_addRow if you want to add them one-by-one).

Predefining the numbers of columns and (particularly) rows is unnecessary and opaque. If a column is defined this way, then the user has to know what implied bounds it has - presumably [0, \infty) - and implied cost - presumably zero. This isn't so bad, but it still seems safer to force the user to define the bounds (as HiGHS does with Highs_addVars, or the cost as well with Highs_addCols). With rows, it's clear, giving a positive number in some initial definition (without the matrix coefficients or bounds) is pointless. You then need a separate method to add matrix coefficients and bounds to a row that already exists, as well as a method to add new rows with matrix coefficients and bounds. Unnecessary and confusing for users.

Can I add that the modelling aspect of the HiGHS API is considered to be more than sufficient by JuMP, who are very demanding in many ways.

We've also no intention of matching the API functionality of a very poor solver like lpsolve

[mingodad]

Sorry but I disagree with Unnecessary and confusing for users and very poor solver like lpsolve lpsolve can be slow or unable to solve several problems but it's API is a piece of cake to use.

Each head is world in itself !

[jajhall]

Other than "it's what lpsolve does" could you explain why you think that predefining the numbers of columns and (particularly) rows like this is useful. The examples you quote don't predefine a positive number of rows

So, we'll have to disagree. Be thankful you have the performance of HiGHS and an API that's accepted by modern minds in the world of modelling languages

[mingodad]

Of course this is how we progress people bring different points of view and ideas (just don't assume your point of view is a dominant/optimal one).

[jajhall]

Sure, I'm open to suggestions. Just explain why you think this is a worthwhile extension of the API