Revision as of 02:48, 25 April 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.

Developer(s)

Kohei Yoshida --- Original author and current maintainer

Change log is here.

Download and Test

Interested in testing it? I usually post the binary on my website. Right now, I only maintain x86 Linux binary 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 Beta) 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

TODO: Add content here.

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)

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		planned
Branch and Cut		planned

Non-Linear Programming (NLP)

Algorithm	Developer	Status
Quasi-Newton Method with BFGS Update	Kohei Yoshida	in progress
Penalty Method		proposed
Barrier Method		proposed
Genetic Algorithm		planned

Mixed Integer Non-Linear Programming (MINLP)

?

Third Party Library Integration

lp_solve

In an nutshell, lp_solve is a Mixed Integer Linear Programming (MILP) solver supervised by 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. lp_solve provides excellent documentation for v5.1 and v5.5.

The strategy for integration here is to export these algorithms provided by lp_solve as UNO services thereby making them visible to the current Calc Solver framework. To achieve this, the lp_solve library needs to be modified into its own UNO component and be installed alongside the current core Solver component. The downside of this approach is that, as a result of this, the Solver package is no longer 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.

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.

Resources

Third Party Library

Integrating a third party library is considered, but we need to keep it in mind that we cannot use GPL'ed code due to licensing incompatibility. LGPL-licensed library can be used, as long as such library is sufficently de-coupled from the core component code.

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)

Commercial

np_sol
cplex

Links

@@ Line 104: / Line 104: @@
 === Mixed Integer Non-Linear Programming (MINLP) ===
 * ?
+== Third Party Library Integration ==
+=== lp_solve ===
+In an nutshell, [http://lpsolve.sourceforge.net/ lp_solve] is a Mixed Integer Linear Programming (MILP) solver supervised by 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.  lp_solve provides excellent documentation for [http://lpsolve.sourceforge.net/5.1/ v5.1] and [http://lpsolve.sourceforge.net/5.5/ v5.5].
+The strategy for integration here is to export these algorithms provided by lp_solve as UNO services thereby making them visible to the current Calc Solver framework.  To achieve this, the lp_solve library needs to be modified into its own UNO component and be installed alongside the current core Solver component.  The downside of this approach is that, as a result of this, the Solver package is no longer 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]].
+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)==

Difference between revisions of "Optimization Solver"