Scoop Kernel is a C# project which provides some optimization algorithms and some utilities for testing the algorithms.
This section describes the projects in the Scoop Kernel solution.
Scoop Kernel is a library for building optimizers based on iterative improvement algorithms, such as Descent/Hill climbing, Tabu search, Guided local search etc. It gives a framework and helpful utilities, but you'll have to build the specifics by subclassing solutions, constraints, objectives, moves, neighborhoods etc. Here is a short introduction to the most important classes/interfaces:
- Encoding. Represents an optimization problem. Could be called Problem, but the name sticks for historical reasons.
- ISolution/Solution. Represents a solution to the optimization problem/encoding.
- CriteriaSet. A collection of constraints and objectives. Each encoding contains one, but they can be used independently as well.
- IConstraint. Represents a constraint; a rule for whether a solution is feasible or not.
- IObjective. Represents an objective; a function that evaluates the value/cost of a solution.
- AggregateObjective. Combines several objectives as a weighted sum.
- SolutionCache. One belongs to each solution object and stores derived data associated with that solution. This helps minimizing recalculation of data used by constraints and objectives and other interested parties. To use, implement an ICacheClient.
- Move. Represents a particular change that can be made to a particular solution. (E.g. a specific permutation of certain solution elements.)
- Neighborhood. A collection of moves, typically related. (E.g. all possible permutations of a certain set of solution elements.)
- Descent. The simplest optimizer. Checks a sequence of neighborhoods and performs the most improving (by objective value) feasible (according to the constraints) move, if any, in each. Never degrades the solution.
- INeighborhoodSelector. Provides the sequence of neighborhoods to be explored (e.g. by Descent).
- INeighborhoodExplorer. Selects one move from a neighborhood, normally the best feasible one (e.g. for Descent). The simplest is ReverseExplorer. More efficient are DeltaValueExplorer, ParallelDeltaExplorer or StatisticalDeltaValueExplorer.
- StopCriterion. Allows optimizers to be stopped. Analog to CancellationToken.
Other available optimizers are:
- BlackBoardMonitor. Manages a collection of optimizers and operators that work on one or more pools of solutions, possibly in parallel.
- IteratedLocalSearch.
- FocalPointSearch.
- TabuSearch.
- RandomWalk.
In addition there are some optimizers that are not as well tested and documented which are considered experimental:
- ConflictBasedBranchAndBound. A branch-and-bound optimizer that uses a conflict graph to prune the search space.
- FocalPointSearch. A search algorithm that focuses on a subset of the solution space based on previous solutions.
- GuidedLocalSearch.
- RunAway.
- SeededSolutions.
- TwoLevelOptimizer. An optimizer that uses two levels of optimization, typically a local search followed by a global search.
Some useful utilities:
- BestSolutionTracker. Efficiently keeps track of the best solution found by one or more optimizers.
- OptimizerRunner. Allows optimizing for a given time or number of iterations with a oneliner.
- EventHandlerManager. Facilitates listening to events in optimizers and sub-optimizers.
Code that is regarded as experimental may have lower level of documentation and testing. Use at your own risk!
ScoopInstrumentation contains classes not normally used in optimization proper, but that can be useful when debugging and testing optimizers. Examples include:
- CriteriaChecker. Allows you to wrap a criterion to verify that each invocation of DeltaValue and LegalMove produces the correct result.
- CriteriaComparer. Verifies that two criteria always produce the same results.
- ObjectiveValueLogger. Logs the value of one or more objectives in each iteration.
Contains mainly Windows Forms controls used in the test bench.
This is a Windows Forms application for running and analyzing optimizers interactively. It must be configured for a specific problem class by providing plugins. For an example, see ScoopRosteringTestBench.
Contains utilities for testing optimizer components, e.g. for verifying that DeltaValue is implemented correctly.
If you want to contribute to this project check out the guidelines in CONTRIBUTING.md.
This software is distributed under the LGPL 3.0 only license.
The icons used in ScoopInstrumentation.Windows are from Google's Material Symbols and are licensed under Apache License Version 2.0