Memory usage accumulation in CBC solver with python-mip wrapper

164 Views Asked by At

The code below solves an IP relating to an $n\times n$ chessboard using CBC solver with python-mip wrapper (version 1.15.0). 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?
0

There are 0 best solutions below