<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body text="#000000" bgcolor="#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="moz-cite-prefix">Am 04.07.19 um 01:32 schrieb Pierre Le
Bodic:<br>
</div>
<blockquote type="cite"
cite="mid:CAHmigS9sCCfiBf+8JzUiQ8QUq5XvqSnnFeEEN_G915zD4nYvKA@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<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" moz-do-not-send="true">this discussion</a>,
as well as answers and references therein. See also <a
href="https://doi.org/10.1287/educ.2013.0112"
target="_blank" moz-do-not-send="true">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"
moz-do-not-send="true">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"
moz-do-not-send="true">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>
<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 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="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"
moz-do-not-send="true">Scip@zib.de</a><br>
<a href="https://listserv.zib.de/mailman/listinfo/scip"
rel="noreferrer" target="_blank" moz-do-not-send="true">https://listserv.zib.de/mailman/listinfo/scip</a><br>
</blockquote>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
Scip mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Scip@zib.de">Scip@zib.de</a>
<a class="moz-txt-link-freetext" href="https://listserv.zib.de/mailman/listinfo/scip">https://listserv.zib.de/mailman/listinfo/scip</a>
</pre>
</blockquote>
<br>
<pre class="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="moz-txt-link-abbreviated" href="mailto:witzig@zib.de">witzig@zib.de</a></pre>
</body>
</html>