---
title: "MINP"
year: "2021"
motto: "Optimization Algorithm"
description: "Code and design a mixed integer nested partition optimization algorithm for the investigation of the academic researcher Dr. Ebert Brea."
stack: ["cpp"]
website: "https://revistasenlinea.saber.ucab.edu.ve/index.php/tekhne/article/view/5209"
url: "https://rolandoandrade.me/projects/minp/"
author: "Rolando Andrade"
---

# MINP

> Optimization Algorithm

Code and design a mixed integer nested partition optimization algorithm for the investigation of the academic researcher Dr. Ebert Brea.

Year: 2021. Stack: cpp. Website: https://revistasenlinea.saber.ucab.edu.ve/index.php/tekhne/article/view/5209

Some problems have too many possible solutions to check them all. Finding the shortest delivery route. Scheduling shifts in a factory. Splitting resources across projects. Each new variable multiplies the number of options.

The usual methods struggle here. Brute force takes forever. Gradient descent gets stuck in local minima, good spots that are not the best one. And when some variables must be whole numbers while others can take any value, the math gets harder.

Dr. Ebert Brea at Universidad Catolica Andres Bello was developing an extension to the Nested Partitions method. He needed someone to turn his mathematical theory into working code. I joined the project to build it in C++.

## Whole numbers and fractions

The Mixed Integer Nested Partitions (MINP) algorithm solves nonlinear problems where some variables must be whole numbers. Think of choosing how many trucks to send (a whole number) and how much cargo each truck carries (any amount).

The algorithm repeats four stages until it converges:

1. **Partitioning.** It splits the search space into smaller regions. Each region holds a subset of the possible solutions.
2. **Random sampling.** It takes random samples inside each region. The samples estimate how good the solutions there might be.
3. **Finding the promising region.** Based on the samples, it picks the region that most likely holds better solutions.
4. **Checking the stopping rule.** It decides whether to stop. If not, it focuses on the promising region and splits it again.

Each round zooms in on better parts of the search space. Bad regions get dropped. Good regions get explored more deeply.

## Why the proof matters

Nested Partitions is a metaheuristic. Metaheuristics do not promise the best solution. They find good solutions in a reasonable time.

The method has a useful mathematical property. Dr. Brea proved that it converges, using Markov chain theory. Given enough iterations, the algorithm will find a global optimum. That proof is what separates a rigorous method from random guessing.

The extension to mixed integer problems added complexity. Whole number variables cannot take just any value. The partitioning scheme has to respect that, so every region contains only valid whole number combinations.

## Fast code for long experiments

The C++ code had to be fast. Research experiments often run thousands of iterations. Slow code means waiting days for results.

I organized the code around the four stages, with one module per stage. That made testing easier. We could check each stage on its own before connecting them.

Random numbers needed care. Bad randomness creates biased samples, and biased samples point the algorithm to the wrong region. I used a well tested generator and checked the statistical properties of its output.

Memory also needed attention. Each iteration creates new regions and samples. Without careful cleanup, memory use keeps growing. I tracked allocations and freed memory as soon as a region was no longer needed.

## Knowing when to stop

Deciding when to stop is hard. Stop too early and you miss better solutions. Stop too late and you waste computing time.

Dr. Brea developed a new stopping rule for the paper. It tracks how much the best solution found so far has improved over recent iterations. When the improvement stalls, the algorithm stops.

To implement it, I kept a history. Each iteration records its best solution. The stopping rule reads that history and computes how fast things improve. The stopping threshold became a parameter you can tune.

## Testing on known problems

The algorithm needed proof that it worked. We ran it on standard benchmark problems from the literature. Their best solutions are already known, so we could check whether our code found them.

We also measured how fast it converged. How many iterations does it need? How does that change as the problem grows? The data from these experiments supported the theory in the paper.

I wrote scripts to automate the experiments. Each benchmark ran many times with different random seeds. The scripts collected statistics and generated the tables for the publication.

## From equations to code

This project showed me how academic research works. A good algorithm needs both theory and code. The math proves the method can work. The code proves it does.

I learned to read mathematical notation and turn it into code. The paper describes the algorithm with symbols and equations. Turning those into functions and loops takes careful reading.

Working with a researcher taught me patience. We went through many rounds. A new version of the paper could mean code changes. A new experiment could reveal bugs or edge cases.

The paper was published in Tekhne, the engineering journal at UCAB. Seeing my code contribute to academic knowledge felt rewarding. The algorithm now exists as working software, not only as theory.

[Book a call with Rolando](https://rolandoandrade.me/pricing/)
