<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<style type="text/css" style="display:none;"><!-- P {margin-top:0;margin-bottom:0;} --></style>
</head>
<body dir="ltr">
<div id="divtagdefaultwrapper" style="font-size:12pt;color:#000000;font-family:Calibri,Helvetica,sans-serif;" dir="ltr">
<p style="margin-top:0;margin-bottom:0">Hello Pierre and Jakob,</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">Thank you for your feedback and for explaining how performance variability is an well-known issue with MIP in general and not specifically SCIP-related. I have now read more about this issue and see that many people have
discussed it. </p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">It's nice to know this is a known and somewhat expected phenomenon, but disconcerting to know that seemingly very minor changes in my model may produce surprising and unpredictable results. </p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">- Rich </p>
</div>
<hr style="display:inline-block;width:98%" tabindex="-1">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" style="font-size:11pt" color="#000000"><b>From:</b> Jakob Witzig <witzig@zib.de><br>
<b>Sent:</b> Thursday, July 4, 2019 12:34:25 AM<br>
<b>To:</b> Levinson, Richard J. (ARC-TI)[SGT, INC]<br>
<b>Cc:</b> Pierre Le Bodic; scip@zib.de<br>
<b>Subject:</b> [EXTERNAL] Re: [SCIP] Performance affected by order of variable/constraint creation?</font>
<div> </div>
</div>
<div style="background-color:#FFFFFF">Hi Rich,<br>
<br>
as Pierre already said, what you describe is called performance variability. As you might have noticed, the problems after presolving already differ in the number of constraints:<br>
<br>
pwdFirstSol:<br>
<br>
presolved problem has 302 variables (288 bin, 0 int, 0 impl, 14 cont) and 339 constraints\<br>
45 constraints of type <knapsack><br>
288 constraints of type <disjunction><br>
6 constraints of type <linear><br>
<br>
expFirstSol:<br>
<br>
presolved problem has 302 variables (288 bin, 0 int, 0 impl, 14 cont) and 331 constraints\<br>
37 constraints of type <knapsack><br>
288 constraints of type <disjunction><br>
6 constraints of type <linear><br>
<br>
Since SCIP does not perform a full presolving but works with internal limits, the ordering of the variables and constraints has a significant impact. You can try to change the working limits by using presolving/abortfac = 0 (default: 0.0008). However, I don't
believe that you can completely avoid the described behavior because at some point the variable (or constraint) ordering will kick in if ties need to be broken and no other criteria led to decision.<br>
<br>
Best,<br>
Jakob <br>
<br>
<div class="x_moz-cite-prefix">Am 04.07.19 um 01:32 schrieb Pierre Le Bodic:<br>
</div>
<blockquote type="cite">
<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="https://urldefense.proofpoint.com/v2/url?u=http-3A__listserv.zib.de_pipermail_scip_2013-2DNovember_001736.html&d=DwMDaQ&c=ApwzowJNAKKw3xye91w7BE1XMRKi2LN9kiMk5Csz9Zk&r=RGQs01M1_zpPhg3LMQwHs_WgzOfXJDF7VhR6M6yfzB0&m=Lb15eT_K0mBYWLEUboWhl2teQYlRClu_0ow_hUzShtk&s=Gc5ICEsY-kBSwA6JnYNGOZLAT1i6u1XfBEeEB7AoOjU&e=" target="_blank">
this discussion</a>, as well as answers and references therein. See also <a href="https://urldefense.proofpoint.com/v2/url?u=https-3A__doi.org_10.1287_educ.2013.0112&d=DwMDaQ&c=ApwzowJNAKKw3xye91w7BE1XMRKi2LN9kiMk5Csz9Zk&r=RGQs01M1_zpPhg3LMQwHs_WgzOfXJDF7VhR6M6yfzB0&m=Lb15eT_K0mBYWLEUboWhl2teQYlRClu_0ow_hUzShtk&s=nCVThefGAiiia_jPbda1Dszmg3_hvgTHicGd9RP8Q70&e=" 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://urldefense.proofpoint.com/v2/url?u=https-3A__scip.zib.de_doc_html_group-5F-5FPublicVariableMethods.php-23ga274db1c9e91d873799f6484e45a8d6bc&d=DwMDaQ&c=ApwzowJNAKKw3xye91w7BE1XMRKi2LN9kiMk5Csz9Zk&r=RGQs01M1_zpPhg3LMQwHs_WgzOfXJDF7VhR6M6yfzB0&m=Lb15eT_K0mBYWLEUboWhl2teQYlRClu_0ow_hUzShtk&s=fl7GU5MAgCAaBOVa9ebx9ndUPeWcMkzc1ITNzpnRBqI&e=">
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="x_gmail_quote">
<div dir="ltr" class="x_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="x_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="x_gmail-m_-8720675171293846992gmail-m_-3635246425244515423divtagdefaultwrapper" dir="ltr" style="font-size:12pt; color:rgb(0,0,0); font-family:Calibri,Helvetica,sans-serif">
<div id="x_gmail-m_-8720675171293846992gmail-m_-3635246425244515423divtagdefaultwrapper" dir="ltr" style="">
<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=""><br>
</span></span></p>
<p style="margin-top:0px; margin-bottom:0px"><span style="font-size:12pt"><span style="">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=""><br>
</span></span></p>
<ul style="margin-bottom:0px; margin-top:0px">
<li><span style="font-size:12pt"><span style="">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=""> I create the EXP</span><span style="">-related variables and constraints before </span><span style="">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="">In both cases, the optimal solution is exactly the same. <br>
<br>
</span></li><li><span style="">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="">I've attached two CIP input files</span><span style=""> </span><span style="">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="x_gmail-m_-8720675171293846992gmail-m_-3635246425244515423divtagdefaultwrapper" dir="ltr" style="">
<br>
</div>
<div id="x_gmail-m_-8720675171293846992gmail-m_-3635246425244515423divtagdefaultwrapper" dir="ltr" style="">
Also attached the SCIP output logs from running with each of the two attached CIP in the interactive shell.
<p style="margin-top:0px; margin-bottom:0px"><br>
</p>
<p style="margin-top:0px; margin-bottom:0px">Attached files:</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="">
<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=""></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://urldefense.proofpoint.com/v2/url?u=https-3A__listserv.zib.de_mailman_listinfo_scip&d=DwMDaQ&c=ApwzowJNAKKw3xye91w7BE1XMRKi2LN9kiMk5Csz9Zk&r=RGQs01M1_zpPhg3LMQwHs_WgzOfXJDF7VhR6M6yfzB0&m=Lb15eT_K0mBYWLEUboWhl2teQYlRClu_0ow_hUzShtk&s=7_Ndnx6MyAfT30WbQpIg64XSpujTLy4WfdJPm7rYiK0&e=" rel="noreferrer" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a><br>
</blockquote>
</div>
<br>
<fieldset class="x_mimeAttachmentHeader"></fieldset>
<pre class="x_moz-quote-pre">_______________________________________________
Scip mailing list
<a class="x_moz-txt-link-abbreviated" href="mailto:Scip@zib.de">Scip@zib.de</a>
<a class="x_moz-txt-link-freetext" href="https://urldefense.proofpoint.com/v2/url?u=https-3A__listserv.zib.de_mailman_listinfo_scip&d=DwMDaQ&c=ApwzowJNAKKw3xye91w7BE1XMRKi2LN9kiMk5Csz9Zk&r=RGQs01M1_zpPhg3LMQwHs_WgzOfXJDF7VhR6M6yfzB0&m=Lb15eT_K0mBYWLEUboWhl2teQYlRClu_0ow_hUzShtk&s=7_Ndnx6MyAfT30WbQpIg64XSpujTLy4WfdJPm7rYiK0&e=">https://listserv.zib.de/mailman/listinfo/scip</a>
</pre>
</blockquote>
<br>
<pre class="x_moz-signature" cols="72">--
Jakob Witzig
Zuse Institute Berlin (ZIB)
Division Mathematical Optimization and Scientific Information
Research Group Mathematical Optimization Methods
Takustrasse 7
14195 Berlin
Tel. : +49 (0)30 84185-416
Fax : +49 (0)30 84185-269
email: <a class="x_moz-txt-link-abbreviated" href="mailto:witzig@zib.de">witzig@zib.de</a></pre>
</div>
</body>
</html>