Solving the Mixed-Integer Knapsack Problem by Decrease of Dimension and Use of Dynamic Programming

摘要

A method for finding an optimal solution of mixed-integer programming problems with one constraint is proposed. Initially, this method lessens the number of variables and the interval of their change; then, for the resulting problem one derives recurrent relations of dynamic programming that are used for computing. Using a matrix for information storage, we can solve problems of a sufficiently large dimension. The computational experiments demonstrate that the method in question is highly efficient.