jmejia8 / bilevelheuristics.jl

Metaheuristics for solving bilevel optimization problems.

BilevelHeuristics.jl

This package implements different heuristic and metaheuristic algorithms for Bilevel Optimization (BO).

BilevelHeuristics.jl is still in early development so please send feedback or open issues.

Installation

Open the Julia REPL (Julia 1.6 or later) and press ] to open the Pkg prompt. To add this package, use the add command:

Type ]

pkg> add BilevelHeuristics

Or, equivalently, via the Pkg API:

julia> import Pkg; Pkg.add("BilevelHeuristics")

Algorithms

Current implemented Bilevel Metaheuristics include:

• BCA: Bilevel Centers Algorithm
• QBCA: BCA with a lower-level Quasi-Newton optimization method.
• QBCA2: Improved QBCA (implements conditions to avoid pseudo-feasible solutions)
• SABO: Surrogate-assisted Bilevel Optimization.
• SMS-MOBO: S-metic-selection-based Multi-objective Bilevel Optimization.
• BLEMO: Bilevel Evolutionary Multi-objective Optimization

Example

The following example illustrates the usage of BilevelHeuristics.jl. Here, BCA is used, but this example works for the other optimizers.

Defining objective functions corresponding to the BO problem.

Upper level (leader problem):

using BilevelHeuristics

F(x, y) = sum(x.^2) + sum(y.^2)
bounds_ul = [-ones(5) ones(5)] 

Lower level (follower problem):

f(x, y) = sum((x - y).^2) + y[1]^2
bounds_ll = [-ones(5) ones(5)];

Approximate solution:

res = optimize(F, f, bounds_ul, bounds_ll, BCA())

Output:

+=========== RESULT ==========+
  iteration: 108
    minimum: 
          F: 4.03387e-10
          f: 2.94824e-10
  minimizer: 
          x: [-1.1460768817533927e-5, 7.231706879604178e-6, 3.818596951258517e-6, 2.294324313691869e-6, 1.8770952450067828e-6]
          y: [1.998748659975197e-6, 9.479307908087866e-6, 6.180041276047425e-6, -7.642051857319683e-6, 2.434166021682429e-6]
    F calls: 2503
    f calls: 5062617
    Message: Stopped due UL function evaluations limitations. 
 total time: 26.8142 s
+============================+

x, y = minimizer(res) # upper (x) and lower (y) level decision vectors
Fmin, fmin = minimum(res) # upper and lower objective values.

TO DO

• Parallelize the lower-level optimization procedures.

bilevelheuristics.jl's Issues

Validate using `resize_population`

BilevelHeuristics.jl/src/algorithms/BCA/BCA.jl

Line 193 in cb0d8e7

parameters.N = round(Int, parameters.K*(D - (D-2)*p))

TagBot trigger issue

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

If you'd like for me to do this for you, comment TagBot fix on this issue.
I'll open a PR within a few hours, please be patient!

Error in Nesded heuristic (env. selection)

BilevelHeuristics.jl/src/algorithms/Heuristic/multi_objective.jl

Line 61 in 4cc2eea

delete_mask = ones(Bool, length(status.population))

It should be:

    for (j, sol) in enumerate(get_ul_population(status.population))
        i = findfirst( s -> s==sol, population_ul)
        isnothing(i) && continue
        delete_mask[j] = false
    end

Implement more features

Implement SMS-MOBO and update documentation considering constrained problems.

Update seed

BilevelHeuristics.jl/src/algorithms/BCA/lower-level.jl

Line 20 in cb0d8e7

opts_ll = options.ll

BLEMO

If there is an example for bilevel multi-objective problem with constrained conditon using BLEMO algorithm.