ERGO-Code / HiGHS

Linear optimization software
MIT License
943 stars 175 forks source link

Fix the O(N^2) bug of passColName and passRowName #1782

Closed metab0t closed 4 months ago

metab0t commented 4 months ago

Reland https://github.com/ERGO-Code/HiGHS/pull/1780

I also simplify some logic here. The result of emplace has contained the duplicate key-value pair if it detects duplication, so we can mark the value as duplicate directly instead of using the slow search-erase-insert combo.

metab0t commented 4 months ago

@jajhall CI tests pass. It is ready to be reviewed.

metab0t commented 4 months ago

This may pass the CI tests, but that's because there's no unit test to check that duplicate names are marked as such

https://github.com/ERGO-Code/HiGHS/blob/13363c9f1252b015cf6527132eb9cf8f4b5bf020/check/TestNames.cpp#L68-L88

In the beginning, col0_name is unique, so it has corresponding column.

But after col0_name is assigned to num_col_ / 2 column, it will be duplicate and cannot get column by the name.

metab0t commented 4 months ago

There is still one edge case: if a name is marked as duplicate and the corresponding column is assigned with a new name, then the old name should not be deleted directly (there might be other columns with this old name).

However, this is an edge case and checking it would require $O(N)$ iteration through the col_names_. In practice, I believe that few people will set the name of a variable twice.

The final and complete solution is to use https://en.cppreference.com/w/cpp/container/unordered_multimap to map name to column/row if we want to allow multiple columns/rows to have the same name.

jajhall commented 4 months ago

Indeed, there's a limit to making this idiot-proof