Review of Reservoir Problem OR753 October 29, 2014 Remote Sensing and GISc, IST Reservoir Model • Multipurpose Reservoir • • • • Water Supply Flood Control Recreation Hydropower • Objective Function may be related to any of the above uses. • Conflicting objectives Water Supply with Constant Release • Notation • CAP=reservoir capacity [m3] • St=storage volume at the beginning of month t [m3] • It=inflow volume during month t [m3] (known) • Rt=release volume during month t [m3] • Rmin= Required minimum release each month [m3] (known) • Smin= Required minimum storage [m3] (known) Constraints • Mass Balance Equation St = St-1+ It- Rt • Capacity Constraint St ≤ CAP St ≥ Smin Rt ≥ Rmin For all t All variables greater than or equal to zero Objective Function Minimize CAP Integer Programming Integer Programming (IP) IP is an LP in which some or all of the variables are required to be non-negative integers • Pure Integer Programming Problem • All variables are required to be Integers • Mixed Integer Programming Problem • Only some of the variables are required to be integers • LP Relaxation of the IP • LP obtained by omitting all integer constraints on variables • Optimal value for LP relaxation > optimal value of IP Example: • Pure IP • MILP • 0-1 IPs LP Relaxation Any IP may be viewed as the LP relaxation plus additional constraints (the constraints that state which variables must be integers or be 0 or 1). IP • IPs are usually much harder to solve than LPs • LP Relaxation is a less constrained version of IP • This means that the feasible region for any IP must be contained in the feasible region for the corresponding LP relaxation • For any IP that is a max problem, this implies that Optimal z-value for LP relaxation ≥ optimal z-value for IP Example • Feasible region for this problem consists of the following set of points: S {(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1)}. • Unlike the feasible region for any LP, this is not a convex set • By simply computing and comparing the z-values for each of the six points in the feasible region, we find the optimal solution is z =33, x1=0, x2=3 Properties • If the feasible region for a pure IP’s LP relaxation is bounded, then the feasible region for the IP will consist of a finite number of points • In theory, such an IP could be solved by enumerating the z-values for each feasible point and determining the feasible point having the largest z-value • The problem with this approach is that most actual IPs have feasible regions consisting of billions of feasible points • In such cases, a complete enumeration of all feasible points would require a large amount of computer time What about rounding-off IP Relaxation solution? • In our example optimal solution to the LP relaxation: x1 =13/7 and x2 = 0 • Rounding this solution yields the a possible optimal solution x1= 2, x2 = 0 This is infeasible • OR x1 =1, x2 =0 as possible optimal solution This is not optimal (x1 =0, x2 =3 is the optimal solution) Solving IP Problem • Enumeration • Branch and Bound Method Enumeration • Each variable can take a finite number of discrete (integer) values • The simple approach is to enumerate all these possibilities • Chose the best feasible solution (optimal value) • Becomes hard as number of variables increases • Example: If there are X1, X2, X3 and X4 binary (1,0) decision variables • How many possible solutions? Enumeration: Possible Solutions X1 X2 X3 X4 0 0 0 0 0 0 0 0 0 0 X1 X2 X3 X4 1 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 24 = 16 possible solution • many of these may be infeasible Conceptually simple but computationally impossible for large problems • Enumerating all possible solutions is of course not feasible when there are too many variables • If there are 100 variables • 1 billion solutions per second will require about 400 billions year • Age of Earth is = 4.54 Billions years!!!!!!!!!!!!!!!! Branch and Bound (tree search) Method • Systematically enumerating feasible solutions to find out the optimal solution • Not all of the feasible solutions are enumerated but a small fraction of them • Guarantees to find the optimal integer solution with small number of enumeration Branch and Bound: Procedure • Convert IP problem to a LP relaxation problem • Solve the problem • The optimal solution may have non-integer values of the decision variables • Select a variable with non-integer value and generate two new problems (branching) by forcing that variable to be integer 1. Original LP relaxation plus the selected variable=1 2. Original LP relaxation plus the selected variable=0 Solve these two problems • • Drop any infeasible or inferior solution • Repeat the procedure till the optimal solution is found • Note: If you solve the LP relaxation of a pure IP and obtain a solution in which all variables are integers, then the optimal solution to the LP relaxation is also the optimal solution to the IP. Branch and Bound: Example Max 30x1 + 50x2 + 40x3 + 50x4 Subject To 100x1 + 50x2 ≤ 150 45x1 + 600x2 + 900x3 + 800x4 ≤ 1,050 x1, x2, x3, x4 are binary (1,0) variables Optimal Solution: Z= 106.406; x1 = 1.5, x2 = 0, x3 = 0, x4 = 1.22813 Branch and Bound: Example Z =105.31 x1=1 x2=1 x3=0 x4=0.506 x4=1 x4=0 Z =97.08 x1=1 x2=0.3416 x3=0 x4=1 Z =98 x1=1 x2=1 x3=0.45 x4=0 x3=0 Z =80 x1=1 x2=1 x3=0 x4=0 Z =89.11 x1=1 x2=0 x3=0.227 x4=1 Z =78.75 x1=1 x2=0.175 x3=1 x4=0 x3=0 Multiple optimal solutions x2=1 x2=0 x3=1 Z =80 x1=1 x2=0 x3=0 x4=1 Infeasible x3=1 Infeasible Integer Programming: Some useful Formulation • Binary Variables (x1, x2, x3,..) • x1 and x2 are mutually exclusive (either both are absent or only one is present) • X1+X2 ≤ 1 • Either x1 or x2 is present (exactly one) • X1+X2 = 1 • At least x1 or x2 is present • X1+X2 ≥ 1 • x1 can not be present unless x2 is present • X1-X2 ≤ 0 • either both x1 and x2 are present or both are absent • X1-X2 = 0 Integer Programming: Some useful Formulation • X3 can’t be undertaken unless either X1 or X2 or both are undertaken • X 3 ≤ X1 + X2 X1 X2 0 1 1 0 1 1 0 0 X3 1, 0 1, 0 1, 0 0 • X3 should be undertaken if either or both X1 and X2 are undertaken (X3 may still be undertaken if both X1 and X2 are absent) • X3 ≥ X1 • X3 ≥ X2 X1 X2 0 1 1 0 1 1 0 0 X3 1 1 1 1, 0 • X3 will strictly and only be undertaken if either or both X1 and X2 are undertaken • X3 ≥ X1 • X3 ≥ X2 • X3 ≤ X1 + X2 X1 X2 0 1 1 0 1 1 0 0 X3 1 1 1 0 Integer Programming: Some useful Formulation • To approximate the non-linear relationship X1=X2X3 as linear relationships X1<=(X2+X3)/2 X1>=X2+X3-1 X2 X3 X1=X2X3 X1<=(X2+X3)/2 X1>=X2+X3-1 0 0 X1=0 X1<=0 X1>=-1 0 1 X1=0 X1<=0.5 X1>=0 1 0 X1=0 X1<=0.5 X1>=0 1 1 X1=1 X1<=1 X1>=1 Integer Programming: (for detailed description go through example 6, page 488 Winston) • If-Then Constraints If X1 =1 then X2=X3=0 X1 ≤ M(1-y) X2 + X3 ≤ My Where; M = is a large positive number y =1, 0 X1, X2, X3 are 0,1 • Either-Or Constraint • Let X1 is any positive number (variable) • Either X1=0 or greater than N (a given value) X1 ≤ My N-X1 ≤ M(1-y) Where y =1,0 Note: Choose value of M such that both X1 and N-X1 would never exceed M Formulating IP • Any IP, such as above, that has only one constraint is referred to as a knapsack problem. Let M1, M2, and M3 be three large positive numbers, and add the following constraints to (IP 1): Constraint 1: x1 ≤ 0 or x1 ≥ 1,000 Similarly, Constraint 2 & 3 may be formulated Constraint 4 is a straightforward resource constraint that reduces to If–Then Constraints Example: Example 9 (Winston) Where Solution • Find out optimal solution to the LP relaxation • Optimal solution to the LP relaxation is z = 165/4, x1 = 15/4, x2 = 9/4 • We know that optimal z-value for IP ≤ optimal zvalue for LP relaxation • This implies that the optimal z-value for the IP cannot exceed 165/4 • Thus, the optimal z-value for the LP relaxation is an upper bound for Telfa’s profit • Next step is to partition the feasible region for the LP relaxation to find out IP’s optimal solution Solving IPs with LINDO • Note: the shadow prices and reduced costs refer to sub-problems generated during the branch-and bound solution—not to the IP. Unlike linear programming, there is no well-developed theory of sensitivity analysis for integer programming Q 20 (Sec 9.2 Winston, pg. 504) – Homework Assignment due November 26, 2014 • WSP Publishing sells textbooks to college students. WSP has two sales reps available to assign to the A–G state area. The number of college students (in thousands) in each state is given in Figure 9. Each sales rep must be assigned to two adjacent states. For example, a sales rep could be assigned to A and B, but not A and D. WSP’s goal is to maximize the number of total students in the states assigned to the sales reps. Formulate an IP whose solution will tell you where to assign the sales reps. Then use LINDO to solve your IP. END

© Copyright 2020