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

[Levinson, Richard J. (ARC-TI)[SGT, INC]]

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


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20190703/d61d48a8/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pwdFirst.cip
Type: application/octet-stream
Size: 210737 bytes
Desc: pwdFirst.cip
URL: <http://listserv.zib.de/pipermail/scip/attachments/20190703/d61d48a8/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: expFirst.cip
Type: application/octet-stream
Size: 210737 bytes
Desc: expFirst.cip
URL: <http://listserv.zib.de/pipermail/scip/attachments/20190703/d61d48a8/attachment-0001.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pwdFirstSol.rtf
Type: text/rtf
Size: 74057 bytes
Desc: pwdFirstSol.rtf
URL: <http://listserv.zib.de/pipermail/scip/attachments/20190703/d61d48a8/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: expFirstSol.rtf
Type: text/rtf
Size: 1956086 bytes
Desc: expFirstSol.rtf
URL: <http://listserv.zib.de/pipermail/scip/attachments/20190703/d61d48a8/attachment-0001.bin>