Indicate whether the following linear program is an all-integer linear program o
ID: 1721026 • Letter: I
Question
Indicate whether the following linear program is an all-integer linear program or a mixed-integer linear program.
This is a linear program.
Write the LP Relaxation for the problem but do not attempt to solve. If required, round your answers to one decimal place.
Its LP Relaxation is:
Indicate whether the following linear program is an all-integer linear program or a mixed-integer linear program.
This is a linear program.
Write the LP Relaxation for the problem but do not attempt to solve. If required, round your answers to one decimal place.
Its LP Relaxation is:
Explanation / Answer
1.By definition, Mixed integer linear programming (MILP) involves problems in which only some of the variables, xi are constrained to be integers, while other variables are allowed to be non-integers.
So as per the given constraints in the LP, we have only x2 given to be an integer but not x1. So, the given problem is a Mixed integer linear program.
Now, coming to the LP relaxation,we know that, any bounded integer variable can be expressed as a combination of binary variables. In the given problem we will consider x2 to be in [0,1]. So for LP relaxation we will convert all the integer co-efficients using the floor function of log(integer). i.e. floor(log2a)
Now, floor( log 2 (3)) = floor(1.5849) = 1. And the decimal co-efficients are kept unchanged. similarly 405 and 275 will be,( using the same floor function of log to base 2) both 8. And also
Thus, we replace 3 by 1 in the given constraint and they reduce to:
1 x1 + 1.6 x2 <= 8
1.7x1 + 1 x2 <= 8
also x2 will belong to [0,1] and x1 can take any value greater than 0
2. In the second problem since both x1 and x2 are given to be integers, this is an example of all integer linear program.