1
$\begingroup$

I’m working on an optimization problem and need help with correctly prioritizing the allocation of certain variables in a constraint. The rules are:

  • Only one of the variables $y_{t}$, $zn_{t}$ and $z_{t}$ can be non-zero at a time.
  • A prioritization rule is applied to the variables $zn_{t}$ and $z_{t}$. The model initially attempts to satisfy the constraint using $zn_{t}$. However, if $zn_{t}$ proves inadequate, the model then resorts to $z_{t}$, requiring $zn_{t}$ to be set to zero.

The variables are defined as:

  • $0 \leq x \leq 1$
  • All the variables $y_{t}$, $zn_{t}$ and $z_{t}$ are continuous and bounded between 0 and 1.
  • We define binary variables $b_{t}$, $bz_{t}$ and $bzn_{t}$ for enforcing some of the constraints.

The heart of this problem lies in the constraint, which is defined as follows: $\begin{align} & C_{t} \left( x - \sum_{j=1}^{t} z_{j} \right) +\sum_{i=2}^{t} CN_{i, t-i+1} \left( y_i - \sum_{j=i}^{t} zn_{j} \right) \nonumber \\ & + S_{t} \cdot z_{t} + SN_{t} \cdot zn_{t} - CO_{t} \cdot y_{t} - E_t = 0 \quad \forall t \end{align}$

Where:

  • $CN_{i, t-i+1}$ represents values derived from a specific position, determined at the time $i$ and assessed at the later time $t$.

At $t=1$, we can assume that all variables except $x$ takes zero value or more conveniently define the constraint differently for $t=1$ from $t>1$. For $t=1$, we can define this constraint as: $C_{1} \cdot x - E_{1} = 0$

If $C_{t} \left( x - \sum_{j=1}^{t} z_{j} \right) +\sum_{i=2}^{t} CN_{i, t-i+1} \left( y_i - \sum_{j=i}^{t} zn_{j} \right) \nonumber - E_t < 0$ then $zn_{t}$ or $z_{t}$ must take non-zero value. If it is greater than zero then $y_{t}$ must take take non-zero value. How can I ensure that these prioritization rules are consistently applied within the constraints of my model?

$\textbf{Other Constraints:}$ These enforces some of the rules set out above, except priortisation. These can be ignored for the purpose of the question.

$\begin{alignat}{2} & \sum_{j=i}^{t} zn_{j} && \leq y_i \quad && \forall i \\ & \sum_{j=1}^{t} z_{j} && \leq x \quad && \forall t \\ & y_{t} && \leq b_{t} \quad && \forall t \\ & zn_{t} && \leq bzn_{t} \quad && \forall t \\ & z_{t} && \leq bz_{t} \quad && \forall t \\ & b_{t} + bzn_{t} + bz_{t} && \leq 1 \quad && \forall t \\ \end{alignat}$

Improve this question
$\endgroup$
4
  • $\begingroup$ You mentioned that you have three sets of binary variables, but gave no specifics on how they are used. Should we assume that, for example, $b_t = 1 \iff y_t > 0?$ $\endgroup$
    – prubin ♦
    Commented Jan 16 at 3:55
  • $\begingroup$ @prubin That's correct. I have edited the question linked the variables to binary variables by defining constraints. The key question is how to enforce that $zn_{t}>0$ should be tried first but if it is unable to satisfy the constraint then $z_{t}>0$ should be enforced instead. This needs to be done for all time periods $t$. So bringing the binary variables into the objective function is not an option. $\endgroup$
    – Lemma
    Commented Jan 16 at 7:35
  • $\begingroup$ Let $Q_t = C_{t} \left( x - \sum_{j=1}^{t} z_{j} \right) +\sum_{i=2}^{t} CN_{i, t-i+1} \left( y_i - \sum_{j=i}^{t} zn_{j} \right) \nonumber - E_t.$ Just to be clear, you want the choice of which variable among $y_t, z_t, zn_t$ is nonzero to depend on $Q_t$ (which contains all three of those variables) and not on $Q_{t-1}$ (which contains none of them)? $\endgroup$
    – prubin ♦
    Commented Jan 16 at 16:20
  • $\begingroup$ @prubin That's correct. The choice of the variables $y_{t}$, $z_{t}$, $zn_{t}$ will depend upon $Q_{t}$ at each $t$ and not on $Q_{t-1}$. For $t=1$, we can assume this expression simplifies to $C_{1} \cdot x - E{1}$ (that is we don't have any of the other variables), and then for $t \geq 2$ it is as you have written. $\endgroup$
    – Lemma
    Commented Jan 16 at 16:40

2 Answers 2

Reset to default
2
$\begingroup$
  • A prioritization rule is applied to the variables $zn_{t}$ and $z_{t}$. The model initially attempts to satisfy the constraint using $zn_{t}$. However, if $zn_{t}$ proves inadequate, the model then resorts to $z_{t}$, requiring $zn_{t}$ to be set to zero.

This is not a perfectly clear statement. if the primary objective is to maximize the number of $bzn_{t}$ set to $1$, that is

$$ \max \sum_t bzn_{t} $$

then you should do a first optimization with this objective.

If the objective value of this first problem is $K$, then you need to solve a second optimization problem with the original objective and the additional constraint:

$$ \sum_t bzn_{t} = K $$

The solution of the first problem is feasible for the second one, and thus can be provided as initial integer feasible solution to the solver for the second problem.

If the solver supports lexicographic optimization, you can try to use this feature directly.

Improve this answer
$\endgroup$
13
  • $\begingroup$ The constraint is defined for a set of future years. In some years, activating $zn_{t}$ may be sufficient to satisfy the constraint while $z_{t}$ is set to zero. There may be years when activating $zn_{t}$ is not able to satisfy the constraint and we will need to activate $z_{t}$ instead. In some years, we will need to activate $y_{t}$ instead to satisfy the constraint. In any year only one of these three variables can be non-zero. The objective function is simply $\text{minimise } constant \cdot x$ and it is not to maximise the number of $zn_{t}$. Does this clarify the question? $\endgroup$
    – Lemma
    Commented Jan 16 at 15:38
  • $\begingroup$ I have asked a very similar question which may be easier to follow: or.stackexchange.com/questions/11530/logical-conditions $\endgroup$
    – Lemma
    Commented Jan 16 at 15:40
  • $\begingroup$ @Lemma How important is the prioritization rule compared to this objective? $\endgroup$
    – fontanf
    Commented Jan 16 at 15:51
  • $\begingroup$ This prioritization rule is more important than the actual objective. The issue is that this constraint is defined for $\forall t$ or a set of time periods. So, I am not sure if there is a practical way of bringing $zn_{t}$ for the whole vector of time periods or their associated binary variables into the objective to enforce this prioritization condition for all time periods. $\endgroup$
    – Lemma
    Commented Jan 16 at 15:58
  • $\begingroup$ @Lemma then you should do what I wrote in the answer $\endgroup$
    – fontanf
    Commented Jan 16 at 16:10
0
$\begingroup$

This solution is adapted from an answer provided on the Operations Research Stack Exchange, accessible here: Logical conditions.

The original constraint in the problem is given by: \begin{align} C_{t} \left( x - \sum_{j=1}^{t} z_{j} \right) &+ \sum_{i=2}^{t} CN_{i, t-i+1} \left( y_i - \sum_{j=i}^{t} zn_{j} \right) \\ &+ S_{t} \cdot z_{t} + SN_{t} \cdot zn_{t} - CO_{t} \cdot y_{t} - E_t = 0 \quad \forall t \end{align}

We define $B_{t}$ as:

$B_{t} = C_t \left( x - \sum_{j=1}^{t} z_j \right) + \sum_{i=2}^{t} CN_{i, t-i+1} \left( y_i - \sum_{j=i}^{t} zn_j \right)-E_{t}$

We introduce three binary variables $b_{t}$, $bzn_{t}$, and $bz_{t}$, along with their constraints: $y_{t} \le b_{t}, \quad zn_{t} \leq bzn_{t}, \quad z_{t} \leq bz_{t}, \quad b_{t} + bzn_{t} + bz_{t} = 1$

The logical conditions to be enforced are: \begin{alignat}{2} & b_{t} && = 1 &&\iff B_{t} \ge 0, \\ & bzn_{t} && = 1 &&\iff 0 > B_{t} \ge -SN_{t}, \\ & bz_{t} && = 1 &&\iff -SN_{t} > B_{t} \ge -S_{t}. \end{alignat}

Each binary variable $b_{t}$, $bzn_{t}$, $bz_{t}$ corresponds to a specific, non-overlapping range of $B_{t}$. This ensures that the ranges of $B_{t}$ are mutually exclusive and cover all possible scenarios. Since only one binary variable can be active at a time, and each is linked to a distinct range of $B_{t}$, it's sufficient to enforce that if a binary variable is 1, $B_{t}$ must fall within its respective range. The model's structure inherently handles the reverse implication.

If $B_{t} = -SN_{t}$, the model allows for the possibility that either $bz_{t}=1$ or $bzn_{t}=1$, which implies that either $zn_{t}$ or $z_{t}$ could be non-zero. To address this issue, the third condition is modified to:

$-SN_{t} - \epsilon \ge B_{t} \ge -S_{t}$

where $\epsilon$ is a small positive. This change effectively eliminates the overlap in the ranges, making the range $-SN_{t} - \epsilon < B_{t} < -SN_{t}$ infeasible.

Finally, the following inequalities enforce the logical conditions, where $M$ is a valid upper bound on $B$: \begin{align} B_{t} &\ge -SN_{t} \cdot bzn_{t} - S_{t} \cdot bz_{t}, \\ B_{t} &\le M \cdot b_{t} - (SN_{t} + \epsilon) \cdot bz_{t}. \end{align}

These constraints ensure that each binary variable's activation correctly reflects the intended range of $B_{t}$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.