Skip to content

Add native support for matheuristics (ILS, VNS, GRASP, ...) #87

Description

@eugenioLR

Matheuristics combine exact or heuristic subroutines with metaheuristic frameworks. The most common pattern—wrapping an entire optimization algorithm as a local‑search operator—is currently not directly supported: a strategy or algorithm cannot easily be called as a subroutine inside another strategy without loosing all tracking capabilities.

Full matheuristic support would allow users to compose iterative local
search, variable neighbourhood search, GRASP, scatter search, and other
classic hybrid methods out‑of‑the‑box. It depends on constructive
algorithms (#82) for warm‑starting components and will benefit from the
generic component‑swapping infrastructure planned in the EDA refactor (#84).

A partial implementation of VNS was present on previous versions, but it had many problems which made it unworkable for serious applications.

Matheuristics

  • Allow an Algorithm (or SearchStrategy) to be wrapped as an
    Operator so it can be used as a subroutine (e.g. local search
    inside a GA)
  • Implement greedy initializers that use constructive heuristics
    (reuse infrastructure from Add native constructive algorithms #82)
  • Ensure embedded sub‑algorithms can report progress (nested reporters)
    without interfering with the outer loop
  • Provide Iterated Local Search (ILS) as a built‑in strategy
  • Provide Variable Neighbourhood Search (VNS) as a built‑in strategy
  • Provide GRASP (Greedy Randomized Adaptive Search Procedure) as a
    built‑in strategy with configurable constructive phase
  • Provide Scatter Search as a built‑in strategy
  • Document the pattern for users to build their own matheuristics

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or requesthelp wantedExtra attention is neededresearchCheck the state of the art to see how to best do this.

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions