Formulation of integer linear programs: an example

Abstract

Integer linear programming is an important technique because of its potential applicability to a wide range of decision problems. Despite many algorithmic developments, the solution of integer linear programs may still carry a substantial computational cost. Recent research has made it apparent that the user of ILP software may be able to reduce this cost by paying careful attention to the formulation of the ILP model. Here we present illustrative computational results for several ILP formulations of a simple graph partitioning problem which may be useful pedagogically.