Chapter 9 Integer Programming Learning Objectives
Download 87.93 Kb.
|
- Navigate this page:
- Specific Problems
- The Difficulty of Solving IPs
- Example
Chapter 9 - Integer Programming Learning Objectives
Integer Programming Overview and Definitions Defn: Integer Programming (IP) - an LP in which some or all of the variables are required to be non-negative integers. Specific ProblemsPure IP - all variables are integers. Mixed IP - some variables are integers. 0-1 IP - all variables must be equal to 0 or 1. See Example of each. Defn: LP Relaxation - the LP obtained by omitting all integer or 0-1 constraints on variables. The feasible region for the IP problem is a subset of the feasible region for the LP relaxation problem. Hence, the optimal z-value for an LP relaxation will always be equal to or better than the optimal z-value for the original IP. Ex.
max z = 3x1 + 2x2 st 2x1 + x2 4 (1) x1 + 3x2 5 (2) x1 0 (3) x2 0 (4) Pure IP
Feas. region (0,0), (0,1), (1,0), (1,1), (2,0) Mixed IP Add x2 integer Feas. region x2 = 0 and x1 2; x2 = 1 and x1 3/2 0-1 IP Add x1, x2 = 0 or 1 Feas. region (0,0), (0,1), (1,0), (1,1) The Difficulty of Solving IPsIP’s are generally harder to solve than LP’s due to the integer restriction. Unfortunately, we can not take the optimal LP solution and round it off to find the optimal IP solution. Ex. Max z = 4x1 + 5x2 s.t. 2x1 + x2 5 (1) 2x1 + 3x2 5 (2) x1 0 (3) x2 0 (4) The LP optimum is (2.5, 0) with z = 10. If we round up we get (3,0) which is infeasible. If we round down we get (2,0) which has z = 8. Is this optimal for the IP?
The feasible region becomes: (0,0), (0,1), (1,0), (1,1), (2,0) The IP optimum is (1,1) with z = 9.
Step 4 Step 5 Step 6 Step 7 Ex. Section 9.2, Problem 1 Step 2 Step 3 - See table. Step 4 Step 5 Step 6 Step 7 Special types of constraints 1) If - Then constraints If a constraint f(x1, x2, .... xn) > 0 is satisfied then the constraint g(x1, x2, .....xn) 0 must be satisfied. However if f(x1, x2, .... xn) > 0 is not satisfied then the constraint g(x1, x2, .....xn) 0 may or may not be satisfied. Example: Basketball example - if player 1 starts then players 4 and 5 must also start. In general we model it this way: -g(x1, x2, .....xn) M*y f(x1, x2, .... xn) M*(1-y) where y equals 0 or 1.
Example
Looks like x1 > 0 g(x1, x2, .....xn) Looks like x4 + x5 = 2 or x4 + x5 - 2 0
-(x4 + x5 - 2) M*y y = 0, 1 Check that x1 > 0 implies x4 + x5 = 2. If x1 = 0, then x4 and x5 can take on any value. Example
Either one condition is met or the other condition must be met. Either the constraint f(x1, x2, .... xn) 0 is satisfied or the constraint g(x1, x2, .....xn) 0 must be satisfied. However, it is okay to satisfy both of them.
Basketball example - either player 2 or 3 must start. In general we model it this way: f(x1, x2, .... xn) M*y g(x1, x2, .....xn) M*(1-y) If y = 0 then f(x1, x2, .... xn) 0 is enforced and g(x1, x2, .....xn) M*(1-y) = M is a loose constraint. If y = 1 then g(x1, x2, .... xn) 0 is enforced and f(x1, x2, .....xn) M*y = M is a loose constraint. Examplef(x1, x2, .... xn) 0 Looks like x2 1 or 1 - x2 0 g(x1, x2, .....xn) 0 Looks like x3 1 or 1 - x3 0
1 - x3 M*(1-y) y = 0, 1 Check that if y = 0 this forces x2 to equal 1, and x3 can take on any value. If y = 1 then x3 must equal 1 and x2 can take on any value. Second example: Consider a problem with a finite amount of labor available - say 40 hours per week but permit overtime. However, if overtime occurs it must be at least 4 hours. So either OT = 0 or OT 4. Thus, f(x1, x2, .... xn) 0 Looks like OT 0 g(x1, x2, .....xn) 0 Looks like OT 4 or 4 - OT 0
4 - OT M*(1-y) y = 0, 1 Check that if y = 0 this forces OT to equal 0, and 4 - OT is less than M. If y = 1 then 4 - OT 0 (thus OT 4) and OT M is satisfied. The Knapsack Problem You are going on a trip and can take a bag that can at most contain W lbs. of items. You have n items to consider taking with you. Each item i has a different weight, wi and value, vi. How do you maximize the value of the items that you take on the trip? Example
Ex. Problem 2, p. 518-9. Step 2 Step 3
Step 4
Step 5
Step 6
Step 7
What constraint would I add if I must
b) Either both the TV and stereo or neither one? Fixed Charge Problem General idea. Ex: Two machine production problem with purchase costs. There is a fixed charge for buying the machine - whether we make 1 or 1000 parts on it. Model the fixed charge with a variable that equals 0 or 1. Consider Problem 17, p. 494. Step 2 Step 3
Step 4 Step 5
Step 6 Step 7
In Class Example Problem 19, p. 494. Step 2 Step 3
Step 4 Step 5
Step 6 Step 7
Branch-and-Bound Method Overview Using the Branch-and-Bound Method to Solve a Pure IP Problem Step 1 Solve the LP Relaxation Problem. For a Max. problem the z-value to this problem is called the Upper Bound (UB). Step 2 Divide the feasible region into subsets and iteratively search for the optimal solution to the IP Problem. Step 3 Use the Last In First Out (LIFO) method of search to select the next region to examine. Note: (1) It is unnecessary to branch on a subproblem if it is fathomed. It is fathomed if: (a) It is infeasible. (b) The subproblem obtains an optimal solution in which all variables are integers. (c) The optimal z-value for the subproblem is worse than the current Lower Bound (LB). (2) A subproblem may be eliminated from consideration if (a) It is infeasible. (b) If the z-value for the subproblem is less than the LB.
st 4x1 + 9x2 26 (1) 8x1 + 5x2 17 (2) x1 0 (3) x2 0 (4) x1, x2 are integer SP 1
x1 = 23/52 x2 = 35/13
x2 = 35/13 SP 2 SP 3 
z = 47/5 z = x1 = 1 x1 = x2 = 9/5 x2 = SP 1
x2 = 35/13 SP 2 SP 3
z = 47/5 z = x1 = 1 x1 = x2 = 9/5 x2 = x SP 4 SP5
infeasible z = x1 = x2 = X SP 1
  x1 1 x1 = 23/52 x1 0
x2 = 35/13 SP 2 SP 3
z = 47/5 z = x1 = 1 x1 = x2 = 9/5 x2 = x SP 4 SP5
infeasible z = 9 x1 = 3/2 x2 = 1 X SP 1
x1 1 x1 = 23/52 x1 0
x2 = 35/13 SP 2 SP 3
z = 47/5 z = x1 = 1 x1 = x2 = 9/5 x2 = x SP 4 SP5
infeasible z = 9 x1 = 3/2
X x1 2 x1 1 SP 6 SP 7
z = 43/5 z = x1 = 2 x1 = x2 = 1/5 x2 = SP 1
x2 = 35/13 SP 2 SP 3
z = 47/5 z = x1 = 1 x1 = x2 = 9/5 x2 = x SP 4 SP5
infeasible z = 9 x1 = 3/2
X x1 2 x1 1 SP 6 SP 7
z = 43/5 z = x1 = 2 x1 = x2 = 1/5 x2 = x S infeasible z = x1 = x2 = X SP 1 z = 128/13
x1 1 x1 = 23/52 x1 0
x2 = 35/13 SP 2 SP 3
z = 47/5 z = x1 = 1 x1 = x2 = 9/5 x2 = x SP 4 SP5
infeasible z = 9 x1 = 3/2
X x1 2 x1 1 SP 6 SP 7
z = 43/5 z = x1 = 2 x1 = x2 = 1/5 x2 = x S infeasible z = 17/2 x1 = 17/8 x2 = 0 X SP 1 z = 128/13
x1 1 x1 = 23/52 x1 0
x2 = 35/13 SP 2 SP 3
z = 47/5 z = x1 = 1 x1 = x2 = 9/5 x2 = x SP 4 SP5
infeasible z = 9 x1 = 3/2
X x1 2 x1 1 SP 6 SP 7
z = 43/5 z = x1 = 2 x1 = x2 = 1/5 x2 = x S infeasible z = 17/2 x1 = 17/8 x2 = 0
  X x1 3 x1 2
SP 10 SP 11 infeasible z = x1 = x2 = SP 1
z = 128/13
x1 1 x1 = 23/52 x1 0
x2 = 35/13 SP 2 SP 3
z = 47/5 z = x1 = 1 x1 = x2 = 9/5 x2 = x SP 4 SP5
infeasible z = 9 x1 = 3/2
X x1 2 x1 1 SP 6 SP 7
z = 43/5 z = x1 = 2 x1 = x2 = 1/5 x2 = x S infeasible z = 17/2 x1 = 17/8 x2 = 0
X x1 3 x1 2
SP 10 SP 11 infeasible z = 8 x1 = 2 x2 = 0 LB = 8 SP 1
z = 128/13
x1 1 x1 = 23/52 x1 0
x2 = 35/13 SP 2 SP 3
z = 47/5 z = x1 = 1 x1 = x2 = 9/5 x2 = x SP 4 SP5
infeasible z = 9 x1 = 3/2
X x1 2 x1 1 SP 6 SP 7
z = 43/5 z = 7 x1 = 2 x1 = 1 x2 = 1/5 x2 = 1 x S infeasible z = 17/2 x1 = 17/8 x2 = 0
X x1 3 x1 2
SP 10 SP 11 infeasible z = 8 x1 = 2 x2 = 0 LB = 8 SP 1
z = 128/13
x1 1 x1 = 23/52 x1 0
x2 = 35/13 SP 2 SP 3
z = 47/5 z = 26/3 x1 = 1 x1 = 0 x2 = 9/5 x2 = 26/9 x SP 4 SP5
infeasible z = 9 x1 = 3/2
X x1 2 x1 1 SP 6 SP 7
z = 43/5 z = 7 x1 = 2 x1 = 1 x2 = 1/5 x2 = 1 x S infeasible z = 17/2 x1 = 17/8 x2 = 0
X x1 3 x1 2
SP 10 SP 11 infeasible z = 8 x1 = 2 x2 = 0 LB = 8 SP 1
z = 128/13
x1 1 x1 = 23/52 x1 0
x2 = 35/13 SP 2 SP 3
z = 47/5 z = 26/3 x1 = 1 x1 = 0
x SP 4 SP5 SP 12 SP 13
infeasible z = 9 infeasible z = x1 = 3/2 x1 =
X x1 2 x1 1 X SP 6 SP 7
z = 43/5 z = 7 x1 = 2 x1 = 1 x2 = 1/5 x2 = 1 x S infeasible z = 17/2 x1 = 17/8 x2 = 0
X x1 3 x1 2
SP 10 SP 11 infeasible z = 8 x1 = 2 x2 = 0 LB = 8 SP 1
z = 128/13
x1 1 x1 = 23/52 x1 0
x2 = 35/13 SP 2 SP 3
z = 47/5 z = 26/3 x1 = 1 x1 = 0
x SP 4 SP5 SP 12 SP 13
infeasible z = 9 infeasible z = 6 x1 = 3/2 x1 = 0
X x1 2 x1 1 X LB = 8 SP 6 SP 7 X
z = 43/5 z = 7 z = 8 at SP 11 x1 = 2 x1 = 1 x2 = 1/5 x2 = 1 x S infeasible z = 17/2 x1 = 17/8 x2 = 0
X x1 3 x1 2
SP 10 SP 11 infeasible z = 8 x1 = 2 x2 = 0 LB = 8
Ex. Section 9.4, Problem 1 max z = 3x1 + x2 st 5x1 + 2x2 10 4x1 + x2 7 x1, x2 0; x2, integer Solving the LP relaxation yields, z = 17/3
x1 = 4/3 x2 = 5/3 x1 is okay, but x2 must be an integer SP 1
x1 = 4/3 x2 = 5/3 SP 1 z = 17/3
x2 1 x1 = 4/3 x2 2
x2 = 5/3 SP 2 SP 3
z = 5.5 z = x1 = 1.5 x1 = x2 = 1 x2 = Candidate Solution SP 1
x2 1 x1 = 4/3 x2 2
x2 = 5/3 SP 2 SP 3
z = 5.5 z = 5.6 x1 = 1.5 x1 = 1.2 x2 = 1 x2 = 2 Candidate Solution LB = 5.5
To Solve an IP Using LINDO 1. Type in the problem in the same format as if it were an LP. 2. After the END command indicate which variables are integer restricted. For 0-1 variables type in the line INTE Var. Name Ex. INTE x For variables that can assume the values 0, 1, 2, .... type in the line GIN Var. Name Ex. GIN y 3. Using the DOS version of LINDO, to solve the problem use the GO command followed by the SOLU command. In the Windows version of LINDO just use the solution option. Unfortunately, sensitivity analysis cannot be performed for IP’s in the same way that it is for LPs. Chap 9 - Directory: ~banwork ~banwork -> Improved max flow path augmenting ~banwork -> Assignments and Matchings Match workers to jobs, etc ~banwork -> Maximum Flow Assumptions Download 87.93 Kb. Share with your friends:
|
2 2 x2 1
2 1 x2 0
x2 = 9/5 x2 = 26/9