Representation is already a theory of the problem
Combinatorial optimisation searches a discrete feasible domain. The moment we encode that domain, we decide which relationships will be easy for the algorithm to see.
Travelling salesperson, spanning-tree, set-covering, knapsack and scheduling problems illustrate different discrete structures; N-Queens shows the close relationship with constraint satisfaction. Exact algorithms may certify an optimum, but can become computationally prohibitive on difficult instances. Metaheuristics trade that guarantee for practical search within a limited evaluation or time budget.
In a Cartesian space, variables can often be adjusted independently. In a permutation, every object must appear exactly once. Moving one item changes the context of several others. A small edit in representation can therefore become a large structural change in the candidate solution.
The dissertation distinguishes absolute position, relative order and edge relationships. These are not interchangeable. A scheduling problem may care strongly about precedence; a route may care about adjacency; an assignment may care about the position itself. COIN chooses the directed coincidence x→y as its basic learned trait and stores successor probabilities in a row-normalised matrix H. The algorithm should learn the relationship the objective actually rewards.
An algorithm does not search “the problem.” It searches the world created by its representation, operators and evaluation rule.
A neighborhood defines what “nearby” means
Swap, insertion, rotation and inversion operators create different neighborhoods. Their value depends on the structure of the task. A move that is elegant for routing may be destructive for precedence-constrained sequencing.
This explains why combinatorial optimization often becomes problem-dependent: local search needs a meaningful move operator, while genetic algorithms need crossover operators that preserve feasibility and useful structure. The more fragile the representation, the more carefully exploitation must be balanced with exploration.
Building blocks, linkage and disruption
The Building Block Hypothesis suggests that strong solutions contain smaller useful structures that can be recombined. In permutation spaces, identifying those structures is difficult. A sequence can share relative order without sharing absolute positions, and it can share edges without preserving longer order relations.
COIN ultimately focuses on pairwise incidences—directed edge relationships between items. This is a pragmatic compromise: pairwise structure is learnable with a first-order probabilistic model, even though it cannot express every higher-order dependency.
The method families around COIN
Single-solution search
Local search, simulated annealing, iterated local search, tabu search and GRASP move through neighborhoods using different rules for acceptance, memory and diversification.
Population-based search
Genetic algorithms, ant colony optimization, particle swarm optimization and EDAs use collections of candidates to preserve alternatives and learn population-level information.
Recombination
PMX, cycle, order, position, weight-mapping and edge recombination operators preserve different aspects of a permutation. None is universally correct.
Model-building
Estimation of distribution algorithms replace crossover with a learned probability model. EHBSA and NHBSA are especially relevant because they model edge or positional frequency.
A practical learning pathway
- Start with representation: what must remain feasible?
- Define similarity: which structures make two solutions meaningfully related?
- Choose the neighborhood or probabilistic dependency that expresses that similarity.
- Separate intensification from diversification.
- Only then compare algorithms.