Integer Linear programming problems are problems where the variable restriction is not solely to be greater or equal to zero, but also to belong to the integer realm of numbers Z, and not to the real realm, R. Therefore the solution for IP are not contiguous points.
These problems are not as easy to solve as it may seem, as rounding off the result of a linear programing problem brings three issues:
- Rounding results is an exponential function and therefore is hard and time consuming (2n).
- The best feasible solution achieved by the rounding may not be optimal.
- There can be a case where all the optimal solutions are unfeasible.
However, if when solving an Linear programming problem, the solution is an Integer, than this solution is also optimum for the Integer Linear programming version of the same problem. Unfortunately, this may not happen often enough.
One approach is to elaborate more and more constraints so that the feasible region is being reduced to only integers corner points.
another interesting studying aid:
Hillier, F.; Lieberman, G. & Liberman, G. (1990), Introduction to operations research, McGraw-Hill New York.
Hillier, F.; Lieberman, G. & Liberman, G. (1990), Introduction to operations research, McGraw-Hill New York.
No comments:
Post a Comment