NLPSolver

From Apache OpenOffice Wiki
Revision as of 06:11, 16 January 2012 by Bormant (Talk | contribs)

Jump to: navigation, search

Introduction

Optimization

Many scientific and economic problems involve the task of finding a certain optimum to a set of formulas, be it the minimum or the maximum. Additionally there are often also constraints, further restricting the set of possible solutions.

An example would be, to minimize the costs of a company while still meeting the demand of its customers. Such a formula could look like:

where and are the prices of the two products and and are their amounts to be produced. This would be a typical linear optimization problem, since the target variables ( and ) are linear. A nonlinear problem on the other hand could involve much more complicated relations between the variables. An example for this is the Rosenbrock Function:

In practice nonlinear optimization is used for curve fitting (by minimizing an error function) or for more complicated economical relations.

Spreadsheets - Calc

Since optimization problems consist of several variables and many different relations between them, they can be modeled inside a spreadsheet and therefore allow for easy user interaction. It is therefore useful, to have an embedded tool to solve such a model.

In Calc, there is by default a solver for linear problems. To lift this limit, the extension Solver for Nonlinear Programming can be used to add more solvers which are also capable of handling nonlinear problems (as well as linear ones).

When to use?

Since the Solver for Nonlinear Programming can handle both - linear and nonlinear problems - you may ask yourself, why it is still necessary to have the OpenOffice.org Linear Solver then. The answer is easy: performance.

Solving nonlinear problems is a large burden and is still an active field of research in mathematics. There are not many all-round solutions. Often it is necessary to precisely know the problem to be solved and choose the appropriate method as well as their parameters according to that knowledge.

Since the representation of optimization models in a spreadsheet cannot be analyzed that deeply, the solver has to be able to handle a broad spectrum of optimization problems.

Another problem is, that many algorithms tend to get trapped in local extrema. That means that the solution they find, may not be the best overall (global) solution.

One category of algorithms which overcome both problems are Evolutionary Strategies which are slow, in comparison to the deterministic approach by the OpenOffice.org Linear Solver.

Evolutionary Strategies

In nature there is not much analysis but things "just work" through a complex system of behaviors and events. Ant colonies build very short routes over time to transport food into their anthill - just by instinct. Bird swarms stay together and follow a leader in a certain formation. The simple change of the leaders mind, influences the behavior of all the other birds in the swarm. Similarly, a human population is influenced by each others knowledge. People talk, share information and make up their own mind based on what they learned, read and heard so far.

Several people had the idea, to use these principles to solve numerical and combinatorial problems. This is also the approach our Solver for Nonlinear Programming chooses to solve nonlinear optimization problems. The solution is found by annealing the solution towards the (global) optimum, which is achieved by "structured trial and error". Due to the randomization it becomes very likely to find the global optimum instead of getting stuck in a local optimum. Also it doesn't matter (much) how the problem is structured, since the solver will adjust itself automatically by learning.

The biggest downside of this approach is, that it has to evaluate the whole optimization model many times to find the solution, which costs a lot of time and is therefore rather slow.

Solvers

DEPS - Differential Evolution & Particle Swarm Optimization

DEPS consists of two independent algorithms: Differential Evolution and Particle Swarm Optimization. Both are especially suited for numerical problems, such as nonlinear optimization, and are complementary to each other in that they even out their others shortcomings.

The idea behind Particle Swarm Optimization is to represent every solution vector as coordinates in an n-dimensional room. Each individual (particle) traverses through that space and keeps track of its own best point so far. This information as well as the knowledge about the particle with the best current solution influence how it will move in each iteration. Due to that, the particles will always try to build a swarm and float around the best solutions, traversing possible even better solutions on its way.

Differential Evolution on the other hand is a strategy to "recombine" two individuals similar to Genetic Algorithms. Instead of crossing over chromosomes (i.e. mixing up their variables), the knowledge about the target function is used to anneal both points.

In each iteration of the algorithm, each individual chooses one of both strategies and applies them to its current solution vector. The probability, which strategy is chosen, can be modified with the option Agent Switch Rate.

SCO - Social Cognitive Optimization

SCO takes into account the human behavior of learning and sharing informations. Each individual has access to a common library with knowledge shared between all individuals.

In each step, an individual looks up the (presumably) best information available in the library and builds a decision based on it together with its own current knowledge about the problem. Afterwards it replaces one of the worse informations from the library with its newly learned solution.

That way all individuals work together (the social aspect) and make up their own mind (the cognitive aspect). Therefore it's called Social Cognitive Optimization.

Usage

Regardless whether you use DEPS or SCO, you start by going to Tools -> Solver and set the Cell to be optimized, the direction to go (minimization, maximization) and the cells to be modified to reach the goal. Then you go to the Options and specify the solver to be used and if necessary adjust the according parameters.

There is also a list of constraints you can use to restrict the possible range of solutions or to penalize certain conditions. However, in case of the evolutionary solvers DEPS and SCO, these constraints are also used to specify bounds on the variables of the problem. Due to the random nature of the algorithms, it is highly recommended to do so and give upper (and in case "Assume Non-Negative Variables" is turned off also lower) bounds for all variables. They don't have to be near the actual solution (which is probably unknown) but should give a rough indication of the expected size ( or maybe ).

Bounds are specified by selecting one or more variables (as range) on the left side and entering a numerical value (not a cell or a formula) on the right side. That way you can also choose one or more variables to be Integer or Binary only.

Options and Parameters

General Options

Size of Swarm ... defines the number of individuals to participate in the learning process. Each individual finds its own solutions and contributes to the overall knowledge.
Learning Cycles ... defines the number of iterations, the algorithm should take. In each iteration, all individuals make a guess on the best solution and share their knowledge.
Variable Bounds Guessing ... If enabled (default), the algorithm tries to find variable bounds by looking at the starting values.
Variable Bounds Threshold When guessing variable bounds, this threshold specifies, how the initial values are shifted to build the bounds. The calculation is as follows: .

Example:

The is and the is (default). In this case, the lower bound would be and the upper bound .

Use ACR Comparator If disabled (default), the BCH Comparator is used. It compares two individuals by first looking at their constraint violations and only if those are equal, it measures their current solution.

If enabled, the ACR Comparator is used. It compares two individuals dependent on the current iteration and measures their goodness with knowledge about the libraries worst known solutions (in regard to their constraint violations).

Use Random Starting Point If enabled, the library is simply filled up with randomly chosen points.

If disabled, the currently present values (as given by the user) are inserted in the library as reference point.

Stagnation Limit If this number of individuals found solutions within a close range, the iteration is stopped and the best of these values is chosen as optimal.
Stagnation Tolerance Defines in what range solutions are considered "similar".
Show Enhanced Solver Status If enabled, an additional dialog is shown during the solving process which gives information about the current progress, the level of stagnation, the currently best known solution as well as the possibility, to stop or resume the solver.

DEPS-specific Options

Agent Switch Rate Specifies the probability for an individual to choose the Differential Evolution strategy.
DE: Crossover Probability ... defines the probability of the individual being combined with the globally best point. If crossover is not used, the point is assembled from the own memory of the individual.
DE: Scaling Factor During crossover, the scaling factor decides about the "speed" of movement.
PS: Constriction Coefficient ... defines the speed at which the particles/individuals move towards each other.
PS: Cognitive Constant ... sets the importance of the own memory (in particular the best reached point so far).
PS: Social Constant ... sets the importance of the global best point between all particles/individuals.
PS: Mutation Probability ... defines the probability, that instead of moving a component of the particle towards the best point, it randomly chooses a new value from the valid range for that variable.

SCO-specific Options

Size of Library ... defines the amount of information to store in the public library. Each individual stores knowledge there and asks for information.

Scripting

There are a number of reasons why it may be useful to access the solver from within a scripting language (like OpenOffice.org Basic). One of them could be, that you don't want to specify all of the constraints whenever you want to run the solver on a specific problem. In that case you could handle the solver setup from Basic.

Properties and Methods

Apart from the default properties and methods defined by the XSolver interface, DEPS and SCO publish the following properties:

Property Type Meaning
SwarmSize Integer Size of Swarm
LearningCycles Integer Learning Cycles
GuessVariableRange Boolean Variable Range Guessing
VariableRangeThreshold Double Variable Range Threshold
UseACRComparator Boolean Use ACR Comparator
UseRandomStartingPoint Boolean Use Random Starting Point
StagnationLimit Integer Stagnation Limit
Tolerance Double Stagnation Tolerance
EnhancedSolverStatus Boolean Show Enhanced Solver Status
com.sun.star.comp.Calc.NLPSolver.DEPSSolverImpl
AgentSwitchRate Double Agent Switch Rate
DEFactor Double Scaling Factor
DECR Double Crossover Probability
PSC1 Double Cognitive Constant
PSC2 Double Social Constant
PSWeight Double Constriction Coefficient
PSCL Double Mutation Probability
com.sun.star.comp.Calc.NLPSolver.SCOSolverImpl
LibrarySize Integer Size of Library

Example

The following example will iterate over the row 5 to 300 (the internal numbering starts at 0!) from sheet 1 and solve each of them separately by minimizing the objective in the same row.

Sub OptimizeDEPS
  Dim Solver as Object
  Set Solver = CreateUnoService("com.sun.star.comp.Calc.NLPSolver.DEPSSolverImpl")
  Solver.Document = ThisComponent
  Solver.Maximize = false
 
  Dim ObjectiveCell as new com.sun.star.table.CellAddress
  ObjectiveCell.Sheet = 0
  ObjectiveCell.Column = 10
 
  Dim VariableCells(0) as new com.sun.star.table.CellAddress
  VariableCells(0).Sheet = 0
  VariableCells(0).Column = 2
 
  For TargetRow = 4 To 299
    ObjectiveCell.Row = TargetRow
    VariableCells(0).Row = TargetRow
    Solver.Objective = ObjectiveCell
    Solver.Variables = VariableCells
    Solver.solve
  Next
 
  MsgBox "Done."
End Sub

License and Disclaimer

This extension has been developed at Sun Microsystems Inc. and is licensed under the terms of the GNU Lesser General Public License version 3.

Research and implementation of DEPS and SCO have been done by Xiao-Feng Xie of adaptivebox.net. Both were modified and applied to the needs of the OpenOffice.org Solver by Andreas Schneider for Sun Microsystems, Inc.

Personal tools