Optimization

AbstractOptimizer

Abstract base type for optimizer implementations.

fixpoint_reached(optimizer::AbstractOptimizer, graph::DAG)

Interface function that can be implemented by optimization algorithms that can reach a fixpoint, returning as a Bool whether it has been reached. The default implementation returns false.

See also: optimize_to_fixpoint!

optimize!(optimizer::AbstractOptimizer, graph::DAG, n::Int)

Function calling the given optimizer n times, muting the graph. Returns true if the requested number of operations has been applied, false if not, usually when a fixpoint of the algorithm has been reached.

If a more efficient method exists, this can be overloaded for a specific optimizer.

optimize_step!(optimizer::AbstractOptimizer, graph::DAG)

Interface function that must be implemented by implementations of AbstractOptimizer. Returns true if an operations has been applied, false if not, usually when a fixpoint of the algorithm has been reached.

It should do one smallest logical step on the given DAG, muting the graph and, if necessary, the optimizer's state.

optimize_to_fixpoint!(optimizer::AbstractOptimizer, graph::DAG)

Interface function that can be implemented by optimization algorithms that can reach a fixpoint. The algorithm will be run until that fixpoint is reached, at which point fixpoint_reached should return true.

A usual implementation might look like this:

    function optimize_to_fixpoint!(optimizer::MyOptimizer, graph::DAG)
        while !fixpoint_reached(optimizer, graph)
            optimize_step!(optimizer, graph)
        end
        return nothing
    end

RandomWalkOptimizer

An optimizer that randomly pushes or pops operations. It doesn't optimize in any direction and is useful mainly for testing purposes.

This algorithm never reaches a fixpoint, so it does not implement optimize_to_fixpoint!.

ReductionOptimizer

An optimizer that simply applies an available NodeReduction on each step. It implements optimize_to_fixpoint!. The fixpoint is reached when there are no more possible NodeReductions in the graph.

See also: SplitOptimizer

SplitOptimizer

An optimizer that simply applies an available NodeSplit on each step. It implements optimize_to_fixpoint!. The fixpoint is reached when there are no more possible NodeSplits in the graph.

See also: ReductionOptimizer

GreedyOptimizer

An implementation of the greedy optimization algorithm, simply choosing the best next option evaluated with the given estimator.

The fixpoint is reached when any leftover operation would increase the graph's total cost according to the given estimator.