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.

sir, will you have some courses about the system simulation?

Have you produced this video using power point ?

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.

Hi,

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

Sir can I use graphical method to solve a pure ip?