search

coin-or / Clp

COIN-OR Linear Programming Solver
Other
392 stars 82 forks source link

Guidence to add user customed pivoting rule #262

Open dxyzx0 opened 1 year ago

dxyzx0 commented 1 year ago

I have several questions:

  1. Is there any guidence to help me implement my own pivoting rule? What methods should be implemented?
  2. What's the relationship between the cpp source files with prefix Abc and Clp?

Thanks a lot!

jjhforrest commented 1 year ago
  1. I am not sure which methods should be implemented. I searched on "dual pivoting algorithms in simplex method" and was not impressed. It should be fairly simple to implement any method. For dual simplex look at ClpDualRowPivot.?pp for the method you need to inherit from and ClpDualRowDantzig.?pp for the simplest implementation and then look at ClpDualRowSteepest.?pp for a more efficient implementation. For primal simplex, you would look at ClpPrimalColumn versions.
  2. I would only look at Clp versions. The Abc versions were a partially successful attempt to parallelize the simplex method which were implemented more than 10 years ago for a conference and not kept up to date (Abc was short for Aboca - "A Bit Of Clp Accelerated" - Aboca actually being a small Italian frazione).
dxyzx0 commented 1 year ago

Thanks for your quick reply! I'll try to read the ClpDualRowPivot.cpp.

Sorry to bring up other questions: I'm trying to understand the main function initialSolve since the presolve solving postsolve part are in the function. But it's too long to read and hard to follow what's happening.

  1. There're many do* in the code. What's the meaning of doCrash (or functionality of crash) ?
  2. What does the function initSolve try to do? Could you please divide the code into several parts and explain the functionality?
  3. What's the functionality of ExtraInfo and SpecialOption? How many special options are there?
  4. In the function dual, I didn't see the two phase of simplex. How does CLP solves the lp problem?

Sorry for my unorganized problems and I'm trying to understand how CLP uses simplex to solve problems. Any recommendation for reading the source code of simplex method?

Thanks a lot!