Experiments with dynamic programming algorithms for nonseparable problems

In this paper the authors report on numerical experiments with dynamic programming algorithms designed for solving problems with nonseparable objective functions of the C-programming type. The experiments were conducted with the view to evaluate the efficiency of C-programming’s exclusionary rules when they are incorporated in the conventional parametric Lagrangian search method. Two classical nonseparable problems are considered: (1) the variance minimization problem and (2) the nonlinear fractional knapsack problem. The results indicate that the incorporation of C-programming’s exclusionary rules in the Lagrangian procedure significantly improves the efficiency of the line search procedure.