MDP

Maximum Diversity Problem (MDP)

Problem description

Given a set of n elements and a dissimilarity (distance) value for every pair of elements, the Maximum Diversity Problem consists of selecting a subset of m elements (m < n) such that the sum of the pairwise distances between the selected elements is as large as possible.

• Solution structure: an unordered subset of exactly m elements out of the n available in the instance.
• Constraints: the subset must contain exactly m elements; both n and m are fixed by the instance being solved.
• Objective function: the sum of the pairwise distances between every pair of elements in the selected subset.
• Optimization sense: maximization — the higher the total diversity, the better the solution.

Metaheuristics used

The problem is solved with a Scatter Search, a population-based metaheuristic that evolves a small set of reference solutions (the RefSet) combining quality and diversity:

• Construction: an initial population of solutions is built and the best and most diverse ones are kept in the RefSet.
• Combination: subsets of reference solutions are systematically combined to produce new candidate solutions.
• Improvement: every generated solution is refined with a local search before entering the RefSet.
• Diversification: whenever the RefSet is refreshed, solutions that differ the most from the ones already selected are favored, so the search does not converge prematurely around a single region of the solution space.
• Cycle: combination and improvement are repeated, refreshing the RefSet with newly found solutions, until no new solutions appear or a time limit is reached.

The experiment compares three configurations of the scatter search that differ in how much information from the search history they exploit:

• Without information: purely random construction and combination, plain local search.
• With information: greedy-randomized construction and combination guided by the distance contribution of each candidate element.
• With memory: construction and combination guided by an adaptive memory (frequency and quality of each element across the search) plus a tabu-driven local search.

Class diagram

classDiagram
    direction LR

    class Experiment
    class ExperimentManager
    class InstancesManager
    class InstanceFile {
        <<record>>
        +String fileName
        +String name
        +String type
        +loadInstance() Instance
    }
    class Instance
    class Node
    class Solution
    class OptimizationAlgorithm {
        <<interface>>
        +createSolution(timeout) Solution
    }
    class ScatterSearch
    class SSConfig {
        <<enumeration>>
        WITHOUT_INF
        WITH_INF
        WITH_MEMORY
    }
    class Constructive {
        <<abstract>>
    }
    class RandomConstructive
    class GraspD2Constructive
    class TabuD2Constructive
    class Combinator {
        <<abstract>>
    }
    class RandomCombinator
    class D2Combinator
    class TabuD2Combinator
    class Diversificator {
        <<abstract>>
    }
    class NotUsedNodesDiv
    class ImprovementMethod {
        <<abstract>>
    }
    class LocalSearch
    class ImprovedLocalSearch
    class LocalSearchTabuSearch
    class TabuD2Calculator

    OptimizationAlgorithm <|.. ScatterSearch
    OptimizationAlgorithm <|.. Constructive
    Constructive <|-- RandomConstructive
    Constructive <|-- GraspD2Constructive
    Constructive <|-- TabuD2Constructive
    Combinator <|-- RandomCombinator
    Combinator <|-- D2Combinator
    Combinator <|-- TabuD2Combinator
    Diversificator <|-- NotUsedNodesDiv
    ImprovementMethod <|-- LocalSearch
    ImprovementMethod <|-- ImprovedLocalSearch
    ImprovementMethod <|-- LocalSearchTabuSearch

    ScatterSearch --> SSConfig : configured by
    ScatterSearch ..> Constructive : builds with
    ScatterSearch ..> Combinator : combines with
    ScatterSearch ..> Diversificator : diversifies with
    ScatterSearch ..> ImprovementMethod : improves with
    ScatterSearch ..> Solution : returns
    TabuD2Constructive ..> TabuD2Calculator : shares memory
    TabuD2Combinator ..> TabuD2Calculator : shares memory

    Experiment ..> InstancesManager : reads instances
    Experiment ..> OptimizationAlgorithm : runs configs
    Experiment ..> ExperimentManager : records solutions
    InstancesManager "1" o-- "*" InstanceFile : registers
    InstanceFile ..> Instance : loadInstance()
    Instance "1" o-- "*" Node
    Solution --> Instance
    Solution "1" o-- "*" Node : selected
    ExperimentManager ..> Solution : saves + reports

Loading

Implementation aspects

• ssmdp.instance — everything related to problem data:

  • Instance: in-memory instance (distance matrix, nodes, m).
  • Node: an element of the instance; asks its owning Instance for the distance to another node.
  • InstanceFile: a lightweight record (file name, display name and type) that lazily loads an Instance from a classpath resource.
  • InstancesManager: holds the registered list of available InstanceFiles and lets callers query them all, by type, by position, or by file name.
  • FormatException: signals a malformed instance file.

• ssmdp.algorithm — the scatter search itself:

  • Solution: a candidate solution; keeps the selected nodes (or their precomputed distance contributions), the objective value, and its position inside the RefSet.
  • ScatterSearch: orchestrates the whole RefSet life cycle (construction, combination, improvement, diversification). Its SSConfig enum selects one of the three configurations described above by wiring together a different Constructive, Combinator and ImprovementMethod.
  • constructive/: Constructive (strategy interface) plus RandomConstructive, GraspD2Constructive and TabuD2Constructive.
  • combinator/: Combinator (strategy interface) plus RandomCombinator, D2Combinator and TabuD2Combinator.
  • diversificator/: Diversificator (strategy interface) with NotUsedNodesDiv, which favors solutions built from the least-used elements.
  • improvement/: ImprovementMethod (strategy interface) plus LocalSearch, ImprovedLocalSearch (incremental, sorted-candidate variant) and LocalSearchTabuSearch (tabu-tenure based, used by the memory configuration).
  • tabud2/TabuD2Calculator: the adaptive memory (frequency and quality per element) shared by the memory-aware constructive and combinator.

• ssmdp.util — supporting data structures used by the scatter search: BoundedSortedList (implements the RefSet itself), Weighted (element/weight pair), Combinations (generates the RefSet subsets to combine), plus WeightedIterator, RotateListView and RandomList.

• ssmdp.Experiment / ssmdp.ExperimentManager — Experiment is the entry point: it runs the three configurations over every instance and hands each resulting Solution to the ExperimentManager. When the experiment finishes, the manager prints a comparison table to the console (mean deviation from the best solution found — shown as a percentage — and the number of instances where each configuration achieved that best result) and saves every run under experiments/<datetime>/: the solution obtained for each instance and algorithm (<instance>/<algorithm>.txt) plus an HTML report (report.html) with the results and analysis tables.

Benchmark instances live under src/main/resources/instances and are loaded through InstanceFile/InstancesManager.