Integer Programming for Land Allocation

1. WOOD 492 MODELLING FOR DECISION SUPPORT Lecture 16 Integer Programming

2. Example: land Allocation An area of land, divided into three types Three land uses: Timber, Forage, and Recreation Maximum budget Costs and revenues for each land use option Some external requirements Objective: maximize net profits Oct 15, 2012 Wood 492 - Saba Vahid 2 Example 8

3. Oct 15, 2012 3 Why Integer Programming? Discrete inputs and outputs e.g. selecting the number of shifts for a production facility (1,2, etc.) Assigning equipment or personnel to production tasks (cant assign 1.5 machines or half a person to do a task!) Wood 492 - Saba Vahid

4. Oct 15, 2012 4 Binary (yes/no) variables Variables are either 1(yes) or 0 (no) Facility Location problem (a location is either selected or not) Road building Harvesting a block Network problems (selecting a minimum distance/cost path from A to B in a network) Why Integer Programming? Wood 492 - Saba Vahid

5. Oct 15, 2012 5 Logical conditions: if {x} , then {y} If product A is made, then product B should be made too If an activity is selected, it should be performed completely (all of a harvest block must be harvested) Select one of a few possible options (selecting a cutting pattern) Why Integer Programming? Wood 492 - Saba Vahid

6. Oct 15, 2012 6 Solve the LP relaxation and round the answers effective when solution values are sufficiently large (errors may be ignored) Normally the rounded answers are not feasible, or are far from optimal ( example ) Exhaustive search of all feasible points Computationally infeasible due to exponential growth of the number of answers Solution Approach Wood 492 - Saba Vahid

7. Oct 15, 2012 7 Rounding LP Solutions Rounded solutions are not feasible (1,2) or (2,2) 0 1 2 3 4 1 2 x 2 x 1 LP relaxation feasible region Optimal solution for LP relaxation (1.5,2) 0 1 2 3 x 1 1 2 x 2 Z (objective function, Max) Optimal solution for LP relaxation (2,1.8) Rounded solution is not optimal (2,1) or infeasible (2,2) Optimal Integer solution (0,2) Back Z (objective function, Max) Wood 492 - Saba Vahid

8. Oct 15, 2012 8 Branch and Bound Divide and conquer! Divide problem into smaller problems by portioning the feasible solution region Cutting Planes Solve the LP relaxation of the problem If answers are integer : Done! Otherwise, add constraints until you reach an integer answer Solution Approach Wood 492 - Saba Vahid

9. Next Class Integer formulation examples Branch and bound Oct 15, 2012 9 Wood 492 - Saba Vahid