Integer Linear ProgrammingIntroductionIn many network planning problems the variables can take only integer val-ues, because they represent choices among a finite number of possibilities.Such a mathematical program is known as integer program.Remark: Often the variables can only take two values, 0 and 1. Then wespeak about 0-1 programming.If the problem, apart from the restriction that the variables are integer val-ued, has the same formulation as a linear program, then it is called an integerlinear program (ILP).Sometimes it happens that only a subset of the variables are restricted to beinteger valued, others may vary continuously. Then we speak about a mixedprogramming task. If it is also linear, then it is a mixed ILP.A general ILP is formulated as follows:min Z = c1x1+ c2x2+ . . . + cnxnSubject toa11x1+ a12x2+ . . . + a1nxn= b1a21x1+ a22x2+ . . . + a2nxn= b2......am1x1+ am2x2+ . . . + amnxn= bmx1, . . . , xn∈ Zwhere Z denotes the set of integers.One can, of course, use other LP formulations, too, and then add the inte-grality constraint x1, . . . , xn∈ Z to obtain an ILP.Comments:The minimum can be replaced by maximum, this does not make any essentialdifference.If x1, . . . , xn∈ Z is replaced by x1, . . . , xn∈ {0, 1}, then we obtain a 0-1programming problem. Many of the tasks encountered in network designbelong to this class, as will be seen later.It is imp ortant to know that ILP is usually much more difficult to solve thanLP. Often we have to apply heuristic or approximative approaches, becausefinding the exact global optimum for a large problem is rarely
View Full Document
Unlocking...