# Structured Convolutional Kernel Networks for Airline Crew Scheduling

arXiv: https://arxiv.org/abs/2105.11646 · HTML: https://mlsanity.com/paper/2105.11646/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 49 references that are in the map.
- First posted on arXiv 25 May 2021.

## Builds on (most cited first, 21 of 21)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [LSTM: A Search Space Odyssey](https://mlsanity.com/paper/1503.04069/) (2015)
- [Conditional Random Fields as Recurrent Neural Networks](https://mlsanity.com/paper/1502.03240/) (2015)
- [Optimal Power Flow Using Graph Neural Networks](https://mlsanity.com/paper/1910.09658/) (2019)
- [Structured Prediction Energy Networks](https://mlsanity.com/paper/1511.06350/) (2015)
- [Convolutional Kernel Networks](https://mlsanity.com/paper/1406.3332/) (2014)
- [End-to-End Kernel Learning with Supervised Convolutional Kernel Networks](https://mlsanity.com/paper/1605.06265/) (2016)
- [Learning Deep Structured Models](https://mlsanity.com/paper/1407.2538/) (2014)
- [Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization](https://mlsanity.com/paper/1309.2375/) (2013)
- [SEARNN: Training RNNs with Global-Local Losses](https://mlsanity.com/paper/1706.04499/) (2017)
- [Deep Value Networks Learn to Evaluate and Iteratively Refine Structured Outputs](https://mlsanity.com/paper/1703.04363/) (2017)
- [Deep Structured Prediction with Nonlinear Output Transformations](https://mlsanity.com/paper/1811.00539/) (2018)
- [CRF-CNN: Modeling Structured Information in Human Pose Estimation](https://mlsanity.com/paper/1611.00468/) (2016)
- [Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields](https://mlsanity.com/paper/1504.04406/) (2015)
- [Machine Learning in Airline Crew Pairing to Construct Initial Clusters for Dynamic Constraint Aggregation](https://mlsanity.com/paper/2010.00134/) (2020)
- [Flight-connection Prediction for Airline Crew Scheduling to Construct Initial Clusters for OR Optimizer](https://mlsanity.com/paper/2009.12501/) (2020)
- [Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields](https://mlsanity.com/paper/1712.08577/) (2017)

## Built on by (most cited first, 2 of 2)

- [Learning to Schedule Heuristics for the Simultaneous Stochastic Optimization of Mining Complexes](https://mlsanity.com/paper/2202.12866/) (2022)
- [Learning on Graphs for Mineral Asset Valuation Under Supply and Demand Uncertainty](https://mlsanity.com/paper/2212.03865/) (2022)

## Abstract (arXiv)

Motivated by the needs from an airline crew scheduling application, we introduce structured convolutional kernel networks (Struct-CKN), which combine CKNs from Mairal et al. (2014) in a structured prediction framework that supports constraints on the outputs. CKNs are a particular kind of convolutional neural networks that approximate a kernel feature map on training data, thus combining properties of deep learning with the non-parametric flexibility of kernel methods. Extending CKNs to structured outputs allows us to obtain useful initial solutions on a flight-connection dataset that can be further refined by an airline crew scheduling solver. More specifically, we use a flight-based network modeled as a general conditional random field capable of incorporating local constraints in the learning process. Our experiments demonstrate that this approach yields significant improvements for the large-scale crew pairing problem (50,000 flights per month) over standard approaches, reducing the solution cost by 17% (a gain of millions of dollars) and the cost of global constraints by 97%.