💰 quantitative finance

A novel robust mixed integer linear programming model for index tracking problem under no rebalancing: heuristic optimization approach

This paper proposes a novel robust mixed integer linear programming model for the index tracking problem under no rebalancing, accompanied by a hybrid heuristic algorithm that combines genetic and local search capabilities to efficiently solve the NP-hard problem and outperform commercial solvers on both in-sample and out-of-sample data.

Original authors: Danial Ramezani, Mostafa Abouei Ardakan, Mohamadreza Dehghani Ahmadabad

Published 2026-07-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Danial Ramezani, Mostafa Abouei Ardakan, Mohamadreza Dehghani Ahmadabad

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build a miniature version of a massive, chaotic orchestra. Your goal is to pick just a few instruments (maybe 10 out of hundreds) that, when played together, sound exactly like the full symphony. In the financial world, this is called Index Tracking. Instead of buying every single stock in a market (which is expensive and messy), fund managers want to pick a small "tracking portfolio" that mimics the market's performance perfectly.

For a long time, managers tried to do this by looking at how similar stocks were to each other in the past, like checking if a violin and a cello always played the same notes. But the authors of this paper, Danial Ramezani and his team, say that approach is a bit like trying to predict tomorrow's weather by only looking at yesterday's clouds. It's too shaky. They argue that relying on simple past correlations is noisy and often fails when the market changes its mood.

The New "Robust" Recipe
The team proposed a new mathematical recipe (a model) that is "robust." Think of this as building a boat that doesn't just float in calm water but is designed to survive the worst possible storm. Instead of just guessing which stocks will match the market, their model asks: "What if the relationship between these stocks goes wrong? What if they act their worst?" By planning for the worst-case scenario, the model picks a group of assets that stays steady even when things get messy.

They also introduced a special "safety buffer" in their math. Imagine you are packing a suitcase for a trip where you aren't sure if it will rain or shine. A normal packer might just guess. This new model packs for the rain and the sun, ensuring you have what you need no matter what happens. This approach allows the portfolio to track the market for a long time without needing constant adjustments (rebalancing), which saves money on transaction fees.

The Super-Search Team (GALB)
Here is the tricky part: finding the perfect 10 instruments out of hundreds is a puzzle so huge that even the world's fastest supercomputers (called "exact solvers" like CPLEX) can get stuck or take forever to solve it. The problem is "NP-hard," which is a fancy way of saying it's a maze with too many dead ends.

To solve this, the authors created a new search team called GALB. You can think of GALB as a hybrid detective.

The Genetic Algorithm (GA): This part is like a swarm of explorers running in all directions, trying different combinations of stocks. It's great at finding new, interesting paths quickly.
Local Branching: This is the "zoom-in" expert. When the explorers find a promising spot, this expert stops and looks very closely at the immediate neighborhood to see if they can tweak the solution just a little bit to make it perfect.

By mixing the "wide search" of the explorers with the "close inspection" of the expert, GALB finds high-quality solutions much faster than the slow, brute-force computers.

What the Numbers Say
The team tested their new model and their GALB search team against the old methods and the super-fast CPLEX computer using data from famous markets like the Dow Jones, Hang Seng, DAX, FTSE 100, S&P 100, and nikkei 225.

Speed: In these tests, the CPLEX computer took up to 1,800 seconds (30 minutes) to try and solve the problem for some markets, and sometimes it gave up without finding the best answer. In contrast, the GALB team found great solutions in just 120 seconds for smaller markets and 300 seconds for larger ones.
Accuracy: The portfolios created by GALB didn't just find answers quickly; they found better answers. When the team looked at how well the portfolios performed in the future (called "out-of-sample" data), the new model consistently had lower errors. For example, in the Dow Jones test, the new model had a tracking error (MAD) of 0.00402 compared to 0.00458 for the older Model 3.
Stability: The portfolios they built were made of only 10 assets (a very small number compared to the hundreds available). Despite this small size, they tracked the massive markets over long periods without needing to be constantly rearranged.

What They Say It's NOT
The authors are careful to point out what their method is not. They explicitly argue against the idea that you can just look at the past correlations of stocks to predict the future. They show that models ignoring "worst-case" scenarios (like the older Model 1) often produce portfolios that look good in the test but fail when real-world conditions change. They also note that while their heuristic (GALB) is amazing, it is an approximation; it finds solutions that are "equal or even superior" to exact solvers in a shorter time, but it doesn't guarantee a mathematical proof of perfection for every single possible scenario in the universe, though it did converge to optimal solutions for the problem sizes they tested.

The Bottom Line
In these simulations and tests, the authors suggest that their new "robust" model, paired with the GALB search team, is a powerful way to build a small, low-cost portfolio that mimics a huge market. It seems to handle the chaos of the stock market better than older methods, keeping the tracking error low and the need for expensive rebalancing to a minimum. While the paper shows these results hold up across several major global indices, the authors present this as a strong, tested approach rather than a magic bullet that solves every financial mystery in existence.

Technical Summary: A Novel Robust Mixed Integer Linear Programming Model for Index Tracking Under No Rebalancing

Problem Definition
The paper addresses the Index Tracking (IT) problem, a core challenge in passive fund management where the objective is to construct a portfolio using a subset of assets that replicates the performance of a specific market benchmark. The authors identify critical limitations in existing mathematical formulations:

Sensitivity to Correlation: Traditional models often rely on historical asset correlations, which can be noisy, unstable across different market regimes, and prone to overfitting in-sample data, leading to poor out-of-sample performance.
Rebalancing Costs: Many strategies require frequent rebalancing to maintain tracking accuracy, incurring significant transaction costs and liquidity risks.
Computational Complexity: The IT problem is NP-hard due to its combinatorial nature (selecting a subset of assets and determining weights), making it difficult to solve optimally for large datasets within reasonable timeframes using exact solvers.

The specific goal of this study is to develop a model that is robust against parameter uncertainty (specifically correlation deviations), capable of tracking indices over long periods without the need for rebalancing, and solvable efficiently via a novel heuristic.

Methodology

1. Mathematical Formulation (Model 4)
The authors propose a novel Mixed-Integer Linear Programming (MILP) formulation that integrates two distinct objectives into a single robust model:

Robustness via Correlation Uncertainty: Drawing on the robust optimization approach of Bertsimas and Sim (2003), the model incorporates a "worst-case" scenario for asset correlations. It minimizes the downside deviation of correlations ( $\Gamma$ coefficients taking their worst values) to ensure the portfolio remains effective even if correlations shift unfavorably.
Tracking Error Minimization: The model simultaneously minimizes the Mean Absolute Deviation (MAD) between the portfolio return and the benchmark index return.
Constraints: The formulation includes standard real-world constraints such as cardinality (limiting the number of assets, $K$ ), buy-in thresholds (minimum and maximum weights), and no short-selling.
Objective Function: The objective function (Eq. 19) combines the tracking error term and the robust correlation term, scaled by coefficients $\xi$ and $\psi$ to normalize values between 0 and 1.

2. Solution Approach: GALB Heuristic
Recognizing that exact solvers struggle with larger problem sizes, the authors developed GALB (Genetic Algorithm with Local Branching), a hybrid metaheuristic:

Genetic Algorithm (GA): Serves as the global search engine, utilizing crossover and mutation operators to evolve a population of candidate solutions (portfolios).
Local Branching: Integrated as a local search mechanism. When specific conditions are met (e.g., a set number of GA iterations without improvement), the algorithm applies local branching to the best solution found. This involves defining a Hamming distance neighborhood around the current best solution and solving a restricted MILP sub-problem to explore nearby solutions more deeply.
Fitness Function: A specialized fitness function (Algorithm 2) is designed to evaluate solutions without the computational overhead of running an exact solver at every step. It decodes asset weights and calculates the robust objective value directly, handling the worst-case correlation scenarios efficiently.

Experimental Setup
The study utilized data from eight major markets: Dow Jones, Hang Seng, CAC 40, EURO STOXX 50, DAX, FTSE 100, S&P 100, and Nikkei 225. Data sources included the OR-library and Yahoo Finance (July 2018 – January 2024).

Comparisons: The proposed Model 4 and GALB were compared against:
- Existing formulations (Model 1 based on correlation maximization, Model 3 based on MAD minimization).
- The commercial exact solver CPLEX.
Metrics: Performance was evaluated using Correlation ( $\rho$ ), Mean Absolute Deviation (MAD), Root Mean Squared Error (RMSE), Standard Deviation of tracking error (STD), and Beta. Both in-sample and out-of-sample results were analyzed.
Parameters: Experiments tested various uncertainty levels ( $\Gamma = 0, 50\%, 75\%, 90\%$ ) and fixed the portfolio size to 10 assets ( $K=10$ ).

Key Results

Superiority of the Robust Formulation:
- When solved by CPLEX, the proposed Model 4 consistently outperformed Model 1 and Model 3 in out-of-sample metrics across all tested markets (Dow Jones, CAC 40, EURO STOXX 50).
- Specifically, Model 4 achieved higher correlation with the index and lower tracking errors (MAD, RMSE, STD) in out-of-sample periods, demonstrating its robustness against market regime changes.
- In terms of computational efficiency, CPLEX solved the proposed model faster than Model 3 for several markets (e.g., 72s vs. 118s for Dow Jones).
Performance of the GALB Heuristic:
- Efficiency: GALB found solutions of equal or superior quality to CPLEX in significantly less time (e.g., 120s vs. 1800s for Dow Jones; 300s vs. 1800s for others).
- Optimality: For smaller problem sizes, GALB converged to the global optimum (identical results to CPLEX) in many runs, particularly when $\Gamma=0$ .
- Out-of-Sample Dominance: In most markets (Hang Seng, DAX, Nikkei 225, S&P 100), the portfolios generated by GALB (especially with $\Gamma=75\%$ or $90\%$ ) yielded better out-of-sample tracking performance than those from CPLEX, even when CPLEX had more time to search.
- No Rebalancing: The resulting portfolios, consisting of only 10 assets, tracked the indices over long periods with minimal deviation, validating the "no rebalancing" claim.

Significance and Claims
The paper claims a twofold contribution:

A Robust Formulation: It introduces a MILP model that is more robust than traditional IT models, capable of handling correlation uncertainty and delivering superior out-of-sample performance without requiring frequent rebalancing.
A Powerful Heuristic: It presents GALB, a hybrid algorithm that effectively balances global exploration (GA) and local exploitation (Local Branching). The authors assert that GALB not only solves NP-hard IT problems faster than commercial solvers but also generates portfolios that outperform exact solver solutions in terms of real-world tracking accuracy.

The study concludes that the proposed approach allows for the construction of lean portfolios (as few as 10 assets) that maintain high correlation with large, volatile indices (like Nikkei 225) over extended periods, effectively reducing management costs associated with turnover and rebalancing.

Technical Summary: A Novel Robust Mixed Integer Linear Programming Model for Index Tracking Under No Rebalancing

More like this