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 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.
By far the most frequent occurrence of an integer variable is the 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 δ (delta).
Within an MP model we may wish to define a binary variable, δ, which is to take the value 1 if some activity is carried out, e.g. a new factory is built, and 0 otherwise. In order to do this we must do two things: - define the decision variable δ as a binary variable;
- specify constraints which relate the value of δ to the consequences of building or not building the factory.
Suppose that we have decision variables, x
When δ takes the value 1, this permits each x There are several points to note here: - we could have used any upper bound on the value of x
_{r}as the coefficient of δ instead of X_{MAXr}; - we could have implemented the restriction as a single constraint on the total quantity of raw material processed: Σ
_{r}x_{r}- X_{TOTMX}δ ≤ 0 where X_{TOTMX}is the maximum total quantity of raw material which can be processed; - we have not forced δ to be 0 if all the x
_{r}'s are zero.
There is a good reason for using as tight a bound as the coefficient of the δ as we can obtain. We are constructing the δ
variable for a purpose, e.g. to impose a fixed cost, FIXCST, on it for
building the factory. When we come to solve the problem, the first
stage is to solve the problem as an LP. The model may decide that it
wants to use some of the x
Using a higher limit instead of X What would be the effect of implementing the relationship between the δ variable and the x Thus
the tightness of the individual constraints compared with the aggregate
constraint depends on the relationship between the limits which apply
in each case. But there is a complication: the continuous solution will
reflect the constraints which are included in the model. Thus if the
optimum solution without any fixed cost would be x What about including the individual constraints In this model there would be no point in imposing a constraint which forced δ = 0 if all the x What if this were not so? We should need some form of constraint
where M is some large constant. Strictly speaking, this does not impose the constraint we require. It states that δ must be 0 if Σ In practice if you find yourself needing to impose constraints both ways on some logical relationship, it is usually possible, and better, to reformulate it using a Special Ordered Set of Type 2. |

LP Training > 5. Integer Programming >