Optimization Solver
The goal of this project is to develop a Calc addon component that solves a constrained linear or nonlinear programming model for an optimum solution. An optimum solution in this case is defined as a feasible point that either maximizes or minimizes the objective function while satisfying all given constraints.
This component is written in C++, so a good knowledge of C++ and design pattern helps tremendously if you want to hack at it. Of course, at least a basic knowledge of operations research is a prerequisite, but you don't necessarily need to be an expert to get involved.
Contents
 1 Developer(s)
 2 Screenshots
 3 Download and Test
 4 Hacking Solver
 5 Task Breakdown
 5.1 Core Optimization Algorithms
 5.2 Third Party Library Integration
 5.3 User Interface (UI)
 5.3.1 Disable cell updates during execution (Implemented Kohei, 2006620)
 5.3.2 Immediate value as RHS of constraint (implemented Kohei, 20060618)
 5.3.3 Automatic loading/saving of a model
 5.3.4 Storing multiple models in a single document
 5.3.5 Options dialog
 5.3.6 i18n
 5.3.7 Userdefined Hessian matrix calculation
 5.4 Miscellaneous
 5.5 Documentation
 6 Resources
Developer(s)
 Kohei Yoshida  Original author, and current maintainer
Change log is here.
Screenshots
A picture is worth a thousand words. :)
Download and Test
A binary snapshot is available on Kohei Yoshida's website. Right now, the x86 Linux binary is actively maintained for each snapshot release, but Windows binary for the February 2006 snapshot is available thanks to Kami.
Alternatively, you can download and install OpenSUSE 10.1 from the OpenSUSE project website. The edition of OO.o shipped with OpenSUSE 10.1 includes this Solver.
To install, follow these steps (in English build):
 Download the latest solver.uno.zip, but don't unzip it.
 Open Calc, go to Tools  Package Manager.
 Select "My Packages", and click "Add".
 Locate that solver.uno.zip file you have downloaded, and hit OK to load it.
 Once Calc finishes registering the component, close all OO.o windows, and restart Calc. You should then see a floating toolbar with the word "Solver" on it.
Hacking Solver
The easiest way to get started is to download and compile ooobuild from CVS. The Solver code can be found at ooobuild/scratch/scsolver
. Build ooobuild normally as instructed in ooobuild page, and you should have a top level scsolver
module directory at ooobuild/build/[upstream build name]/scsolver
. The upstream build name here refers to the name of a (semi)latest milestone that the build script has downloaded for you when you ran configure & download
.
Directory Structure
The scsolver
module is structured as follows:
 idl  IDL files for exported UNO interfaces.
 docs  some, admittedly very outdated doc files. The class diagram may be somewhat useful.
 prj  contains files that are necessary for OO.o build process.
 source  main source directory
 inc  headers
 numeric  numerical code (including optimization/matrix codes)
 service  UNO interface
 ui  UI code (uses UNO's dialog framework  fairly rudimentary)
 util  ?
 workben  contains files that are not part of the build process i.e. test files, files for building a separate binary UNO package etc.
The backend numerical codes are all found in source/numeric
, whereas all the UI related codes are found in source/ui
.
Exported UNO Interface
There are currently no UNO interfaces exported by this feature.
Task Breakdown
Core Optimization Algorithms
Listed below are algorithms proposed to be included in future versions of Calc Solver. Some are being actively developed, while the others are still in planning.
Linear Programming (LP)
With the exception of the Interior Point, much of linear programming will be delegated to the Simplexbased lp_solve
.
Algorithm  Developer  Status  Date Finished 

Revised Simplex Method  Kohei Yoshida  finished  20060316 
Bounded Revised Simplex Method  Kohei Yoshida  in progress  
Interior Point Method  proposed 
Mixed Integer Linear Programming (MILP)
Algorithm  Developer  Status  Date Finished 

Branch and Bound  lp_solve


Branch and Cut  lp_solve (?)

NonLinear Programming (NLP)
Algorithm  Developer  Status  Date Finished 

QuasiNewton Method with BFGS Update  Kohei Yoshida  in progress  
Adaptive Penalty Method  in consideration  
Generalized Reduced Gradient (GRG) Method  Leandro Silveira Monteiro da Silva  proposed  
Penalty Method  proposed  
Barrier Method  proposed  
Genetic Algorithm  planned 
Mixed Integer NonLinear Programming (MINLP)
 ?
Third Party Library Integration
lp_solve
In a nutshell, lp_solve is a Mixed Integer Linear Programming (MILP) solver supervised by Kjell Eikland and Peter Notebaert. It is released under GPL/LGPL. It provides the revised simplex method and the BranchandBound method for solving pure LP and MILP. The lp_solve project provides excellent documentation for v5.1  stable branch and v5.5  latest branch. The package can be downloaded from here.
There are two possible integration strategies. In the first strategy, the algorithms provided by lp_solve is exported as UNO services in order to provide access for the current Calc Solver framework. To make this happen, the lp_solve library needs to be modified into its own UNO component and be installed alongside the current core Solver component. Since lp_solve itself is an external library i.e. a code that will not be submitted under JCA, the modification made to lp_solve will also be treated as external code licensed under LGPL. In the second strategy, Solver is simply dynamically linked to the lp_solve library, thus avoiding the overhead of UNO.
On the main Solver component side, a new class will be created as a derived class of numeric::opres::lp::BaseAlgorithm
, and this new class will convert the model's properties passed from the Solver dialog into a format that can be digested by lp_solve. Once lp_solve reaches a solution, or decides that no solution exists, that result will be pushed back to the Solver component so that Solver can send the solution back to Calc, or displays an appropriate error message indicating no solution is found.
User Interface (UI)
Disable cell updates during execution (Implemented Kohei, 2006620)
During Solver's execution, it modifies the values of those cells that are associated with a model so that the model defined as a set of formulas and numbers inside spreadsheet cells can be converted into the standard format of LP model. It would be nice to disable cell updates during the solutionfinding phase to prevent slowdown of the process.
The implementation of this feature was fairly simple: just calling the (un)lockControllers()
method exported by the XModel
interface of the SpreadsheetDocument
object enables or disables cell updates. Thanks to Niklas Nebel for giving me the tip.
Immediate value as RHS of constraint (implemented Kohei, 20060618)
It is probably a standard behavior to allow a direct input of a value (i.e. 12.5
) on the right hand side (RHS) of a constraint, instead of always requiring it to be a cell reference (i.e. =$Sheet1.$A$5
). To implement this, an additional check needs to be put in place to see if a given input string is a valid 3D cell reference (sheet  column  row). If the check fails, then we can try to convert the string into a doubleprecision and use it as the RHS value. If even that conversion fails, then alert the user with an appropriate error message.
The initial implementation of this feature is already in CVS.
Automatic loading/saving of a model
Currently, loading and saving of a model to its associated document is done by storing the model information as a metadata of the document. It may be useful to automate some of loading and saving of the model.
Storing multiple models in a single document
Users often want to save multiple models into a single document, whereas currently one model can be saved per document. It would be nice to add the capability of adding multiple models. One way to implement this is to save the model data into a region of cells, which would allow storing as many models as the cells can hold in a single file. It would also be nice to support saving and loading Excel Solver's model format to allow migration from Excel Solver.
Alternatively, we could also have multiple metadata entries with a nice frontend dialog to implement multiple model storage. Which approach should be taken is subject to discussion.
Options dialog
We need to create an options dialog to let user configure runtime behavior of the solver. At a minimum, the following options need to be present:
 algorithm type (LP, MILP, QP, NLP, ...)
 integer constraint
 positive variable constraint
The options dialog should also have sensible default values since most users just want to run the solver, get the answer and move on.
i18n
At a minimum, string l10n mechanism needs to be in place. Work is in progress with Michael Meeks' help.
Userdefined Hessian matrix calculation
There are 3rd party highperformance Hessian matrix calculation program out there. It would be nice to add a hook for such 3rd party software, so that the user can use it to speed up iteration.
Miscellaneous
Automatic Algorithm Selection
We may need an optional mechanism to select appropriate optimization algorithms (LP vs QP, linear vs nonlinear) based on the characteristics of a given model. But such machanism should be optional so that the user can still pick and choose desired algorithms.
Decoupling of Algorithms and UI
Eventually, the UI for Solver needs to be drawn by VCL to take advantage of VCL's better widget controls over those of UNO's. To achieve this goal, the backend algorithm framework needs to be exported as a UNO service independently of the UI.
On the other hand, there is also a move to improve UNO AWT framework to support more widgets, and add i18n framework. It may make sense to just extend our current UI, which is drawn by UNO AWT in order for us to reuse the work that has already been done.
Documentation
 General user's guide.
 Howto docs for adding a new algorithm with perhaps a skeleton code.
Resources
Third Party Library
Use of a third party library is encouraged, as long as there is no licensing conflict with OpenOffice.org. We cannot integrate GPL'ed code due to licensing incompatibility. LGPLlicensed library can be used, as long as such library is decoupled and completely isolated from the core component code. BSDlicensed code can be used in a similar fashion, but due to its advertizing clause it cannot be used within the core component that needs to become a part of OO.o (Sun's requirement?). So, both LGPL and BSD codes must be completely decoupled from the core Solver code.
TODO: How about CPL? Does it pose any constraint as far as integration goes? Kohei 06:16, 25 April 2006 (CEST)
If you know of any other third party libraries not listed here, feel free to add it below.
 Free Software
 GLPK (GPL)
 lp_solve (GPL/LGPL)
 COINOR (CPL)
 SciPy  Scientific Tools for Python released under BSD license. Currently for Python only (?)
 Commercial
Links
 Kohei Yoshida's Solver Page
 NEOS Guide
 XL2000: Solver Uses Generalized Reduced Gradient Algorithm
 Learn to program a simple calc Addin in C++
 Learn to program a calc Addin in C++