CO227 Lecture Notes - Lecture 4: Integer Programming

• School: University of Waterloo
• Department: Combinatorics and Optimization
• Course: CO227
• Professor: Patrick Roh

Document Summary

One of the most common applications of integer programming is scheduling. A student is planning to take 5 courses this term. Each course has a class everyday at the same time. The student has a point system to rank how much he wants to take the course ( more points is better): We need to decide if the student takes course i. Let xi be a variable used to determine if the student takes course i (1=yes, 0=no) Since student can"t half-tale a course, these variables must be integers: objective function. We want to maximize the total # of points. Objective function max 4x1 + 5x2 + 2x3 + 4x4 + 3x5 + 3x6 + 2x7 + 5x8 + 1x9: constraints. The student can only take at most one class from 9-10am, course 1 or 2: The student can only take at most one class from 10-11am, courses 2,5,6: X2 + x5 + x6 <= 1.