previous				contents				next

3. Discrete Variables

3.1 Integer Variables

Integer variables are ones which take the values 0, 1, 2, ... N. An upper bound, N, must always be specified. These have obvious application where some material must be used in an integer multiple, e.g. bags of various items to be mixed together to make animal feed.

In practice models are never exact and it is therefore spurious to seek the purported accuracy of identifying whether a decision variable whose value in the continuous solution is 20.45 should actually be 20 or 21 (or possibly some other value). Some IP codes, such as XPRESS-MP, recognise this and enable the user to define partial integer variables, which take integer values up to some limit and continuous ones thereafter. For myself, I believe in the counting system of the Yancos people of the Amazon: "one, two, three, lots", but you may wish to count a little further before reaching "lots".

Note that within an MP model you cannot use a single integer variable as an index to a function: y = f(x), where x takes values 1, 2, 3, ... N. This can indeed be represented, but by a series of binary variables, preferably within a Special Ordered Set of type 1.

3.2 Binary Variables

By far the most frequent occurrence of an integer variable is the binary variable. Here only two values are permitted: 0 or 1. This is used to represent a yes/no decision, 1 representing "yes" and 0 "no". This is also the hardest type for an LP-based technology such as Integer Programming to handle. This is because in the continuous solution a binary variable is constrained simply to lie between 0 and 1 and so if the continuous optimum value does not happen to lie at 0 or 1 the IP algorithm must do all the work of deciding which extreme to push it to.

Contrast this with a general integer variable. If we have a general integer variable with an upper bound of 10 and it takes the value 5.5 in the continuous solution, the chances are that the optimum integer value will be 5 or 6. Further, pushing the variable to either of those values is unlikely to have as much effect on other decision variables in the solution as pushing a binary variable from, say, 0.3 to 0 or to 1. Even pushing a binary variable from 0.01 to 0 can have an enormous effect (indeed it may make the problem infeasible) because it is eliminating the activities associated with that variable entirely.

There are very many uses of binary variables. Examples of the use of individual binary variables (as opposed to binary variables grouped together into Special Ordered Sets) include:

• whether to do something or not (indicator variables);
• fixed costs;
• representing logical conditions;
• non-mutually-exclusive sets.

Binary variables are conventionally represented by the Greek letter d (delta).

previous				contents				next