addRow has bottleneck in assessMatrix

[odow]

I have the following model (really, something more complicated, but this is the essential constraint):

julia> using HiGHS

julia> function create_model(N)
           highs = Highs_create()
           for _ in 1:N^2
               Highs_addCol(highs, 0.0, -Inf, Inf, 0, C_NULL, C_NULL)
           end
           for i in 1:N
               for j in 2:N
                   b = N * (i - 1) + j
                   a = b - 1
                   Highs_addRow(highs, -Inf, 0.0, 2, [a, b], [1.0, -1.0])
               end
           end
           Highs_destroy(highs)
           return 
       end

and it's slow to build. (On the order of 1-5 minutes to build the full model for moderate instances, and yet the LP solves in 5 seconds.)

I know that I could create the full matrix up front and call passModel, but ideally addRow wouldn't be too much slower. Here's a profile for create_model(200):

which shows that the bottleneck is in the assessMatrix method used to check that the constraint doesn't contain small/large/duplicate coefficients. In particular, it's this assign call:

HiGHS/src/util/HighsMatrixUtils.cpp

Lines 146 to 151 in dcdb627

	// Set up a zeroed vector to detect duplicate indices
	vector<HighsInt> check_vector;
	if (vec_dim > 0) check_vector.assign(vec_dim, 0);
	for (HighsInt ix = 0; ix < num_vec; ix++) {
	HighsInt from_el = matrix_start[ix];
	HighsInt to_el = matrix_start[ix + 1];

Here vec_dim is the number of columns, N^2, and we create a new vector for each of the N * (N - 1) constraints, even though each row only has two coefficients!

Some potential solutions would be:

• If there are few coefficients, just do a loop through the coefficients to check for duplicates.
• use a different data-structure, like a map
• cache the vector so we can re-use it between calls, avoiding the need to malloc a new vector for each constraint
• add an option to disable assessMatrix, assuming the user knows they are providing something good.

[jajhall]

I'm on it