An Introduction to Optimization, 4th Edition

CHAPTER 19

INTEGER LINEAR PROGRAMMING

19.1 Introduction

This chapter is devoted to linear programs with the additional constraint that the solution components be integers. Such problems are called integer linear programming (ILP) (or simply integer programming) problems, and arise naturally in many practical situations. For example, in Example 15.1, the decision variables represent production levels, which we allowed to take real values. If production levels correspond to actual numbers of products, then it is natural to impose the constraint that they be integer valued. If we expect solutions that are very large in magnitude, then ignoring the integer constraint might have little practical consequence. However, in cases where the solution is a relatively small integer (on the order of 10, say), then ignoring the integer constraint could lead to dramatically erroneous solutions.

Throughout this section, we use the notation for the set of integers, ⁿ the set of vectors with n integer components, and ^{m × n} the set of m × n matrices with integer entries. Using this notation, we can express an ILP problem in following form:

19.2 Unimodular Matrices

There is a class of ILP problems that ...