[SCIP] Dependent variables?

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

Hi Gregor,


Thank you for your helpful suggestions for adjusting the branching priority and/or branching factors. I look forward to trying them out.


- Rich

________________________________
From: Scip <scip-bounces at zib.de> on behalf of Gregor Hendel <hendel at zib.de>
Sent: Sunday, May 5, 2019 4:50:56 PM
To: scip at zib.de
Subject: Re: [SCIP] Dependent variables?

Good morning Richard and list,

you have two possibilities to tell SCIP which variables should be prioritized (branched on/assigned first in the tree).

1. The hard way: Assign a higher branching priority (SCIPvarChgBranchPriority()) to some variables. All branching rules and some of the primal heuristics will only consider fractional branching candidates that have the highest priority. Lower priority variables are excluded from the branching decision until there is no high priority variable left. The default priority of all variables is 0. Since the priority is an integer attribute of a variable, you can in principle fix the variable order for SCIP to branch on, by assigning unique priorities to every variable.

2. The soft way: Assign a higher branching factor (SCIPvarChgBranchFactor()) to fine-tune the scoring mechanism. If your s variables (start times) have a branching priority of 10.0 (the default is 1.0, of course), they are much more likely to be selected for branching, unless the (unweighted) branching score of another variable (say, a job end variable e) is 10 times higher than that of the best s variable.

Branching enthusiasts may even mix 1. and 2. Let us know if you experience a good impact with one of the above methods.

Happy branching,
Gregor

Am 03.05.19 um 18:51 schrieb Levinson, Richard J. (ARC-TI)[SGT, INC]:
Hello,

I'm looking for a way to specify that some variables are the "primary" decision variables to drive search, while other variables are "dependent" variables, which depend on the primary variables via constraints, so that the dependent variable assignments are made only after feasible assignments for the primary variables have been found.

Is there a way to tell SCIP that some variables are considered ‘dependent’, i.e. they should not be considered as part of the search space, but must be propagated using constraints in the problem?


Or if there is no way to specify that some variables should not be part of the search space, is there an option to specify the order/priority for assigning variables?  So the solver searches first through the domains of the primary (high priority) variables to find a feasible solution before it searches for consistent assignments for the dependent variables.


For example, we may have variables s, e, d, representing a job's start, end, and duration times, and we want to first search for feasible assignments for s and e before applying the constraint that e-s = d.


Thank you,


    Rich Levinson



_______________________________________________
Scip mailing list
Scip at zib.de<mailto: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/20190506/52aeb2f7/attachment.html>