Memory usage accumulation in CBC solver with python-mip wrapper

[quanhoang-pm]

The code below solves an IP relating to an $n\times n$ chessboard using CBC solver with python-mip wrapper (version 1.15.0), with CBC Version: Trunk / Build Date: Oct 24 2021. It solves the problem repeatedly with a time limit of 60 seconds. Within the given time limit, the program only produces a feasible solution. The IP itself does not matter, it only illustrates my question in the end.

import itertools

import mip
import numpy as np


def getAllCells(n):
    return tuple(itertools.product(range(n), repeat=2))

def sameMainDiagonal(cellA, cellB):
    return cellA[0] - cellA[1] == cellB[0] - cellB[1]

def sameAntiDiagonal(cellA, cellB):
    return cellA[0] + cellA[1] == cellB[0] + cellB[1]

def getAllNeighborCells(n, cell):
    allCells = getAllCells(n)
    sameRowCells = [x for x in allCells if x[0] == cell[0] and x != cell]
    sameColumnCells = [x for x in allCells if x[1] == cell[1] and x != cell]
    sameMajorDiagonalCells = [x for x in allCells if sameMainDiagonal(x, cell) and x != cell]
    sameAntiDiagonalCells = [x for x in allCells if sameAntiDiagonal(x, cell) and x != cell]
    allNeighbors = sameRowCells + sameColumnCells + sameAntiDiagonalCells + sameMajorDiagonalCells
    assert len(set(allNeighbors)) == len(allNeighbors)
    return allNeighbors

n = 12

for iterationIndex in itertools.count(start=0):
    print(f'\n{iterationIndex = }')
    model = mip.Model(name='perQueenAttackAtMostOneQueen', solver_name='CBC')
    model.max_seconds = 60

    varsArr = np.empty(shape=(n, n), dtype=object)
    for i in range(n):
        for j in range(n):
            varsArr[i, j] = model.add_var(name=f'x_{i}_{j}', var_type=mip.BINARY)
    cellAndNeighborsDict = {cell: getAllNeighborCells(n, cell) for cell in getAllCells(n)}
    for cell in getAllCells(n):
        arr = np.array(cellAndNeighborsDict[cell])
        nNeighbors = arr.shape[0]
        allNeighborVars = varsArr[
            arr[:, 0],
            arr[:, 1],
        ]
        x, y = cell
        model.add_constr((nNeighbors - 1) * varsArr[x, y] + allNeighborVars.sum() <= nNeighbors)

    model.objective = mip.maximize(varsArr.sum())
    model.optimize()
    resultArr = np.empty(shape=(n, n), dtype=int)
    for i in range(n):
        for j in range(n):
            resultArr[i, j] = varsArr[i, j].x
    print(resultArr)
    del model

During the execution on my laptop (Ubuntu 22.04LTS), I notice that the memory usage slowly increases after each iteration. Below are the statistics

iterationIndex = 2 --> 195 MB
iterationIndex = 6 --> 250 MB
iterationIndex = 14 --> 380 MB
iterationIndex = 30 --> 700 MB
iterationIndex = 35 --> 780 MB

Intuitively, the program's memory usage should be reset to 0 after each iteration (since the model variable is re-created). I've tried del model at the end of the iteration, but it does not resolve the problem.

I wonder what is the cause of the accumulation. Right now, I suspect that the search tree stored in CBC solver still exists even after it reaches the time limit.

My questions:

• Is there something happening under the hood in CBC solver that causes the accumulation of memory usage? Does it have anything to do with python-mip wrapper?
• How to completely remove the (memory usage of) existing models in python-mip?

Side note. This question has been asked on stackoverflow, but it has received no answer until now. It is posted on CBC's discussions as well.

[jjhforrest]

It looks like a "feature" of python-mip or the interface to cbc. I added a print statement to the Cbc_C_Interface when the model is created and when it is deleted - as you can see it is odd.
Welcome to new model
Welcome to new model
Deleting model
Welcome to new model
Welcome to new model
Welcome to new model
Welcome to new model
Deleting model
Deleting model
Deleting model
Deleting model
Deleting model
Deleting model
Deleting model
Deleting model
Deleting model
Deleting model
Deleting model
Deleting model
Deleting model
Deleting model etc
If I add code to track memory usage, I get a similar picture BUT the memory used keeps dropping down to 180K bytes. So I don't think it is a problem. This was with Cbc master version.

[quanhoang-pm]

Thanks for your reply. I have one question, how can you test my code with the Cbc master version? I can think of two possibilities:

(1) My code is tested directly with the latest Cbc binaries included in python-mip wrapper,
(2) You rewrite the code in C++ to test it in Cbc.

By the way, do you guys plan to upgrade CBC binaries in python-mip in the near future? It seems to be discussed in #351.

[jjhforrest]

I looked at instructions for python-mip and cbc - and downloaded master code to /home/john/clean6 and then used coinbrew with --enable-relocatable. I built in directory /home/john/clean6/python and then added
export DYLD_LIBRARY_PATH=/home/john/clean6/python/lib:$DYLD_LIBRARY_PATH
export LD_LIBRARY_PATH=/home/john/clean6/python/lib:$LD_LIBRARY_PATH
export PMIP_CBC_LIBRARY="/home/john/clean6/python/lib/libCbc.so"

Not sure the LD_LIBRARY_PATH was needed. It is the last export that tells python-mip where to look.

[s-c-e]

I had this same issue. In my application, I was looping through, iteratively building an overall solution to a problem I had broken down into smaller chunks.

• WSL (Ubuntu)
• python-mip 1.15.0

I tried quite a few avenues to free up the memory that accumulates. In my case, it was several GBs and the OS was eventually killing things. Garbage collection (gc, del), inspecting memory on the python side (tracemalloc), trying to modify the python-mip library (special attention to Model.__del__, Model.clear(), and globals), running with/without CBC multithreading, encapsulating with with, etc.

I couldn't figure it out. Posting my workaround here, in case it's helpful for others. I encapsulated the call in a separate process that could be fully terminated on completion. Pseudocode:

import multiprocessing

output_chunks = []

for i in range(num_iterations):
    with multiprocessing.Pool(1) as pool:
        output_chunks += pool.apply(my_optimization_function, args=(a, b, c, ))
        pool.close()
        pool.terminate()

When I monitor this, the memory usage spikes when the optimization function is called (of course); but, on each iteration, I can see that the memory is returned back to the OS.

Hope it helps others in a similar situation!