Rafael Julio Suseno, Nurwahyu Alamsyah, Jap Robertus Kurniawan Setiabudi, Kevin Matthew Siregar, Adri Gabriel Sooai, Benedictus Erlangga, Minarni Wartiningsih, Agustinus Bimo Gumelar, Paul L. Tahalele
Meal planning for special diets (such as keto, vegan, and gluten-free) and food allergies require an efficient computational approach due to the complexity of food combinations that meet nutritional requirements, individual preferences, and ingredient availability. This research proposes a hybrid backtracking-branch and bound algorithm-based framework to dynamically optimize food combination search. The backtracking algorithm explores the solution space with a pruned state-space search, while branch and bound ensures optimal solutions through evaluation functions based on calorie targets, macronutrient ratios (protein: fat: carbohydrate), and user preferences. The system implementation includes a graphical interface (GUI) that allows setting food preferences, allergies, and dietary restrictions. Evaluation on 100 user scenarios showed that the algorithm generated meal plans with an average deviation of 2.2% from the calorie target and 97% adherence to dietary restrictions. A case study of a keto diet user with a nut allergy achieved a nutritional composition of 54% fat, 44% protein and 2% carbohydrate. Participant testing (n=50) showed an 88% satisfaction rate in terms of personalization and ease of use. This system contributes to precision nutrition by integrating combinatorial optimization techniques and public health needs. Future developments could include the integration of machine learning for dynamic preference adaptation and expansion of the global food database. © 2025 IEEE.
Widya Mandala Surabaya Catholic University, Department of Informatics, Surabaya, Indonesia; Universitas Muhammadiyah Yogyakarta, Department of Information Technology, Daerah Istimewa, Yogyakarta, Indonesia; University Centre of Excellence in Artificial Intelligence for Tourism & Agriculture, Widya Mandira Catholic University, Dept. of Computer Science, NTT, Kupang, Indonesia; Ciputra University, School of Medicine, Public Health Department, Surabaya, Indonesia; Ciputra University, School of Medicine, Surgery Department, Surabaya, Indonesia