Integer programming and pricing revisited

Three applications of duality are mentioned: mathematical, computational, and economic. One of the earliest attempts to produce a dual of an integer program with economic interpretations was by Gomory & Baumol in 1960. This is described together with its economic properties and some refinements and corrections. A more recent integer programming dual due to Chvátal, whose main use to date has been computational, is then described. It is shown that this can be given an economic interpretation as a generalization of Gomory & Baumol's dual which rectifies some of the deficiencies of the latter. The computational problems of calculating Chvátal's dual are remarked on.