Addressing the Diet Problem with Constraint Programming Enhanced with Machine Learning

In Colombia there is a problem related to eating habits that has its origin, mainly, in two causes: the lack of budget that allows access to a wider variety of food, and the lack of awareness among the population about their nutritional needs. To tackle this issue, a solution has been proposed using a Constraint Programming (CP) approach enhanced with Machine Learning (ML) for a version of the Diet Problem (DP). A CP model was developed to find a shopping list that meets a family’s nutritional needs while minimizing costs; and a synthetic dataset was created to test the model, which was run multiple times to collect results. Since DP is an NP-complete problem and computational time to find optimal solutions varies from one solver to another, a ML classifier was used to choose a solver that best performs in small cap time limits based on instance features (i.e., selection from an Algorithm Portfolio). After carrying out an extensive evaluation of the CP model, including our approach that implements a Classifier for algorithm selection, the model correctly selects the best solver over 68.07% of the time, for a sample of 1378 instances. By analyzing the performance of different solvers on a set of instances, it can be predicted which solver is likely to achieve the best results on new instances. This approach could be extended to tuning solver parameters, which would further improve their efficiency and effectiveness. (The dataset used for the creation of this paper is available on: https://github.com/Git-Fanfo/dataset_CCC )