Dynamic programming in package Mathematica

¹ University of Niš, Faculty of Sciences and Mathematics, Višegradska 33, 18000 Niš, Serbia
² Laboratory “Hybrid Methods of Modelling and Optimization in Complex Systems”, Siberian Federal University, Prosp. Svobodny 79, 660041 Krasnoyarsk, Russia

^* Corresponding author: arstupin@gmail.com

Abstract

Dynamic programming (DP) is a powerful algorithmic technique for solving optimization problems by breaking them down into simpler subproblems. This paper presents an implementation of DP algorithms for two classic optimization problems: the Knapsack problem and the Traveling Salesman Problem (TSP). The solutions are developed and demonstrated using the Mathematica® programming language. For the Knapsack problem, we present two variants: with and without item repetition. The paper describes the mathematical formulation of each variant and provides detailed Mathematica code for their implementation. Examples are given to illustrate the effectiveness of the algorithms in finding optimal solutions. The TSP implementation demonstrates how DP can be applied to find the shortest Hamiltonian contour in a given network. The paper outlines the mathematical model, recurrent formula, and step-by-step solution process. An example with a four-node network is provided to showcase the algorithm's application. This work highlights the versatility of dynamic programming in solving complex optimization problems and demonstrates the effectiveness of Mathematica as a tool for implementing and visualizing these solutions. The presented algorithms and code snippets serve as valuable resources for researchers and practitioners working on similar optimization challenges.