Class Notes (806,783)
York University (33,491)
Marketing (184)
MKTG 2030 (72)
Ben Kelly (12)
Lecture

# Lecture4.pdf

13 Pages
39 Views

School
York University
Department
Marketing
Course
MKTG 2030
Professor
Ben Kelly
Semester
Winter

Description
Omis2010 – Lecture 4 Integer Linear Programming Integer Programming • Linear programming allows us to solve large -scale problems. It gives answers in terms of continuous variables • However, there are many situations where we need solutions to problems which are not allowed to fall in a continuous range Integer Programming (ILP) • An integer programming (ILP) in which all variables are required to be integers is called a pure/all integer programming problem. • An IP in which only some of the variables are required to be integers is called a mixed integer programming problem. • An integer programming problem in which all the variables must be 0 or 1 is called a binary IP or a 0-1 integer program. Integrality Conditions MAX: 350 X1+ 300 X2 } profit S.T.: 1 X1+ 1 X2200 } filters 9X1 + 6 X2≤ 1566 } labour 12 + 16 ≤ 2880 } bolts X1 X2 X1 X2≥ 0 } non-negativity X1,nd X2 must be integers } integrality Integrality conditions are easy to state but make the problem much more difficult (and sometimes impossible) to solve. Relaxation • Original ILP MAX: 2X1+ 3X 2 S.T.: X + 3X ≤ 8.25 1 2 2.5X1+ X ≤28.75 X1, 2 ≥ 0 X1, 2 must be integers • LP Relaxation MAX: 2X1+ 3X 2 S.T.: X + 3X ≤ 8.25 1 2 2.5X1+ X ≤28.75 Omis2010 – Lecture 4 Integer Linear Programming X1, 2 ≥ 0 When solving an LP relaxation, sometimes you “get lucky” and obtain an integer feasible solution. But what if you don’t? Integer Feasible vs. LP Feasible Region Bounds • The optimal solution to an LP relaxation of an ILP problem gives us a bound on the optimal objective function value. • For maximization problems, the optimal relaxed objective function values is an upper bound on the optimal integer value. • For minimization problems, the optimal relaxed objective function values is a lower bound on the optimal integer value. Rounding • It is tempting to simply round a fractional solution to the closest integer solution. • In general, this does not work reliably: – The rounded solution may be infeasible. Omis2010 – Lecture 4 Integer Linear Programming – The rounded solution may be suboptimal. How Rounding Down Can Result in an Infeasible Solution Example: All-Integer LP • Consider the following all -integer linear program: Max 3x1+ 2x 2 s.t. 3x 1 x <29 x1+ 3x 2 7 -x1+ x 2 1 x1, 2 > 0 and integer • LP Relaxation Solving the problem as a linear program ignoring the integer constraints, the optimal solution to the linear program gives fractional values for both x and x . From the graph 1 2 we see that the optimal solution to the linear program is: x = 2.5, x = 1.5, z = 10.5 1 2 Omis2010 – Lecture 4 Integer Linear Programming Rounding Up If we round up the fractional solutio1 (x = 2.5, x = 1.5) to the LP relaxation problem, 2 we get x1= 3 and x2= 2. From the graph we see that this point lies outside the feasible region, making this solution infeasible. Rounding Down By rounding the optimal solution down to x = 2, x = 1, we see that this solution 1 2 indeed is an integer solution within the feasible region, and substituting in the objective function, it gives z = 8. We have found a feasible a ll-integer solution, but have we found the OPTIMAL all-integer solution? --------------------- The answer is NO! The optimal solution is 1 = 3 and 2 = 0 giving z = 9, as evidenced in the next slide. • Complete Enumeration of Feasible ILP Solutions There are eight feasible integer solutions to this problem: x1 x2 z 1. 0 0 0 2. 1 0 3 3. 2 0 6 4. 3 0 9 ← optimal solution 5. 0 1 2 6. 1 1 5 7. 2 1 8 8. 1 2 7 Omis2010 – Lecture 4 Integer Linear Programming Branch-and-Bound • The Branch-and-Bound (B&B) algorithm can be used to solve ILP problems. • Requires the solution of a series of LP problems termed “candidate problems”. • Theoretically, this can solve any ILP. • Practically, it often takes LOTS of computational effort (and time). Stopping Rules • Because B&B can take so long, most ILP packages allow you to specify a suboptimality tolerance factor. • This allows you to stop once an integer solution is found that is within some % of the globa l optimal solution. • Bounds obtained from LP relaxations are helpful here. – Example • LP relaxation has an optimal obj. value of \$64,306. • 95% of \$64,306 is \$61,090. • Thus, an integer solution with obj. value of \$61,090 or better must be within 5% of the optimal solution. An Employee Scheduling Problem: Air-Express Defining the Decision Variables X1 = the number of workers assigned to shift 1 X2 = the number of workers assigned to shift 2 X3 = the number of workers assigned to shift 3 X4 = the number of workers assigned to shift 4 X5 = the number of workers assigned to shift 5 Omis2010 – Lecture 4 Integer Linear Programming X6 = the number of workers assigned to shift 6 X7 = the number of workers assigned to shift 7 Shifts
More Less

Related notes for MKTG 2030

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.