Highs::getRows has linear scaling before a solve

[odow]

See jump-dev/HiGHS.jl#207

JuMP really likes to build and operate on rows, not columns. Querying the constraint function is a somewhat common operation, and it happens one-by-one; users don't have access to query a range of constraints in a single go.

This code in C shows what we'd like to do:

#include "interfaces/highs_c_api.h"

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    if (argc < 2) {
        printf("Usage: %s <integer>\n", argv[0]);
        return 1;
    }
    int N = atoi(argv[1]);
    void* highs = Highs_create();
    int ret;
    double INF = Highs_getInfinity(highs);
    for (int i = 0; i < N; i++) {
        ret = Highs_addCol(highs, 0.0, -INF, INF, 0, NULL, NULL);
    }
    int index[2] = {0, 0};
    double value[2] = {1.0, 1.0};
    for (int i = 1; i < N; i++) {
        index[0] = i;
        index[1] = i - 1;
        ret = Highs_addRow(highs, 0.0, INF, 2, index, value);
    }
    for (int i = 1; i < N; i++) {
        index[0] = i;
        index[1] = i - 1;
        ret = Highs_addRow(highs, 0.0, INF, 2, index, value);
    }
    double lower = 0.0;
    double upper = 0.0;
    int num_row = 0;
    int num_nz = 0;
    int matrix_start[1] = {0};
    int matrix_index[2] = {0, 0};
    double matrix_value[2] = {0.0, 0.0};
    for (int i = 0; i < N - 1; i++) {
        ret = Highs_getRowsByRange(highs, i, i, &num_row, &lower, &upper,
                                   &num_nz, NULL, NULL, NULL);
        ret = Highs_getRowsByRange(highs, i, i, &num_row, &lower, &upper,
                                   &num_nz, matrix_start, matrix_index,
                                   matrix_value);
    }
    Highs_destroy(highs);
    return 0;
}

In theory this should have O(N) scaling. But it has O(N^2). Double N and the runtime increase by a factor of 4:

$ time ./examples/main 1000
Running HiGHS 1.9.0 (git hash: 2dfbec111): Copyright (c) 2025 HiGHS under MIT licence terms
./examples/main 1000  0.02s user 0.01s system 92% cpu 0.033 total

$ time ./examples/main 2000
Running HiGHS 1.9.0 (git hash: 2dfbec111): Copyright (c) 2025 HiGHS under MIT licence terms
./examples/main 2000  0.07s user 0.01s system 96% cpu 0.083 total

$ time ./examples/main 4000
Running HiGHS 1.9.0 (git hash: 2dfbec111): Copyright (c) 2025 HiGHS under MIT licence terms
./examples/main 4000  0.27s user 0.01s system 98% cpu 0.276 total

$ time ./examples/main 8000
Running HiGHS 1.9.0 (git hash: 2dfbec111): Copyright (c) 2025 HiGHS under MIT licence terms
./examples/main 8000  0.97s user 0.01s system 99% cpu 0.987 total

$ time ./examples/main 16000
Running HiGHS 1.9.0 (git hash: 2dfbec111): Copyright (c) 2025 HiGHS under MIT licence terms
./examples/main 16000  3.75s user 0.02s system 99% cpu 3.780 total

$ time ./examples/main 32000
Running HiGHS 1.9.0 (git hash: 2dfbec111): Copyright (c) 2025 HiGHS under MIT licence terms
./examples/main 32000  14.99s user 0.06s system 99% cpu 15.097 total

Since we're iterating over every constraint, I think this means that each call to getRows is iterating over the entire constraint matrix.

This could be acceptable after Highs_run when HiGHS has stored the constraint matrix in column-major order, but so far all we have done is add rows one-by-one, so things should still be in row-major order.

[jajhall]

The row-extraction method was written when there was only ever a column-wise representation of the matrix, and its first action is to ensure that the representation is column-wise.

It's not hard to implement the row-wise extraction (and the column-wise extraction that isn't implemented when the matrix is held row-wise).

[odow]

Cool cool. Fixing this would speed up @jd-lara's Sienna models by a lot because he has a sanity check that loops through each constraint to check for malformed data etc, and querying the rows was a significant portion of the total runtime. (He can't as easily do the check as each constraint is being built because not all data is available yet. He could also store a copy of the data in a different data structure to do the check more efficiently, but then we need 2x the memory requirements.)

[odow]

If you look at jump-dev/HiGHS.jl#207 (comment) vis a vis Gurobi, the larger examples should run in milliseconds, not seconds.

[jajhall]

I was passing the matrix down to the new code by value, not reference!

I get linear time for your C code