<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=iso-8859-1"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
span.EmailStyle18
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:70.85pt 3.0cm 70.85pt 3.0cm;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:2069066540;
mso-list-type:hybrid;
mso-list-template-ids:1873963236 135659521 135659523 135659525 135659521 135659523 135659525 135659521 135659523 135659525;}
@list l0:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=PT link="#0563C1" vlink="#954F72"><div class=WordSection1><p class=MsoNormal><span lang=EN-GB>Hi,<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-GB><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-GB>We have been using CBC lately for some experiments at SISCOG, and despite some bumps along the way, the experience generally has been going smoothly. However, we have stumbled upon a situation that we are having trouble understanding, and wondered if you might be so kind as to give us a helping hand.<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-GB><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-GB>The situation is the following: we have created an LP that is apparently choking CBC. What I mean with this is that CBC doesn't even start doing its normal business (cuts, B&B): it apparently gets stuck in solving the relaxation. I say this because I run the optimiser as follows:<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-GB><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>cbc -seconds 14400 -import test.lp -maxNodes 0 -log 3 -solve<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-GB><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-GB>And the process outputs the following:<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-GB><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Welcome to the CBC MILP Solver<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Version: 2.9<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Build Date: Sep 2 2016<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>command line - Z:\siscog\cbc-2.9\bin\cbc.exe -seconds 14400 -import test.lp -maxNodes 0 -log 3 -solve (default strategy 1)<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>seconds was changed from 1e+100 to 14400<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>maxNodes was changed from 2147483647 to 0<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>logLevel was changed from 1 to 3<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Continuous objective value is 12360 - <b>98540.20</b> seconds<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cgl0006I 80 SOS (17507 members out of 84939) with 17507 overlaps - too much overlap or too many others<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cgl0002I 2740 variables fixed<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cgl0010I element in row 1092 for column 14740 changed from 60000 to 3194<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cgl0010I element in row 1092 for column 14741 changed from 60000 to 3194<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>...<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cgl0010I element in row 6795 for column 86500 changed from 60000 to 3689<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cgl0009I 227869 elements changed<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cgl0003I 0 fixed, 0 tightened bounds, 509271 strengthened rows, 0 substitutions<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cgl0003I 0 fixed, 0 tightened bounds, 485426 strengthened rows, 0 substitutions<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cgl0003I 0 fixed, 0 tightened bounds, 461291 strengthened rows, 0 substitutions<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cgl0003I 0 fixed, 0 tightened bounds, 436698 strengthened rows, 0 substitutions<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cgl0003I 0 fixed, 0 tightened bounds, 413801 strengthened rows, 0 substitutions<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cgl0003I 0 fixed, 0 tightened bounds, 390727 strengthened rows, 0 substitutions<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cgl0003I 0 fixed, 0 tightened bounds, 368252 strengthened rows, 0 substitutions<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cgl0003I 0 fixed, 0 tightened bounds, 345562 strengthened rows, 0 substitutions<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cgl0003I 0 fixed, 0 tightened bounds, 324250 strengthened rows, 0 substitutions<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cgl0004I processed model has 337921 rows, 86501 columns (79703 integer (79703 of which binary)) and 4943399 elements<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cutoff increment increased from 1e-005 to 0.00999<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cbc0020I Exiting on maximum time<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cbc0005I Partial search - best objective 1e+050 (best possible -128040), took 0 iterations and 0 nodes (98741.26 seconds)<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Cuts at root node changed objective from -128040 to -128040<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Clique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Result - Stopped on time limit<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>No feasible solution found<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Lower bound: -128040.000<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Enumerated nodes: 0<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Total iterations: 0<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Time (CPU seconds): 98743.25<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Time (Wallclock seconds): 98743.25<o:p></o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:35.4pt'><span lang=EN-GB style='font-family:Consolas'>Total time (CPU seconds): 98751.52 (Wallclock seconds): 98751.52<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-GB><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-GB>As you can see, it took more than 27 hours (way above the given time limit of 4 hours), and it didn't even try any cuts at the root node. And, by the way, the execution time is quite variable: I've seen it take 12h, 15h, and 17h on different occasions, though using an unstable version. (I don't think this is due to using the computer simultaneously with the CBC run, since I'm running on a multiple core CPU, and CBC is pretty much running on its dedicated core.)<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-GB><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-GB>By means of profiling (using </span><span lang=EN-GB style='font-family:Consolas'>gprof</span><span lang=EN-GB>; see the result attached), I have come to some faint conclusion that dualizing the problem is what's costing these much CPU cycles, but we have no hint on how to pursue further with the analysis.<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-GB><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-GB>I have tried the following:<o:p></o:p></span></p><p class=MsoListParagraph style='text-indent:-18.0pt;mso-list:l0 level1 lfo2'><![if !supportLists]><span lang=EN-GB style='font-family:Symbol'><span style='mso-list:Ignore'>·<span style='font:7.0pt "Times New Roman"'> </span></span></span><![endif]><span lang=EN-GB>Turning preprocessing off; didn't seem to help.<o:p></o:p></span></p><p class=MsoListParagraph style='text-indent:-18.0pt;mso-list:l0 level1 lfo2'><![if !supportLists]><span lang=EN-GB style='font-family:Symbol'><span style='mso-list:Ignore'>·<span style='font:7.0pt "Times New Roman"'> </span></span></span><![endif]><span lang=EN-GB>Based on some notes I found on the web (http://www.fastercoin.com/f2_files/naqs.html) about how to deal with degeneracy, I tried the idiot heuristic, as suggested, but to no avail.<o:p></o:p></span></p><p class=MsoListParagraph style='text-indent:-18.0pt;mso-list:l0 level1 lfo2'><![if !supportLists]><span lang=EN-GB style='font-family:Symbol'><span style='mso-list:Ignore'>·<span style='font:7.0pt "Times New Roman"'> </span></span></span><![endif]><span lang=EN-GB>Running CLP over the LP, confirming that all the time is spent in solving the relaxation.<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-GB><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-GB>I have also ruled out the sheer size of the problem (~100.000 variables; ~1.000.000 constraints) as a possible cause, since we have been solving larger LPs, and with a similar variable/constraints ratio.<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-GB><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-GB>Another possibly important note: I have, on other occasions, experienced the same problem with other LPs, but the one I send you is the only one that appears to cause this problem consistently, while the others appeared to cause it non-deterministically, which might indicate that the problem is indeed rooted in some non-deterministic component (such as perturbation).<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-GB><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-GB>We have found that the LP is feasible and that the optimal solution has objective 12360.0 (which, by the way, is also the objective of the relaxation).<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-GB><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-GB>You can find the offending LP here: https://drive.google.com/open?id=0B-5kPpSmX5imendFcUhiYlNqelE<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-GB><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-GB>If you could offer some hints as to what might be the possible causes, and corresponding solutions, we would be much obliged.<o:p></o:p></span></p><p class=MsoNormal><span lang=EN-GB><o:p> </o:p></span></p><p class=MsoNormal><span lang=EN-GB>Thank you in advance,</span><span lang=EN-GB style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black;mso-fareast-language:PT'><br>Rudi Araújo <br></span><span lang=EN-GB style='font-size:8.0pt;font-family:"Arial",sans-serif;color:black;mso-fareast-language:PT'>Software Engineer </span><span lang=EN-GB style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black;mso-fareast-language:PT'><br><br></span><b><span lang=EN-GB style='font-size:9.0pt;font-family:"Arial",sans-serif;color:black;mso-fareast-language:PT'>SISCOG - Sistemas Cognitivos, SA</span></b><span lang=EN-GB style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black;mso-fareast-language:PT'> <br></span><span lang=EN-GB style='font-size:7.5pt;font-family:"Arial",sans-serif;color:black;mso-fareast-language:PT'>Campo Grande, 378 - 3º, 1700-097 Lisboa • Portugal <br>Tel: +351 217 529 100 • Fax: +351 217 529 101<br></span><span lang=EN-GB style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black;mso-fareast-language:PT'><br><br></span><span style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black;mso-fareast-language:PT'><a href="http://www.siscog.pt"><b><span lang=EN-GB style='font-size:9.0pt;color:black;text-decoration:none'>www.siscog.pt</span></b></a></span><span lang=EN-GB style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black;mso-fareast-language:PT'> <br><br></span><b><span lang=EN-GB style='font-size:10.0pt;font-family:"Arial",sans-serif;color:#E36C0A;mso-fareast-language:PT'>"Optimising the resources of the world"</span></b><span lang=EN-GB style='font-size:10.0pt;font-family:"Arial",sans-serif;color:black;mso-fareast-language:PT'> <br><br></span><span lang=EN-GB style='font-size:7.5pt;font-family:"Arial",sans-serif;color:#736972;mso-fareast-language:PT'>DISCLAIMER<br>This message may contain confidential information. You should not copy or address this message to third parties.<br>If you are not the appropriate recipient we kindly ask you to delete the message and notify the sender.<br>The contents of this message and its attachments are the sole responsibility of the sender and under no circumstances can SISCOG - Sistemas Cognitivos, SA be liable for any resulting consequences. <br><br></span><span style='font-size:7.5pt;font-family:"Arial",sans-serif;color:#736972;mso-fareast-language:PT'>AVISO<br>Esta mensagem pode conter informação considerada confidencial, não devendo ser copiada ou endereçada a terceiros.<br>Se o receptor não for o destinatário apropriado, agradecemos que destrua a mensagem e informe o emissor do sucedido.<br>O conteúdo desta mensagem bem como dos respectivos anexos é da responsabilidade exclusiva do emissor, não podendo a SISCOG - Sistemas Cognitivos, SA ser responsabilizada por eventuais consequências.</span><o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p></div></body></html>