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

[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 <http://listserv.zib.de/pipermail/scip/2013-November/001736.html>,
as well as answers and references therein. See also this more recent survey
<https://doi.org/10.1287/educ.2013.0112>.
For your particular problem, I would first try to use the function
SCIPchgVarBranchPriority
<https://scip.zib.de/doc/html/group__PublicVariableMethods.php#ga274db1c9e91d873799f6484e45a8d6bc>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> 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
> https://listserv.zib.de/mailman/listinfo/scip
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20190704/8c97784b/attachment.html>