Formulating Integer Linear Programs: A Rogues' Gallery

“Convincing yourself is easy, persuading a colleague is harder, but proving it to a computer is hardest of all!”—R. Hamming, ca 1985.

The art of formulating linear and integer linear programs is, well, an art: It is hard to teach, and even harder to learn. To help demystify this art, we present a set of modeling building blocks that we call “formulettes.” Each formulette consists of a short verbal description that must be expressed in terms of variables and constraints in a linear or integer linear program. These formulettes can better be discussed and analyzed in isolation from the much more complicated models they comprise. Not all models can be built from the formulettes we present. Rather, these are chosen because they are the most frequent sources of mistakes. We also present Naval Postgraduate School (NPS) format; a define-before-use formulation guide we have followed for decades to express a complete formulation.