Structured Convolutional Kernel Networks for Airline Crew Scheduling

• URL: http://arxiv.org/abs/2105.11646v1
• Date: Tue, 25 May 2021 03:47:06 GMT
• Title: Structured Convolutional Kernel Networks for Airline Crew Scheduling
• Authors: Yassine Yaakoubi, Fran\c{c}ois Soumis, Simon Lacoste-Julien
• Abstract summary: We introduce structured convolutional kernel networks (Struct-CKN), which combine CKNs from Mairal et al. (2014) in a structured prediction framework. Our experiments demonstrate that this approach yields significant improvements for the large-scale crew pairing problem.
• Score: 22.520832696173738
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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%.

Related papers

• Auto-Train-Once: Controller Network Guided Automatic Network Pruning from Scratch [72.26822499434446]
  Auto-Train-Once (ATO) is an innovative network pruning algorithm designed to automatically reduce the computational and storage costs of DNNs. We provide a comprehensive convergence analysis as well as extensive experiments, and the results show that our approach achieves state-of-the-art performance across various model architectures.
  arXiv  Detail & Related papers  (2024-03-21T02:33:37Z)
• Neural Network with Local Converging Input (NNLCI) for Supersonic Flow Problems with Unstructured Grids [0.9152133607343995]
  We develop a neural network with local converging input (NNLCI) for high-fidelity prediction using unstructured data. As a validation case, the NNLCI method is applied to study inviscid supersonic flows in channels with bumps.
  arXiv  Detail & Related papers  (2023-10-23T19:03:37Z)
• Fixing the NTK: From Neural Network Linearizations to Exact Convex Programs [63.768739279562105]
  We show that for a particular choice of mask weights that do not depend on the learning targets, this kernel is equivalent to the NTK of the gated ReLU network on the training data. A consequence of this lack of dependence on the targets is that the NTK cannot perform better than the optimal MKL kernel on the training set.
  arXiv  Detail & Related papers  (2023-09-26T17:42:52Z)
• Personalizing Federated Learning with Over-the-Air Computations [84.8089761800994]
  Federated edge learning is a promising technology to deploy intelligence at the edge of wireless networks in a privacy-preserving manner. Under such a setting, multiple clients collaboratively train a global generic model under the coordination of an edge server. This paper presents a distributed training paradigm that employs analog over-the-air computation to address the communication bottleneck.
  arXiv  Detail & Related papers  (2023-02-24T08:41:19Z)
• Convergence Rates of Training Deep Neural Networks via Alternating Minimization Methods [6.425552131743896]
  We propose a unified framework for analyzing the convergence rate of deep neural networks (DNNs) In this paper, we show the detailed local convergence exponent if the KL rate $theta$ varies in $[0,1)$.
  arXiv  Detail & Related papers  (2022-08-30T14:58:44Z)
• Better Training using Weight-Constrained Stochastic Dynamics [0.0]
  We employ constraints to control the parameter space of deep neural networks throughout training. The use of customized, appropriately designed constraints can reduce the vanishing/exploding problem. We provide a general approach to efficiently incorporate constraints into a gradient Langevin framework.
  arXiv  Detail & Related papers  (2021-06-20T14:41:06Z)
• Clustered Federated Learning via Generalized Total Variation Minimization [83.26141667853057]
  We study optimization methods to train local (or personalized) models for local datasets with a decentralized network structure. Our main conceptual contribution is to formulate federated learning as total variation minimization (GTV) Our main algorithmic contribution is a fully decentralized federated learning algorithm.
  arXiv  Detail & Related papers  (2021-05-26T18:07:19Z)
• Tailored Learning-Based Scheduling for Kubernetes-Oriented Edge-Cloud System [54.588242387136376]
  We introduce KaiS, a learning-based scheduling framework for edge-cloud systems. First, we design a coordinated multi-agent actor-critic algorithm to cater to decentralized request dispatch. Second, for diverse system scales and structures, we use graph neural networks to embed system state information. Third, we adopt a two-time-scale scheduling mechanism to harmonize request dispatch and service orchestration.
  arXiv  Detail & Related papers  (2021-01-17T03:45:25Z)
• Flight-connection Prediction for Airline Crew Scheduling to Construct Initial Clusters for OR Optimizer [23.980050729253612]
  We present a case study of using machine learning classification algorithms to initialize a large-scale commercial solver (GENCOL) Small savings of as little as 1% translate to increasing annual revenue by dozens of millions of dollars in a large airline.
  arXiv  Detail & Related papers  (2020-09-26T01:32:07Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.