Application of Supervised Machine Learning Methods on the Multidimensional Knapsack Problem

摘要

Machine Learning (ML) has gained much importance in recent years as many of its effective applications are involved in different fields, healthcare, banking, trading, gaming, etc. Similarly, Combinatorial Optimisation (CO) keeps challenging researchers by new problems with more complex constraints. Merging both fields opens new horizons for development in many areas. This study investigates how effective is to solve CO problems by ML methods. The work considers the Multidimensional Knapsack Problem (MKP) as a study case, which is an np-hard CO problem well-known for its multiple applications. The proposed approach suggests to use solutions of small-size MKP to build models with different ML methods; then, to apply the obtained models on large-size MKP to predict their solutions. The features consist of scores calculated based on information about items while the labels consist of decision variables of optimal solutions calculated from applying CPLEX Solver on small-size MKP. Supervised ML methods build models that help to predict structures of large-size MKP solutions and build them accordingly. A comparison of five ML methods is conducted on standard data set. The experiments showed that the tested methods were able to reach encouraging results. In addition, the study proposes a Genetic Algorithm (GA) that exploits ML outputs essentially in initialisation operator and to repair unfeasible solutions. The algorithm denoted GaPR explores the ML solution neighbourhood as a way of intensification to approach optimal solutions. The carried out experiments indicated that the approach was effective and competitive.