Enforcing Variable Allocation Priorities in JuMP Model

Specific Domains Optimization (Mathematical)
,
1

Hello Everyone,

I’m working on an optimization problem in Julia’s JuMP and need help with correctly prioritizing the allocation of certain variables in a constraint. My primary constraint is as follows:

C \cdot x + S \cdot z + SN \cdot zn - CO \cdot y - E = 0

Here are the rules for the allocation of variables z, zn, and y:

  1. Only one of z, zn, and y can be non-zero at a time.
  2. z should only be non-zero if zn cannot satisfy the constraint.
  3. zn is tried first if C \cdot x - E < 0 but if it is unable to satisfy the constraint then z is activated instead. If C \cdot x - E > 0 then y becomes active (i.e. non-zero).

I’ve implemented the following constraints in JuMP, but I am unsure if they correctly enforce the priority of zn over z and other rules:

using JuMP
model = Model()
@variables(model, begin
    0 <= x <= Xmax
    0 <= y <= Ymax
    0 <= z <= Zmax
    0 <= zn <= ZNmax
    b, Bin
    bz, Bin
    bzn, Bin
end)

@constraints(model, begin
    C * x + S * z + SN * zn - CO * y - E == 0
     y <= Ymax *b 
    z <= Zmax*(1 - b)
    zn <= ZNmax*(1 - b)
    z <= Zmax * bz
    zn <= ZNmax * bzn
    bz <= bzn # This is to prioritise allocation of z over zn
end)

I am confused whether the constraints z <= Zmax * (1 - b) and zn <= ZNmax * (1 - b) could inadvertently cause both z and zn to be active simultaneously, potentially making the model infeasible or conflicting with other constraints.

My specific questions are:

  • Does the use of binary variables b, bz, and bzn effectively model the prioritization of zn over z?
  • Are the constraints involving the binary variables appropriately formulated to reflect the stated rules, especially considering the potential for simultaneous activation of z and zn? Should I introduce a constraint b + bz + bzn ≤ 1 and replace the constraints z ≤ Zmax (1-b) and zn ≤ ZNmax (1-b)?

Thanks in advance for your help!

2

Hi @Lemma, welcome to the forum.

Do you have data for the constants?

One approach is to use an objective function like Min, 2 * b_z + b_zn so that zn will be used before z.

Here’s how I would write it:

using JuMP
model = Model()
@variables(model, begin
    0 <= x <= Xmax
    0 <= y <= Ymax
    0 <= z <= Zmax
    0 <= zn <= ZNmax
    b_y, Bin
    b_z, Bin
    b_zn, Bin
end)
@constraints(model, begin
    C * x + S * z + SN * zn - CO * y - E == 0
    b_z + b_zn + b_y == 1
    y <= Ymax * b_y
    z <= Zmax * b_z
    zn <= ZNmax * b_zn
end)
@objective(model, Min, 2 * b_z + b_zn)
3

Thank you

In reality, these are vectors of constraints. The variables and constraints need to be defined for different time periods, and I’m not sure whether the logic of bringing the binary variables into the objective function can be made to work, as we need to ensure this prioritization at each time period. Isn’t there a way to make the prioritization of allocating variable zn over z work within the constraints alone?

I can try to produce data for constants if it is difficult to advise without it. We can assume upper bounds of all variables to be 1, if it helps.

4

I’ve provided detailed data to better illustrate the intricacies involved. I recognize that the actual constraint is more complicated than it might initially appear. Thus, I am not entirely sure if providing further detailed information will simplify or complicate the process of seeking help!

The heart of this problem lies in the constraint:

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

In this formulation:

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

  • As stated earlier only one of 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}, necessitating zn_{t} to be set to zero.

\textbf{Other Constraints:}

\sum_{j=i}^{t} zn_{j} \leq y_i \quad \forall i \\ \sum_{j=1}^{t} z_{j} \leq x \quad \forall t

\begin{alignat}{2} & y_{t} && \leq b_{t} \quad && \forall t \\ & zn_{t} && \leq bzn_{t} \quad && \forall t \\ & z_{t} && \leq bz_{t} \quad && \forall t \end{alignat}

\begin{equation} b_{t} + bzn_{t} + bz_{t} \leq 1 \quad \forall t \end{equation}

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

Here is some Julia code to for data:


CO_t = [101952.54, 108607.57, 104110.54, 101795.33, 96946.19, 105835.76, 97503.49, 115670.92, 118546.51, 95337.66]
S_t = [121669.00, 111155.80, 112721.78, 127023.87, 92841.44, 93485.17, 90808.74, 123304.79, 121126.27, 124800.49]
SN_t = [139144.73, 131966.34, 118459.17, 131221.17, 104730.98, 125596.84, 105734.13, 137786.76, 120873.93, 116586.48]
C_t = [6322.78, 8871.17, 7280.75, 7842.17, 5093.95, 8088.18, 8060.48, 8084.67, 9718.74, 8409.10]
E_t = [5000.0, 5555.56, 6111.11, 6666.67, 7222.22, 7777.78, 8333.33, 8888.89, 9444.44, 10000.0]
CN2 = [4061.56, 5092.99, 3375.76, 5303.79, 6717.18, 4274.28, 5669.64, 3527.19, 5865.31, 4157.62] # i =2
CN3 = [3732.77, 5346.05, 3080.43, 6315.76, 3018.78, 5711.27, 4080.03, 5940.78, 6848.75] # i =3
CN4 = [3995.01, 5304.63, 5368.17, 5289.01, 3892.33, 6811.00, 4788.50, 6385.63, 5425.57] # i =4
CN5 = [5797.92, 4189.75, 6255.19, 4586.02, 6524.41, 5325.09, 6526.94, 3076.77]
CN6 = [5770.13, 5901.02, 5005.30, 6824.33, 5575.96, 4695.42]

In the model, the selection of data from the CN arrays depends on the time period (t) and the status of the corresponding y variables. Specifically:

  • At time t = 2 , if the variable y_{2} is positive, then we utilize the data from the array CN2.

  • Similarly, at time t = 5, if y_{5} is positive, we use the data from CN5.

A key expression in the constraint is:

\sum_{i=2}^{t} CN_{i, t-i+1} \left( y_i - \sum_{j=i}^{t} zn_{j} \right)

which dynamically incorporates values from the CN arrays based on the time period t and the state of y_i and zn_j variables.

For instance, when evaluated at t = 5 with the conditions that only y_{2} and y_{5} are positive (and treating them as 1 for simplicity), while all zn variables are zero, the expression calculates to 11101.71. This result is derived as follows:

  • From the array CN2, we take the value at the 4th position (accounting for i = 2 at t = 5)), which is 5303.79.

  • From the array CN5, we select the value at the 1st position (since i = 5 at t = 5), which is 5797.92.

By summing these two values, 5303.79+ 5797.92, we obtain the total of 11101.71.

Please let me know if it is still unclear or if it is not possible to model prioritisation constraint using integer programming techniques?

5

What do z and zn represent, practically speaking, in the model?

If z is a regular power station and zn is some emergency generator, then the prioritization should happen automatically with their objective costs.

I don’t now if you can easily enforce a constraint like “if x makes the problem infeasible, use y.”

Perhaps someone else has an idea though.

6

The objective is defined as: \text{Minimize } Z = MV \cdot x.

These variables z_{t} and zn_{t} represent the sales of initial and new assets, respectively. We sell and generate revenue equal to S_{t} or SN_{t} at time t, depending on whether the initial or new asset is sold. Sales are made when the return from the assets is less than the expenses E_{t} at time t.
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 sales are made. If it is greater than zero then purchases are made. The expression in brackets represent amount of asset available (post-sale).

The variable y_{t} represents purchases at a cost of CO_{t} at time t. We purchase assets at a cost of CO_{t} when the revenue from assets exceeds expenses E_{t}. The question is: Can we prioritize the sale of new assets over initial assets, but make it mutually exclusive?

If mutual exclusivity was not required, I guess this could be achieved by adding the constraint:bz_{t} \leq bzn_{t}.

I have now also posted this question on the OR Stack Exchange in case someone there knows the answer: combinatorial optimization - Priotization rules for variable allocation in linear programming - Operations Research Stack Exchange

7

Is a big-M type of approach not possible for this problem?

8

One thing to consider is that constraints can only enforce feasibility. They can’t be used to incentivize the model to prefer one solution over another.

If the solution is infeasible unless it uses z, then that works. But if it can satisfy either by using z or by using zn, then this seems like something that should go in the objective.