A Deep Learning Approach to Predicting Solutions in Streaming Optimisation Domains

Alissa, Mohamad; Sim, Kevin; Hart, Emma

Abstract

In the field of combinatorial optimisation, per-instance algorithm selection still remains a challenging problem, particularly with respect to streaming problems such as packing or scheduling. Typical approaches involve training a model to predict the best algorithm based on features extracted from the data, which is well known to be a difficult task and even more challenging with streaming data. We propose a radical approach that bypasses algorithm-selection altogether by training a Deep-Learning model using solutions obtained from a set of heuristic algorithms to directly predict a solution from the instance-data. To validate the concept, we conduct experiments using a packing problem in which items arrive in batches. Experiments conducted on six large datasets using batches of varying size show the model is able to accurately predict solutions, particularly with small batch sizes, and surprisingly in a small number of cases produces better solutions than any of the algorithms used to train the model.

Citation

Alissa, M., Sim, K., & Hart, E. (2020). A Deep Learning Approach to Predicting Solutions in Streaming Optimisation Domains. . https://doi.org/10.1145/3377930.3390224

• Conference Name: GECCO ’20
• Conference Location: Cancún, Mexico
• Start Date: Jul 8, 2020
• End Date: Jul 12, 2020
• Acceptance Date: Mar 20, 2020
• Publication Date: 2020-06
• Deposit Date: Apr 23, 2020
• Publicly Available Date: Jun 30, 2020
• Pages: 157-165
• DOI: https://doi.org/10.1145/3377930.3390224
• Keywords: Algorithm Selection Problem, Deep Learning, Bin-packing
• Public URL: http://researchrepository.napier.ac.uk/Output/2654979