Cutwidth Problem (CWP) — Implementation

🏠 Home · ← Prev: CWP — Description

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

The complete, runnable source code is available in this repository under problems/no-framework/CWP. 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 : ordering
    ExperimentManager ..> Solution : saves + reports

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

Problem data — package `cwp.instance`

Instance: the in-memory representation of the graph — the number of vertices, the number of edges, and the adjacency matrix. It builds one Node per vertex.
Node: a vertex of an Instance; it holds its index and asks the instance whether it is connected to another vertex (isVertex returns 1 if there is an edge, 0 otherwise).
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 (all tagged with type CW_hb, the Harwell-Boeing set) 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 `cwp.algorithm`

Solution: keeps the ordered list of nodes (the permutation), evaluates the objective (the maximum cut), and implements the position-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 `cwp`

Experiment: the main program. It loads the CW_hb 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 adjacency matrix and builds one Node per vertex. Vertices are numbered from 0, and getWeight(i, j) is 1 when there is an edge between i and j.

package cwp.instance;

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

public class Instance {

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

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

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

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

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

    public int getNumEdges() {
        return numEdges;
    }

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

    public String getName() {
        return name;
    }

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

}

package cwp.instance;

public class Node {

    private int index;
    private Instance instance;

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

    public int isVertex(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 ordering (a list of nodes) and its objective value (totalWeight, the maximum cut). calculateWeightChangeNode evaluates the objective a position-swap would produce without modifying the solution — the operation used by the local search strategies — while changeNode applies the swap.

package cwp.algorithm;

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

import cwp.instance.Instance;
import cwp.instance.Node;

public class Solution {

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

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

    public void calculateWeight() {
        totalWeight = calculateWeight(nodes);
    }

    private int calculateWeight(List<Node> ordering) {
        int weight = 0;

        // The solution weight is the maximum cut of the ordering: for each
        // position, the number of edges from a node in that position or
        // before it to a node after it
        for (int i = 0; i < ordering.size(); i++) {
            int cut = 0;
            for (int j = 0; j <= i; j++) {
                for (int k = i + 1; k < ordering.size(); k++) {
                    cut += ordering.get(j).isVertex(ordering.get(k));
                }
            }

            weight = Math.max(weight, cut);
        }

        return weight;
    }

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

        // Build a new ordering with the positions of both nodes swapped
        for (Node node : nodes) {
            if (node.equals(oldNode)) {
                newNodes.add(newNode);
            } else if (node.equals(newNode)) {
                newNodes.add(oldNode);
            } else {
                newNodes.add(node);
            }
        }

        return calculateWeight(newNodes);
    }

    public void changeNode(Node oldNode, Node newNode) {
        int changes = 0;

        for (int i = 0; i < nodes.size(); i++) {
            if (nodes.get(i).equals(oldNode)) {
                nodes.set(i, newNode);
                changes++;
            } else if (nodes.get(i).equals(newNode)) {
                nodes.set(i, oldNode);
                changes++;
            }

            if (changes == 2) {
                break;
            }
        }

        calculateWeight();
    }

    public int 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 CWP is a minimization problem, "best" means the smallest objective value.

package cwp.algorithm;

import cwp.algorithm.constructive.Constructive;
import cwp.algorithm.constructive.RandomConstructive;
import cwp.algorithm.improvement.BestImprovement;
import cwp.algorithm.improvement.FirstImprovement;
import cwp.algorithm.improvement.FirstImprovement.CandidatesOrder;
import cwp.algorithm.improvement.ImprovementMethod;
import cwp.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 ordering

Constructive methods are subclasses of the abstract Constructive. The random constructive shuffles all the nodes into a random permutation.

package cwp.algorithm.constructive;

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

import cwp.algorithm.Solution;
import cwp.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 cwp.algorithm.constructive;

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

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

public class RandomConstructive extends Constructive {

    private static final Random random = new Random();

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

    @Override
    public Solution createSolution() {

        // A solution is a random ordering of all the instance nodes
        List<Node> nodes = new ArrayList<>(instance.getNodes());
        Collections.shuffle(nodes, random);

        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 cwp.algorithm.improvement;

import cwp.algorithm.Solution;

public abstract class ImprovementMethod {

    public abstract void improveSolution(Solution solution);

}

BestImprovement scans the entire swap neighborhood and applies the move that reduces the maximum cut the most, repeating until no improving move remains:

package cwp.algorithm.improvement;

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

public class BestImprovement extends ImprovementMethod {

    @Override
    public void improveSolution(Solution solution) {

        Instance instance = solution.getInstance();

        boolean nodeChanged;
        int 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 (!oldNode.equals(newNode)) {

                        int 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 cwp.algorithm.improvement;

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

import cwp.algorithm.Solution;
import cwp.instance.Instance;
import cwp.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 (!oldNode.equals(newNode)) {

                        int 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: CPH — Description →

Navigation Menu

Uh oh!

Cutwidth Problem (CWP) — Implementation

Design

Problem data — package `cwp.instance`

The search — package `cwp.algorithm`

Entry point — package `cwp`

Implementation Details

Problem data: Instance and Node

Solution

The multi-start driver

Construction: random ordering

Improvement: best and first improvement

Uh oh!

FilesExpand file tree

cwp-implementation.md

Latest commit

History

cwp-implementation.md

File metadata and controls

Cutwidth Problem (CWP) — Implementation

Design

Problem data — package cwp.instance

The search — package cwp.algorithm

Entry point — package cwp

Implementation Details

Problem data: Instance and Node

Solution

The multi-start driver

Construction: random ordering

Improvement: best and first improvement

Problem data — package `cwp.instance`

The search — package `cwp.algorithm`

Entry point — package `cwp`