### Install MHLib.jl Package Source: https://github.com/ac-tuwien/mhlib.jl/blob/master/README.md Installs the latest stable version of the MHLib.jl package from the Julia package registry. For development versions, a direct Git URL can be used. ```julia ] add MHLib ``` ```julia ] add https://github.com/ac-tuwien/MHLib.jl.git ``` -------------------------------- ### Complete TSP Example with LNS in Julia using MHLib Source: https://context7.com/ac-tuwien/mhlib.jl/llms.txt Provides a full example of solving the Traveling Salesperson Problem (TSP) using Large Neighborhood Search (LNS) with the MHLib library in Julia. It defines custom structures for TSP instances and solutions, and implements TSP-specific methods for construction, local improvement, shaking, destruction, and repair. ```julia using MHLib using Random # TSP Instance struct TSPInstance n::Int d::Matrix{Int} end function TSPInstance(n::Int) coords = [rand(1:100, 2) for _ in 1:n] d = [round(Int, sqrt(sum((coords[i] .- coords[j]).^2))) for i in 1:n, j in 1:n] TSPInstance(n, d) end # TSP Solution mutable struct TSPSolution <: PermutationSolution{Int} inst::TSPInstance obj_val::Int obj_val_valid::Bool x::Vector{Int} destroyed::Union{Nothing, Vector{Int}} end TSPSolution(inst::TSPInstance) = TSPSolution(inst, -1, false, collect(1:inst.n), nothing) MHLib.to_maximize(::Type{TSPSolution}) = false function MHLib.calc_objective(s::TSPSolution) n = length(s.x) sum(s.inst.d[s.x[i], s.x[mod1(i+1, n)]] for i in 1:n) end Base.copy!(s1::TSPSolution, s2::TSPSolution) = begin s1.inst = s2.inst; s1.obj_val = s2.obj_val; s1.obj_val_valid = s2.obj_val_valid copy!(s1.x, s2.x) s1.destroyed = isnothing(s2.destroyed) ? nothing : copy(s2.destroyed) end Base.copy(s::TSPSolution) = TSPSolution(s.inst, s.obj_val, s.obj_val_valid, copy(s.x), isnothing(s.destroyed) ? nothing : copy(s.destroyed)) # TSP-specific methods MHLib.construct!(s::TSPSolution, ::Nothing, ::Result) = initialize!(s) function MHLib.local_improve!(s::TSPSolution, ::Any, result::Result) if !two_opt_neighborhood_search!(s, false) result.changed = false end end MHLib.shaking!(s::TSPSolution, k::Int, ::Result) = random_two_exchange_moves!(s, k) function MHLib.destroy!(s::TSPSolution, k::Int, ::Result) random_remove_elements!(s, get_number_to_destroy(s, length(s.x); min_abs=3*k, max_abs=3*k)) end MHLib.repair!(s::TSPSolution, ::Nothing, ::Result) = greedy_reinsert_removed!(s) # Efficient delta evaluation for 2-opt function MHLib.two_opt_move_delta_eval(s::TSPSolution, p1::Integer, p2::Integer) n = length(s.x) if p1 == 1 && p2 == n; return 0; end prev = mod1(p1 - 1, n) nxt = mod1(p2 + 1, n) d = s.inst.d x = s.x d[x[prev], x[p2]] + d[x[p1], x[nxt]] - d[x[prev], x[p1]] - d[x[p2], x[nxt]] end # Greedy insertion for repair function MHLib.insert_val_at_best_pos!(s::TSPSolution, val::Int) x, d = s.x, s.inst.d best_pos = length(x) + 1 delta_best = d[val, x[end]] + d[val, x[1]] - d[x[1], x[end]] for i in 2:length(x) delta = d[val, x[i-1]] + d[val, x[i]] - d[x[i-1], x[i]] if delta < delta_best delta_best = delta best_pos = i end end insert!(x, best_pos, val) s.obj_val += delta_best end ``` -------------------------------- ### GVNS: General Variable Neighborhood Search Implementation in Julia Source: https://context7.com/ac-tuwien/mhlib.jl/llms.txt Demonstrates the setup and execution of the GVNS algorithm using MHlib.jl. It includes defining a custom solution type, configuring construction, local improvement, and shaking methods, and running the optimization process. ```julia using MHLib using Random # Solution type for maximization problem mutable struct BitStringSolution <: BoolVectorSolution obj_val::Int obj_val_valid::Bool x::Vector{Bool} end BitStringSolution(n) = BitStringSolution(-1, false, Vector{Bool}(undef, n)) MHLib.calc_objective(s::BitStringSolution) = sum(s.x) Base.copy!(s1::BitStringSolution, s2::BitStringSolution) = begin s1.obj_val = s2.obj_val; s1.obj_val_valid = s2.obj_val_valid; copy!(s1.x, s2.x) end Base.copy(s::BitStringSolution) = BitStringSolution(s.obj_val, s.obj_val_valid, copy(s.x)) Random.seed!(42) sol = BitStringSolution(100) # Define method lists meths_ch = [MHMethod("construct", construct!)] # Construction heuristics meths_li = [MHMethod("li1", local_improve!, 1)] # Local improvement (1-flip) meths_sh = [MHMethod("sh1", shaking!, 1), # Shaking methods MHMethod("sh2", shaking!, 2), MHMethod("sh3", shaking!, 3)] # Create GVNS with configuration gvns = GVNS(sol, meths_ch, meths_li, meths_sh; titer=500, # Maximum iterations ttime=30.0, # Time limit (seconds) tciter=50, # Max iterations without improvement log=true, # Enable logging lfreq=-1, # Log frequency (-1 for logarithmic: 1,2,5,10,20,...) consider_initial_sol=false # Don't consider initial solution as valid ) # Run the optimization run!(gvns) # Access results println("Best objective: ", obj(gvns.scheduler.incumbent)) println("Best iteration: ", gvns.scheduler.incumbent_iteration) println("Total runtime: ", gvns.scheduler.run_time) # Output detailed statistics method_statistics(gvns.scheduler) main_results(gvns.scheduler) ``` -------------------------------- ### PermutationSolution Operations (TSP) Source: https://context7.com/ac-tuwien/mhlib.jl/llms.txt Shows how to implement solutions for permutation-based problems, using the Traveling Salesperson Problem (TSP) as an example. It includes defining a `TSPSolution` type, implementing objective calculation for TSP, and basic initialization. ```julia using MHLib using Random mutable struct TSPSolution <: PermutationSolution{Int} n::Int distances::Matrix{Int} obj_val::Int obj_val_valid::Bool x::Vector{Int} destroyed::Union{Nothing, Vector{Int}} end function TSPSolution(n::Int, distances::Matrix{Int}) TSPSolution(n, distances, -1, false, collect(1:n), nothing) end MHLib.to_maximize(::Type{TSPSolution}) = false # Minimization problem function MHLib.calc_objective(s::TSPSolution) total = sum(s.distances[s.x[i], s.x[mod1(i+1, length(s.x))]] for i in 1:length(s.x)) return total end Base.copy!(s1::TSPSolution, s2::TSPSolution) = begin s1.n = s2.n; s1.distances = s2.distances s1.obj_val = s2.obj_val; s1.obj_val_valid = s2.obj_val_valid copy!(s1.x, s2.x) s1.destroyed = isnothing(s2.destroyed) ? nothing : copy(s2.destroyed) end Base.copy(s::TSPSolution) = TSPSolution(s.n, s.distances, s.obj_val, s.obj_val_valid, copy(s.x), isnothing(s.destroyed) ? nothing : copy(s.destroyed)) # Create random TSP instance n = 10 distances = [rand(1:100) for i in 1:n, j in 1:n] distances = distances + distances' # Symmetric for i in 1:n; distances[i,i] = 0; end sol = TSPSolution(n, distances) initialize!(sol) # Random permutation ``` -------------------------------- ### Logging and Statistics with GVNS in Julia Source: https://context7.com/ac-tuwien/mhlib.jl/llms.txt This snippet showcases MHLib.jl's logging and statistics capabilities using the Guided Variable Neighborhood Search (GVNS) metaheuristic. It defines a custom solution type, initializes GVNS with specific parameters for logging, runs the optimization, and then accesses and prints various scheduler data, including best objective, runtime, and method statistics. ```julia using MHLib using Random mutable struct LogDemoSolution <: BoolVectorSolution obj_val::Int obj_val_valid::Bool x::Vector{Bool} end LogDemoSolution(n) = LogDemoSolution(-1, false, Vector{Bool}(undef, n)) MHLib.calc_objective(s::LogDemoSolution) = sum(s.x) Base.copy!(s1::LogDemoSolution, s2::LogDemoSolution) = begin s1.obj_val = s2.obj_val; s1.obj_val_valid = s2.obj_val_valid; copy!(s1.x, s2.x) end Base.copy(s::LogDemoSolution) = LogDemoSolution(s.obj_val, s.obj_val_valid, copy(s.x)) Random.seed!(42) sol = LogDemoSolution(50) gvns = GVNS(sol, [MHMethod("construct", construct!)], [MHMethod("li", local_improve!, 1)], [MHMethod("sh", shaking!, 1)]; titer=100, log=true, # Enable logging lnewinc=true, # Log new incumbent solutions lfreq=-1 # Logarithmic frequency: 1,2,5,10,20,50,100... ) run!(gvns) # Access scheduler data sched = gvns.scheduler println("\n=== Results ===") println("Best objective: ", obj(sched.incumbent)) println("Found at iteration: ", sched.incumbent_iteration) println("Found at time: ", sched.incumbent_time, " seconds") println("Total iterations: ", sched.iteration) println("Total runtime: ", sched.run_time, " seconds") # Method statistics (applications, success rate, time) method_statistics(sched) # Main results summary main_results(sched) # Check solution validity check(sched.incumbent) # Get git version for reproducibility logging println("Version: ", git_version()) ``` -------------------------------- ### Get MHLib.jl Git Version Source: https://github.com/ac-tuwien/mhlib.jl/blob/master/README.md Retrieves the abbreviated git version string of the MHLib.jl project. This function is useful for logging and ensuring reproducibility of optimization runs by recording the exact software version used. ```julia using MHLib git_version() ``` -------------------------------- ### Define Custom Solution Type (BoolVectorSolution) Source: https://context7.com/ac-tuwien/mhlib.jl/llms.txt Demonstrates how to define a custom solution type inheriting from MHLib's BoolVectorSolution. This involves implementing objective value calculation, initialization, and copy operations. The example shows a `MyBoolSolution` type. ```julia using MHLib mutable struct MyBoolSolution <: BoolVectorSolution obj_val::Int obj_val_valid::Bool x::Vector{Bool} end MyBoolSolution(n::Int) = MyBoolSolution(-1, false, Vector{Bool}(undef, n)) MHLib.calc_objective(s::MyBoolSolution) = sum(s.x) Base.copy!(s1::MyBoolSolution, s2::MyBoolSolution) = begin s1.obj_val = s2.obj_val s1.obj_val_valid = s2.obj_val_valid copy!(s1.x, s2.x) end Base.copy(s::MyBoolSolution) = MyBoolSolution(s.obj_val, s.obj_val_valid, copy(s.x)) # Usage sol = MyBoolSolution(10) initialize!(sol) # Random initialization for BoolVectorSolution println("Objective: ", obj(sol)) # Calculates and caches objective invalidate!(sol) # Mark objective as invalid after changes ``` -------------------------------- ### KnapsackSolution Operations in MHLib.jl Source: https://context7.com/ac-tuwien/mhlib.jl/llms.txt Defines and demonstrates the KnapsackSolution type, which extends SubsetVectorSolution for knapsack problems. It includes custom objective calculation, feasibility checks, delta evaluation for element addition, and copy operations. Usage examples show initialization, resetting, filling, and neighborhood search. ```julia using MHLib mutable struct KnapsackSolution <: SubsetVectorSolution{Int} weights::Vector{Int} values::Vector{Int} capacity::Int obj_val::Int obj_val_valid::Bool x::Vector{Int} # Selected elements first, then unselected sel::Int # Number of selected elements end function KnapsackSolution(weights, values, capacity) n = length(weights) KnapsackSolution(weights, values, capacity, -1, false, collect(1:n), 0) end function MHLib.calc_objective(s::KnapsackSolution) sum(s.values[s.x[i]] for i in 1:s.sel; init=0) end MHLib.may_be_extendible(s::KnapsackSolution) = s.sel < length(s.x) function MHLib.element_added_delta_eval!(s::KnapsackSolution; update_obj_val=true, allow_infeasible=false) total_weight = sum(s.weights[s.x[i]] for i in 1:s.sel) if total_weight <= s.capacity || allow_infeasible update_obj_val && invalidate!(s) return true else s.x[s.sel], s.x[end] = s.x[end], s.x[s.sel] s.sel -= 1 return false end end Base.copy!(s1::KnapsackSolution, s2::KnapsackSolution) = begin s1.weights = s2.weights; s1.values = s2.values; s1.capacity = s2.capacity s1.obj_val = s2.obj_val; s1.obj_val_valid = s2.obj_val_valid copy!(s1.x, s2.x); s1.sel = s2.sel end Base.copy(s::KnapsackSolution) = KnapsackSolution(s.weights, s.values, s.capacity, s.obj_val, s.obj_val_valid, copy(s.x), s.sel) # Usage weights = [10, 20, 30, 40, 15] values = [60, 100, 120, 140, 70] sol = KnapsackSolution(weights, values, 50) empty!(sol) fillup!(sol) remove_randomly_selected!(sol, 2) two_exchange_random_fill_neighborhood_search!(sol, false) ``` -------------------------------- ### LNS: Large Neighborhood Search Implementation in Julia Source: https://context7.com/ac-tuwien/mhlib.jl/llms.txt Illustrates the use of the LNS framework in MHlib.jl for solving optimization problems. It covers defining a custom solution with destroy support, implementing custom destroy and repair methods, and configuring the LNS with different method selection strategies. ```julia using MHLib using Random # Solution with destroy support mutable struct LNSSolution <: BoolVectorSolution obj_val::Int obj_val_valid::Bool x::Vector{Bool} destroyed::Vector{Int} end LNSSolution(n) = LNSSolution(-1, false, Vector{Bool}(undef, n), Int[]) MHLib.calc_objective(s::LNSSolution) = sum(s.x) Base.copy!(s1::LNSSolution, s2::LNSSolution) = begin s1.obj_val = s2.obj_val; s1.obj_val_valid = s2.obj_val_valid copy!(s1.x, s2.x); copy!(s1.destroyed, s2.destroyed) end Base.copy(s::LNSSolution) = LNSSolution(s.obj_val, s.obj_val_valid, copy(s.x), copy(s.destroyed)) # Custom destroy method function my_destroy!(sol::LNSSolution, k::Int, result::Result) # Select k random positions to destroy num = get_number_to_destroy(sol, length(sol.x); min_abs=k, max_abs=k) sol.destroyed = rand(1:length(sol.x), num) invalidate!(sol) end # Custom repair method function my_repair!(sol::LNSSolution, ::Nothing, result::Result) for pos in sol.destroyed sol.x[pos] = rand(Bool) end empty!(sol.destroyed) invalidate!(sol) end Random.seed!(42) sol = LNSSolution(100) # Method lists meths_ch = [MHMethod("construct", construct!)] meths_de = [MHMethod("de1", my_destroy!, 5), # Destroy 5 elements MHMethod("de2", my_destroy!, 10), # Destroy 10 elements MHMethod("de3", my_destroy!, 15)] # Destroy 15 elements meths_re = [MHMethod("repair", my_repair!)] # Create LNS with Metropolis acceptance criterion lns = LNS(sol, meths_ch, meths_de, meths_re; titer=1000, ttime=60.0, init_temp_factor=0.1, # Initial temperature = obj_val * factor temp_dec_factor=0.99, # Geometric cooling method_selector=UniformRandomMethodSelector(), # Random method selection log=true ) run!(lns) method_statistics(lns.scheduler) main_results(lns.scheduler) # Alternative: Weighted random selection weights_de = [0.5, 0.3, 0.2] # Probabilities for destroy methods weights_re = [1.0] # Single repair method weighted_selector = WeightedRandomMethodSelector(weights_de, weights_re) lns_weighted = LNS(sol, meths_ch, meths_de, meths_re; titer=1000, method_selector=weighted_selector ) ``` -------------------------------- ### MHMethod and Scheduler Framework in MHLib.jl Source: https://context7.com/ac-tuwien/mhlib.jl/llms.txt Implements a metaheuristic framework using MHMethod and Scheduler. It defines custom solution types (SimpleSolution), wraps functions as MHMethods for construction, local improvement, and shaking, and configures a Scheduler with termination criteria and logging. Demonstrates manual method execution and checking termination conditions. ```julia using MHLib mutable struct SimpleSolution <: BoolVectorSolution obj_val::Int obj_val_valid::Bool x::Vector{Bool} end SimpleSolution(n) = SimpleSolution(-1, false, Vector{Bool}(undef, n)) MHLib.calc_objective(s::SimpleSolution) = sum(s.x) Base.copy!(s1::SimpleSolution, s2::SimpleSolution) = begin s1.obj_val = s2.obj_val; s1.obj_val_valid = s2.obj_val_valid; copy!(s1.x, s2.x) end Base.copy(s::SimpleSolution) = SimpleSolution(s.obj_val, s.obj_val_valid, copy(s.x)) function my_construct!(sol::SimpleSolution, ::Nothing, result::Result) initialize!(sol) end function my_local_improve!(sol::SimpleSolution, k::Int, result::Result) k_flip_neighborhood_search!(sol, k, false) end function my_shaking!(sol::SimpleSolution, k::Int, result::Result) k_random_flips!(sol, k) end construct_method = MHMethod("construct", my_construct!) improve_method = MHMethod("improve", my_local_improve!, 1) shake_method = MHMethod("shake", my_shaking!, 2) sol = SimpleSolution(50) methods = [construct_method, improve_method, shake_method] scheduler = Scheduler(sol, methods; titer=100, ttime=60.0, tciter=20, log=true, checkit=false ) res = perform_method!(scheduler, construct_method, sol) res = perform_method!(scheduler, improve_method, sol) if check_termination(scheduler) println("Termination condition met") end method_statistics(scheduler) main_results(scheduler) ``` -------------------------------- ### Solve TSP using LNS in Julia Source: https://context7.com/ac-tuwien/mhlib.jl/llms.txt This snippet demonstrates solving the Traveling Salesperson Problem (TSP) using the Large Neighborhood Search (LNS) metaheuristic in MHLib.jl. It initializes a TSP instance, sets up the LNS with construction, destruction, and repair methods, and runs the search. It then prints the best tour length and method statistics. ```julia using MHLib using Random Random.seed!(42) inst = TSPInstance(50) sol = TSPSolution(inst) lns = LNS(sol, [MHMethod("construct", construct!)], [MHMethod("de$i", destroy!, i) for i in 1:3], [MHMethod("repair", repair!)]; titer=500, init_temp_factor=0.0, log=true ) run!(lns) println("\nBest tour length: ", obj(lns.scheduler.incumbent)) method_statistics(lns.scheduler) ``` -------------------------------- ### ALNS Implementation with Adaptive Method Selection in Julia Source: https://context7.com/ac-tuwien/mhlib.jl/llms.txt Implements an Adaptive Large Neighborhood Search (ALNS) in Julia using the MHLib library. It defines a custom solution structure `ALNSSolution` and demonstrates how to configure ALNS with adaptive parameters for method selection, including segment size, reaction factor, and scoring for different solution qualities. ```julia using MHLib using Random mutable struct ALNSSolution <: BoolVectorSolution obj_val::Int obj_val_valid::Bool x::Vector{Bool} destroyed::Vector{Int} end ALNSSolution(n) = ALNSSolution(-1, false, Vector{Bool}(undef, n), Int[]) MHLib.calc_objective(s::ALNSSolution) = sum(s.x) Base.copy!(s1::ALNSSolution, s2::ALNSSolution) = begin s1.obj_val = s2.obj_val; s1.obj_val_valid = s2.obj_val_valid copy!(s1.x, s2.x); copy!(s1.destroyed, s2.destroyed) end Base.copy(s::ALNSSolution) = ALNSSolution(s.obj_val, s.obj_val_valid, copy(s.x), copy(s.destroyed)) function alns_destroy!(sol::ALNSSolution, k::Int, result::Result) num = get_number_to_destroy(sol, length(sol.x); min_abs=3*k, max_abs=3*k) sol.destroyed = rand(1:length(sol.x), num) invalidate!(sol) end function alns_repair!(sol::ALNSSolution, ::Nothing, result::Result) for pos in sol.destroyed sol.x[pos] = rand(Bool) end empty!(sol.destroyed) invalidate!(sol) end Random.seed!(42) sol = ALNSSolution(100) meths_ch = [MHMethod("construct", construct!)] meths_de = [MHMethod("de$i", alns_destroy!, i) for i in 1:5] # 5 destroy methods meths_re = [MHMethod("repair", alns_repair!)] # Create ALNS with adaptive parameters alns = ALNS(sol, meths_ch, meths_de, meths_re; titer=2000, ttime=120.0, # ALNS-specific parameters segment_size=100, # Iterations per segment for weight updates gamma=0.025, # Reaction factor for weight updates sigma1=10, # Score for new global best solution sigma2=9, # Score for better than current solution sigma3=3, # Score for worse but accepted solution # LNS parameters init_temp_factor=0.05, temp_dec_factor=0.995, log=true ) run!(alns) method_statistics(alns.scheduler) main_results(alns.scheduler) ``` -------------------------------- ### BoolVectorSolution Operations (MaxOnes) Source: https://context7.com/ac-tuwien/mhlib.jl/llms.txt Illustrates operations on solutions encoded as boolean vectors, including initialization, shaking (random bit flips), local search (k-flip neighborhood), variable flipping, and calculating solution distance (Hamming distance). ```julia using MHLib mutable struct MaxOnesSolution <: BoolVectorSolution obj_val::Int obj_val_valid::Bool x::Vector{Bool} end MaxOnesSolution(n) = MaxOnesSolution(-1, false, Vector{Bool}(undef, n)) MHLib.calc_objective(s::MaxOnesSolution) = sum(s.x) Base.copy!(s1::MaxOnesSolution, s2::MaxOnesSolution) = begin s1.obj_val = s2.obj_val; s1.obj_val_valid = s2.obj_val_valid; copy!(s1.x, s2.x) end Base.copy(s::MaxOnesSolution) = MaxOnesSolution(s.obj_val, s.obj_val_valid, copy(s.x)) sol = MaxOnesSolution(20) initialize!(sol) # Random initialization # Shaking: flip k random bits k_random_flips!(sol, 3) # Local search: k-flip neighborhood search # Parameters: solution, k (number of bits to flip), best_improvement (true/false) k_flip_neighborhood_search!(sol, 1, false) # First improvement 1-flip search # Flip single variable and get updated objective new_obj = flip_variable!(sol, 5) # Flip bit at position 5 # Distance between solutions (Hamming distance for BoolVectorSolution) sol2 = copy(sol) k_random_flips!(sol2, 2) println("Distance: ", dist(sol, sol2)) ``` -------------------------------- ### Neighborhood Search and Solution Manipulation in MHLib.jl Source: https://context7.com/ac-tuwien/mhlib.jl/llms.txt Demonstrates common metaheuristic operations like 2-opt neighborhood search, random exchanges, element removal, and reinsertion for solution improvement. These functions modify a solution object in place. ```julia improved = two_opt_neighborhood_search!(sol, true) random_two_exchange_moves!(sol, 2) random_remove_elements!(sol, 3) random_reinsert_removed!(sol) greedy_reinsert_removed!(sol) ``` === COMPLETE CONTENT === This response contains all available snippets from this library. No additional content exists. Do not make further requests.