Class MVCExactCoverSolver

java.lang.Object

es.urjc.etsii.grafo.algorithms.cmsa.CMSASolver<MSTSolution, MSTInstance, Integer>

es.urjc.etsii.grafo.graphs.mvc.MVCExactCoverSolver

public class MVCExactCoverSolver
extends CMSASolver<MSTSolution, MSTInstance, Integer>

Exact solver for the CMSA "Solve" step of the Minimum Vertex Cover demo: given a restricted set of candidate vertices, finds the smallest subset of those candidates that covers every edge of the original instance.

Mork does not bundle any ILP solver, so instead of delegating to CPLEX/Gurobi/OR-Tools, this implementation performs an exhaustive branch and bound search. This is only tractable because the restricted sub-instance is expected to stay small: CMSA only keeps a limited number of candidate vertices active at any given time, aging out and dropping the ones that are not selected by this solver. In problems where the sub-instance can grow large, a real MIP/ILP solver would be plugged in instead, implementing the same CMSASolver contract.

When invoked by CMSA, selecting every candidate vertex is a feasible (if not optimal) solution to the restricted problem because candidates come from previously constructed feasible vertex covers. The solver validates this invariant and throws an exception if it is violated.

Constructor Summary

Constructors

Constructor	Description
MVCExactCoverSolver()

Method Summary

Modifier and Type	Method	Description
MSTSolution	solve(MSTInstance instance, Set<Integer> restrictedComponents, long maxDurationInMillis)	Solves the sub-instance induced by restricting the problem to the given set of solution components.

Methods inherited from class CMSASolver

toString

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Details

MVCExactCoverSolver

@AutoconfigConstructor
public MVCExactCoverSolver()

Method Details

solve

public MSTSolution solve(MSTInstance instance,
 Set<Integer> restrictedComponents,
 long maxDurationInMillis)

Description copied from class: CMSASolver

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.

Specified by:

solve in class CMSASolver<MSTSolution, MSTInstance, Integer>

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