Understanding Clp_addColumns from Clp_C_Interface.h

[infinity77]

Dear CLP Community,

this is my first message here and I am a very new user of CLP, so I apologize in advance for my ignorant questions. I would also like to mention that my proficiency in C++ is close to zero.

I am trying to build a model in CLP (and I can only use the Clp_C_Interface for this). I first tried with Clp_loadProblem and, while it works, it appears I can do better using Clp_addColumns. But I can't understand what the two parameters columnStarts and rows are supposed to contain. This is the signature of Clp_addColumns:

CLPLIB_EXPORT void CLP_LINKAGE Clp_addColumns(Clp_Simplex *model, int number, const double *columnLower,
  const double *columnUpper,
  const double *objective,
  const CoinBigIndex *columnStarts, const int *rows,
  const double *elements);

Assuming I have a model with 20 rows (constraints) and 15 columns (variables) and I want to add one column at the time using Clp_addColumns, I understand that the parameters columnLower, columnUpper and objective are of size 1 (1 element only, as it's one column at the time). The elements parameter should have 20 elements (rows per column). But I am at complete loss when it comes to columnStarts and rows parameters,

I have consulted the help page for Clp_addColumns and also for addColumns, but I can't figure out how to proceed.

As a side note, I have looked at the simple example in this issue: #113, and I am building the model in the same way:

Clp_Simplex *mod = Clp_newModel();
Clp_resize(mod, m, 0);

Thank you in advance for any suggestions.

Andrea.

[jpfasano]

Andrea, elements normally only has non-zero values. rows is used to indicate the row number of the corresponding value in elements. When more than one column is being added, then the index into elements of where each column starts is stored in columnStarts. So, if you are adding a column with nonzero elements of 3 in row 4 and -6 in row 8, then you could define columnStarts, rows, and elements as: ``` double elements[2] = {3.0, -6.0}; int rows[2] = {4, 8}; int columnStarts[2] = {0,2}; // note: the number of elements in the i’th column is (columnStarts[i+1]-columnStarts[i]) // the number of elements in columnStarts will be one more than the number of columns being added ``` I hope this helps (and is correct). JP

…

On Tue, Mar 16, 2021 at 5:36 AM Andrea Gavana ***@***.***> wrote: Dear CLP Community, this is my first message here and I am a very new user of CLP, so I apologize in advance for my ignorant questions. I would also like to mention that my proficiency in C++ is close to zero. I am trying to build a model in CLP (and I can only use the Clp_C_Interface for this). I first tried with Clp_loadProblem and, while it works, it appears I can do better using Clp_addColumns. But I can't understand what the two parameters columnStarts and rows are supposed to contain. This is the signature of Clp_addColumns: CLPLIB_EXPORT void CLP_LINKAGE Clp_addColumns(Clp_Simplex *model, int number, const double *columnLower, const double *columnUpper, const double *objective, const CoinBigIndex *columnStarts, const int *rows, const double *elements); Assuming I have a model with 20 rows (constraints) and 15 columns (variables) and I want to add *one column at the time* using Clp_addColumns, I understand that the parameters *columnLower*, *columnUpper* and *objective* are of size 1 (1 element only, as it's one column at the time). The *elements* parameter should have 20 elements (rows per column). But I am at complete loss when it comes to *columnStarts* and *rows* parameters, I have consulted the help page for Clp_addColumns and also for addColumns, but I can't figure out how to proceed. As a side note, I have looked at the simple example in this issue: #113 <#113>, and I am building the model in the same way: Clp_Simplex *mod = Clp_newModel();Clp_resize(mod, m, 0); Thank you in advance for any suggestions. Andrea. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#179>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACJMOGOKNQB3J6EDVC7OV43TD4RDNANCNFSM4ZIF2PZQ> .

[infinity77]

Thank you for your answers JP and tkralphs. I know already about CyLP and sparse matrices: one of the issues I mentioned in my email is that - whether I use sparse matrices myself or let CyLP do the work, the conversion itself from dense to sparse is going to defy the purpose.

Trying with a couple of matrices that I have as examples, just the simple conversion to COO format takes between 0.1 to 0.2 seconds, which is the same time I get by directly using Clp_loadProblem and about 10 times as slow as the lpsolve Cython wrapper.

[tkralphs]

Clp provides a range of different ways of getting data into the solver through its C++ interface and CoinUtils provides yet more ways (e.g., look for addColumns in https://github.com/coin-or/Clp/blob/master/src/ClpModel.cpp). Any of these could be added to the C interface easily. I'm still not very clear on how sparse your data actually is, though. If it is sparse in reality, you probably can't avoid it being converted at some point, since Clp uses sparse methods to do the factorization whenever doing so is likely to be more efficient (although I think you can force dense if you really want). @jjhforrest is probably the right person to answer this question in more detail.

[infinity77]

@tkralphs : Thank you very much for your comments. I am definitely convinced that at some point the data will have to be converted to sparse (potentially by CLP). What I find particularly puzzling in all of this is the behaviour of Clp_loadProblem (or similarly Clp_addColumns) compared to the performances of using the CLP executable and reading from MPS files the exact same problem.

For some of the linear systems I am testing, I have mps files - which vary in size between 300 kb to 1.1 Mb - representing medium-size problems. Now, for both lpsolve and CLP I can actually invoke the executable with those mps files as input and write down the elapsed time for each stage:

LPSolve: lp_solve.exe  -mps -max -s1 -sd -presolve -S1 -v4 MPS_FILE.mps

CLP    : clp.exe MPS_FILE.mps -scal=geo -max=on -presolve=on -solv

Both solvers give elapsed time for loading the mps file, time spent on presolve and time spent on solve. This is what I get comparing the two solvers on different matrices that I have (the size of the matrix is below the X-axis for each test):

Please note that the scale is logarithmic. So, using an mps file, CLP is able to setup the problem in 20/30 ms, while when I use Clp_loadProblem the average is around 100 ms for smaller problems to 500 ms for larger ones. You will also notice that CLP is blazing fast in actually solving the problem, that's why I am trying so hard to find a "reasonable" way (for me) to populate the model as fast as possible.

You could also argue that I could simply use the executable as above, but I am solving very many different linear systems one after the other inside a Python-based application, for which I would have to generate the mps file first, invoke the operating system with something like:

os.system('clp.exe MPS_FILE.mps -scal=geo -max=on -presolve=on -solv -solu output_file')

And then read the output file. All of this adds a lot of overhead that defeats the purpose. I am very puzzled by all of this.

My apologies for the long message.

Andrea.

[tkralphs]

Interesting data. Clp is surely not optimized for a use case in which loadProblem would be the bottleneck. Just eyeballing the code, the guts of loadProblem is just copying the data to avoid assuming ownership of the memory. I could imagine that this copying operation could be cache inefficient. It could also be skipped altogether with a method that assumes ownership. The reading of MPS files takes place in the CoinMpsIO::readMps() in CoinUtils, but after reading, the data is loaded into Clp by... loadProblem! However, it uses a slightly different version in which the matrix object is cloned rather than copying the individual arrays. I don't see a good reason that would be so much more efficient that it overcomes the cost of file IO.

In any case, I guess it would not be too difficult to replicate what is happening when reading the MPS file from disk by using the same variant of loadProblem. Implementing a version of loadProblem that avoids copying data would be another possible approach.

You could try profiling by running the code in a loop in order to get enough samples to see where the time is really spent. I don't know how accurate this would be, but if did enough replications, it would give you some insight.

[jhmgoossens]

Could this behavior not be due to marshalling between the Cython and the C interface of Clp/CBC? I'm not familiar with Cython, but I can imagine some marshalling of the arrays of doubles is involved?

[infinity77]

Hi @tkralphs , @jhmgoossens ,

thank you for your answers. First of all, I would like to say that debugging the COIN code is way above my capabilities - my knowledge of C++ is minuscule at best, and the COIN code is very mature and long. I will never get out of that maze with some meaningful conclusions.

That said, I have done a few more tests. To address @jhmgoossens question, this is the only line I am timing in Cython:

start = time.clock()

Clp_loadProblem(self._model, n, m,
                &col_starts[0], &row_indices[0], &constraints_matrix[0, 0],
                &col_lb[0], &col_ub[0], &obj[0], &row_lb[0], &row_ub[0])

end = time.clock()
print(end - start)

As you can see, everything is passed by reference. I can't imagine there being any copying/marshalling of data as that call is pretty much a straight C-invocation into the COIN C interface.

Timing the executable loading time and the Clp_loadProblem interface multiple times (10 runs averaged), I get the following:

Again, please note that the scale is logarithmic. What this tells me is that, whatever clp.exe is doing is between 3 and 40 times faster than the Clp_loadProblem interface.

I have no idea on how to implement a version of loadProblem that does not go into all the gimmicks @tkralph has described. It would definitely be most useful, as at the moment the loading time compared to the solve time are disproportionately far apart.