How can I limit the running time of COIN-CBC, as the maxSeconds argument does not seem to work for me?

user_9789008 0
Viewed 1802

I would like to solve a small-ish Mixed Integer Program using COIN-CBC (or any other free MIP solver available from PuLP), but with a time limit of, say, 10 seconds. However, the maxSeconds argument does not seem to work for me.

For an example instance, I call the solver without time limit this way:

prob.solve(pulp.PULP_CBC_CMD())

I call it with time limit this way:

prob.solve(pulp.PULP_CBC_CMD(maxSeconds=10))

The former terminates in 50.89 seconds, solution value 15.65287864835175. The latter terminates in 53.53 seconds, solution value 15.65287864835175. I would have expected it to terminate in (roughly) 10 seconds, probably with a higher solution value.

(I am aware of this post: Time limit for mixed integer programming with Python PuLP. But its answers refer to CPLEX and GUROBI, which I cannot use; I need a free solver.)

Am I doing something wrong?

pulp linear-programming python
1 Answers

Thank you for your suggestions. I think my question is answered.

I looked at the log-files. (For completeness: I upgraded to PuLP 2.3 to do so, meaning I now use the argument timeLimit instead of maxSeconds.) I think I understand what's going on: that is, I think presolving this problem takes about 67 seconds, and the time limit does not chop off presolving.

Here's the log without time limit:

Welcome to the CBC MILP Solver 
Version: 2.9.0 
Build Date: Feb 12 2015 

command line - C:\Users\Dylan\More Programs\WPy64-3771\python-3.7.7.amd64\lib\site-packages\pulp\apis\..\solverdir\cbc\win\64\cbc.exe C:\Users\Dylan\AppData\Local\Temp\17364266f50a4759aa9fb37ebf74bf9a-pulp.mps ratio None allow None threads None presolve on strong None gomory on knapsack on probing on branch printingOptions all solution C:\Users\Dylan\AppData\Local\Temp\17364266f50a4759aa9fb37ebf74bf9a-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 122856 COLUMNS
At line 613557 RHS
At line 736409 BOUNDS
At line 859260 ENDATA
Problem MODEL has 122851 rows, 122850 columns and 367850 elements
Coin0008I MODEL read with 0 errors
String of None is illegal for double parameter ratioGap value remains 0
String of None is illegal for double parameter allowableGap value remains 0
String of None is illegal for integer parameter threads value remains 0
String of None is illegal for integer parameter strongBranching value remains 5
Option for gomoryCuts changed from ifmove to on
Option for knapsackCuts changed from ifmove to on
Continuous objective value is 15.6529 - 55.52 seconds
Cgl0004I processed model has 122851 rows, 122850 columns (350 integer (350 of which binary)) and 367850 elements
Cbc0038I Initial state - 0 integers unsatisfied sum - 0
Cbc0038I Solution found of 15.6529
Cbc0038I Relaxing continuous gives 15.6529
Cbc0038I Before mini branch and bound, 350 integers at bound fixed and 122500 continuous
Cbc0038I Mini branch and bound did not improve solution (60.18 seconds)
Cbc0038I After 60.41 seconds - Feasibility pump exiting with objective of 15.6529 - took 1.45 seconds
Cbc0012I Integer solution of 15.652879 found by feasibility pump after 0 iterations and 0 nodes (60.56 seconds)
Cbc0001I Search completed - best objective 15.6528786483516, took 0 iterations and 0 nodes (61.35 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from 15.6529 to 15.6529
Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

Result - Optimal solution found

Objective value:                15.65287865
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             62.68
Time (Wallclock seconds):       62.68

Option for printingOptions changed from normal to all
Total time (CPU seconds):       66.76   (Wallclock seconds):       66.76

Here's the log with time limit:

Welcome to the CBC MILP Solver 
Version: 2.9.0 
Build Date: Feb 12 2015 

command line - C:\Users\Dylan\More Programs\WPy64-3771\python-3.7.7.amd64\lib\site-packages\pulp\apis\..\solverdir\cbc\win\64\cbc.exe C:\Users\Dylan\AppData\Local\Temp\df26386989ec445da5518920510d3869-pulp.mps sec 10 ratio None allow None threads None presolve on strong None gomory on knapsack on probing on branch printingOptions all solution C:\Users\Dylan\AppData\Local\Temp\df26386989ec445da5518920510d3869-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 122856 COLUMNS
At line 613557 RHS
At line 736409 BOUNDS
At line 859260 ENDATA
Problem MODEL has 122851 rows, 122850 columns and 367850 elements
Coin0008I MODEL read with 0 errors
seconds was changed from 1e+100 to 10
String of None is illegal for double parameter ratioGap value remains 0
String of None is illegal for double parameter allowableGap value remains 0
String of None is illegal for integer parameter threads value remains 0
String of None is illegal for integer parameter strongBranching value remains 5
Option for gomoryCuts changed from ifmove to on
Option for knapsackCuts changed from ifmove to on
Continuous objective value is 15.6529 - 56.17 seconds
Cgl0004I processed model has 122851 rows, 122850 columns (350 integer (350 of which binary)) and 367850 elements
Cbc0020I Exiting on maximum time
Cbc0005I Partial search - best objective 1e+050 (best possible 15.652879), took 0 iterations and 0 nodes (60.49 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from 15.6529 to 15.6529
Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

Result - Stopped on time limit

No feasible solution found
Lower bound:                    15.653
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             64.34
Time (Wallclock seconds):       64.34

Option for printingOptions changed from normal to all
Total time (CPU seconds):       68.37   (Wallclock seconds):       68.37

From the second log, we can see that the time limit is indeed passed and acknowledged, and that CBC exits without finding a feasible solution, as soon as it can. We also see, from the first log, that no branching was done at all: apparently, the problem was presolved, which took about 67 seconds.

This answers my question: maxSeconds (or timeLimit) is being registered just fine. Apparently, the time limit does not chop off presolving, but I guess I have bigger problems if the presolving takes more than ten seconds.

user_97890080
Related