CBC Solver Hangs on Certain MPS Problems -- PuLP Should Handle More Gracefully

[TCRichards]

Discussed in #698

^{Originally posted by TCRichards November 3, 2023}
Hello,

I’m working on a real-time decision making tool that uses PuLP with the CBC solver to solve optimization problems.

I occasionally encounter problems where CBC does not solve the problem in any reasonable amount of time, and hangs on a pre-processing step before the cut step begins. Even when I pass a time limit to CBC, the solver hangs without honoring the time limit. I see some other posts about the time limit not being honored in pre-processing steps, so this is a known issue: #456.

My issue seems very similar to coin-or/python-mip#145, but I’m using Pulp version 2.7.0 and CBC version 2.10.3 and it still occurs (whereas the other issue is resolved). I regularly solve problems of comparable size in seconds, but this problem hangs for at least a day before I gave up and killed it.

I can reproduce the issue on MacOS and Linux, but interestingly it doesn't seem to hang on Windows.

The most recent logging that I see before CBC hangs is:

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

command line - /Users/thomasrichards/bitbucket/pop/venv/lib/python3.11/site-packages/pulp/solverdir/cbc/osx/64/cbc /var/folders/y2/lnwr112s2c59l1l9b9l2vlsw0000gq/T/9117d51b01ce4c1f969ae57bcc993123-pulp.mps -sec 20 -timeMode elapsed -branch -printingOptions all -solution /var/folders/y2/lnwr112s2c59l1l9b9l2vlsw0000gq/T/9117d51b01ce4c1f969ae57bcc993123-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 8409 COLUMNS
At line 33844 RHS
At line 42249 BOUNDS
At line 46884 ENDATA
Problem MODEL has 8404 rows, 4634 columns and 20223 elements
Coin0008I MODEL read with 0 errors
seconds was changed from 1e+100 to 20
Option for timeMode changed from cpu to elapsed
Continuous objective value is -305.798 - 0.04 seconds
Cgl0002I 288 variables fixed
Cgl0003I 0 fixed, 0 tightened bounds, 291 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 186 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 2 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 1 strengthened rows, 0 substitutions
Cgl0004I processed model has 5472 rows, 3442 columns (1149 integer (1149 of which binary)) and 14462 elements
Cbc0038I Initial state - 82 integers unsatisfied sum - 17.3203
Cbc0038I Pass   1: (0.18 seconds) suminf.    0.00000 (0) obj. 11000.2 iterations 592
Cbc0038I Solution found of 11000.2
Cbc0038I Relaxing continuous gives -289.993
Cbc0038I Before mini branch and bound, 1067 integers at bound fixed and 1650 continuous
Cbc0038I Full problem 5472 rows 3442 columns, reduced to 595 rows 356 columns
Cbc0038I Mini branch and bound did not improve solution (0.23 seconds)
Cbc0038I Freeing continuous variables gives a solution of -299.65
Cbc0038I Round again with cutoff of -300.264
Cbc0038I Pass   2: (0.29 seconds) suminf.    0.00000 (0) obj. -300.264 iterations 276
Cbc0038I Solution found of -300.264
Cbc0038I Relaxing continuous gives -302.994
Cbc0038I Before mini branch and bound, 1067 integers at bound fixed and 1778 continuous
Cbc0038I Full problem 5472 rows 3442 columns, reduced to 312 rows 203 columns
Cbc0038I Mini branch and bound did not improve solution (0.32 seconds)
Cbc0038I Round again with cutoff of -303.553
Cbc0038I Pass   3: (0.38 seconds) suminf.    0.03653 (1) obj. -303.553 iterations 153
Cbc0038I Pass   4: (0.38 seconds) suminf.    0.00000 (0) obj. -303.553 iterations 3

Here's the MPS file that causes the hang:
cbc_hang.txt

I forked PuLP and added a fix for my version that addresses this issue for my use case. For my application, it's MUCH better for the solver to fail quickly and raise an Exception than hang for multiple hours, since I'm using PuLP for real-time decision making. My approach involves using a timer in PuLP's main thread that will kill the CBC solver process if it takes >10 seconds longer than the specified time limit if a new argument killOnTimeLimit.

Forked code is here: https://github.com/TCRichards/pulp

I'm happy to make a Pull Request for this issue if the maintainers agree others would benefit from this ability.