Linear Solver CLP Interface C++ Inner Workings

[iainfullelove]

Hi guys,

I have a problem I'm using the linear solver in Google ortools (version 8) to help solve.
This problem involves iteratively solving a small LP (no integer variables) and then a large min-cut problem (Bienstock-Zuckerberg Algorithm).
I'm using C++ for this algorithm, integrating Google ortools with cmake.
Within ortools I'm using the CLP solver. I considered using COINOR CLP or OSI directly, but found the ortools interface to be alot nicer and easier to use.
I typically have to iteratively solve an LP problem 10 - 50 times during the solution process.
I build the MPSolver object and associated constraints/objective once at the start of the algorithm, and then update the variables in each iteration.
However, I was wondering about how Google ortools interfaces with CLP in the backend.
I did see in ortools/linear_solver/linear_solver.h the comment:

• For developers: How the wrapper works
• MPSolver stores a representation of the model (variables,
• constraints and objective) in its own data structures and a
• pointer to a MPSolverInterface that wraps the underlying solver
• (GLOP, CBC, CLP, GLPK, or SCIP) that does the actual work. The
• underlying solver also keeps a representation of the model in its
• own data structures. The model representations in MPSolver and in
• the underlying solver are kept in sync by the 'extraction'
• mechanism: synchronously for some changes and asynchronously
• (when MPSolver::Solve is called) for others. Synchronicity
• depends on the modification applied and on the underlying solver.
  */

So every time I call the Solve() method, the complete LP matrix that is used by CLP isn't being re-created in memory for CLP (and is just updated when I update the MPVariables in the ortools code?), or, every time I iteratively run a LP problem, the complete LP matrix is being re-built in memory for CLP and then CLP is run?

The reason I'm interested in this is just for algorithm efficiency and runtime speed.

For the LP problems that are iteratively run, their sizes typically range 100,000 - 500,000 rows and 20 - 200 columns.

Thanks for you help,
Iain

[lperron]

Yes. CLP/CBC APIs are a nightmare of unfriendliness. Other solvers have better support for incrementality. Coin OR solvers do not, and I will not work on those directly. I will accept PR gladily. Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53 00 Le sam. 2 janv. 2021 à 05:13, iainfullelove <[email protected]> a écrit :

…

Hi guys, I have a problem I'm using the linear solver in Google ortools (version 8) to help solve. This problem involves iteratively solving a small LP (no integer variables) and then a large min-cut problem (Bienstock-Zuckerberg Algorithm). I'm using C++ for this algorithm, integrating Google ortools with cmake. Within ortools I'm using the CLP solver. I considered using COINOR CLP or OSI directly, but found the ortools interface to be alot nicer and easier to use. I typically have to iteratively solve an LP problem 10 - 50 times during the solution process. I build the MPSolver object and associated constraints/objective once at the start of the algorithm, and then update the variables in each iteration. However, I was wondering about how Google ortools interfaces with CLP in the backend. I did see in ortools/linear_solver/linear_solver.h the comment: - For developers: How the wrapper works - - MPSolver stores a representation of the model (variables, - constraints and objective) in its own data structures and a - pointer to a MPSolverInterface that wraps the underlying solver - (GLOP, CBC, CLP, GLPK, or SCIP) that does the actual work. The - underlying solver also keeps a representation of the model in its - own data structures. The model representations in MPSolver and in - the underlying solver are kept in sync by the 'extraction' - mechanism: synchronously for some changes and asynchronously - (when MPSolver::Solve is called) for others. Synchronicity - depends on the modification applied and on the underlying solver. */ So every time I call the Solve() method, the complete LP matrix that is used by CLP isn't being re-created in memory for CLP (and is just updated when I update the MPVariables in the ortools code?), or, every time I iteratively run a LP problem, the complete LP matrix is being re-built in memory for CLP and then CLP is run? The reason I'm interested in this is just for algorithm efficiency and runtime speed. For the LP problems that are iteratively run, their sizes typically range 100,000 - 500,000 rows and 20 - 200 columns. Thanks for you help, Iain — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#2309>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3LICZ7V4GAWE2577TDSX2MOZANCNFSM4VQYMMYQ> .

[lperron]

Can you try with GLOP instead of CLP ?

[iainfullelove]

Thanks for the reply @lperron. Yeah i've heard there can be some issues with integrating nicely with the COIN-OR suite.

I ended up testing with GLOP and seem to be having really good results so far, seems like a good solver.