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-mipwrapper? - How to completely remove the (memory usage of) existing models in
python-mip?