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.
Note that this project is now hosted and maintained externally at http://code.google.com/p/scsolver.
- Kohei Yoshida --- Lead developer
- Michael Meeks --- initial integration and general design advice
- Jody Goldberg --- general advice on optimizer development and overall design
- Tor Lillqvist --- win32 build fixes
- Rene Engelhard --- Debian build fixes
- Laurent Godard --- French translation & UNO API help
- Kazunari Hirano --- Japanese translation
- Konstantin Lavrov --- Russian translation & menu integration
- Rolf Meyer --- German translation
Menu item location
This is a screen shot of the main dialog after it gets launched for the first time. All input fields are empty.
Some general behaviors of this dialog are as follows:
- By default, the focus is on the text input field on the immediate right of the Set target cell label.
- Under Subject to the constraints, the Change and Delete buttons are disabled unless there is a highlighted item in the list box on their left.
- Dismissing the dialog by clicking Close will not clear user input.
|Target||text input||This field takes the address of the cell whose value is to be optimized.|
|Goal||radio button||This radio button defines whether the target cell value is to be maximized or minimized.|
|Variable cell||text input||This field takes the range address of cells that whose values will change during optimization run.|
|Constraint box||list box||This list box maintains a list of currently defined constraints.|
|Add||button||Add a new constraint to the list of constraints.|
|Change||button||Modify the highlighted constraint definition.|
|Delete||button||Delete the highlighted constraint definition.|
|Solve||button||Optimize the current model.|
|Reset||button||Reset all input values. This essentially removes all input values.|
|Options||button||Launch a separate Options dialog.|
|Save||button||Save the current input values to document's metadata section. Note that clicking this button only puts the data into the document model on memory. The user still need to save the file after clicking this button to permanently save the data to disk.|
|Load||button||Load input values from document's metadata section.|
|Close||button||Close this dialog.|
|Cell Reference||text input||This field takes the address of the cell that represents the left-hand-side (LHS) of a constraint equation. The value of this field must be a valid cell reference.|
|Equality||combo box||Defines the relationship between the left hand side (LHS) and the right hand side (RHS) terms.|
|Constraint||text input||The right-hand-side (RHS) value of the constraint equation. This can be a cell reference or a numeric value.|
|Assume linear model||check box||When this box is checked, the Solver uses a linear algorithm to solve the current model. When this box is not checked, it uses a non-linear algorithm.|
|Allow only positive values||check box||When this box is checked, the Solver tries to find a solution while all variables are positive.|
|Allow only integer values||check box||When this box is checked, the Solver tries to find a solution with all variables being integers. Fractional values are not allowed.|
lp_solve - a Mixed Integer Linear Programming (MILP) solver supervised by Kjell Eikland and Peter Notebaert - is used as the linear optimizer. lp_solve 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 latest package can be downloaded from here.
Currently a draft implementation of Quasi-Newton with BFGS update is included to optimize unconstrained non-linear models. But this algorithm is still not very robust and needs massive improvement.
A somewhat easier way to get started is to download and compile ooo-build from gnome.org Subversion repository. To check out ooo-build, run
svn co svn://svn.gnome.org/svn/ooo-build/trunk ooo-build
The Solver code is found in
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:
- 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)
- tool - utility code used throughout the module.
- util - ?
- workben - contains files that are not part of the build process.
- nlp_skel - set of skeleton files for independent non-linear optimizer development.
- addon_pkg - contains files necessary to build a stand-alone Solver as a UNO package.
The backend numerical codes are all found in
source/numeric, whereas all the UI related codes are found in
Optimizer Development mini-Framework
How to set up
There is now a way to develop a new optimization algorithm without even touching the main code base! This is ideal for someone who just wants to contribute an optimizer code, but doesn't necessarily have time or desire to build the whole OO.o or even to understand the entire scsolver module. Currently this mini-framework support only NLP algorithm development, but in future support for LP algorithm may be added if there is demand.
An example set of source files is in scsolver/workben/optimizer/nlp_skel. Make a copy of the whole directory as a sibling to the original directory, change into it and compile by typing make. This will compile a binary executable named skel.
Those who are familiar with the Makefile format can read the provided Makefile to see how the example binary is built. Here is the gist of how to build a test optimizer program with your own optimizer code:
- Set the header include path to scsolver/source/inc.
- Compile the following files from the main source tree:
- scsolver/source/numeric/funcobj.cxx (includes class BaseFuncObj - the abstract base class for function object)
- scsolver/source/numeric/nlpbase.cxx (includes class BaseAlgorithm - the abstract base class for NLP optimizer)
- scsolver/source/numeric/nlpmodel.cxx (includes class Model - the NLP model class)
- scsolver/source/numeric/exception.cxx (exception classes that the optimizer can throw during optimization run).
- scsolver/source/tool/global.cxx (some global functions that are used in the above files).
- Provide the following:
- NLP optimizer class derived from BaseAlgorithm.
- A function object class derived from BaseFuncObj. This will represent an objective function to optimize.
- The main function.
You then need to link the object files you compiled from the main source tree with the one(s) you compiled from your own code.
Testing of your algorithm against a variety of objective functions can be done by creating multiple function objects and plugging them to the model instance one at a time for optimization run. Refer to the files in the nlp_skel directory for basic execution flow and how to use the optimizer API.
Once the algorithm beomes good enough to be integrated, .... [to be continued]
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.
|Quasi-Newton Method with BFGS Update||NLP||Kohei Yoshida||Handles only unconstrained non-linear models.|
|Generalized Reduced Gradient (GRG) Method||NLP||Leandro Silveira Monteiro da Silva||Excel Solver's default algorithm.|
|Hooke & Jeeves Method [documentation]||NLP||Jorma Kuha||non-linear models with upper and lower boundary constraint for each variable.|
|Levenberg-Marquardt algorithm||NLP||popular in solving curve-fitting equation but may be applicable for general non-linear models. Suggested by Laurent Godard.|
User Interface (UI) Tasks
|Solve for a specified value||Add an additional constraint to emulate solving for a specified value.|
|Progress window||A separate window with a button to let user abort optimization when the optimization routine is on-going. Such window should also have a progress bar and a text message area. The window will disappears once the Solver finds a solution, or fails to find a solution.|
|Restore original values||Provide an option to restore original values when the user aborts the optimization run or the optimizer fails to find a solution.|
|Arithmetics on cell (range) address in constraint dialog||Extend the constraint parser to support input such as A2:A4 + B2:B4 > 4. If the sheet name is missing, assume the current active sheet.|
|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.
|Options dialog|| 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:
The options dialog should also have sensible default values since most users just want to run the solver, get the answer and move on.
|Algorithm specific options||Each algorithm requires a different set of parameters to control their run-time behavior. We need to have a good UI to allow algorithm-specific settings. The internal data structure to hold the algorithm options must be designed such that it allows variable number of parameters with names that are specific to each optimizer algorithm.|
|String l10n||Framework is now in place, and the strings are translated for French and Japanese. Extend the list of translated languages.|
|Redesign constraint dialog||The current constraint dialog, being separate from the main dialog, causes a focus related problem on Linux platform after returning from range selection mode. We should probably embed that UI functionality onto the main dialog to avoid focus problem.|
|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.|
|Options page in OO.o's Options dialog||Joachim Lingner presented on the possibility of an extension to use OO.o's Options dialog to store extension specific options. Find a way to take advantage of that framework.|
|Remove boost ublas dependency||The use of boost ublas in the matrix class is causing difficulty porting to other platforms, especially on Solaris. We need to remove dependency on ublas or make it optional.|
|Use UNO component version for internal build||Currently, we maintain two versions of Solver, one for the internal version integrated into ooo-build, and one for external UNO component as an extension to the upstream version. We need to unify these two separate versions by having ooo-build also use the UNO component version to ease maintenance. This page (Extensions Integration into Installation Set) explains how that can be done.|
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 mechanism should be optional so that the user can still pick and choose desired algorithms.
|User's guide||We need a user's guide. We don't even have one. :-(|
|How-to docs on hacking||Do we really need this?|
Build an extension package in scsolver module
Packaging in scp2 module
UNIX packaging in setup_native module
ooo-build ooinstall integration
Currently, when scsolver is built as an uno extension package,
ooinstall fails. This needs to be resolved.
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 (?)
- CVXOPT - Convex optimization written in Python.
- Non-Linear FitLM
- another list of free and non-free optimisation solvers from the ASCEND project
- Design and Use of the Microsoft Solver
- All checkins to the CVS repository in the last week
- Kohei Yoshida's Solver Page
- Jorma Kuha's Direct Optimizer Page
- NEOS Guide
- XL2000: Solver Uses Generalized Reduced Gradient Algorithm
- Automatically Tuned Linear Algebra Software (ATLAS)
- Learn to program a simple calc Addin in C++
- Learn to program a calc Addin in C++
- overview: local optimizers and global optimizers