Operations Research 09A: Integer Programming vs Linear Programming Relaxation

Operations Research 09A: Integer Programming vs Linear Programming Relaxation


In this video, I’ll talk about some basic
concepts of integer programming and linear programming relaxation. An integer programming problem is an optimization
problem with integer decision variables. If all the decision variables are required
to be integers, then this problem is called a pure IP problem. If only some of the decision variables are
required to be integers, then this problem is called a mixed IP problem. If all the decision variables must be 0 or
1, then this problem is called a 0-1 IP problem or binary IP problem. In this course, we will only focus on integer
linear programming, which requires the objective function and all the constraints to be linear. The LP problem obtained by omitting all the
integer or 0-1 constraints on variables is called the LP relaxation of the IP problem. Let’s check some examples. This is a maximization problem with two decision
variables, x1 and x2. They are both required to be greater than
or equal to 0, and they are both required to be integer numbers. So, it is a pure IP problem. This is the second example. The only difference is that only x2 is required
to be an integer, and x1 is not required to be an integer. So, it is a mixed IP problem. This is the third example. The difference between this one and the first
one is that both x1 and x2 are required to be binary. That means, either 0 or 1. So it is a 0-1 IP problem. This is the last example. The only difference between this one and the
first one is that there is no integer requirement for the decision variables. This is a LP problem because both the objective
function and the constraint are linear. It is called the LP relaxation of the first
three examples. Now let’s answer these four questions. Question 1: Which problem’s feasible region
is larger? An IP problem or its LP relaxation? The answer is that in general the LP relaxation
has a larger feasible region. This is because the variables can take both
integer numbers and fractional numbers in the LP relaxation. Question 2: For a maximization problem, which
optimal z value is larger? An IP problem or its LP relaxation. The answer is that in general the LP relaxation
has a larger optimal z value. This is because the feasible region is larger
for the LP relaxation and it has more options or a better chance to contain the largest
z value. Similarly, for a minimization problem, in
general the LP relaxation has a smaller optimal z value. This is because the feasible region is larger
for the LP relaxation and it has more options or a better chance to contain the smallest
z value. Question 3: Which one is more difficult to
solve? An IP problem or its LP relaxation? The answer is that in general, an IP problem
is more difficult to solve than the LP relaxation. This is because we can use the simplex method
to check only the extreme points for the LP relaxation and there will be path that leads
us to the optimal solution. For the IP problem, theoretically, we need
to enumerate all the possible integer combinations in the feasible region and check their z value
before we can conclude which one or which ones are the optimal solutions. Question 4: Can we use the rounding method
to solve an IP problem? That means, after we get the optimal solution
for the decision variables to the LP relaxation, can we round these variables to the nearest
integer and claim that the rounded solution is the optimal solution to the IP problem? The answer is no. Let’s see an example. This is a IP problem with two variables, x1
and x2. We can represent it in this figure. This is the constraint. Because x1 and x2 are both integer numbers. The feasible region contains just these six
points: (0,0), (1,0), (0,1), (1,1), (0,2), (0,3). We can check the z value of each point. The optimal solution is x1=1, x2=1, z*=7. The feasible region of the LP relaxation is
marked by the shaded area. The optimal solution is this extreme point
x1=1.6, x2=0, and z*=8. If we round down to point (1, 0), the z value
is 5 and it is not optimal. If we round up to point (2, 0), this point
is not feasible because it violates the constraint. So, that’s why we cannot use the rounding
method to solve an IP problem. Okay, that is about integer programming and
linear programming relaxation. Thanks for watching.

5 thoughts on “Operations Research 09A: Integer Programming vs Linear Programming Relaxation”

  1. Hi Guys, please comment and let me know what you think about this Operations Research Open Course. Your feedback is really appreciated. If you enjoy the video, please subscribe and share. All my replies here are only related to the content in my own videos. I am afraid I won't be able to answer other questions. Thanks for your understanding.

  2. Hi,

    What's the difference between an integer programming problem and a linear integer programming problem?

Leave a Reply

Your email address will not be published. Required fields are marked *