Eurowings First Airline to Deploy Lufthansa Systems’ Renewed Cloud-Native Crew Pairing Optimizer 🔗

Foundation: Crew pairingThe problem of assembling individual flight legs into multi-day duty sequences (pairings) that cover every scheduled flight while satisfying regulatory rest rules, base-return constraints, and cost objectives. Typically modelled as a set-covering or set-partitioning problem and solved via column generation. is one of the classic large-scale optimisation problems in airline operations. The task is to assemble individual flight legs into multi-day duty sequences — called pairings — that cover every scheduled flight while satisfying crew rest regulations, base-return rules, and cost constraints. Because the number of feasible pairings grows combinatorially with the route network, airlines solve crew pairing via column generationA decomposition technique for large linear programmes with too many variables to enumerate. A master problem selects from a subset of columns (variables); a sub-problem generates new columns that can improve the objective. Widely used in crew scheduling, cutting stock, and vehicle routing.: a master problem selects the best subset of pairings from a candidate pool, while a sub-problem generates new candidate pairings that can improve the objective. This decomposition has been a mainstay of airline OR since the 1990s, with Lufthansa Systems’ crew tools among the earliest industrial implementations documented in academic literature.

Eurowings has become the first airline to go live with Lufthansa Systems’ renewed NetLine/Crew Pairing Application, a cloud-native solution with an integrated optimizer designed to produce efficient crew rotations while reducing planning complexity. The renewed application replaces legacy on-premises crew pairing infrastructure with a modern cloud architecture, aiming to give planners faster solve cycles and more flexible scenario analysis. The deployment was announced by Lufthansa Systems in November 2025 and reported by AircraftIT and Runway Girl Network.

Empirical Benchmark Shows LP Algorithm Asymptotic Behaviour Diverges Sharply by Application Class: Simplex, Interior-Point, and PDHG Scale Differently 🔗

Foundation: Every large optimisation model eventually reaches a Linear Programming (LP)Optimises a linear objective over a polyhedron defined by linear constraints; the foundational building block of MIP, column generation, and Benders decomposition. solver. Three algorithm families dominate: the simplex method (mature, warm-start friendly), interior-point methods (IPMs, dominant since the 1980s, strong for dense hard instances), and first-order methods such as the Primal-Dual Hybrid Gradient (PDHG) algorithm (re-emerging in commercial solvers over the past five years). The conventional guidance — “use IPM for hard instances, simplex for warm-starts” — rests on decades of intuition but thin empirical evidence at modern problem sizes. This paper provides that evidence.

Submitted to arXiv on 17 April 2026 (arXiv:2604.16192), Edward Rothberg (Gurobi CEO) benchmarks the asymptotic runtime growth of simplex, IPM, and PDHG across six LP application areas using large-language-model-generated instance families that are simultaneously synthetic and realistic. Regression models fit observed solve time against problem size; asymptotic exponents are compared across algorithms and application types. Key finding: asymptotic behaviour diverges meaningfully between algorithms, and the crossover points are application-class-dependent. First-order methods (PDHG) show more favourable scaling than interior-point on several application types at very large scale.

PyVRP+ Wires an LLM Metacognitive Layer into Hybrid Genetic Search, Auto-Evolving Heuristic Operators Across CVRP, VRPTW, and EVRP Benchmarks 🔗

Foundation: PyVRP is the leading open-source solver for Vehicle Routing Problems (VRPs)Assigns a fleet of vehicles to customer visits, minimising total distance or cost while satisfying capacity, time-window, and other operational constraints.. Its engine is a Hybrid Genetic Search (HGS): an evolutionary algorithm that maintains a population of routes and breeds better solutions by applying local-search mutation and crossover operators. The bottleneck has always been operator design — deciding which operators to include, how to tune their parameters, and when to invoke each requires substantial domain expertise and is rarely revisited after the solver ships. PyVRP+ asks whether a large language model can close that loop automatically.

Submitted to arXiv on 9 April 2026 (arXiv:2604.07872), the paper embeds an LLM as a metacognitive layer that observes solver state — population diversity, incumbent gap, stagnation signals — and proposes new heuristic operators expressed as Python code. These candidate operators enter a competitive selection pool evaluated on held-out instances; survivors are integrated into the search. The result is a self-evolving solver that adapts its operator set to the problem class at hand without human intervention. Benchmarks across Capacitated VRP (CVRP), VRP with Time Windows (VRPTW), and Electric VRP (EVRP) show meaningful gap reductions versus base PyVRP. Drawn from the Paper Candidates archive.

Second-Order Cone Programming

A second-order cone program is a convex optimization problem that minimizes a linear function over the intersection of an affine set and the product of second-order cones. It is more general than linear and quadratic programming, yet can be solved with comparable efficiency. — Boyd & Vandenberghe, Convex Optimization (2004), §4.4

Second-Order Cone Programming (SOCP) is a class of convex optimisation in which the feasible set is defined by one or more second-order (Lorentz) cone constraints of the form ‖Ax + b‖₂ ≤ c^Tx + d, alongside linear equality and inequality constraints. SOCP subsumes Linear Programming (LP) and convex Quadratic Programming (QP), is subsumed by Semidefinite Programming (SDP), and can be solved to global optimality in polynomial time by interior-point methods regardless of problem size.

One-line version: SOCP optimises a linear objective over cone constraints, subsumes LP and convex QP, and finds the global optimum in polynomial time — it is the natural solver for portfolio risk bounds, power flow relaxations, and any problem with Euclidean-norm constraints.

Related terms: Conditional Value at RiskExpected loss above the VaR threshold at a specified confidence level; a CVaR constraint couples naturally with SOCP position-size limits in portfolio optimisation. · Distributionally Robust OptimisationOptimises against the worst-case distribution in an ambiguity set; Wasserstein-ball DRO with piecewise-linear loss reduces to SOCP. · Stochastic ProgrammingOptimisation under uncertainty with known probability distributions; SOCP provides the inner solver for many stochastic programs with quadratic or norm-bounded recourse.

→ Full concept page