15.1 Integer-valued decision variables

In the previous chapter we learnt how to solve optimization problems by finding real-valued solutions to decision problems. Recall that in the Furniture Factory example, we discovered that the optimal solution was to produce 5.93 tables, 3.70 sofas, and 0 beds. But in real-life, we cannot produce fractional tables or sofas, so this becomes a problem, which we will learn to solve in this Chapter.

In addition to decision variables like physical products (e.g., how many cars or tables to produce) that must be integer-valued, there are other examples of integer-valued optimization problems, such as:

• how many days to operate a factory; (perhaps operating costs are charged or rental contracts are executed for the whole day even if you only need some fraction of it)
• how many shifts to assign an employee; (another indivisible quantity)

Note that we can have some decision variables that are real-valued, and others that must be integer-valued. In such a case, we call this a mixed-integer optimisation problem.

We can also consider the special case of binary-valued decision variables (i.e., when your decision variable \(X\) can only take values of 1 or 0). These can be used to model binary (Yes/No) decisions:

• Should I invest or not? \(X_i\) = 1 or 0
• Is worker Bob assigned to shift \(j\)? \(X_j\) = 1 or 0

And finally, we will also see how we can represent logical constraints using binary decision variables. This allows us to encode constraints like, “if A, then B”.