Mixed Integer Linear Programming: Formal definition and solution space
This post is a continuation of the series (previous post) on the theory and applications of Mixed Integer Linear Programming (MILP). Today, we look at
- the formal, general definition of MILP,
- how its space of feasible solutions looks like.
The first part describes how MILP models look in general, what are and are not valid MILP expressions. The second part shows a little bit of theory behind MILP, which will be useful in the future posts when we will be talking about the actual algorithm for solving MILP.
This is quite a long post, so grab a coffee and dive in!
Formal definition of Mixed Integer Linear Programming
In the following text, I will use upper-case bold letters (e.g., A, E) for matrices and lower-case bold letters for vectors (e.g., x, y). MILP is an optimisation problem that can be formulated in matrix notation as follows
Lets break this monster down. We are given a problem instance represented by matrices and vectors A, E, b, f, c, d from various domains (ℝ stands for a set of real numbers and ℤ for a set of integer numbers). For example, if we return to our budget problem from the first post, the problem instance represents assets, their costs, estimated profits and also the budget. We say that integer vector x and continuous vector y are a feasible solution to the given problem instance, if the following conditions holds
By writing these conditions component-wise, we get
where
