Science Domain

Physics & Materials Science

Operations Research in Physical Sciences

Three fundamental OR problems from physics and materials science: predicting stable crystal structures via global optimisation, solving Ising/QUBO models that bridge statistical mechanics and combinatorial optimisation, and scheduling particle accelerator beam time as a resource-constrained project.

Science Context

New materials are discovered by finding new crystal structures. Given a chemical formula, the goal is to find the minimum-energy atomic arrangement. The search space is exponentially large and riddled with many local minima. Methods like USPEX use evolutionary algorithms, while AIRSS employs random restarts with ab-initio relaxation. Density Functional Theory (DFT) evaluates each candidate in minutes, making efficient global search critical.

Problem Statement

Continuous global optimisation over atomic positions and unit cell parameters. Energy is evaluated by DFT (approximately minutes per evaluation). USPEX uses evolutionary operators; AIRSS uses random restart with local relaxation.

Min E(x₁, ..., xₙ, a, b, c, α, β, γ) subject to: Periodic boundary conditions Space group symmetry constraints Minimum interatomic distances Fixed stoichiometry where xᵢ are fractional coordinates, (a, b, c, α, β, γ) are cell parameters, E is the DFT total energy.

Interactive Solver: 1D Lennard-Jones Crystal

A simplified 1D "crystal": atoms in a periodic box with Lennard-Jones pair potential E = Σ 4ε[(σ/r)¹² - (σ/r)⁶]. Find the arrangement that minimises total energy.

Atoms

Algorithm

Atom Positions (1D periodic box)

Best Energy per Iteration

Best Energy

Evaluations

% Improvement

Time (ms)

Evidence Base

Published

Oganov, A. R. & Glass, C. W. (2006)

Crystal structure prediction using ab initio evolutionary techniques: principles and applications.

J. Chem. Phys. 124, 244704.

Published

Pickard, C. J. & Needs, R. J. (2006)

High-pressure phases of silane.

Phys. Rev. Lett. 97, 045504.

Published

Drozdov, A. P. et al. (2019)

Superconductivity at 250 K in lanthanum hydride under high pressures.

Nature 569, 528-531.

Science Context

The Ising model (1925) describes magnetic spins on a lattice. Each spin is +1 or -1, and the system energy depends on pairwise interactions and external fields. D-Wave realised that physical quantum annealing can solve QUBO (Quadratic Unconstrained Binary Optimisation) problems by encoding them as Ising Hamiltonians. Lucas (2014) showed all 21 of Karp's NP-complete problems can be formulated as QUBO instances.

Problem Formulation

QUBO and Ising are equivalent formulations:

QUBO: min xᵀQx xᵢ ∈ {0, 1} Ising: H = -∑ᵢⱼ Jᵢⱼ sᵢsⱼ - ∑ᵢ hᵢsᵢ sᵢ ∈ {-1, +1} Mapping: sᵢ = 2xᵢ - 1 Karp's 21 NP-complete problems → QUBO: Max-Cut, Graph Coloring, Number Partitioning, SAT, Vertex Cover, Clique, Independent Set, Set Packing, Set Cover, Exact Cover, ...

Interactive Solver: QUBO-to-Ising Mapper

Select a problem, view the Q matrix heatmap, convert to Ising parameters, solve via simulated annealing with animated spin updates, and compare against brute force.

Problem

Q Matrix Heatmap

Spin Configuration (SA progress)

Ising Parameters (J coupling, h field)

Energy vs SA Step

SA Objective

Brute Force Obj

Spin Flips

SA Time (ms)

Evidence Base

Published

Lucas, A. (2014)

Ising formulations of many NP problems.

Frontiers in Physics 2, 5.

Operational

D-Wave Systems (2020)

Advantage quantum computer: system overview and performance benchmarks.

D-Wave technical datasheet.

Science Context

CERN's LHC serves 4 major experiments (ATLAS, CMS, ALICE, LHCb). Synchrotrons like ESRF allocate 40+ beamlines. Beam time is a contested, non-storable resource. Scheduling must balance physics priorities, technical maintenance stops, luminosity delivery targets, and detector readiness across a calendar year.

Problem Formulation

Resource-Constrained Project Scheduling (RCPSP) with a single shared renewable resource (the particle beam). Each experiment is a project requiring contiguous or fragmented beam-time blocks.

Min C_max (makespan / idle time) subject to: ∑ beam_usage(t) ≤ 1 ∀ time slot t (beam capacity) ∑ₙ xᵢₙ ≥ Lᵢ ∀ experiment i (luminosity req) xᵢₙ = 0 for t ∈ technical_stops xᵢₙ ∈ {0, 1} assignment variable where xᵢₙ = 1 if experiment i is scheduled at week t, Lᵢ is luminosity target for experiment i.

Interactive Solver: Simplified LHC Year

Schedule 5 experiments over a 40-week beam year with 2 fixed technical stops (weeks 16-17, 31-32). Adjust time requirements and choose an algorithm.

Algorithm

Gantt Chart (40 weeks)

Weeks Scheduled

Idle Weeks

Targets Met

Conflicts

Evidence Base

Published

Gayet, P. et al. (2009)

LHC machine scheduling and beam operation planning.

Proceedings of EPAC 2009.

Operational

Fischer, C. et al. (2016)

Optimisation of the LHC schedule for Run 2 and beyond.

CERN technical reports.

Exploring Optimisation in Physics?

From crystal structure prediction to quantum annealing and accelerator scheduling, mathematical optimisation drives discovery in the physical sciences.

Connect on LinkedIn

Disclaimer

Data shown is illustrative. Crystal energies use simplified Lennard-Jones potentials, QUBO matrices are small-scale demonstrations, and accelerator schedules are simplified for educational purposes and do not represent any actual facility's operations.