[SCIP] [EXTERNAL] Re: Performance affected by order of variable/constraint creation?

Fri Jul 5 21:14:46 CEST 2019

Hello Pierre and Jakob,

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.

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.

- Rich

________________________________
From: Jakob Witzig <witzig at zib.de>
Sent: Thursday, July 4, 2019 12:34:25 AM
To: Levinson, Richard J. (ARC-TI)[SGT, INC]
Cc: Pierre Le Bodic; scip at zib.de
Subject: [EXTERNAL] Re: [SCIP] Performance affected by order of variable/constraint creation?

Hi Rich,

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:

pwdFirstSol:

presolved problem has 302 variables (288 bin, 0 int, 0 impl, 14 cont) and 339 constraints\
     45 constraints of type <knapsack>
    288 constraints of type <disjunction>
      6 constraints of type <linear>

expFirstSol:

presolved problem has 302 variables (288 bin, 0 int, 0 impl, 14 cont) and 331 constraints\
     37 constraints of type <knapsack>
    288 constraints of type <disjunction>
      6 constraints of type <linear>

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.

Best,
Jakob

Am 04.07.19 um 01:32 schrieb Pierre Le Bodic:
Hi Rich,

I believe that what your are observing is what we refer to as "performance variability", a common phenomenon in solvers. See for instance this discussion<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=>, as well as answers and references therein. See also this more recent survey<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=>.
For your particular problem, I would first try to use the function SCIPchgVarBranchPriority <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=> to give the PWD-related variables a higher priority, thus ensuring that these are branched on before any other, independently of the creation order.

Kind regards
Pierre

On Thu, 4 Jul 2019 at 05:14, Levinson, Richard J. (ARC-TI)[SGT, INC] <richard.j.levinson at nasa.gov<mailto:richard.j.levinson at nasa.gov>> wrote:

Hello SCIP team,

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.

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.

  *   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.

  *   But when I create the EXP-related variables and constraints before the PWD variables, then it takes 651 seconds to find the optimal solution and takes over 100 seconds to find the first feasible solution.

  *   In both cases, the optimal solution is exactly the same.

  *   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.

I've attached two CIP input files where the only difference is the sequence of the variables and constraints. The variables and constraints are the same but in a different order.

Also attached the SCIP output logs from running with each of the two attached CIP in the interactive shell.

Attached files:

  *   pwdFirst.cip = PWD vars and constraints created first (this is the fast case)
  *   expFirst.cip = EXP vars and constraints created first (this is the slow case)

  *   pwdFirstSol.rtf = SCIP output for the PWD first case (fast result)

  *   expFirstSol.rtf  = SCIP output for the EXP first case  (slow result)

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.

Thank you,

    Rich Levinson

_______________________________________________
Scip mailing list
Scip at zib.de<mailto:Scip at zib.de>
https://listserv.zib.de/mailman/listinfo/scip<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=>

_______________________________________________
Scip mailing list
Scip at zib.de<mailto:Scip at zib.de>
https://listserv.zib.de/mailman/listinfo/scip<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=>

--
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: witzig at zib.de<mailto:witzig at zib.de>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20190705/e18a7aea/attachment.html>