  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%.
