The goal of this project is to develop a Calc add-on component that solves a constrained linear or non-linear 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.
- 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, 2006-6-20)
- 5.3.2 Immediate value as RHS of constraint (implemented --Kohei, 2006-06-18)
- 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 User-defined Hessian matrix calculation
- 5.4 Miscellaneous
- 5.5 Documentation
- 6 Resources
- Kohei Yoshida --- Original author, and current maintainer
Change log is here.
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.
The easiest way to get started is to download and compile ooo-build from CVS. The Solver code can be found at
ooo-build/scratch/scsolver. Build ooo-build normally as instructed in ooo-build page, and you should have a top level
scsolver module directory at
ooo-build/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.
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
Exported UNO Interface
There are currently no UNO interfaces exported by this feature.
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 Simplex-based
|Revised Simplex Method||Kohei Yoshida||finished||2006-03-16|
|Bounded Revised Simplex Method||Kohei Yoshida||in progress|
|Interior Point Method||proposed|
Mixed Integer Linear Programming (MILP)
|Branch and Bound||
|Branch and Cut||
Non-Linear Programming (NLP)
|Quasi-Newton Method with BFGS Update||Kohei Yoshida||in progress|
|Adaptive Penalty Method||in consideration|
|Generalized Reduced Gradient (GRG) Method||Leandro Silveira Monteiro da Silva||proposed|
Mixed Integer Non-Linear Programming (MINLP)
Third Party Library Integration
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 Branch-and-Bound 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, 2006-6-20)
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 solution-finding 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, 2006-06-18)
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 double-precision 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 front-end dialog to implement multiple model storage. Which approach should be taken is subject to discussion.
We need to create an options dialog to let user configure run-time 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.
At a minimum, string l10n mechanism needs to be in place. Work is in progress with Michael Meeks' help.
User-defined Hessian matrix calculation
There are 3rd party high-performance 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.
Automatic Algorithm Selection
We may need an optional mechanism to select appropriate optimization algorithms (LP vs QP, linear vs non-linear) 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 back-end 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.
- General user's guide.
- How-to docs for adding a new algorithm with perhaps a skeleton code.
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. LGPL-licensed library can be used, as long as such library is de-coupled and completely isolated from the core component code. BSD-licensed 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)
- COIN-OR (CPL)
- SciPy - Scientific Tools for Python released under BSD license. Currently for Python only (?)
- 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++