Revision as of 18:11, 12 May 2006

Summary

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.

Developer(s)

• Kohei Yoshida --- Original author, and current maintainer
• <add your name here>

Change log is here.

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 (currently in RC) 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 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 & make.

Directory Structure

The scsolver module is structured as follows:

• 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

The scsolver module exports the following UNO services and interfaces:

• org.openoffice.sc.solver.XLpAlgorithm - Interface for LP algorithm object. Any third party LP library needs to export this interface for it to be callable from the main Solver framework.
• org.openoffice.sc.solver.XLpModel - Interface for LP model. An object that supports this interface can be passed onto another object of type XLpAlgorithm to compute a solution.

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)

Mixed Integer Linear Programming (MILP)

Non-Linear Programming (NLP)

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 integration strategy here is to export these algorithms provided by lp_solve as UNO services thereby making them visible to the current Calc Solver framework. To implement this, the lp_solve library needs to be modified into its own UNO component and be installed alongside the current core Solver component. This task requires a fair amount of knowledge of C++ UNO component framework and familiarity with the lp_solve API, but both can be learned as necessary.

The downside of this approach is that, as a result of this, the Solver package will no longer be a single component install, but this is necessary because

• you can't put multiple shared libraries into a single package as this will cause package registration to fail, and
• due to lp_solve's license we are not allowed to mix its code with our own which must be submitted under JCA.

Despite these constraints, this approach has been demonstrated to be workable in the past, so it's just a matter of someone doing the actual work! :-)

User Interface (UI)

• Options dialog
• i18n
• User-defined Hessian matrix calculation

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.

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

• np_sol
• cplex
• LINDO API

Links

• Kohei Yoshida's Solver Page
• NEOS Guide
• Learn to program a simple calcAddin in C++
• Learn to program a calc Addin in C++