MMDP

MaxMin Diversity Problem (MMDP)

Problem description

Given a set of n elements and a distance value for every pair of elements, the MaxMin Diversity Problem consists of selecting a subset of m elements (m < n) such that the smallest pairwise distance among 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 minimum pairwise distance among every pair of elements in the selected subset.
• Optimization sense: maximization of a minimum (a maximin objective) — solutions are compared by how large their worst (smallest) pairwise distance is.

This differs from the closely related Maximum Diversity Problem (MDP), whose objective is the sum of the pairwise distances instead of their minimum.

Metaheuristics used

The problem is solved with a multi-start local search:

• Construction: a random selection of m elements out of the n available.
• Improvement (local search): the neighborhood swaps a selected element for one that is not currently selected. Two exploration strategies are compared:
  • First improvement, trying candidates either in random or in lexicographical order and applying the first swap that improves the solution.
  • Best improvement, evaluating every possible swap and applying the one that improves the solution the most.
• Multi-start: construction (optionally followed by improvement) is repeated many times within a time budget, keeping the best solution found across all restarts.

Four configurations are compared experimentally: pure random construction, first improvement with random candidate order, first improvement with lexicographical candidate order, and best improvement.

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 MultiStartSearch
    class MSConfig {
        <<enumeration>>
        RANDOM
        FIRST_IMPROVEMENT_RANDOM
        FIRST_IMPROVEMENT_LEXICOGRAPHICAL
        BEST_IMPROVEMENT
    }
    class Constructive {
        <<abstract>>
    }
    class RandomConstructive
    class ImprovementMethod {
        <<abstract>>
    }
    class FirstImprovement
    class BestImprovement

    Constructive <|-- RandomConstructive
    ImprovementMethod <|-- FirstImprovement
    ImprovementMethod <|-- BestImprovement

    MultiStartSearch --> MSConfig : configured by
    MultiStartSearch ..> Constructive : builds with
    MultiStartSearch ..> ImprovementMethod : improves with
    MultiStartSearch ..> Solution : returns

    Experiment ..> InstancesManager : reads instances
    Experiment ..> MultiStartSearch : 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

• mmdp.instance — 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 (each tagged with its type, i.e. its instance set) and lets callers query them all, by type, by position, or by file name.
  • FormatException: signals a malformed instance file.

• mmdp.algorithm — the search itself:

  • Solution: keeps the list of selected nodes, evaluates the minimum pairwise distance, and implements the node-swap operation used by the local search.
  • MultiStartSearch: drives the multi-start loop under a time limit. Its MSConfig enum selects one of the four configurations by wiring together a Constructive and an optional ImprovementMethod.
  • constructive/: Constructive (strategy interface) plus RandomConstructive.
  • improvement/: ImprovementMethod (strategy interface) plus FirstImprovement (with a CandidatesOrder enum for random/lexicographical order) and BestImprovement.

• mmdp.Experiment / mmdp.ExperimentManager — Experiment is the entry point: it runs the four 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 (the GKD-Ia and GKD-Ic sets) live under src/main/resources/instances and are loaded through InstanceFile/InstancesManager.