Download Integer Programming and Algebraic Geometry: A Real-World Application - Prof. Brendan E. Ha and more Study notes Mathematics in PDF only on Docsity! Lecture Notes Math 499/699 September 29, 2004 We can finally consider our first use of Algebraic Geometry in a ”real world” problem, integer programming. Let’s begin with a simple problem. Suppose that a local air freight company has only two customers, UPS and FedEx, who pay it to fly packages from Houston to Dallas. Each plane used can only carry loads up to 3700 kilos and up to 20 cubic meters. UPS places its packages into groupings weighing exactly 400 kilos and taking up 2 cubic meters of volume. The groupings from FedEx come weighing 3700 kilos and taking up 3 cubic meters. FedEx is willing to pay $15 per package for on-time delivery while UPS will only pay $11 per grouping. As the manager of the shipping company, your problem is to decide how many shipments from each of the companies should be included in each flight to maximize your revenues. Mathematically, we are saying we want to maximize 11U+15F subject to the following constraints: 4U + 5F ≤ 37 (weight limit in hundreds of kilos) 2U + 3F ≤ 20 (volume limit in cubic meters) U,F ∈ Z≥0 Notice that we need U,F to both be integers. This is an important restriction and the characteristic feature of integer programming problems. Integer programming problems are generalizations of the mathematical trans- lation of the above example. Namely, in an integer programming problem we are looking for the largest or smallest value of some linear function c1A1 + . . . + cnAn on the set of all (A1, . . . , An) ∈ Zn≥0 satisfying some set of linear inequalities: f1 = a11A1 + a12A2 + . . . + a1nAn ≤ (or ≥) b1 f2 = a21A1 + a22A2 + . . . + a2nAn ≤ (or ≥) b2 ... fs = as1A1 + as2A2 + . . . + asnAn ≤ (or ≥) bs. In addition, we assume that the Aij , bi are integers, not necessarily positive. We can go back to our example and think of it in geometric terms. We are really looking for the element (U,F ) ∈ Z2 lying in the convex polygon in R2 bounded above by the lines U + 5F = 37, 2U + 3F = 20 and below by the axes U = 0, F = 0. The polygon described is known as the feasible region. Definition. The feasible region of an integer programming problem is the set P of all (A1, . . . , An) ∈ Rn satisfying the inequalities in the statement of the problem. 1 It is possible for the feasible region to contain no integer points, and thus the problem have no solutions. Example: In R2 consider the region A + B ≤ 1 3A−B ≥ 1 2A−B ≤ 1 A,B ≥ 0 One way of solving our original problem, is to just plug the values of all of the integer valued points in our feasible region into the equation 11U + 15F and find the maximum value. It turns out to be the point (4, 4). We can do this quite quickly for our problem, but what about problems in more equations or just larger feasible regions? The general integer programming problem is known to be NP-complete. In order to discuss general integer programming problems, we can make life easier by standardizing the problems using the following observations. 1. Given a linear functional `(A1, . . . , An), we need only consider minimizing it since maximizing ` is just minimizing −`. 2. We need only consider inequalities of the form ≤ because ai1A1 + . . . + ainAn ≥ bi ⇔ −ai1A1 − . . .− ainAn ≤ −bi. 3. By introducing new ”slack variables”, we can change our inequalities to equalities. These slack variables will have coefficient zero in the linear function to be minimized. Here is an example of introducing a slack variable. Suppose you are given 3A1 −A2 + 2A3 ≤ 9. Then you can introduce an A4 ≥ 0 such that 3A1 −A2 + 2A3 + A4 = 9. Applying 1,2, and 3 above, any integer programming problem can be written in standard form: Minimize: c1A1 + . . . + cnAn subject to : a11A1 + a12A2 + . . . + a1nAn = b1 a21A1 + a22A2 + . . . + a2nAn = b2 ... as1A1 + as2A2 + . . . + asnAn = bs Aj ∈ Z≥0, j = 1, . . . , n. We can now turn our attention to solving such problems by turning them into questions about polynomials. First suppose that all of the coefficients aij , bj are nonnegative. We introduce an indeterminant zi for each of the equations in the standard form and exponentiate to obtain the equality zai1A1+ai2A2+...+ainAni = z bi i 2
