Difference between revisions of "Optimization Solver"
(→Third Party Library) |
(added summary) |
||
Line 1: | Line 1: | ||
+ | =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)= | =Developer(s)= | ||
* [[User:Kohei|Kohei Yoshida]] --- Original author and current maintainer | * [[User:Kohei|Kohei Yoshida]] --- Original author and current maintainer | ||
Line 24: | Line 29: | ||
=== Linear Programming (LP) === | === Linear Programming (LP) === | ||
{| border="1" cellspacing="0" cellpadding="5" width="100%" | {| border="1" cellspacing="0" cellpadding="5" width="100%" | ||
− | !Algorithm | + | !width="40%"|Algorithm |
− | !Developer | + | !width="30%"|Developer |
− | !Status | + | !width="15%"|Status |
− | !Date Finished | + | !width="15%"|Date Finished |
|- | |- | ||
|Revised Simplex Method | |Revised Simplex Method | ||
Line 48: | Line 53: | ||
=== Mixed Integer Linear Programming (MILP) === | === Mixed Integer Linear Programming (MILP) === | ||
{| border="1" cellspacing="0" cellpadding="5" width="100%" | {| border="1" cellspacing="0" cellpadding="5" width="100%" | ||
− | !Algorithm | + | !width="40%"|Algorithm |
− | !Developer | + | !width="30%"|Developer |
− | !Status | + | !width="15%"|Status |
− | !Date Finished | + | !width="15%"|Date Finished |
|- | |- | ||
|Branch and Bound | |Branch and Bound | ||
Line 67: | Line 72: | ||
=== Non-Linear Programming (NLP) === | === Non-Linear Programming (NLP) === | ||
{| border="1" cellspacing="0" cellpadding="5" width="100%" | {| border="1" cellspacing="0" cellpadding="5" width="100%" | ||
− | !Algorithm | + | !width="40%"|Algorithm |
− | !Developer | + | !width="30%"|Developer |
− | !Status | + | !width="15%"|Status |
− | !Date Finished | + | !width="15%"|Date Finished |
|- | |- | ||
|Quasi-Newton Method with BFGS Update | |Quasi-Newton Method with BFGS Update |
Revision as of 06:57, 22 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.
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 | Date Finished |
---|---|---|---|
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)
- ?
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
- Commercial
- np_sol
- cplex