Integer programming is an extension of linear programming that permits some of the decision variables to be restricted to integer values. The method is based on the LP solution of the same problem (with all variables continuous) but adds addition bounds to force some variables to integer values. Integer programming typically uses a branch and bound technique to search the space of integer values. An all integer solution close to the LP optimum solution is first found. This then acts as a bound so that the complete set of integer values does not need to be searched. Integer programming needs close integration with a linear programming tool and is often included as part of the linear programming tool. While linear programming can deal with a very large number of decision variables and constraints the number of integer variables in the problem must be quite restricted otherwise the branch and bound search tree will be too large to be searched in reasonable time.
For the LP problem described in the Linear Programming Solutions section, perhaps the numbers of items produced per week should be integers. Running this as integer programming the solution is optimum at £421.50 with 16 item A and 83 item B, which would be expected from the LP problem.
A more typical use of integer programming is to extend the problem to see if overtime is justified. Integer variables with values 0 or 1 to represent if 7 overtime hours per week should be used, are added for each process. An overtime shift for a process costs £40. The optimum solution is now £432.55 by producing 105 of item B using overtime only for the polishing process.
With the use of integer values it is possible to build sophisticated optimisation models that investigate decisions such as opening or closing factories, purchase of new equipment, numbers of shifts and many other key decisions.
Optimal Solutions welcomes enquiries on Integer Programming, and would be pleased to offer consultancy on this, or any other aspect of Optimisation. You can get in touch by sending a message from our Contact Us page, or by calling us on the number below.