Branch and Bound Variable

[Nicholas Parham]

If I have a model with two integer variables: 

    Y_i: integer time to schedule activity i

    X_it: binary indicator if activity i is scheduled in time t

How can I communicate to AMPL/the solvers that I would only like to branch and bound on Y? Does setting variable priority effectively do this? I would like to make sure X_it is never considered.

[AMPL Google Group]

If you set a much higher priority on the Y_i variables than on the X_it variables, then it is likely that the solution will be found and proved without any branching on the X_it variables. However, that is not guaranteed, as each solver has its own methods of making branching decisions.

I can see how Y[i] might be defined by an expression like sum {t in T} t * X[i,t], where sum {t in T} X[i,t] = 1. Then the Y[i] variables could be substituted out of the problem, and necessarily the would not be branched on. I do not see a way to substitute the X[i,t] variables out of the problem, however.

--
Robert Fourer
am...@googlegroups.com

{#HS:2055148375-112598#}

On Tue, Nov 1, 2022 at 9:33 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

If I have a model with two integer variables X_it and a Y_i, but the X_it takes on a value based on Y_i - how do I communicate to AMPL/solvers that I would only like to execute branch and bound on Y_i? Does setting priority effectively do this? I would like to make sure that X_it is never considered during this process.

[Nicholas Parham]

Thanks for the response! I was thinking there might be a benefit to retaining Y and branching/bounding on it rather than a bunch of binaries. I completely disregarded the fact that there would be no guarantee that the X's were binary and not fractional at the nodes.

[AMPL Google Group]

This reminds me that there are a few very special situations where you can skip branching on some variables. One of them arises in linearizing the condition

y[i,j] = 1 <==> x[i] = 1 and x[j] = 1

where all of the variables involved are binary. A well-known linear equivalent is given by

y[i,j] <= x[i]
y[i,j] <= x[j]
y[i,j] >= x[i] + x[j] - 1

If x[i] = 0 or x[j] = 0, these constraints imply y[i,j] <= 0; if x[i] = x[j] = 1, they imply y[i,j] >= 1. Thus it is not necessary to define y[i,j] explicitly as binary; it can be defined instead as a continuous variable >= 0 and <= 1, which skips branching on y[i,j].

--
Robert Fourer
am...@googlegroups.com

{#HS:2055148375-112598#}

On Thu, Nov 3, 2022 at 2:37 AM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Thanks for the response! I was thinking there might be a benefit to retaining Y and branching/bounding on it rather than a bunch of binaries. I completely disregarded the fact that there would be no guarantee that the X's were binary and not fractional at the nodes.

On Wed, Nov 2, 2022 at 9:54 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

If you set a much higher priority on the Y_i variables than on the X_it variables, then it is likely that the solution will be found and proved without any branching on the X_it variables. However, that is not guaranteed, as each solver has its own methods of making branching decisions.

I can see how Y[i] might be defined by an expression like sum {t in T} t * X[i,t], where sum {t in T} X[i,t] = 1. Then the Y[i] variables could be substituted out of the problem, and necessarily the would not be branched on. I do not see a way to substitute the X[i,t] variables out of the problem, however.

--
Robert Fourer
am...@googlegroups.com