Minimal Inequalities and Subadditive Duality

Abstract

In this note, we use a duality theorem for mixed integer programs (first explicitly stated by Johnson (1973) for the one-row group problem) to characterize minimal inequalities. This characterization extends earlier results, which assumed either a rational or a bounded constraint set (Blair (1978), Jeroslow (1979), Johnson (1976)), by relaxing these assumptions either entirely or almost so. It also extends results given first by Gomory and Johnson (1969) for the group problem.