<div dir="ltr"><div>Hi Rich,</div><div><br></div><div>I believe that what your are observing is what we refer to as "performance variability", a common phenomenon in solvers. See for instance <a href="http://listserv.zib.de/pipermail/scip/2013-November/001736.html" target="_blank">this discussion</a>, as well as answers and references therein. See also <a href="https://doi.org/10.1287/educ.2013.0112" target="_blank">this more recent survey</a>.<br></div><div>For your particular problem, I would first try to use the function <a href="https://scip.zib.de/doc/html/group__PublicVariableMethods.php#ga274db1c9e91d873799f6484e45a8d6bc">SCIPchgVarBranchPriority </a>to give the PWD-related variables a higher priority, thus ensuring that these are branched on before any other, independently of the creation order.</div><div><br></div><div>Kind regards</div><div>Pierre<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, 4 Jul 2019 at 05:14, Levinson, Richard J. (ARC-TI)[SGT, INC] <<a href="mailto:richard.j.levinson@nasa.gov" target="_blank">richard.j.levinson@nasa.gov</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div dir="ltr">
<div id="gmail-m_-8720675171293846992gmail-m_-3635246425244515423divtagdefaultwrapper" style="font-size:12pt;color:rgb(0,0,0);font-family:Calibri,Helvetica,sans-serif" dir="ltr">
<div id="gmail-m_-8720675171293846992gmail-m_-3635246425244515423divtagdefaultwrapper" dir="ltr" style="font-size:12pt;color:rgb(0,0,0);font-family:Calibri,Helvetica,sans-serif,Helvetica,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols">
<p style="margin-top:0px;margin-bottom:0px">Hello SCIP team,</p>
<p style="margin-top:0px;margin-bottom:0px"><br>
</p>
<p style="margin-top:0px;margin-bottom:0px">I have a CIP model where I've noticed a big performance difference when I swap the order in which I create/add variables and constraints to the SCIP model. I first noticed this using my C-API code but have now reproduced
it using the interactive shell. </p>
<p style="margin-top:0px;margin-bottom:0px"><span style="font-size:12pt"><span style="font-family:Calibri,Helvetica,sans-serif,Helvetica,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px"><br>
</span></span></p>
<p style="margin-top:0px;margin-bottom:0px"><span style="font-size:12pt"><span style="font-family:Calibri,Helvetica,sans-serif,Helvetica,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px">This
is a job scheduling app where I have four types of jobs SAB, PPA, PWD and EXP. Performance varies greatly depending on the order in which I create the variables and constraints for these jobs. </span></span></p>
<p style="margin-top:0px;margin-bottom:0px"><span style="font-size:12pt"><span style="font-family:Calibri,Helvetica,sans-serif,Helvetica,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px"><br>
</span></span></p>
<p style="margin-top:0px;margin-bottom:0px"></p>
<ul style="margin-bottom:0px;margin-top:0px">
<li><span style="font-size:12pt"><span style="font-family:Calibri,Helvetica,sans-serif,Helvetica,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px">When I create the PWD-related variables
and constraints before the EXP variables, then it finds an optimal solution in 0.8 seconds and converges to prove optimality after 20 seconds. <br>
<br>
</span></span></li><li>But when<span style="font-family:Calibri,Helvetica,sans-serif,Helvetica,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px"> I create the EXP</span><span style="font-family:Calibri,Helvetica,sans-serif,Helvetica,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px">-related
variables and constraints before </span><span style="font-family:Calibri,Helvetica,sans-serif,Helvetica,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px">the PWD variables, then it
takes 651 seconds to find the optimal solution and takes over 100 seconds to find the first feasible solution. <br>
<br>
</span></li><li><span style="font-family:Calibri,Helvetica,sans-serif,Helvetica,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px">In both cases, the optimal solution is exactly the same. <br>
<br>
</span></li><li><span style="font-family:Calibri,Helvetica,sans-serif,Helvetica,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px">In a different case, when I create SAB and PPA model before PWD
and EXP, then it also takes about 100 secs to find the optimal solution and 525 seconds to converge and prove optimality. <br>
</span></li></ul>
<p style="margin-top:0px;margin-bottom:0px"><br>
</p>
<span style="font-family:Calibri,Helvetica,sans-serif,Helvetica,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px">I've attached two CIP input files</span><span style="font-family:Calibri,Helvetica,sans-serif,Helvetica,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px"> </span><span style="font-family:Calibri,Helvetica,sans-serif,Helvetica,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px">where
the only difference is the sequence of the variables and constraints. The </span>variables and constraints are the same but in a different order. </div>
<div id="gmail-m_-8720675171293846992gmail-m_-3635246425244515423divtagdefaultwrapper" dir="ltr" style="font-size:12pt;color:rgb(0,0,0);font-family:Calibri,Helvetica,sans-serif,Helvetica,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols">
<br>
</div>
<div id="gmail-m_-8720675171293846992gmail-m_-3635246425244515423divtagdefaultwrapper" dir="ltr" style="font-size:12pt;color:rgb(0,0,0);font-family:Calibri,Helvetica,sans-serif,Helvetica,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols">
Also attached the SCIP output logs from running with each of the two attached CIP in the interactive shell.
<p></p>
<p style="margin-top:0px;margin-bottom:0px"><br>
</p>
<p style="margin-top:0px;margin-bottom:0px">Attached files:</p>
<p style="margin-top:0px;margin-bottom:0px"></p>
<ul style="margin-bottom:0px;margin-top:0px">
<li>pwdFirst.cip = PWD vars and constraints created first (this is the fast case)</li><li>expFirst.cip = EXP vars and constraints created first (this is the slow case)</li></ul>
<br>
<ul style="margin-bottom:0px;margin-top:0px">
<li>pwdFirstSol.rtf = SCIP output for the PWD first case (fast result)<br>
</li></ul>
<ul style="font-family:Calibri,Helvetica,sans-serif,Helvetica,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px;margin-bottom:0px;margin-top:0px">
<li>expFirstSol.rtf = SCIP output for the EXP first case (slow result)</li></ul>
<div><br>
</div>
<div><br>
</div>
<p style="margin-top:0px;margin-bottom:0px">Can you please explain what is causing this order dependency, and how I might be able to eliminate or control it via SCIP parameters? For example, can I use Variable Branching options to override these ordering effects?
I'd rather the performance not depend on the order of my C++ code statements.</p>
<p style="margin-top:0px;margin-bottom:0px"><br>
</p>
<p style="margin-top:0px;margin-bottom:0px">Thank you,</p>
<p style="margin-top:0px;margin-bottom:0px"> Rich Levinson</p>
<p style="margin-top:0px;margin-bottom:0px"> </p>
<p style="margin-top:0px;margin-bottom:0px"><span style="font-family:Calibri,Helvetica,sans-serif,Helvetica,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px"></span></p>
</div>
</div>
</div>
_______________________________________________<br>
Scip mailing list<br>
<a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a><br>
<a href="https://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a><br>
</blockquote></div>