ABSTRACT
Integer programming can be considered a by-product of the impressive developments in the area of linear programming. Prior to the formal introduction of linear programming in the late 1940s, developments in discrete optimization problems were restricted to purely theoretical investigations including primarily the solution of systems of linear or nonlinear equations in discrete variables and the integer optimization of a linear (or nonlinear) function subject to a single linear (or non-linear) equality constraint. The coloring problem is perhaps the most renowned integer problem that was tackled by mathematicians prior to the formal introduction of integer programming in 1958. It seeks the determination of the minimum number of colors needed to color a (planar) map such that regions (e.g., states) with a common boundary (other than a point) must have different colors.
