What is Mixed-Integer Linear Programming?
When trying to solve optimization problems in programming, you must find the right algorithm for the job as they are often designed for specific types and categories of problems. One such category of algorithms is solvers. They are a type of mathematical program whose only purpose is to solve or optimize problems that are represented by a series of equations.
Let’s have a look at one particular type; the Mixed-Integer Linear Programming (MILP) solver. These solvers operate over real numbers but the equations are restricted to linear equalities and inequalities such as the ones below.
The most important equation is your objective function, the one which the solver will try to either maximize or minimize depending on what you are looking for. For example, take the optimization function below:
If we try to maximize that function while respecting the constraints defined in the previous equations, we would have to try various assignments to x, y, and z until we found the highest objective value. The result for the above would be x = 6, y = 1, and z = 1 for a maximum output of 1 from the objective function.
This is called linear programming (LP) but that’s only half of a MILP solver. The mixed-integer (MI) part comes from a need to introduce either binary (0 or 1) or integer (whole numbers) variables into the problem. This can be a common requirement especially when you need to use constraints like the step function below:
A MILP will solve this type of problem by first solving the LP and assigning a real number to the MI variable. Then it will run a separate algorithm (like branch and bound) to assign a new value to that variable and re-run the LP solver. It will repeat this process until all MI variables are assigned and it found the optimal answer (might need to try all permutations). Note that re-running the LP solver does not mean that it starts from scratch, it simply re-evaluates the equations that have been impacted by the assignment of the particular MI variable.
Introducing MI variables into a given problem should not be done lightly, especially if you need to add a lot of them, as it makes the problem NP-Hard (non-deterministic polynomial-time). NP-hard is a classification of difficulty given to programming problems that cannot be solved deterministically in polynomial-time or, in laymen’s terms, it has the possibility of not being solvable in any reasonable amount of time.
With a basic understanding of MILP out of the way, why would you use it? Any problem that can be modelled with linear inequalities, for the most part, and isn’t so simple that a more basic algorithm is sufficient, would benefit from leveraging it. That’s a bit broad though so let’s be more specific. Common applications include optimizing resource allocations like minimizing manufacturing or labour costs, optimizing business operations by finding the optimal amount of units to sell to maximize profits, or how to logistically get a job done in the minimum amount of time (source).
Personally, I am particularly interested in the financial application of MILP solvers. There are a lot of mathematical rules in finance that translate rather well to linear inequalities. Some of those include maximizing asset and liability allocations, minimizing taxes, and optimizing government benefits and tax credits. Putting all of those together has resulted in a complex financial planning engine called Allswealth. It’s an enormous system of equations, built upon all of the Canadian financial rules, that is designed to optimize one’s finances over their entire life.
Here’s an example for Canada’s Old Age Security (OAS). Its rules are that you can get paid $626.49 / month (not taxable) when you are 65 years or older as long as you make less than $129,581 in taxable income. If your income is more than $79,054, it will be partially clawed back at a rate of 15% of every dollar over that threshold. There is also a rule that says you can delay starting your OAS up to 5 years and receive an increase of 0.6% per delayed month to your paid amount but it will not be considered for the sake of brevity. There are other rules around eligibility but we will not focus on those either.
Let’s translate those rules into linear inequalities! Note that taxable income (ti) will be assumed to have other equations in the system that governs its assignment.
- To start, let’s break down the taxable income (ti) into the various parts that are impacted by thresholds
2. Let’s assign the OAS amount (oas)
3. Introduce a binary variable (z). This is necessary since the optimization algorithm will “game” the above equations and avoid putting anything in (b) in equation 1 given that it will have a negative impact on equation 2 and nothing is restricting (c ) from simply encompassing the entire value of (ti).
We want (z) to act as a logic operator to tell us if we are using (c ), and if so, we floor (oas) to 0 since the taxable income (ti) will be above the maximum threshold.
As we saw earlier, this kind of step function cannot be achieved with linear inequalities and must be a binary variable that will obey the following constraints:
4. Add another equation to force (oas) to 0 when (z) is 1.
5. Add the OAS variable to pre-existing income equations (not shown here) so that the remuneration is felt
6. Repeat this process for every tax year so that the OAS amount is considered throughout the user’s entire life.
With those equations, we’ve described how to add support for OAS to a pre-existing system of equations that describe one’s future finances. That system is now equipped to consider potentially lowering someone’s taxable income for any given year (by using non-taxable income sources like a TFSA) in exchange for increasing their OAS benefits. That’s the power of levering MILP for finances; using optimization to make complex financial decisions that may seem simple at first but have complex consequences like a push-pull relationship with regards to increasing taxable income.
That was just a taste of MILP but if you want to learn more, you can read this great article by Brilliant which goes more in-depth into the problem and even explains how the solver approaches finding a solution. Or if you want another example of what MILP can do in finance, head over to this Allswealth blog post to read about how it optimizes RRSPs and TFSAs when contributions can’t be maximized to either.
