Saturday, August 30, 2014

Coin CBC command line

For a small project I was trying out the binary distribution of COIN-OR’s CBC. The good news, it can solve the problem quickly (provided I allow a  reasonable gap). I encountered a few issues:
  1. The Windows executables are not built with parallel threading support.
  2. The CSV writer is too simplistic. Names (with commas in them) are not properly quoted.

Threads option ignored

C:\projects\test>cbc model1a.lp ratio 0.05 threads 8 solve printing csv solution model1a.csv
Welcome to the CBC MILP Solver
Version: 2.8.8
Build Date: Dec 23 2013
Revision Number: 1998

command line - cbc model1a.lp ratio 0.05 threads 8 solve printing csv solution model1a.csv (default strategy 1)
ratioGap was changed from 0 to 0.05
No match for threads - ? for list of commands
No match for 8 - ? for list of commands
Continuous objective value is 57.0769 - 0.02 seconds
Cgl0002I 30 variables fixed
Cgl0003I 0 fixed, 0 tightened bounds, 527 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 475 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 429 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 291 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 69 strengthened rows, 0 substitutions
Cgl0004I processed model has 743 rows, 499 columns (346 integer) and 2429 elements
Cbc0038I Pass   1: suminf.    0.00000 (0) obj. 12146 iterations 431
Cbc0038I Solution found of 12146
Cbc0038I Before mini branch and bound, 316 integers at bound fixed and 140 continuous
Cbc0038I Full problem 743 rows 499 columns, reduced to 247 rows 145 columns
Cbc0038I Mini branch and bound improved solution from 12146 to 166 (0.50 seconds)
0  Obj 166 Dual inf 0.22137435 (11)
End of values pass after 26 iterations
26  Obj 166 Dual inf 549.2981 (110)
Perturbing problem by 0.001 % of 0.92934395 - largest nonzero change 1.9181672e-005 (% 0.0011298852) - largest zero chan
ge 1.9246056e-005
120  Obj 166
Optimal - objective value 166
Cbc0038I Round again with cutoff of 164.5
Cbc0038I Pass   2: suminf.    7.33333 (22) obj. 164.5 iterations 163
Cbc0038I Pass   3: suminf.    6.22857 (20) obj. 164.5 iterations 71
Cbc0038I Pass   4: suminf.    5.33336 (18) obj. 164.5 iterations 34
Cbc0038I Pass   5: suminf.    4.10000 (14) obj. 164.5 iterations 28
Cbc0038I Pass   6: suminf.    0.00750 (3) obj. 164.5 iterations 166
Cbc0038I Solution found of 162
Cbc0038I Before mini branch and bound, 311 integers at bound fixed and 141 continuous
Cbc0038I Full problem 743 rows 499 columns, reduced to 296 rows 158 columns
Cbc0038I Mini branch and bound did not improve solution (0.74 seconds)
Cbc0038I Round again with cutoff of 159.8
Cbc0038I Pass   7: suminf.    8.02667 (26) obj. 159.8 iterations 29
Cbc0038I Pass   8: suminf.    7.10546 (36) obj. 159.8 iterations 122
Cbc0038I Pass   9: suminf.    7.12365 (46) obj. 159.8 iterations 40
Cbc0038I Pass  10: suminf.   18.70686 (90) obj. 159.8 iterations 281
Cbc0038I Pass  11: suminf.    9.66191 (71) obj. 159.8 iterations 220
Cbc0038I Pass  12: suminf.    9.07849 (73) obj. 159.8 iterations 59
Cbc0038I Pass  13: suminf.    9.67900 (63) obj. 159.8 iterations 157
Cbc0038I Pass  14: suminf.    8.05376 (64) obj. 159.8 iterations 92
Cbc0038I Pass  15: suminf.    9.90251 (61) obj. 159.8 iterations 100
Cbc0038I Pass  16: suminf.    8.87667 (61) obj. 159.8 iterations 59
Cbc0038I Pass  17: suminf.   11.47273 (46) obj. 159.8 iterations 120
Cbc0038I Pass  18: suminf.   10.18668 (44) obj. 159.8 iterations 33
Cbc0038I Pass  19: suminf.    7.58501 (60) obj. 159.8 iterations 60
Cbc0038I Pass  20: suminf.    6.99899 (78) obj. 159.8 iterations 36
Cbc0038I Pass  21: suminf.    7.66668 (32) obj. 159.8 iterations 128
Cbc0038I Pass  22: suminf.    7.13455 (64) obj. 159.8 iterations 106
Cbc0038I Pass  23: suminf.    7.20358 (59) obj. 159.8 iterations 80
Cbc0038I Pass  24: suminf.    7.13455 (64) obj. 159.8 iterations 67
Cbc0038I Pass  25: suminf.    8.20892 (48) obj. 159.8 iterations 257
Cbc0038I Pass  26: suminf.    7.32000 (30) obj. 159.8 iterations 124
Cbc0038I Pass  27: suminf.    9.03479 (27) obj. 159.8 iterations 92
Cbc0038I Pass  28: suminf.    7.34334 (33) obj. 159.8 iterations 59
Cbc0038I Pass  29: suminf.    7.32000 (30) obj. 159.8 iterations 53
Cbc0038I Pass  30: suminf.    7.32000 (30) obj. 159.8 iterations 31
Cbc0038I Pass  31: suminf.   16.85062 (65) obj. 159.8 iterations 288
Cbc0038I Pass  32: suminf.    5.71250 (21) obj. 159.8 iterations 277
Cbc0038I Pass  33: suminf.    5.00000 (15) obj. 159.8 iterations 69
Cbc0038I Pass  34: suminf.    5.00000 (15) obj. 159.8 iterations 72
Cbc0038I Pass  35: suminf.    5.00000 (15) obj. 159.8 iterations 136
Cbc0038I Pass  36: suminf.    9.86669 (43) obj. 159.8 iterations 256
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 178 integers at bound fixed and 89 continuous
Cbc0038I Full problem 743 rows 499 columns, reduced to 542 rows 307 columns - 15 fixed gives 331, 197 - ok now
Cbc0038I Full problem 743 rows 499 columns, reduced to 328 rows 197 columns
Cbc0038I Mini branch and bound did not improve solution (1.22 seconds)
Cbc0038I After 1.23 seconds - Feasibility pump exiting with objective of 162 - took 0.92 seconds
Cbc0012I Integer solution of 162 found by feasibility pump after 0 iterations and 0 nodes (1.24 seconds)
Cbc0038I Full problem 743 rows 499 columns, reduced to 317 rows 154 columns
Cbc0038I Full problem 743 rows 499 columns, reduced to 0 rows 0 columns
Cbc0031I 19 added rows had average density of 171.78947
Cbc0013I At root node, 19 cuts changed objective from 151 to 154.55353 in 100 passes
Cbc0014I Cut generator 0 (Probing) - 207 row cuts average 2.5 elements, 7 column cuts (7 active)  in 0.203 seconds - new
frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 1562 row cuts average 349.6 elements, 0 column cuts (0 active)  in 0.842 seconds - n
ew frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.094 seconds - new
frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.037 seconds - new fr
equency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 1.313 s
econds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 191 row cuts average 191.0 elements, 0 column cuts (0 active)  in 0.253 seconds
- new frequency is 1
Cbc0011I Exiting as integer gap of 7.4464682 less than 1e-010 or 5%
Cbc0001I Search completed - best objective 162, took 17263 iterations and 0 nodes (6.98 seconds)
Cbc0035I Maximum depth 0, 42 variables fixed on reduced cost
Cuts at root node changed objective from 151 to 154.554
Probing was tried 100 times and created 214 cuts of which 0 were active after adding rounds of cuts (0.203 seconds)
Gomory was tried 100 times and created 1562 cuts of which 0 were active after adding rounds of cuts (0.842 seconds)
Knapsack was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.094 seconds)
Clique was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.037 seconds)
MixedIntegerRounding2 was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (1.313 s
econds)
FlowCover was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 100 times and created 191 cuts of which 0 were active after adding rounds of cuts (0.253 seconds)

Result - Optimal solution found (within gap tolerance)
Objective value:                162.00000000
Lower bound:                    154.554
Gap:                            0.05
Enumerated nodes:               0
Total iterations:               17263
Time (CPU seconds):             7.05
Time (Wallclock seconds):       7.05

Option for printingOptions changed from normal to csv
Total time (CPU seconds):       7.08   (Wallclock seconds):       7.08

C:\projects\test>

A better error message could indicate this executable was not compiled with parallel threading support.
I think parallel CBC does not work very well on Windows. I have tried also a GAMS version of the model using GAMS/CBC with threads=8. This leads to a crash:

image (1)

Looks like this is just not working very well. May be it is good threads are disabled in the Windows executable from the binary dsitribution.

Incorrect CSV output

The column name has some embedded commas, so the name should be quoted by the CSV writer. Here is a fragment of the output.

Assign(Student1,MON,m3),0
Assign(Student1,SCH,m1),1
Assign(Student1,MON,m4),0
Assign(Student1,MON,m7),0
Assign(Student1,MON,m8),0
Assign(Student1,GES,m11),0
Assign(Student1,GES,m12),0
Assign(Student1,GES,m13),0

Update: running on Mac (GAMS/CBC)

This also looks very scary (memory overruns?):

Maximum depth 0, 6 variables fixed on reduced cost
7 added rows had average density of 51.857143
At root node, 17 cuts changed objective from 158.29268 to 161.10418 in 8 passes
Cut generator 0 (Gomory) - 37 row cuts average 58.3 elements, 0 column cuts (12 active)
CutS egaerncehr actoomrp l0e t(eGdo m-o rbye)s t-  o3b7j ercotwi vceu t1se +a5v0e,r atgoeo k5 82.039  eilteemreanttiso,n s0  acnodl u0m nn ocduetss  ((1182. 5a5c tsievceo
nds)
Maximum depth 0, 6 variables fixed on reduced cost

The CBC log is pretty dense and messy (matter of taste of course), so not always easy to see strange messages, but this gibberish is of course a sign of a problem.

Update2: Mac again

After recompiling from sources I could run the problem with multiple threads (when reading from MPS files). May be a build problem in the GAMS version of CBC. But now I see my LP files are no longer accepted:

Coin3007W ### CoinLpIO::is_invalid_name(): Name is empty
Coin3007W ### CoinLpIO::are_invalid_names(): Invalid name: vnames[1396]: (null)
Coin3007W ### CoinLpIO::setLpDataRowAndColNames(): Invalid row names

Not a very clear message. I would like to see what I should do to fix my file. The solution is bogus so the lp file is read in incorrectly. (To be complete: this was tar file version 2.8.12).  I am not a happy camper…

Friday, August 8, 2014

Excel Solver Error Message

Error messages really need to be formulated with care. I am already confused my code does not work and I would like to see a message that clearly states what is wrong and what I should do to remedy the situation.

A counter example is here:



Two Excel Solver bugs in two lines!! More info on the first one: http://yetanothermathprogrammingconsultant.blogspot.com/2014/04/how-do-they-make-bug-like-this.html.

Just want to make a few quick plots:

Update: fixed by coding the number as a string in the variant. An alternative fix is shown here. Both are not obvious (to me).