MaxMin Diversity Problem (MMDP) — Implementation

🏠 Home · ← Prev: MMDP — Description

This document describes the Java implementation of the multi-start local search for the MaxMin Diversity Problem. The problem itself and the algorithm design are covered in the MMDP description.

The complete, runnable source code is available in this repository under problems/no-framework/MMDP. The implementation targets Java 25 and uses modern language features such as records and switch expressions. Every class name below links to its source file.

Design

The diagram shows the main classes of the application and the relationships between them.

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

Figure 1. Class diagram of the multi-start local search applied to the MMDP.

Problem data — package `mmdp.instance`

Instance: the in-memory representation of an instance — the pairwise distance matrix, the list of Nodes, and the number m of elements to select.
Node: an element of an Instance; it holds its index and asks the 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 — GKD-Ia or GKD-Ic) and lets callers query them all, by type, by position, or by file name.
FormatException: a checked exception signalling a malformed instance file.

The search — package `mmdp.algorithm`

Solution: keeps the list of selected nodes, evaluates the objective (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.
Construction — package constructive: Constructive (abstract base) plus RandomConstructive.
Improvement — package improvement: ImprovementMethod (abstract base) plus FirstImprovement (with a CandidatesOrder enum for random/lexicographical order) and BestImprovement.

Entry point — package `mmdp`

Experiment: the main program. It loads the GKD-Ia instances through InstancesManager, runs the four MultiStartSearch configurations on each instance under a fixed per-run time budget (TIMEOUT_MILLIS, 10 seconds), and hands each resulting Solution to the ExperimentManager.
ExperimentManager: collects the results, computes statistics (the mean percentage deviation from the best solution found and the number of instances where each method reached that best value), prints a comparison table to the console, and saves each run under experiments/<datetime>/ — one file per instance and algorithm plus an HTML report (report.html).

Implementation Details

This section shows the implementation of the most relevant classes.

Problem data: Instance and Node

An Instance stores the full distance matrix and builds one Node per element. A Node knows its index and delegates distance queries to its instance.

package mmdp.instance;

import java.util.ArrayList;
import java.util.List;

public class Instance {

    private double weights[][];
    private List<Node> nodes;
    private int numSolutionNodes;
    private String name;

    public Instance(String name, int numSolutionNodes, double[][] weights) {
        this.name = name;
        this.numSolutionNodes = numSolutionNodes;
        this.weights = weights;
        nodes = new ArrayList<Node>();
        for (int i = 0; i < weights.length; i++) {
            nodes.add(new Node(i, this));
        }
    }

    public Node getNode(int index) {
        return nodes.get(index);
    }

    public double getWeight(int i, int j) {
        return weights[i][j];
    }

    public int getNumNodes() {
        return nodes.size();
    }

    public List<Node> getNodes() {
        return nodes;
    }

    public String getName() {
        return name;
    }

    public int getNumSolutionNodes() {
        return numSolutionNodes;
    }

    public String getDescription() {
        return name + " (n=" + getNumNodes() + ", m=" + numSolutionNodes + ")";
    }

}

package mmdp.instance;

public class Node {

    private int index;
    private Instance instance;

    public Node(int index, Instance instance) {
        this.index = index;
        this.instance = instance;
    }

    public double getDistanceTo(Node node) {
        return instance.getWeight(index, node.index);
    }

    public int getIndex() {
        return index;
    }

    @Override
    public int hashCode() {
        return index;
    }

    @Override
    public boolean equals(Object o) {
        if (o instanceof Node node) {
            return index == node.index;
        } else {
            return false;
        }
    }

    @Override
    public String toString() {
        return Integer.toString(index);
    }

}

Solution

The Solution holds the selected nodes and its objective value (totalWeight, the minimum pairwise distance). calculateWeightChangeNode evaluates the objective that a swap would produce without modifying the solution — the operation used by the local search strategies — while changeNode applies the swap.

package mmdp.algorithm;

import java.util.ArrayList;
import java.util.List;

import mmdp.instance.Instance;
import mmdp.instance.Node;

public class Solution {

    private Instance instance;
    private List<Node> nodes;
    private double totalWeight;

    public Solution(Instance instance, List<Node> nodes) {
        this.instance = instance;
        this.nodes = nodes;
        calculateWeight();
    }

    public void calculateWeight() {
        totalWeight = nodes.get(0).getDistanceTo(nodes.get(1));

        for (int i = 0; i < nodes.size(); i++) {
            for (int j = i + 1; j < nodes.size(); j++) {
                totalWeight = Math.min(totalWeight, nodes.get(i).getDistanceTo(nodes.get(j)));
            }
        }
    }

    public double calculateWeightChangeNode(Node oldNode, Node newNode) {
        List<Node> newNodes = new ArrayList<>();

        for (Node node : nodes) {
            if (node.equals(oldNode)) {
                newNodes.add(newNode);
            } else {
                newNodes.add(node);
            }
        }

        double newTotalWeight = newNodes.get(0).getDistanceTo(newNodes.get(1));

        for (int i = 0; i < newNodes.size(); i++) {
            for (int j = i + 1; j < newNodes.size(); j++) {
                newTotalWeight = Math.min(newTotalWeight, newNodes.get(i).getDistanceTo(newNodes.get(j)));
            }
        }

        return newTotalWeight;
    }

    public void changeNode(Node oldNode, Node newNode) {
        for (int i = 0; i < nodes.size(); i++) {
            if (nodes.get(i).equals(oldNode)) {
                nodes.set(i, newNode);
                break;
            }
        }

        calculateWeight();
    }

    public boolean contains(Node node) {
        return nodes.contains(node);
    }

    public double getTotalWeight() {
        return totalWeight;
    }

    public List<Node> getNodes() {
        return nodes;
    }

    public Instance getInstance() {
        return instance;
    }

    @Override
    public String toString() {
        return nodes.toString();
    }

}

The multi-start driver

MultiStartSearch wires a Constructive and an optional ImprovementMethod according to the chosen MSConfig, then repeatedly builds, improves and keeps the best solution until the restart budget or the time limit is reached. Because the MMDP is a maximization problem, "best" means the largest objective value.

package mmdp.algorithm;

import mmdp.algorithm.constructive.Constructive;
import mmdp.algorithm.constructive.RandomConstructive;
import mmdp.algorithm.improvement.BestImprovement;
import mmdp.algorithm.improvement.FirstImprovement;
import mmdp.algorithm.improvement.FirstImprovement.CandidatesOrder;
import mmdp.algorithm.improvement.ImprovementMethod;
import mmdp.instance.Instance;

public class MultiStartSearch {

    public enum MSConfig {
        RANDOM, FIRST_IMPROVEMENT_RANDOM, FIRST_IMPROVEMENT_LEXICOGRAPHICAL, BEST_IMPROVEMENT
    }

    private static final int NUM_SOLUTIONS = 5000;

    private Constructive constructive;
    private ImprovementMethod improvingMethod;

    public MultiStartSearch(Instance instance, MSConfig methodConfig) {

        constructive = new RandomConstructive(instance);

        switch (methodConfig) {
            case RANDOM -> improvingMethod = null;
            case FIRST_IMPROVEMENT_RANDOM ->
                improvingMethod = new FirstImprovement(CandidatesOrder.RANDOM);
            case FIRST_IMPROVEMENT_LEXICOGRAPHICAL ->
                improvingMethod = new FirstImprovement(CandidatesOrder.LEXICOGRAPHICAL);
            case BEST_IMPROVEMENT -> improvingMethod = new BestImprovement();
        }
    }

    public Solution calculateSolution(long millisTimeout) {

        long finishTime = System.currentTimeMillis() + millisTimeout;

        Solution bestSolution = null;

        for (int i = 0; i < NUM_SOLUTIONS; i++) {

            Solution solution = constructive.createSolution();

            if (improvingMethod != null) {
                improvingMethod.improveSolution(solution);
            }

            if (bestSolution == null
                    || solution.getTotalWeight() > bestSolution.getTotalWeight()) {
                bestSolution = solution;
            }

            // If the time limit has been exceeded, exit the algorithm
            if (System.currentTimeMillis() > finishTime) {
                break;
            }
        }

        return bestSolution;
    }

}

Construction: random selection

Constructive methods are subclasses of the abstract Constructive. The random constructive shuffles the node list and takes the first m nodes.

package mmdp.algorithm.constructive;

import java.util.ArrayList;
import java.util.List;

import mmdp.algorithm.Solution;
import mmdp.instance.Instance;

public abstract class Constructive {

    protected Instance instance;

    public Constructive(Instance instance) {
        this.instance = instance;
    }

    public Instance getInstance() {
        return instance;
    }

    public List<Solution> createSolutions(int numSolutions) {
        List<Solution> solutions = new ArrayList<Solution>();
        for (int i = 0; i < numSolutions; i++) {
            solutions.add(createSolution());
        }
        return solutions;
    }

    public abstract Solution createSolution();

}

package mmdp.algorithm.constructive;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

import mmdp.algorithm.Solution;
import mmdp.instance.Instance;
import mmdp.instance.Node;

public class RandomConstructive extends Constructive {

    private static final Random random = new Random();

    public RandomConstructive(Instance instance) {
        super(instance);
    }

    @Override
    public Solution createSolution() {

        // Shuffle a copy of the instance node list and take the first
        // m nodes as the randomly selected solution nodes
        List<Node> shuffledNodes = new ArrayList<>(instance.getNodes());
        Collections.shuffle(shuffledNodes, random);

        List<Node> nodes = new ArrayList<>(
                shuffledNodes.subList(0, instance.getNumSolutionNodes()));

        return new Solution(instance, nodes);
    }

}

Improvement: best and first improvement

Improvement methods are subclasses of the abstract ImprovementMethod, which exposes a single improveSolution operation that improves a solution in place.

package mmdp.algorithm.improvement;

import mmdp.algorithm.Solution;

public abstract class ImprovementMethod {

    public abstract void improveSolution(Solution solution);

}

BestImprovement scans the entire swap neighborhood and applies the move with the largest improvement, repeating until no improving move remains:

package mmdp.algorithm.improvement;

import mmdp.algorithm.Solution;
import mmdp.instance.Instance;
import mmdp.instance.Node;

public class BestImprovement extends ImprovementMethod {

    @Override
    public void improveSolution(Solution solution) {

        Instance instance = solution.getInstance();

        boolean nodeChanged;
        double bestWeight;
        Node bestOldNode;
        Node bestNewNode;

        do {
            nodeChanged = false;
            bestWeight = solution.getTotalWeight();
            bestOldNode = null;
            bestNewNode = null;

            for (int i = 0; i < solution.getNodes().size(); i++) {
                Node oldNode = solution.getNodes().get(i);

                for (Node newNode : instance.getNodes()) {

                    if (!solution.contains(newNode)) {

                        double newWeight = solution.calculateWeightChangeNode(oldNode, newNode);

                        // Keep the best change that improves the solution
                        if (newWeight > bestWeight) {
                            bestWeight = newWeight;
                            bestOldNode = oldNode;
                            bestNewNode = newNode;
                        }
                    }
                }
            }

            if (bestNewNode != null) {
                solution.changeNode(bestOldNode, bestNewNode);
                nodeChanged = true;
            }

        } while (nodeChanged);
    }

}

FirstImprovement applies the first improving move it finds, visiting candidates in the order selected by its CandidatesOrder (random or lexicographical):

package mmdp.algorithm.improvement;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import mmdp.algorithm.Solution;
import mmdp.instance.Instance;
import mmdp.instance.Node;

public class FirstImprovement extends ImprovementMethod {

    public enum CandidatesOrder {
        RANDOM, LEXICOGRAPHICAL
    }

    private final CandidatesOrder order;

    public FirstImprovement(CandidatesOrder order) {
        this.order = order;
    }

    @Override
    public void improveSolution(Solution solution) {

        Instance instance = solution.getInstance();

        List<Node> candidates = new ArrayList<>(instance.getNodes());
        switch (order) {
            case RANDOM -> Collections.shuffle(candidates);
            case LEXICOGRAPHICAL -> candidates.sort(Comparator.comparingInt(Node::getIndex));
        }

        boolean nodeChanged;

        do {
            nodeChanged = false;

            for (int i = 0; i < solution.getNodes().size(); i++) {
                Node oldNode = solution.getNodes().get(i);

                for (Node newNode : candidates) {

                    if (!solution.contains(newNode)) {

                        double newWeight = solution.calculateWeightChangeNode(oldNode, newNode);

                        // Keep the first change that improves the solution
                        if (newWeight > solution.getTotalWeight()) {
                            solution.changeNode(oldNode, newNode);
                            nodeChanged = true;
                            break;
                        }
                    }
                }
            }

        } while (nodeChanged);
    }

}

Next: CWP — Description →

Navigation Menu

Uh oh!

MaxMin Diversity Problem (MMDP) — Implementation

Design

Problem data — package `mmdp.instance`

The search — package `mmdp.algorithm`

Entry point — package `mmdp`

Implementation Details

Problem data: Instance and Node

Solution

The multi-start driver

Construction: random selection

Improvement: best and first improvement

Uh oh!

FilesExpand file tree

mmdp-implementation.md

Latest commit

History

mmdp-implementation.md

File metadata and controls

MaxMin Diversity Problem (MMDP) — Implementation

Design

Problem data — package mmdp.instance

The search — package mmdp.algorithm

Entry point — package mmdp

Implementation Details

Problem data: Instance and Node

Solution

The multi-start driver

Construction: random selection

Improvement: best and first improvement

Problem data — package `mmdp.instance`

The search — package `mmdp.algorithm`

Entry point — package `mmdp`