Integer programming is generally from linear programming but allowing you to have integer variables, which means you may restrict the values of your variables to be integers. There are some problems linear programming is not suitable but integer programming can be helpful, for example: setup cost / time, facility location, machine scheduling, vehicle routing. All of these problems are actually doing selection or assignment – tell one person or one thing to do something at a specific time.
Formulation
Integer programming allows us to integrate some selection rules on variables:
| At least | must select at least 1 item among item 2, 3, 4: x2 + x3 + x4 >= 1 |
| At most | must select at most 2 items among item 1, 3, 4: x1 + x3 + x4 <= 2 |
| Or | select item 2 or item 3: x2 + x3 >= 1 select item 2; otherwise items 3 and 4 together: 2x2 + x3 + x4 >= 2 |
| if-else | if item 2 is selected, select item 3: x2 <= x3 if item 1 is selected, do not select items 3 and 4: 2(1 – x1) >= x3 + x4 |
Or even selection rules on constrains. Formulating constraints need to be aware of the objective functions.
Fixed-charge constraint
In general, fixed-charge constraint is in the form of x <= My. When x = 0, y could be anything; when x is positive, y must be 1. Both x and y are decision variables: x is fractional, y is binary, M is natural upper bound of x, so when y =1, this constraint actually does not impose unnecessarily strict limit to x. When x is binary, M is actually 1.
Facility Location Problems
One typical managerial decision is where to locate a scarce resource? As long as you allocating some important things, and that takes some cost and that has an impact on your performance, then it is a facility location problem. Discrete location problem means there are finite set of candidate locations, among which we want to choose a subset.
In general three are some demand nodes and some potential locations. Facility location problems are typically categorized based on their objective functions:
| Set covering | Build a minimum number of facilities to cover all demands eg: fire station, police station |
| Maximum covering | Build a given number of facilities to cover as many demands as possible eg: retail stores, cellular networks |
| Fixed charge location | Finding a balance between benefit of covering demands and cost of building facilities eg: services costs depend on distances, distribution centers. |
Machine Scheduling Problems
In many cases, jobs / tasks must be assigned to machines / agents. The simplest form is sequencing, where you have only 1 machine and multiple jobs. You need to order these jobs to minimize the number of jobs delayed. Basically there are n factorial (n!) ways to sequence them. Somehow it is impossbile to enumerate them all. Integer programming may help.
Machine scheduling problem can be categorized in multiple ways:
- Single machine serial production
- Multiple parallel machines
- Flow shop problems – a job has multiple stages, and go through same order of machines.
- Job shop problems – a job may need to go back to a particular stage, which could be much more flexible.
Vehicle Routing Problems
In many cases we need to delivery / collect item from customers in the most efficient way. From a starting point, we want to choose a route, going through each node exactly once, hoping this particular route has minimum distance. However the capacity of the vehicle should be considered, so it is probably multiple route is required.
In order to generate a tour, we need to make sure for each node, there is exactly one incoming arc and one outgoing arc. But this usually lead to sub tours. We need more constraints to prevent them.
Some Rules of Using Excel Solver
Because solving integer program is much harder and slower than solving linear program, here are some useful rules:
- if you solve some quantities, set them continuous / rIeal value.
- if you solve assignment, set them binary.
- there are few cases you need to set integer but not binary.
My Certificate
For more on Operations Research: Integer Programming, please refer to the wonderful course here https://www.coursera.org/learn/operations-research-modeling
Related Quick Recap
I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at https://KZHU.ai
Don't forget to sign up newsletter, don't miss any chance to learn.
Or share what you've learned with friends!
Tweet
