Integer Programming CIS-418
Integer Programming
• In some problems, decision variables have to be set as integers.
• For example:
– Schedulingproblems
– Choose among a set of options
– Do/Don’t-dodecisions
For example: “To be or not to be? That is the question”…
• We will focus on the last type of problems: do/don’t-do decisions, which are also known as Binary problems.
• Binary variable:
x1 Do
0 Don’tdo
Simon Business School CIS-418 Ricky Roet-Green
2
Interview schedule for a job applicant at Simon
Smith is about to graduate from University of Michigan with a PhD in Operations Management. Simon School invited her for an on-campus visit.
You have collected data on availability of different potential interviewers. Now you need to create a schedule for Smith’s interviews .
Formulate the scheduling problem as an optimization problem. What are the decision variables?
What is the objective?
What are the constraints?
Simon Business School CIS-418 Ricky Roet-Green
3
Interview schedule for a job applicant at Simon
2017-10-02
Interviewer
Start
End
Tilson
Groenevelt
Arie
Raith
Kaniel
Itenberg
Lederer
Seidmann
Dobson
Dewan
1:00 PM
1:30 PM
1:30 PM
2:00 PM
2:00 PM
2:30 PM
2:30 PM
3:00 PM
3:00 PM
3:30 PM
3:30 PM
4:00 PM
4:00 PM
4:30 PM
4:30 PM
5:00 PM
5:00 PM
5:30 PM
Key:
Not available
Available
• What is the decision here?
• Why isn’t it a Linear Programming problem?
Simon Business School CIS-418 Ricky Roet-Green
4
Interview schedule for a job applicant at Simon
2017-10-02
Interviewer
Start
End
Tilson
Groenevelt
Arie
Raith
Kaniel
Itenberg
Lederer
Seidmann
Dobson
Dewan
1:00 PM
1:30 PM
1:30 PM
2:00 PM
2:00 PM
2:30 PM
2:30 PM
3:00 PM
3:00 PM
3:30 PM
3:30 PM
4:00 PM
4:00 PM
4:30 PM
4:30 PM
5:00 PM
5:00 PM
5:30 PM
Key:
Not available
Available
• What is the decision here?
Which professor to assign for each slot.
• Why isn’t it a Linear Programming problem? We cannot assign partial professors…
Simon Business School CIS-418 Ricky Roet-Green
5
Formulate as an Integer Programming problem
Objective: Decision variables: Constraints:
Simon Business School CIS-418 Ricky Roet-Green
6
Formulate as an Integer Programming problem
Objective:
– Schedule maximum number of slots Decision variables:
– Schedule an interview with professor x at time t, 9X10 matrix
Constraints:
– Binaryvariables
– Schedule an interview only when professors are available
– Nomorethanoneinterviewperprofessor
Sum of interviews per professor ≤ 1
– Nomorethanoneprofessorperslot
Sum of all interviews per time slot ≤ 1
Go to excel file “Interview Schedule Data” and solve the problem
x 1 Schedule
0 Don’t schedule
Simon Business School CIS-418 Ricky Roet-Green
7
VBA Syntax
• Subroutine, modified in the excel spreadsheet: Sub
End Sub
• Loops: repeat the same procedure over and over again For To
Next
• Condition: If
Else End if
Simon Business School
CIS-418 Ricky Roet-Green
8
Integer vs. Linear programming
• Even with a linear objective and constraints the problem is difficult. The LP algorithm finds corner solutions, but these may not be integers.
• How we find the solution?
– Comparebetweenallintegerpointsthatareclosetothefeasiblearea
boundaries.
• Some LPs have the property
that solutions are integers.
Otherwise, should we round up or down?
• Relaxed LP (non-integer) solution provides
an upper-bound on the objective value
Simon Business School CIS-418 Ricky Roet-Green
9