In this further optional step, we will look at problems that look and feel like linear programming but are in fact a little different from what we have seen up until now.

Integer linear programming

In the examples and exercises we have considered so far, the values of the decision variable could be any value – that is, they could be whole numbers, or decimal numbers. In our previous example, the decision variables represent the amount of each product to make. In our examples the amount of a product could be any value, so it makes sense to make some fraction of a litre of E10 fuel (from the BioFuels Ltd example).

However, there are many practical situations in which the decision variables are constrained to take integer values only in addition to satisfying the linear constraints. By integer we mean whole numbers. The numbers (0), (1), (-1), (2), (-2) are integers where as (0.25), (-4.35) are not integers. For example, the variable might represent the number of items which are to be produced.

Consider the following example

A charity is organising a campaign and is trying to determine the best way of using the resources it has while generating the largest amount of money that it can subsequently use for its charitable work. The charity decides to make tote bags and bookmarks. Both of the items are made from the same material and they will be made by the same set of volunteers. Each item is made from stitching thread and a standard fabric in the charity’s colour scheme.

The amount of time and fabric required for each item are listed below.

• The tote bags sell for £5.50 and the bookmarks sell for £1.20. All of the money raised from the sales go to support the charity’s efforts.
• You may assume that by the end of the campaign that all of the items are sold.
• How might the charity maximise the amount of money it has to spend on its efforts?

In the example above it is not possible to make a fraction of a tote bag or a fraction of a bookmark. In any such formulation of this problem the decision variable, the number of tote bags to manufacture and the number of bookmarkers to manufacture, have to be integers.

Theoretically and computationally, although this type of problem ‘looks’ and ‘feels’ like the linear programs we have encountered so far, it is in fact a different problem. This type of problem is still an optimisation problem, but it is a different type of optimisation problem. The type of problem is called an Integer Linear Programming (ILP). We will not go into solving this type of problem exactly, however, you would likely study this if you were to study for a degree in Computer Science.

One simple approach to solving integer linear programs is to remove the constraint that the control variables have to have integer values, then solve the problem as a normal linear program, and then ‘search’ in the area for a solution where each of the decision variables only have integer values.

Solve the charity problem

Have a go at solving the charity problem above. 

Can you find an integer solution to the problem?

More than two decision variables

In the examples and exercises we have considered so far there have always been two decision variables. You might be able to think about a situation where there are more than two decision variables. The method we have introduced so far is only really possible for two decision variables, however the underlying idea can be generalised for any number of variables.

Independent of how many decision variables there are, when we are trying to find a solution to a problem we must look in the feasible region. When there are two decision variables, the feasible region is some shape in two dimensions (a polygon), and the criteria are lines on a set of 2D axis. When there are three decision variables the feasible region is some volume in three dimensions, and the criteria are planes in a three dimensional space. 

In general, when there are (n) decision variables the feasible region is some (n)-dimensional polyhedra, and the criteria are hyperplanes in an (n)-dimensional space – that got a bit mathematical!

When the number of decision variables increases it becomes impossible to use the graphical method introduced in this activity, however the idea can be generalised and implemented using a computer. The result of this generalisation is an algorithm called the Simplex algorithm. The simplex algorithm is out of the scope of this course but is one of the fundamental algorithms of the 20th century and has had a significant real world impact. By all means look it up if you are interested.