This paper presents an automatic method for solving discrete programming problems, where some or all variables must take only discrete values. The method is based on systematic parallel shifts in the functional hyperplane in the direction of a reduction of the maximand until a point within the ordinary linear programming set is found which has integral coordinates in the specified (x) variable dimensions. The algorithm is illustrated on two numerical examples.
The discrete programming problem is formulated as maximizing a linear function subject to constraints, with some or all variables being nonnegative integers. The method involves solving a series of subsidiary problems, each with additional constraints on the number of integer variables. The solution is constructed in the form of a tree graph, where each node represents a feasible solution or a nonfeasible solution. The algorithm systematically explores the tree, moving from one node to another until a solution is found.
The method is described in detail, including the formulation of the problem, the steps of the algorithm, and the numerical example. The algorithm is shown to be effective in finding the optimal solution for discrete programming problems, even when the number of variables is large. The method is also shown to be applicable to mixed problems, where not all variables are required to be discrete. The algorithm is designed to be susceptible to programming on an electronic computer and is not intended to replace successful ad hoc methods for particular problems. It may, in fact, be chiefly useful for testing the validity of proposed ad hoc methods for new problems.This paper presents an automatic method for solving discrete programming problems, where some or all variables must take only discrete values. The method is based on systematic parallel shifts in the functional hyperplane in the direction of a reduction of the maximand until a point within the ordinary linear programming set is found which has integral coordinates in the specified (x) variable dimensions. The algorithm is illustrated on two numerical examples.
The discrete programming problem is formulated as maximizing a linear function subject to constraints, with some or all variables being nonnegative integers. The method involves solving a series of subsidiary problems, each with additional constraints on the number of integer variables. The solution is constructed in the form of a tree graph, where each node represents a feasible solution or a nonfeasible solution. The algorithm systematically explores the tree, moving from one node to another until a solution is found.
The method is described in detail, including the formulation of the problem, the steps of the algorithm, and the numerical example. The algorithm is shown to be effective in finding the optimal solution for discrete programming problems, even when the number of variables is large. The method is also shown to be applicable to mixed problems, where not all variables are required to be discrete. The algorithm is designed to be susceptible to programming on an electronic computer and is not intended to replace successful ad hoc methods for particular problems. It may, in fact, be chiefly useful for testing the validity of proposed ad hoc methods for new problems.