Recycling allocations

[mmottl]

HiGHS performs a not insubstantial number of allocations each time a new model is instantiated, e.g. HighsLP. There currently doesn't seem to be any way to reuse these allocations across runs. The API only exposes const references to such objects after they have been passed to Highs. Would it be possible to support recycling these objects? Solving large numbers of smallish problems would likely benefit most from this feature.

It seems the easiest way to support this feature would be by clearing (without reallocation) and then returning (moving) incumbent models and other objects that allocate, replacing them internally with freshly constructed objects. The construction of new, empty objects does not usually cause allocations.

After users fill in new data, they can just pass the updated model again, replacing the empty one. This way previous allocations can be reused, leading to lower, more predictable computational overhead.

[jajhall]

I don't fully understand what you're asking for, but there's no way we can allow users to modify data internal to HiGHS.

Could you achieve your aim using delete and add rows/columns to replace the model without passing in a new one?

[mmottl]

Thanks for your fast reply!

The HighsLP object allows for direct access to the C++ vectors that specify the problem (cost and lower / upper bounds, a_matrix), which is the most efficient way of specifying problems for the intended purpose. Once this object has been passed to the Highs object via passModel, it unfortunately cannot be retrieved anymore except for read-only access. Adding rows and columns is not as efficient.

Having thought about API choices for a solution, it might actually be easiest and most efficient to implement a swapModel function that is just a small modification of the passModel function.

The current implementation of passModel starts as follows:

HighsStatus Highs::passModel(HighsModel model) {
  // This is the "master" Highs::passModel, in that all the others
  // (and readModel) eventually call it
  this->logHeader();
  // Possibly analyse the LP data
  if (kHighsAnalysisLevelModelData & options_.highs_analysis_level)
    analyseLp(options_.log_options, model.lp_);
  HighsStatus return_status = HighsStatus::kOk;
  // Clear the incumbent model and any associated data
  clearModel();
  HighsLp& lp = model_.lp_;
  HighsHessian& hessian = model_.hessian_;
  // Move the model's LP and Hessian to the internal LP and Hessian
  lp = std::move(model.lp_);
  hessian = std::move(model.hessian_);
  // ...

A swapModel function would be almost identical:

HighsStatus Highs::swapModel(HighsModel &model) {
  // This is the "master" Highs::passModel, in that all the others
  // (and readModel) eventually call it
  this->logHeader();
  // Possibly analyse the LP data
  if (kHighsAnalysisLevelModelData & options_.highs_analysis_level)
    analyseLp(options_.log_options, model.lp_);
  HighsStatus return_status = HighsStatus::kOk;
  // Clear the incumbent model and any associated data
  clearModel();
  // Swap the new and old models
  std::swap(model_, model);
  // ...
}

Basically, the only difference is that we would be passing in the new model by mutable reference instead of by value, and instead of std::move we would be calling std::swap. We could surely share most of the code between the current passModel and the new swapModel function.

The advantage is that we wouldn't be calling the destructor of the old model and the constructor of the new model for every solve attempt. The old model would be cleared with clearModel and then returned to the user in the passed model reference.

Imagine a thread solving a model. We could already prepare a new problem while it is running. Once the solver thread is done, we just swap the new model with the old, cleared one. We could immediately start filling in a new problem in the "old" model without having to reallocate the associated vectors unless the new problem exceeded the already allocated size. From then on we only ever swap models and would be practically allocation-free.

One might argue that solving is typically way more expensive than allocations and that the above might not matter that much. But that assumes that problems are always large enough and/or that we never interrupt the solver, e.g. during optimistic solving when a problem can but is unlikely to change before a solution is found.

The same idea can also be applied to other kinds of values, e.g. when calling passLinearObjectives.

What do you think of adding these efficiency improvements?