## Chapter 9 Integer Programming Learning Objectives
- Navigate this page:
- Specific Problems
- The Difficulty of Solving IPs
- Example
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(x _{1}, x_{2}, .... x_{n}) > 0 is satisfied then the constraint g(x_{1}, x_{2}, .....x_{n}) 0 must be satisfied. However if f(x_{1}, x_{2}, .... x_{n}) > 0 is not satisfied then the constraint g(x_{1}, x_{2}, .....x_{n}) 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(x _{1}, x_{2}, .....x_{n}) M*y
f(x where y equals 0 or 1.
Example
Looks like x g(x Looks like x -(x y = 0, 1 Check that x _{1} > 0 implies x_{4} + x_{5} = 2.
If x Example
Either one condition is met or the other condition must be met. Either the constraint f(x 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(x _{1}, x_{2}, .... x_{n}) M*y
g(x _{1}, x_{2}, .....x_{n}) M*(1-y)
If y = 0 then f(x _{1}, x_{2}, .... x_{n}) 0 is enforced and
g(x If y = 1 then g(x _{1}, x_{2}, .... x_{n}) 0 is enforced and
f(x ## Examplef(x Looks like x g(x Looks like x 1 - x y = 0, 1 Check that if y = 0 this forces x _{2} to equal 1, and x_{3} can take on any value. If y = 1 then x_{3} must equal 1 and x_{2} 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(x Looks like OT 0 g(x 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, w_{i} and value, v_{i}. 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 (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 4x 8x x x x SP 1
x x x SP 2 SP 3 z = 47/5 z = x x SP 1
x SP 2 SP 3 z = 47/5 z = x x x SP 4 SP5
infeasible z = x x X SP 1
x _{1} 1 x_{1} = 23/52 x_{1} 0
x SP 2 SP 3 z = 47/5 z = x x x SP 4 SP5
infeasible z = 9 x x X SP 1
x _{1} 1 x_{1} = 23/52 x_{1} 0
x SP 2 SP 3 z = 47/5 z = x x x SP 4 SP5
infeasible z = 9 x X x SP 6 SP 7
z = 43/5 z = x x SP 1
x SP 2 SP 3 z = 47/5 z = x x x SP 4 SP5
infeasible z = 9 x X x SP 6 SP 7
z = 43/5 z = x x x SP 8 SP 9 infeasible z = x x X SP 1 z = 128/13 x _{1} 1 x_{1} = 23/52 x_{1} 0
x SP 2 SP 3 z = 47/5 z = x x x SP 4 SP5
infeasible z = 9 x X x SP 6 SP 7
z = 43/5 z = x x x SP 8 SP 9 infeasible z = 17/2 x x X SP 1 z = 128/13 x _{1} 1 x_{1} = 23/52 x_{1} 0
x SP 2 SP 3 z = 47/5 z = x x x SP 4 SP5
infeasible z = 9 x X x SP 6 SP 7
z = 43/5 z = x x x SP 8 SP 9 infeasible z = 17/2 x x _{2} = 0
X x _{1} 3 x_{1} 2
SP 10 SP 11 infeasible z = x x SP 1
z = 128/13 x _{1} 1 x_{1} = 23/52 x_{1} 0
x SP 2 SP 3 z = 47/5 z = x x x SP 4 SP5
infeasible z = 9 x X x SP 6 SP 7
z = 43/5 z = x x x SP 8 SP 9 infeasible z = 17/2 x x _{2} = 0
X x _{1} 3 x_{1} 2
SP 10 SP 11 infeasible z = 8 x x SP 1
z = 128/13 x _{1} 1 x_{1} = 23/52 x_{1} 0
x SP 2 SP 3 z = 47/5 z = x x x SP 4 SP5
infeasible z = 9 x X x SP 6 SP 7
z = 43/5 z = 7 x x x SP 8 SP 9 X Can’t beat z = 8 at SP 11 infeasible z = 17/2 x x _{2} = 0
X x _{1} 3 x_{1} 2
SP 10 SP 11 infeasible z = 8 x x SP 1
z = 128/13 x _{1} 1 x_{1} = 23/52 x_{1} 0
x SP 2 SP 3 z = 47/5 z = 26/3 x x x SP 4 SP5
infeasible z = 9 x X x SP 6 SP 7
z = 43/5 z = 7 x x x SP 8 SP 9 X Can’t beat z = 8 at SP 11 infeasible z = 17/2 x x _{2} = 0
X x _{1} 3 x_{1} 2
SP 10 SP 11 infeasible z = 8 x x SP 1
z = 128/13 x _{1} 1 x_{1} = 23/52 x_{1} 0
x SP 2 SP 3 z = 47/5 z = 26/3 x x SP 4 SP5 SP 12 SP 13
infeasible z = 9 infeasible z = x X x SP 6 SP 7
z = 43/5 z = 7 x x x SP 8 SP 9 X Can’t beat z = 8 at SP 11 infeasible z = 17/2 x x _{2} = 0
X x _{1} 3 x_{1} 2
SP 10 SP 11 infeasible z = 8 x x SP 1
z = 128/13 x _{1} 1 x_{1} = 23/52 x_{1} 0
x SP 2 SP 3 z = 47/5 z = 26/3 x x SP 4 SP5 SP 12 SP 13
infeasible z = 9 infeasible z = 6 x X x SP 6 SP 7 X
z = 43/5 z = 7 z = 8 at SP 11 x x x SP 8 SP 9 X Can’t beat z = 8 at SP 11 infeasible z = 17/2 x x _{2} = 0
X x _{1} 3 x_{1} 2
SP 10 SP 11 infeasible z = 8 x x Ex. Section 9.4, Problem 1 max z = 3x _{1} + x_{2}
st 5x 4x x Solving the LP relaxation yields, z = 17/3
x _{1} = 4/3
x x _{1} is okay, but x_{2} must be an integer
SP 1
x x SP 1 z = 17/3 x _{2} 1 x_{1} = 4/3 x_{2} 2
x SP 2 SP 3 z = 5.5 z = x x Candidate Solution SP 1
x _{2} 1 x_{1} = 4/3 x_{2} 2
x SP 2 SP 3 z = 5.5 z = 5.6 x x 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: |