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.