Class CMSASolver<S extends Solution<S,I>, I extends Instance, C>

java.lang.Object
es.urjc.etsii.grafo.algorithms.cmsa.CMSASolver<S,I,C>
Type Parameters:
S - Solution class
I - Instance class
C - Solution component class
Direct Known Subclasses:
MVCExactCoverSolver
@AlgorithmComponent public abstract class CMSASolver<S extends Solution<S,I>, I extends Instance, C> extends Object
Solves, exactly or as close to exactly as possible, the sub-instance of the problem induced by restricting it to a given set of solution components. This is the "Solve" step of the CMSA (Construct, Merge, Solve and Adapt) algorithm, see CMSA for more details about the whole procedure.

Mork does not bundle any exact solver: implementations of this class are expected to encode the restricted sub-instance and delegate to whatever exact method fits the problem and is available in the classpath, for example a MIP/ILP solver such as CPLEX, Gurobi, SCIP or OR-Tools, a specialized dynamic programming procedure, or, when the restricted sub-instance is small enough as it is expected in CMSA, an exhaustive branch and bound search.

For guidance on how to formulate the mathematical (MIP/ILP) model of the restricted sub-instance for a given problem, see: Blum, C. (2024). Construct, Merge, Solve & Adapt: A Hybrid Metaheuristic for Combinatorial Optimization. Computational Intelligence Methods and Applications. Springer. ...

  • Constructor Details

    • CMSASolver

      public CMSASolver()

  • Method Details

    • solve

      public abstract S solve(I instance, Set<C> restrictedComponents, long maxDurationInMillis)
      Solves the sub-instance induced by restricting the problem to the given set of solution components. Implementations are free to return a suboptimal solution if the time limit is reached before the sub-instance is solved to optimality, but the returned solution, if any, must always be feasible.
      Parameters:
      instance - original problem instance
      restrictedComponents - set of solution components the returned solution is restricted to use. Values are the same objects returned by CMSAConstructive.usedComponents(Solution)
      maxDurationInMillis - maximum time budget, in milliseconds, to spend solving the sub-instance
      Returns:
      a feasible solution built only using components in restrictedComponents, or null if no feasible solution could be found in the given time budget

    • toString

      public String toString()
      Overrides:
      toString in class Object