pulp.PULP_CBC_CMD(threads=8) hangs on locks

[mhechthz]

I tried to use parallel solution option on CBC, just to check if it works and use it later where it might help.

Parallel solving hangs from time to time non-reproducible:

Welcome to the CBC MILP Solver 
Version: 2.10.3
Build Date: Dec 15 2019

command line - C:\Python312\Lib\site-packages\pulp\solverdir\cbc\win\64\cbc.exe C:\Users\Michael\AppData\Local\Temp\9f2f4340f4914ba58ec92a8628688845-pulp.mps -threads 8 -timeMode elapsed -branch -printingOptions all -solution C:\Users\Michael\AppData\Local\Temp\9f2f4340f4914ba58ec92a8628688845-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 509 COLUMNS
At line 314385 RHS
At line 314890 BOUNDS
At line 377666 ENDATA
Problem MODEL has 504 rows, 62775 columns and 125550 elements
Coin0008I MODEL read with 0 errors
threads was changed from 0 to 8
Option for timeMode changed from cpu to elapsed
Continuous objective value is 241 - 0.33 seconds
Cgl0004I processed model has 504 rows, 62775 columns (62775 integer (62775 of which binary)) and 125550 elements
Cutoff increment increased from 1e-05 to 0.9999
Cbc0038I Initial state - 0 integers unsatisfied sum - 0
Cbc0038I Solution found of 241
Cbc0038I Before mini branch and bound, 62775 integers at bound fixed and 0 continuous
Cbc0038I Mini branch and bound did not improve solution (2.12 seconds)
Cbc0038I After 2.12 seconds - Feasibility pump exiting with objective of 241 - took 0.13 seconds
Cbc0012I Integer solution of 241 found by feasibility pump after 0 iterations and 0 nodes (2.14 seconds)
Cbc0030I Thread 0 used 0 times,  waiting to start 0, 0 cpu time, 0 locks, 0 locked, 0 waiting for locks
Cbc0030I Thread 1 used 0 times,  waiting to start 0, 0 cpu time, 0 locks, 0 locked, 0 waiting for locks
Cbc0030I Thread 2 used 0 times,  waiting to start 0, 0 cpu time, 0 locks, 0 locked, 0 waiting for locks
Cbc0030I Thread 3 used 0 times,  waiting to start 0, 0 cpu time, 0 locks, 0 locked, 0 waiting for locks
Cbc0030I Thread 4 used 0 times,  waiting to start 0, 0 cpu time, 0 locks, 0 locked, 0 waiting for locks
Cbc0030I Thread 5 used 0 times,  waiting to start 0, 0 cpu time, 0 locks, 0 locked, 0 waiting for locks
Cbc0030I Thread 6 used 0 times,  waiting to start 0, 0 cpu time, 0 locks, 0 locked, 0 waiting for locks

This is my test code:

import pulp
import time
import numpy as np

while True:

    print("# "+"="*126)
    print("NEXT ROUND ...")
    
    # Number of tasks and workers
    num_tasks = np.random.randint(200,300)
    num_workers = np.random.randint(200,300)

    # Randomly generate costs for each worker-task pair
   
    #np.random.seed(0)  # For reproducibility
    costs = np.random.randint(1, 100, size=(num_workers, num_tasks))

    # Create the MILP problem
    problem = pulp.LpProblem("TaskAssignment", pulp.LpMinimize)

    # Decision variables: x[i, j] is 1 if worker i is assigned to task j, 0 otherwise
    x = pulp.LpVariable.dicts("x", ((i, j) for i in range(num_workers) for j in range(num_tasks)), cat='Binary')

    # Objective: Minimize the total cost of assignments
    problem += pulp.lpSum(costs[i][j] * x[(i, j)] for i in range(num_workers) for j in range(num_tasks))

    # Constraints: Each task is assigned to exactly one worker
    for j in range(num_tasks):
        problem += pulp.lpSum(x[(i, j)] for i in range(num_workers)) == 1

    # Constraints: Each worker is assigned to at most one task (can be adjusted for more tasks per worker)
    for i in range(num_workers):
        problem += pulp.lpSum(x[(i, j)] for j in range(num_tasks)) <= 1

    problem.writeLP("pulp.lp")
    # Solve the problem using PuLP with CBC in parallel mode
    t0 = time.time()
    print(f"start solving ({num_tasks},{num_workers})...")
    solver = pulp.PULP_CBC_CMD(threads=8)  # Adjust the number of threads according to your machine
    problem.solve(solver)
    dt = time.time() - t0

    # Print the solution
    for i in range(num_workers):
        for j in range(num_tasks):
            if pulp.value(x[(i, j)]) == 1:
                print(f"Worker {i} is assigned to Task {j} with Cost {costs[i][j]}")

    print(f"solution took {dt:.2f} seconds ...")

[pchtsp]

Can you please create a ticket in cbc? As I think it's more of an issue with them.
github.com/coin-or/cbc

[mhechthz]

Ok. I opened an issue at cbc: coin-or/Cbc#640

[mhechthz]

I did some further tests. It seems, that Python-Mip is not facing this problem. Mip uses obviously cbc-c-windows-x86-64.dll and not the cbc.exe but I'm not sure which version but I just installed the brandnew Python 3.12 compatible release candidate.

from mip import Model
import time

# Create a new model
model = Model()

count = 0

while True:

    count += 1
    print("# "+"="*126)
    print(f"NEXT ROUND {count} ...")

    # Load the MPS file
    model.read(r'C:\Users\Michael\AppData\Local\Temp\9f2f4340f4914ba58ec92a8628688845-pulp.mps')

    model.threads = 8

    # Solve the model
    t0 = time.time()
    print(f"start solving ...")
    model.optimize()
    dt = time.time() - t0

    # Check if a solution has been found
    if model.num_solutions:
        print(f"Objective value: {model.objective_value}")
        for var in model.vars:
            if abs(var.x) > 1e-6: # Display non-zero variables
                print(f"{var.name} = {var.x}")
    else:
        print("No solution found.")

    print(f"solution took {dt:.2f} seconds ...")
    print()

[mhechthz]

I replaced the cbc.exe with the one from here: https://github.com/FranksMathematics/CBC_ReleaseParallel_Win86

Now it works and is really fast.

[stumitchell]

That's a good option I think we should consider it what version of CBC is it?

[mhechthz]

C:\bin\CBC\CBC_ReleaseParallel_Win86>.\cbc.exe --version
Welcome to the CBC MILP Solver
Version: trunk
Build Date: Jul 14 2022
command line - --version (default strategy 1)
Unrecognized parameter - -version, exiting...
Total time (CPU seconds):       0.002   (Wallclock seconds):       0.00300002

You probably need to ask the guy from https://github.com/FranksMathematics/CBC_ReleaseParallel_Win86