Memory usage

[foobacca]

Memory usage can get really high. As the iterations continue, memory usage steadily grows. As the number of iterations goes up with the number of people in the pool to choose from, if you have thousands of people in the pool you can end up with several GB of RAM used by the end, occasionally over 10 GB. It seems it shouldn't need that much.

This issue is for discussion of ideas to address this problem.

[foobacca]

From conversation with LLM:

The Problem

Your incremental_model continuously accumulates constraints in the optimization loop (maximin.py:238, 164) without ever releasing memory. There's a coin-or/python-mip#353 about memory accumulation in CBC solver with python-mip where users report similar issues.

Options to Reduce Memory Consumption

Option 1: Periodically Rebuild the Incremental Model (Recommended)

Strategy: Every N iterations, recreate incremental_model from scratch with all current committees instead of continuously adding constraints.

Implementation:

# In _run_maximin_optimization_loop, track iterations
iteration_count = 0
REBUILD_FREQUENCY = 50  # Tune based on your needs

while True:
    iteration_count += 1

    # Rebuild model every N iterations
    if iteration_count % REBUILD_FREQUENCY == 0:
        incremental_model, incr_agent_vars, upper_bound_var = \
            _setup_maximin_incremental_model(committees, covered_agents)

    # ... rest of loop

• Pros: Simple, preserves algorithm correctness, bounded memory growth
• Cons: Some computational overhead from rebuilding
• Expected Impact: Should cap memory at rebuild frequency × constraint growth rate

Option 2: Use Model Configuration to Reduce Memory

Strategy: Tune solver parameters that affect memory usage.

Implementation (in common.py:17 and maximin.py:78):
model = mip.Model(sense=mip.MAXIMIZE)
model.verbose = 0
model.threads = 1  # Reduce from default; fewer threads = less memory
model.preprocess = 0  # Disable preprocessing to save memory
model.sol_pool_size = 1  # Only store best solution, not entire pool

• Pros: Easy to implement, no algorithm changes
• Cons: May slow down solving, limited impact
• Expected Impact: 10-30% memory reduction, but won't solve unbounded growth

Option 3: Multiprocessing Isolation (Nuclear Option)

Strategy: Run the algorithm in a subprocess that can be terminated to fully release memory.

Implementation:

from multiprocessing import Pool

def _run_maximin_in_subprocess(features, people, number_people_wanted, ...):
    return find_distribution_maximin(features, people, ...)

# Wrapper function
def find_distribution_maximin_isolated(...):
    with Pool(processes=1) as pool:
        result = pool.apply(_run_maximin_in_subprocess, args=(...))
    return result

• Pros: Guaranteed memory release
• Cons: Complexity, serialization overhead, harder to debug
• Expected Impact: Complete memory cleanup after run

Option 4: Hybrid Approach - Rebuild + Config

Strategy: Combine Option 1 and 2 for maximum effect.

• Pros: Best memory reduction
• Cons: Slightly more complex
• Expected Impact: Significant reduction (50-70% based on similar issues)

Option 5: Early Termination Criteria

Strategy: Add a maximum number of committees or iterations to prevent unbounded growth.

Implementation:

MAX_COMMITTEES = 1000  # Or based on problem size

while True:
    if len(committees) >= MAX_COMMITTEES:
        report.add_message_and_log("max_committees_reached", ...)
        # Return best solution found so far
        committee_list = list(committees)
        probabilities = _find_maximin_primal(committee_list, covered_agents)
        return committee_list, probabilities, report
    # ... rest of loop

Pros: Guaranteed termination, bounded memory
Cons: May not find optimal solution
Expected Impact: Caps maximum memory usage

My Recommendation

Start with Option 4 (Hybrid): rebuild the model periodically + reduce threads/sol_pool_size. This gives you:

• Immediate memory reduction from config changes
• Bounded growth from periodic rebuilding
• No changes to algorithm correctness
• Minimal performance impact

If that's insufficient, add Option 5 as a safety net.

Sources

• https://python-mip.readthedocs.io/en/latest/classes.html
• Memory usage accumulation in CBC solver with python-mip wrapper coin-or/python-mip#353
• https://python-mip.readthedocs.io/en/latest/intro.html
• https://www.geeksforgeeks.org/python/diagnosing-and-fixing-memory-leaks-in-python/

[pgoelz]

Thanks for documenting and thinking this through! Do you have a dataset we can run, to see if this is just a bug with the CBC solver?
If I understand your writeup right, the maximin model’s memory consumption is much larger when we keep adding constraints iteratively than if we reconstruct it with the same constraints in one go. I don’t see a clear reason why this should be the case, and coin-or/python-mip#353 also sounds like it’s a bug.
If this is indeed the case, I wonder if it’s a better use of development time to move the implementation from CBC to a (hopefully) more stable solver like HiGHS?

[foobacca]

Quite a bit of work has been done in PR #67, which is now merged. It provides Highspy as an alternative to python-mip. The current implementation with Highspy is much better on memory usage, but takes 2-3x as long. See the PR for full details.

[foobacca]

Noticed that coin-or/python-mip#419 is another python-mip issue about memory usage. That one says that 1.13 was fine but 1.14.2 had exploding memory usage.

We can try with 1.17 and see what happens.

[foobacca]

Summary Table

Solver	Duration (mm:ss)	Peak memory usage (MB)	Total num allocations (billion)
MIP 1.15	15:10	1900	3.16
MIP 1.17 (CBC)	27:33	443.2	3.09
MIP 1.17 (HIGHS)	31:24	279.6	5.71
Highspy 1.13	37:05	259.3	6.07

MIP 1.17

MIP 1.17 is out! This appears to have solved the memory leak - but also made the speed more like highspy above. Well, a bit faster, with a bit higher memory usage

Duration: 0:27:32.913000
Total number of allocations: 3086307730
Peak memory usage: 443.2 MB

(Other graphs are on this comment on PR 67.)

MIP 1.17 with HIGHS backend

This time with mip 1.17 but create a mip model with HIGHS solver instead of CBC solver.

Duration: 0:31:24.009000
Total number of allocations: 5714625319
Peak memory usage: 279.6 MB

This was done by installing mip[highs] and then:

--- a/src/sortition_algorithms/committee_generation/solver.py
+++ b/src/sortition_algorithms/committee_generation/solver.py
@@ -298,7 +298,9 @@ def __init__(
 
         self._mip = _mip_module
         # Default to MAXIMIZE, will be changed when set_objective is called
-        self._model = self._mip.Model()
+        # self._model = self._mip.Model()
+        self._model = self._mip.Model(solver_name="HIGHS")
+        # for mip 1.17 we can use HIGHS with self._mip.Model(solver_name="HIGHS")
         self._model.verbose = 1 if verbose else 0

I will edit the comment to add the results when the run has finished.

[foobacca]

I've since added settings for the solver backend - we now have:

• highspy
• mip (which uses the CBC backend)
• mip-cbc (as above)
• mip-highs (mip uses HIGHS backend itself - requires the highsbox package to be installed)
• mip-gurobi (mip uses the gurobi backend - requires access to the gurobi package - either paid for or academic access)

So future profiling runs can include all of the above more easily.