1. Home

Mixed Integer Programming in Trading & Investing (Coding Example)

Contributor Image
Written By
Dan Buckley
Contributor Image
Written By
Dan Buckley
Dan Buckley is an US-based trader, consultant, and part-time writer with a background in macroeconomics and mathematical finance. He trades and writes about a variety of asset classes, including equities, fixed income, commodities, currencies, and interest rates. As a writer, his goal is to explain trading and finance concepts in levels of detail that could appeal to a range of audiences, from novice traders to those with more experienced backgrounds.
» Dan Buckley Profile Page
Updated
Mar 2, 2024

Mixed Integer Programming (MIP) is a specialized form of mathematical optimization.

It’s used in solving problems that require decision-making in discrete steps, often under complex constraints and variables.

In the context of trading and investing, MIP allows for the creation of models that can handle a range of trading/investment decisions, from portfolio optimization to order execution strategies.

 

Key Takeaways – Mixed Integer Programming in Trading & Investing

  • Versatility
    • Mixed Integer Programming (MIP) can accommodate both continuous and discrete variables.
    • Enables precise portfolio decisions including asset selection and quantity.
  • Complex Constraints Handling
    • MIP integrates complex real-world constraints such as minimum buy-in thresholds and categorical asset inclusion.
  • Strategic Optimization
    • Enables optimization of trading strategies that involve binary decisions, such as on/off signals for algorithmic trades.
  • Coding Example
    • We have an MIP coding example below.

 

Portfolio Optimization with MIP

Building Efficient Portfolios

In portfolio management, MIP is used to construct efficient portfolios.

It takes into account the discrete nature of shares (you normally can’t buy a fraction of a share, though some retail brokers allow this) and integrates various constraints like:

  • transaction costs
  • cardinality constraints (limiting the number of assets in a portfolio), and
  • minimum transaction lots

This results in portfolios that are not only theoretically good but also practical and executable.

Managing Transaction Costs & Market Impact

MIP models consider transaction costs, market impact, and potential price slippage in their calculations.

This ensures that the optimized portfolio takes into account the real-world implications of large trades.

This helps to avoid strategies that look good on paper but are costly to implement.

 

Order Execution & Trading

Algorithmic Trading Strategies

In algorithmic trading, MIP is used to develop strategies that decide not just what to trade but also how and when to trade.

It ensures that orders are executed in a way that minimizes market impact, transaction costs, and risk exposure, while considering constraints like order size, timing, and market conditions.

Scheduling and Timing Trades

MIP helps in scheduling trades to optimize execution.

It can consider factors such as:

…to determine the most cost-effective execution schedule.

 

Risk Management & Compliance

Adhering to Regulatory Constraints

MIP models are capable of incorporating regulatory and internal compliance rules into the process.

This includes constraints on position limits, leverage, concentration, and liquidity.

This ensures that portfolios are not only optimized but also fully compliant with regulatory standards.

Stress Testing & Scenario Analysis

MIP allows for stress testing of portfolios under various market scenarios.

By simulating extreme market conditions and adjusting integer variables accordingly, MIP models can help in understanding the potential impact of market events on portfolio performance and risk.

 

Math Behind Mixed Integer Programming (MIP)

The standard form of a MIP is:

  • Minimize: cT*x

Subject to:

  • Ax ≤ b (inequality constraints)
  • Aeqx = beq (equality constraints)
  • x ≥ 0 (non-negativity)
  • xj ∈ Z, j ∈ K (integer constraints)

Where:

  • x = vector of decision variables
  • c = vector of objective function coefficients A
  • Aeq = constraint matrices b,
  • beq = right hand side constraint vectors
  • K = set of indices for integer constrained variables

(And * signifies standard matrix multiplication between the vectors and matrices.)

Key Characteristics

  • The objective and constraints are linear like regular linear programming. This retains convexity and structure.
  • A subset K of the decision variables x are restricted to take only integer values. All other variables can be continuous.
  • This integrality requirement leads to a discrete, nonconvex feasible region. Finding the optimum is NP-hard*.

MIP solution methods rely on branch-and-bound along with LP relaxations to partition and gradually narrow down the feasible region to find an optimal integer solution.

So the math combines linear programs and integrality, which increases the problem complexity.

Algorithms are used to make these computationally tractable.

*NP-hard refers to a class of computational problems that are at least as difficult to solve as the hardest problems in the set of NP (Nondeterministic Polynomial time) problems.

This means problems that are NP-hard have no known efficient (polynomial time) algorithms to solve them.

The integer constraints in mixed integer linear programs (MILPs) make them NP-hard. This means there are no known polynomial-time algorithms that can optimally solve arbitrary MILPs.

The source of complexity is the combinatorial explosion of possible solutions caused by the integer constraints. As the number of integer variables grows, the number of combinations grows exponentially.

So solving MILPs is much more complex than regular linear programming. We have to intelligently search through the exponential solution space to find the optimum.

Therefore, in practice, MILP-solving algorithms like branch-and-cut don’t necessarily find the optimal solution in reasonable time.

But they use sophistical techniques to find high-quality solutions or prove optimality bounds.

 

Future Developments & Challenges

Handling Non-Linearities and Big Data

Challenges include handling non-linearities in market dynamics and integrating big data into MIP models.

This requires sophisticated algorithms and computational power to process and analyze large volumes of data for real-time decision-making.

Integration with AI and Machine Learning

The integration of MIP with AI and machine learning is promising.

Machine learning can help in better forecasts of market conditions and asset price movements, while MIP can use these predictions to make discrete trading decisions.

More and more this is how finance is going.

 

Coding Example – Mixed Integer Programming (MIP)

As covered, MIP is used in portfolio optimization when you have constraints that require integer solutions, such as when certain assets can only be bought in whole amounts or when deciding whether to include or exclude an asset entirely (binary decision).

For demonstration purposes, let’s say we want to optimize the portfolio below with a constraint that only allows holding a maximum of three out of the four asset types, which introduces a binary decision aspect.

The portfolio where we’re to choose 3 of 4 of the following:

  • Stocks: +6% forward return, 15% annualized volatility using standard deviation
  • Bonds: +4% forward return, 10% annualized volatility using standard deviation
  • Commodities: +3% forward return, 15% annualized volatility using standard deviation
  • Gold: +3% forward return, 15% annualized volatility using standard deviation

We’ll use the Python library PuLP for this example, as it is well-suited for linear and mixed-integer programming.

If PuLP is not already installed in your environment, you can install it using pip:

pip install pulp

This code snippet sets up and solves the mixed integer programming problem:

import pulp as pl

# Define the problem
problem = pl.LpProblem("Portfolio_Optimization", pl.LpMaximize)

# Decision variables: allocations to each asset, and binary inclusion variables
stocks_alloc = pl.LpVariable("Stocks_Allocation", 0, 1)
bonds_alloc = pl.LpVariable("Bonds_Allocation", 0, 1)
commodities_alloc = pl.LpVariable("Commodities_Allocation", 0, 1)
gold_alloc = pl.LpVariable("Gold_Allocation", 0, 1)

stocks_include = pl.LpVariable("Stocks_Include", 0, 1, cat='Binary')
bonds_include = pl.LpVariable("Bonds_Include", 0, 1, cat='Binary')
commodities_include = pl.LpVariable("Commodities_Include", 0, 1, cat='Binary')
gold_include = pl.LpVariable("Gold_Include", 0, 1, cat='Binary')

# Objective function: Maximize expected portfolio return
problem += 0.06 * stocks_alloc + 0.04 * bonds_alloc + 0.03 * commodities_alloc + 0.03 * gold_alloc, "Total_Return"

# Constraints
problem += stocks_alloc + bonds_alloc + commodities_alloc + gold_alloc == 1, "Total_Allocation"
problem += stocks_alloc - stocks_include <= 0, "Stocks_Inclusion"
problem += bonds_alloc - bonds_include <= 0, "Bonds_Inclusion"
problem += commodities_alloc - commodities_include <= 0, "Commodities_Inclusion"
problem += gold_alloc - gold_include <= 0, "Gold_Inclusion"
problem += stocks_include + bonds_include + commodities_include + gold_include <= 3, "Max_Assets"

# Solve the problem
problem.solve()

# Print the results
for variable in problem.variables():
    print(f"{variable.name}: {variable.varValue}")

if pl.LpStatus[problem.status] == 'Optimal':
    print("Solution is optimal.")
else:
    print("Solution not found.")

This setup introduces a binary decision variable for each asset type, which controls whether an asset is included in the portfolio.

The objective is to maximize the expected return of the portfolio, subject to the constraint that the total allocation must sum to 100%, and no more than three types of assets can be included.

This is a simplified example to demonstrate the use of MIP in portfolio optimization.

Real-world applications may involve more complex constraints and objectives.

 

Conclusion

Mixed Integer Programming offers a structured approach to solving complex problems in trading/investing.

It provides a framework for considering a multitude of factors and constraints, which can result in strategies that are not only theoretically sound but also practical and compliant with regulatory requirements.

MIP in trading and investing is likely to become more significant, especially with the integration of more advanced computational techniques and data analytics over time.

Related