Formulating Integer Linear Programs: A Rogues’ Gallery

Gerald G. Brown - gbrown@nps.edu
Robert F. Dell - Dell@nps.edu

Operations Research Department, Naval Postgraduate School, Monterey, California 93943

Abstract

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.

Download the PDF
10.1287/ited.7.2.153

Citation Information
Brown, G. Dell, R. F. 2007. Formulating Integer Linear Programs: A Rogues’ Gallery. INFORMS Trans. Ed. 7(2) 153-159. Available online at http://ite.pubs.informs.org/.

DOI: 10.1287/ited.7.2.153