Econometrica: Jul, 1960, Volume 28, Issue 3

An Automatic Method of Solving Discrete Programming Problems

https://doi.org/0012-9682(196007)28:3<497:AAMOSD>2.0.CO;2-M
p. 497-520

A. G. Doig, A. H. Land

In the classical linear programming problem the behaviour of continuous, nonnegative variables subject to a system of linear inequalities is investigated. One possible generalization of this problem is to relax the continuity condition the variables. This paper presents a simple numerical algorithm for the solution of programming problems in which some or all of the variables can take only discrete values. The algorithm requires no special techniques beyond these used in ordinary linear programming, and lends itself to automatic computing. Its use is illustrated on two numerical examples.