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

[Jakob Witzig]

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

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20190704/3da81332/attachment.html>