ABSTRACT
An integer linear program (ILP) is a linear program in which the variables have been
constrained to be integers.
Minimize: Z = cTX Subject to: AX ≤ b
X ≥ 0 X integral.
(19.1)
If all of the variables are each constrained to a finite set of values, we say that
the integer linear program is discrete. Notice that frequently the equality constraints
force the variables to be discrete, for if bi/ai,j > 0 for all j in the constraint
ai,jxj = bi,
then xj cannot exceedmj = ⌊bi/ai, j⌋. Hence xj ∈ {0, 1, 2, . . . ,mj} for all j. DEFINITION 19.1: A discrete linear program (DLP) is an integer linear program
in which the variables are a bounded
Minimize: Z = cTX Subject to: AX = b
0 ≤ xj ≤ mj , j = 1, 2, . . . , n X integral.
