Optimization Solver

From Apache OpenOffice Wiki
Revision as of 23:06, 8 April 2007 by Kohei (Talk | contribs)

Jump to: navigation, search

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.

Developers

Core Developers

Contributors

  • Michael Meeks --- initial integration and general design advice
  • Tor Lillqvist --- win32 build fixes
  • Rene Engelhard --- Debian build fixes

User Interface

Menu item location

Proposed new menu entry location (highlighted) for the solver dialog after integration.

Main Dialog

This is a screen shot of the main dialog after it gets launched for the first time. All input fields are empty.

Main dialog

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.

Widget Table

Name Type Description
Target cell 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.

Constraint Dialog

Constraint input dialog

Widget Table

Name Type Description
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.

Options dialog

Options dialog

Widget Table

Name Type Description
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.
OK button OK button.
Cancel button Cancel button.

Hacking Solver

scsolver02 CWS

The best way to hack the Solver code is to check out the scsolver02 CWS, where the latest code is found. All of Solver source code lives in the scsolver module. Be sure to pass --enable-scsolver to the configure script when building with Solver enabled.

Setting up a CWS build can be tricky, so if you just want to download the Solver code, just do

 cvs -r cws_src680_scsolver02 scsolver

ooo-build

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 [bash,N] 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.

Directory Structure

The 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.
    • optimizer
      • nlp_skel - set of skeleton files for independent non-linear optimizer development.

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.

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.

Since all you need to do to use this mini-framework is to download just the scsolver module, get the module simply by running:

[bash,N] export CVSROOT=:pserver:anoncvs@anoncvs.services.openoffice.org:/cvs cvs co -r cws_src680_scsolver02 scsolver This will check out the scsolver module from scsolver02 CWS.

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.

Integration

Once the algorithm beomes good enough to be integrated, .... [to be continued]

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 Simplex-based lp_solve.

Algorithm Developer Status Date Finished
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)

Algorithm Developer Status Date Finished
Branch and Bound lp_solve
Branch and Cut lp_solve (?)

Non-Linear Programming (NLP)

Algorithm Developer Status Date Finished
Quasi-Newton Method with BFGS Update Kohei Yoshida in progress
Hooke & Jeeves Method [documentation] Jorma Kuha in review
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 Non-Linear 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 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.

It is already integrated into its own module called lpsolve. The glue code is found in source/numeric/lpsolve.cxx and source/inc/numeric/lpsolve.hxx.

User Interface (UI) Tasks

Name Description
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
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:
  • 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.

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.
i18n 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.

Miscellaneous

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.

Documentation

  • General user's guide.
  • How-to 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. 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 (?)
Commercial

Links

Personal tools