cwp-description.md

Cutwidth Problem (CWP)

🏠 Home · ← Prev: MMDP — Implementation

This document describes the Cutwidth Problem and the design of the algorithm used to solve it. The implementation details are covered in the CWP implementation notes.

Problem Description

Given an undirected graph with n vertices and e edges, the Cutwidth Problem (CWP) consists of finding a linear ordering (a permutation) of the vertices that minimizes the maximum number of edges cut between any two consecutive positions of the ordering.

• Solution structure: a permutation of all n vertices of the graph.
• Constraints: the solution must be a permutation — every vertex appears exactly once.
• Objective function: for every position i in the ordering, the cut at i is the number of edges connecting a vertex at a position ≤ i to a vertex at a position > i. The objective value of a solution is the maximum cut over all positions (a minimax objective).
• Optimization sense: minimization — the lower the maximum cut, the better the solution.

Letting $x$ be a solution (an ordering of the vertices, so $x_i$ is the position of vertex $i$), $V$ the set of vertices and $E$ the set of edges, the CWP can be formulated as:

$$ \begin{aligned} \text{minimize} \quad & z(x) = \max_{i \in V} c_i \\ \text{with} \quad & c_i = \big|, { (j,k) \in E : x_j \le x_i < x_k } ,\big| \end{aligned} $$

Here $c_i$ is the cut at vertex $i$ for a given ordering: the number of edges that leave $i$ or any vertex placed before $i$ and reach a vertex placed after $i$.

Instance format

A single instance set is used, the Harwell-Boeing collection (CW_hb). The file format is:

• A first line with the number of vertices (given twice) and the number of edges.
• One line per edge, described by the two (0-based) vertex indices it connects.

32 32 90
17 25
17 15
17 21
17 6
17 18
...

Algorithm Design

The CWP is solved with a multi-start local search: a random solution is built and (optionally) improved with a local search, and this is repeated many times within a time budget, keeping the best solution found across all restarts. Four configurations are compared experimentally, differing in how each restart is improved.

Constructive: random ordering

The constructive method builds a feasible solution as a random permutation of all the vertices of the graph (its node list is shuffled). No objective information is used.

Neighborhood and moves

The local search explores a swap neighborhood: a move exchanges the positions of two vertices in the ordering. Each candidate move is evaluated by recomputing the objective (the maximum cut) of the resulting ordering; a move is improving when it decreases that value.

Local search strategies

Two classic neighborhood-exploration strategies are compared:

• Best improvement: the whole neighborhood is built and the move that improves the solution the most is applied. This repeats from the resulting solution until no improving move exists.
• First improvement: the first move found that improves the current solution is applied immediately, without examining the rest of the neighborhood. This repeats until no improving move exists.

For first improvement, the order in which candidates are visited matters. If the order is always lexicographical (smaller indices first), the search explores more exhaustively the region around low-index vertices and is unlikely to reach other regions that might contain the optimum. For this reason the candidate order is often randomized so that all regions of the search space are visited with similar probability. Both a lexicographical and a random candidate order are compared.

Configurations compared

Four configurations are run and compared:

Configuration	Construction	Improvement
Random	random ordering	none
First improvement (random)	random ordering	first improvement, random candidate order
First improvement (lexicographical)	random ordering	first improvement, lexicographical candidate order
Best improvement	random ordering	best improvement

Pseudocode

The multi-start driver builds and improves solutions until a restart budget or a time limit is reached, keeping the best (here, "better" means a smaller maximum cut, because the CWP is a minimization problem):

$$ \begin{aligned} &\textbf{function } \text{MultiStartSearch}(\text{instance},\ \text{timeout}) \\ &\quad best := \text{null} \\ &\quad \textbf{repeat } N \textbf{ times, or until } \text{timeout} \\ &\qquad s := \text{RandomConstructive}(\text{instance}) \\ &\qquad \textbf{if } \text{improvement enabled} \textbf{ then } \text{improveSolution}(s) \\ &\qquad \textbf{if } best = \text{null} \textbf{ or } s \text{ better than } best \textbf{ then } best := s \\ &\quad \textbf{return } best \end{aligned} $$

Best improvement applies, at each step, the move with the largest improvement:

$$ \begin{aligned} &\textbf{function } \text{BestImprovement}(s) \\ &\quad \textbf{repeat} \\ &\qquad bestMove := \text{none} \\ &\qquad \textbf{for each } \text{pair of vertices } (i,j) \\ &\qquad\quad \textbf{if } \text{swapping positions of } i,j \text{ improves } s \text{ the most so far} \textbf{ then } bestMove := (i,j) \\ &\qquad \textbf{if } bestMove \ne \text{none} \textbf{ then apply } bestMove \textbf{ to } s \\ &\quad \textbf{until } bestMove = \text{none} \end{aligned} $$

First improvement applies the first improving move found over the ordered candidates:

$$ \begin{aligned} &\textbf{function } \text{FirstImprovement}(s,\ order) \\ &\quad candidates := \text{vertices sorted by } order\ (\text{random or lexicographical}) \\ &\quad \textbf{repeat} \\ &\qquad changed := \text{false} \\ &\qquad \textbf{for each } \text{vertex } i,\ \textbf{for each } j \in candidates \\ &\qquad\quad \textbf{if } \text{swapping positions of } i,j \text{ improves } s \textbf{ then} \\ &\qquad\qquad \text{apply swap};\ changed := \text{true};\ \textbf{break} \\ &\quad \textbf{until } changed = \text{false} \end{aligned} $$

---

Next: CWP — Implementation →