Issue 118160

Summary: Replace lp_solve for Calc's linear solver
Product: Calc Reporter: niklas.nebel
Component: codeAssignee: Andre <awf.aoo>
Status: CLOSED FIXED QA Contact: issues@sc <issues>
Severity: Critical    
Priority: P2 CC: awf.aoo, binbjguo, doudou1976, issues, pfg, polo8495, rb.henschel
Version: OOO340m0Flags: doudou1976: 3.4_release_blocker?
Target Milestone: ---   
Hardware: All   
OS: All   
Issue Type: PATCH Latest Confirmation in: ---
Developer Difficulty: ---
Attachments:
Description Flags
proof-of-concept patch none

Description niklas.nebel 2011-06-11 15:30:42 UTC
Created attachment 76606 [details]
proof-of-concept patch

The attached patch changes sccomp/source/solver.cxx to use CoinMP (https://projects.coin-or.org/CoinMP) instead of lp_solve. The options "Epsilon level" and "Limit branch-and-bound depth" are currently ignored. They still have to be mapped to suitable settings, or removed from solver.cxx.
Comment 1 Regina Henschel 2011-06-11 15:41:02 UTC
Can you please point me to the license of CoinMP?
Comment 2 niklas.nebel 2011-06-11 15:52:43 UTC
It's CPL: https://projects.coin-or.org/svn/CoinMP/trunk/CoinMP/LICENSE, and it includes EPL code from other coin-or projects. Whatever that makes for the combination.
Comment 3 Pedro Giffuni 2011-10-30 03:21:04 UTC
According to the OOOWiki, Andre appears to be working on this so I reassigned the issue to him. The current status is this:

-IBM has some ownership over the COIN-OR code so Rob is trying to see if we can get some improvement on the license. This will probably take some time still.

- I was asked by a COIN-OR guy in private about the chosen library: "It is just a wrapper around OSI and does have a couple of bugs in it too."

So we should probably check OSI, which is a general interface for many solvers.
http://www.coin-or.org/projects/Osi.xml

BTW, the author of the proof of concept mentioned:

"In addition to Clp, the Cbc project is needed for the integer 
constraints that the existing, lp_solve-based component supports."
Comment 4 Andre 2011-11-03 12:57:42 UTC
The main problem with CoinMP as well as OSI is the missing documentation. Without it I can not do much more than to apply the patch and run some tests.

So, any information about the whereabouts of documentation is very welcome.

Regarding the Cbc library: the patch already uses integer constraints for variables. Am I missing something?
Comment 5 Pedro Giffuni 2011-11-03 13:41:29 UTC
Unfortunately the few OSI documentation is in the code itself (doxygen).

This slides give a minimal introduction:
http://www.coin-or.org/Presentations/CORSINFORMSWorkshop04/coin-osi.pdf

Concerning the OR math, mixed integer programming can be done with some
tricks by traditional LP methods (Branch and Price?), but I think the CBC code
uses more advanced methods.

If CLP handles basic MIP we could do with that for now. I understand the OSI
interface lets you choose several solvers, some free, some commercial.
Comment 6 Andre 2011-11-03 14:06:11 UTC
Thanks for the link. Maybe that is enough to understand the underlying principles of OSI.

Regarding integer constraints: CoinMP already contains Cbc and, as far as I understand it, uses it automatically when necessary and possible.  In OSI you probably have to make this decision explicitly.
Comment 7 Pedro Giffuni 2011-11-03 14:57:31 UTC
(In reply to comment #6)
> Thanks for the link. Maybe that is enough to understand the underlying
> principles of OSI.
> 
> Regarding integer constraints: CoinMP already contains Cbc and, as far as I
> understand it, uses it automatically when necessary and possible.  In OSI you
> probably have to make this decision explicitly.

Everything has it's pros and it's cons: CoinMP is easier to use but OSI is more flexible. Professional users may want to specify using other solvers (the commercial PLEX code is said to be the top of the line nowadays), and there's also GLPK (LGPL'd).

On FreeBSD we have packages for both CLP (using BLAS/LAPACK) and CoinMP (much less optimized).

Also be aware that the CLP and CBC used in coinMP are very updated. My suggestion is to try CLP (OSI is included) and if afterwards you still want to go CoinMP I will respect that, of course.
Comment 8 Pedro Giffuni 2011-11-03 18:07:11 UTC
Here is another OSI document:

http://dimacs.rutgers.edu/Workshops/COIN/slides/saltzman.pdf

and the doxygen documentation:

http://www.coin-or.org/Doxygen/Osi/annotated.html
Comment 9 Andre 2012-01-20 13:55:12 UTC
Checked in the changes in two parts.

The patch at SVN revision 1233908.  

The second part is about adding CoinMP into the build system.  Checked in at revision 1233909.  CoinMP can be found at ext_libraries/coinmp.  It is used in main/sccomp.
Comment 10 Andre 2012-01-20 15:49:26 UTC
Added the missing CoinMP tar ball.  SVN revision is 1233971.
Comment 11 Andre 2012-01-23 13:49:52 UTC
Using the original tarball from the CoinMP web site.  The old one had the .svn directories included.

SVN revision is 1234787
Comment 12 Pedro Giffuni 2012-02-02 22:45:43 UTC
It would be good to have --with-system-coinmp
as with other modules.
Comment 13 zhao xia 2012-02-13 13:44:47 UTC
Verified against rev. 1236487,Solver function works in svn rev.
Comment 14 Andre 2012-02-13 14:02:46 UTC
Resolved.
Comment 15 Andre 2012-06-12 12:36:21 UTC
This is just for book keeping: I am using a different email address now.
Comment 16 Terry Yang 2012-06-18 09:43:05 UTC
verified on rev.1350879,  Solve work fine now
Comment 17 binguo 2012-11-14 02:19:51 UTC
Verified on Aoo_Trunk_20121109.1800 rev 1407366, pass
Comment 18 binguo 2012-11-14 02:23:38 UTC
close it.