Logical conditions

Specific Domains Optimization (Mathematical)
,
1

I’m working on an optimization problem in JuMP where I need to ensure that certain constraints are enforced based on a binary variable. Here are the variables and constraints I have defined in my model:

Variable Definitions:

@variable(model, 0 <= x[1:n] <= 1)
@variable(model, 0 <= w[1:n, 1:T] <= 1)
@variable(model, 0 <= v[1:T] <= 1)
@variable(model, 0 <= wn[i=1:T, j=1:T] <= 1)
@variable(model, beta[1:T], Bin)

Constraints:

@constraint(model, sum_w[i=1:n], x[i] >= sum(w[i, j] for j in 1:T))
@constraint(model, sum_wn[i=1:T], v[i] >= sum(wn[i, j] for j in i:T))
@constraint(model, [t=1:T], v[t] <= beta[t])
@constraint(model, [i=1:n, t=1:T], w[i, t] <= 1 - beta[t])
@constraint(model, [i=1:T, t=1:T], wn[i, t] <= 1 - beta[t])

Desired Logic:

The binary variable \beta is used to enforce the following conditions:

When \beta[t] = 1:

  • Variable v[t] can take a positive value.

  • Variables w[i,t] and wn[i,t] must be zero.

When \beta[t] = 0:

  • Variable v[t] must be zero.

  • Variable wn[i,t] and w[i,t] can take positive values.

This is enforced by the last three constraints defined above.

To enforce that wn must hit its maximum possible values before w can take a positive value when \beta[t] = 0, I have defined the following constraint:

@constraint(model, [i=1:T, t=1:T], sum(wn[i, j] for j in i:T) - v[t] >= -beta[t])

Problem:

Despite the above constraints, the results suggest that the variables wn are not necessarily taking their maximum possible value or even positive values before the variable w takes a positive value.

Question:

What could be going wrong with my current approach?

2

Try to use an SOS-1 approach here.

Disclaimer: sorry , I am on my phone :sweat_smile:.

Let x be the binary decision variable and p another one. To enforce that p can take arbitrary values if and only if b is equal to one use

(1-x)*p = 0

Or it’s relaxed counterpart

(1-x)*p <= eps

Which helps the solver to navigate the zero crossing. To hit the maximum use

(1-x)*(p-maxval) = 0

Or its relaxed counterpart.

3

I’ve tried using indicator constraint (to replace the last constraint) to enforce the conditions as well, but that gives same results. There is something incorrect in the way I’m trying to enforce the logical conditions.

4

Hi @papar,

You need to introduce a new binary variable:

n, T = 2, 3
model = Model()
@variables(model, begin
    0 <= x[1:n] <= 1
    0 <= w[1:n, 1:T] <= 1
    0 <= v[1:T] <= 1
    0 <= wn[1:T, 1:T] <= 1
    beta[1:T], Bin
    # new
    z_wn[1:T, 1:T], Bin
end)
@constraints(model, begin
    [i in 1:n], x[i] >= sum(w[i, :])
    [i in 1:T], v[i] >= sum(wn[i, i:T])
    [t in 1:T], v[t] <= beta[t]
    [i in 1:n, t in 1:T], w[i, t] <= 1 - beta[t]
    [i in 1:T, t in 1:T], wn[i, t] <= 1 - beta[t]
    # new
    # z_wn can be 1 only if w_n is at it's maximum
    [i in 1:T, t in 1:T], z_wn[i, t] <= w_n[i, t]
    # w can be positive only if z_wn is 1
    [i in 1:n, t in 1:T], w[i, t] <= z_wn[i, t]
end)

But w and wn are not the same size, so I don’t really know what constraint you intend?

5

We will have a problem with the following constraint:

# z_wn can be 1 only if w_n is at its maximum
[i in 1:T, t in 1:T], z_wn[i, t] <= w_n[i, t]

This is due to the constraint:

@constraint(model, sum_wn[i=1:T], v[i] >= sum(wn[i, j] for j in i:T))

Variables wn are restricted by variables v, and in most cases, both of these variables will take values less than 1. If we define the constraint as suggested, it will try to enforce wn variables to hit 1, which usually will not happen.

The maximum possible values of variables wn at t are given by:

wn_{i,t} = v_i - \sum_{j=i}^{t-1} wn_{i,j}

We will need to enforce this as constraint. This is why I was trying to defining a constraint to enforce sum(wn[i, j] for j in i:T) - v[t] >= 0

You are right that w and wn are the same size, but that doesn’t matter as the index t is the same across both, at which decisions are made based on the logical conditions.

Could you please provide further clarification or an alternative approach to correctly enforce the constraint that z_wn can be 1 only if wn is at its maximum as defined below? wn_{i,t} = v_i - \sum_{j=i}^{t-1} wn_{i,j}

6

I interpreted 'at the maximum" to be the upper bound.

You’ll need to change the constraint to something like

    [i in 1:T, t in 1:T], wn[i, t] <= v[i] - sum(wn[i, 1:t-1])
    # z_wn can be 1 only if w_n is at it's maximum
    [i in 1:T, t in 1:T], z_wn[i, t] <= 1 - (v[i] - sum(wn[i, 1:t-1]) - w_n[i, t])

but I didn’t check the details very carefully. I don’t know that I understand your variables very well.

You’re really just looking for a constraint like:
z_wn[i, t] <= 1 - (limit - wn[i, t])
So that if wn is less than limit, then the right-hand side is 1 - positive_value which forces z_wn to 0.

If limit is not in [0, 1] then you’ll need some additional scaling factor in there to get it to work.

1 Like
7

Thank you for your help. Changing the last two constraints to the following seems to work as intended:

[i in 1:T, t in 1:T], sum(wn[i, j] for j in i:T) - v[t] >= -(1 - z_wn[t])
[i in 1:n, t in 1:T], w[i, t] <= z_wn[i, t]

However, I still have a related issue. I want to remove the upper bounds of variables v and wn while still enforcing the same conditions. How can I use indicator constraints to enforce these conditions without using big-M? I’m confused about whether we also need to add constraints for the reverse condition when the binary variable is zero.

The conditions are:

  1. wn should reach its maximum possible value before w can take a positive value.
  2. Ensure that the variable v is zero when either wn or w are positive, and vice versa.

I was considering defining these constraints to replace the ones involving binary variables as follows:

[i in 1:T, t in 1:T], z_wn[t] --> {sum(wn[i, j] for j in i:T) >= v[i]}
[i in 1:n, t in 1:T],  w[i,t] <= z_wn[t]
[t in 1:T], z_wn[t] --> {v[t] == 0}
# Unsure if these two are also needed
[i in 1:T, t in 1:T], !z_wn[t] --> {wn[i, t] == 0}
[i in 1:n, t in 1:T], !z_wn[t] --> {w[i, t] == 0}
# Or instead of these two I need the following three constraints
[i in 1:T, t in 1:T], beta[t] --> {wn[i, t] == 0}
[i in 1:n, t in 1:T], beta[t] --> {w[i, t] == 0}
[t=1:T], beta[t] + z_wn[t] <=1

For clarity, I’ve incorporated your previous answer into the code below (before switching to indicator constraints):

model = Model()
@variables(model, begin
    0 <= x[1:n] <= 1
    0 <= w[1:n, 1:T] <= 1
    0 <= v[1:T] <= 1
    0 <= wn[1:T, 1:T] <= 1
    beta[1:T], Bin
    # new
    z_wn[1:T], Bin
end)
@constraints(model, begin
    [i in 1:n], x[i] >= sum(w[i, :])
    [i in 1:T], v[i] >= sum(wn[i, i:T])
    [t in 1:T], v[t] <= beta[t]
    [i in 1:n, t in 1:T], w[i, t] <= 1 - beta[t]
    [i in 1:T, t in 1:T], wn[i, t] <= 1 - beta[t]
    # new
    # z_wn can be 1 only if wn is at its maximum
    [i in 1:T, t in 1:T], sum(wn[i, j] for j in i:T) - v[i] >= -(1 - z_wn[t])
    # w can be positive only if z_wn is 1
    [i in 1:n, t in 1:T], w[i, t] <= z_wn[i, t]
end)
8

What solver are you using? Only some solvers (like Gurobi) have direct support for indicator constraints. For solvers like HiGHS, we rewrite the indicator based on the variable bounds, so removing the variable bound won’t work.

I would strongly encourage you to keep the upper bound, and to choose a sensible value.

9

I’m using Xpress solver. Choosing appropriate upper bounds is too challenging here. The run time is too long with upper bounds and that’s because of poor scaling. Regardless of the support for solvers other than Gurobi for indicator constraints, may I check whether my implementation of indicator constraints to enforce these conditions is correct?

I’m able to get results with indicator constraints, but not sure whether there are some redundant or if I need any additional constraints.

10

Getting these constraints correct can be subtle. I don’t know if I understand your explanation of the problem well enough to give a definitive answer.

I’m able to get results with indicator constraints, but not sure whether there are some redundant or if I need any additional constraints.

The best thing you can do is always check after the fact that the solution satisfies your expectations. That way, you don’t need to think in terms of indicator constraints, etc, but you can check something like this:

tol = 1e-6
for i in 1:T, t in 1:T
    if value(wn[i,t]) > tol || value(w[i,t]) > tol
        @assert value(v[i]) <= 1e-6
    end
end
11

The solution meets my expectations to a certain extent, but I still have some confusion. I have added some explanations and hope it should be clearer.

I want to enforce the following constraint:

For all i \in \{1, \ldots, T\} and t \in \{1, \ldots, T\}:
\sum_{j=i}^{t} wn[i, j] \geq v[i]
when w is positive.

When either w or wn or both are positive, the variable v must be zero. Conversely, when the variable v is positive, both w and wn must be zero.

To enforce these conditions, I define the following set of indicator constraints:

  1. For all i \in \{1, \ldots, T\} and t \in \{1, \ldots, T\}:
    z\_wn[t] \implies \left( \sum_{j=i}^{t} wn[i, j] \geq v[i] \right)

  2. For all i \in \{1, \ldots, n\} and t \in \{1, \ldots, T\}:
    w[i, t] \leq z\_wn[t]

  3. For all t \in \{1, \ldots, T\}:
    z\_wn[t] \implies (v[t] = 0)

However, I am unsure whether I additionally need the following constraints to enforce that either v or (w and wn) are positive:

  1. For all i \in \{1, \ldots, T\} and t \in \{1, \ldots, T\}:
    \beta[t] \implies (wn[i, t] = 0)

  2. For all i \in \{1, \ldots, n\} and t \in \{1, \ldots, T\}:
    \beta[t] \implies (w[i, t] = 0)

  3. For all t \in \{1, \ldots, T\}:
    \beta[t] + z\_wn[t] \leq 1

Is it clear now? The question I have is whether I also need constraints 4 to 6 here to fully enforce the conditions mentioned above?

12

image

This constraint does’t include t. This is partially what I meant by subtle :smile:

13

Good spot! I’ve corrected it now (see above). Here’s the updated constraint:

For all i \in \{1, \ldots, T\} and t \in \{1, \ldots, T\}: \sum_{j=i}^{t} wn[i, j] \geq v[i]

Thanks for pointing that out! Hopefully, this captures the intent correctly now. :blush:

By the way, I’m still unsure if I need the additional constraints 4 to 6 to ensure either v is zero or both w and 𝑤n are zero. Do you think I need these constraints as well?

Thanks again for your help!

14

It’s useful to write out a truth table for all of the possible conditions, and check each of them.

Considering (1)-(6):

  • I choose \beta[t] = 0 which is always feasible, so (4), (5), and (6) never apply.

Therefore, considering only (1), (2), and (3):

Case w[i,t] > 0:

  • by (2), z\_wn[t] = 1
  • by (2) and (1), the top constraint holds
  • by (2) and (3), v will be zero

Case w[i,t] = 0:

  • by (2), z\_wn[t] = 0 OR z\_wn[t] = 1
  • nothing else can be said

Case wn[i,t] > 0:

  • nothing can be said. You probably need wn[i,t] \le z\_wn[t]?

Case v[t] > 0:

  • by (3), we know that z\_wn[t] = 0, other wise v[t] = 0
  • by (3) and (2), we know that w[i,t] = 0
  • nothing can be said about wn

When writing these sorts of constraints you really need to be careful to consider every possible outcome that could happen.

15

wn doesn’t have an upper bound of 1, so if I add this constraint it will make the problem infeasible. The maximum possible value of wn happens when constraint 1 is enforced.

Do I need an additional constraint here on wn? If so, would something like below work? Introduce binary variables y \in \{0, 1\} along with constriants

\begin{cases} y = 1 \implies v \geq \epsilon \\ y = 1 \implies wn = 0 \end{cases}

where \epsilon is a small number to avoid strict inequality v>0