Optimization Solver

From Apache OpenOffice Wiki
Revision as of 16:25, 17 May 2012 by PauloLima (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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.

Note that this project is now hosted and maintained externally at http://code.google.com/p/scsolver.

Developers

Core Developers

Contributors

  • 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

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

Optimizer Algorithm

Linear Programming

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.

Non-Linear Programming

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.

Hacking Solver

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.
    • 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 source/ui.

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.

Integration

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

TODO List

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.

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

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

Miscellaneous

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

Documentation

Name Description
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?

Tasks

Build Integration

Build an extension package in scsolver module

Completed.

Packaging in scp2 module

Completed.

UNIX packaging in setup_native module

Completed.

ooo-build ooinstall integration

Currently, when scsolver is built as an uno extension package, ooinstall fails. This needs to be resolved.

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
Commercial

Links

Retrieved from "https://wiki.openoffice.org/w/index.php?title=Optimization_Solver&oldid=201179"
Personal tools