1

To provide a clear description of my problem, let me outline the scenario. I have a binary variable $\phi_{k,c}$ where $k$ is an index belonging to the set $\{1, 2, 3, ..., 9\}$. As an example, for a specific value of $c$, the variable $\phi_{k,c}$ might take the following binary sequence: $0 0 0 1 0 0 1 0 1$. My objective is to formulate a constraint in AMPL that selects the minimum value of $k$ when $\phi_{k,c}$ equals $1$. In the provided example, I would like to capture the fact that the first occurrence of $1$ in the array corresponds to $k = 4$.

The expression I have in mind is $k_{min}(c) = \min\{k \; | \; \phi_{k,c} = 1\}$. However, this doesn't seem to be a well-defined mathematical formula.

I am seeking your assistance in formulating a mathematical constraint in AMPL that accurately represents the selection of the minimum value of $k$ when $\phi_{k,c}$ equals $1$.

EhsanK
  • 5,864
  • 3
  • 17
  • 54
Liu Fan
  • 11
  • 1
  • 2
    Does this answer your question? How to find the index of the item, the first time appears? – RobPratt Dec 27 '23 at 14:52
  • 1
    Will this formulation work for your model? Define param K integer > 0; and then var phi {1..K} binary; and var kmin in 1..K;. Then specify the constraint by subj to kminDefn: kmin = min {k in 1..K} (k*phi[k] + K*(1-phi[k]));. To keep the example simple, I have left out the index c, but you could introduce it by adding another index set for phi and kmin. (Applying min to an expression involving variables will work with the newer versions of AMPL MIP solvers.) – 4er Dec 27 '23 at 15:41
  • @4er what you suggest is very similar to my answer :) – Kuifje Dec 27 '23 at 16:26

3 Answers3

0

The index of the non zero $\phi_{k,c}$ variable is given by a variable $x_{k,c} \in \mathbb{R}^+$ with constraint $$ x_{k,c} = k \cdot \phi_{k,c} \quad \mbox{for each $k,c$} \tag{1} $$

You want the minimum of all (non zero) $x_{k,c}$ variables. You can introduce variable $z_c \in \mathbb{R}^+$ and add constraint $$ z_c \le x_{k,c}+9(1-\phi_{k,c}) \quad \mbox{for each $k,c$} \tag{2} $$

You can maximize $z_c$ to make sure that $z_c$ actually reaches one of the $x_{k,c}$ variables.

But this may not be possible (depending on the nature of your problem which is not explicitly described). In this case you can define extra binary variables $\delta_{k,c} \in \{0,1\}$ that take value $1$ if $z_c$ matches value $x_{k,c}$ and add constraints

\begin{align} x_{k,c} - k(1-\delta_{k,c}) &\le z_c \quad &\mbox{for each $k,c$} \tag{3} \\ \delta_{k,c} &\le \phi_{k,c} \quad &\mbox{for each $k,c$} \tag{4} \\ \sum_{k} \delta_{k,c} &= 1 \quad &\mbox{for each $c$} \tag{5} \\ \end{align}

Equation $(5)$ enforces that exactly one of the $\delta_{k,c}$ variables takes value $1$, thus enforcing with $(3)$ that exactly one index $x_{k,c}$ is reached by $z_c$. Constraint $(4)$ makes sure that $\phi_{k,c}=0 \implies \delta_{k,c} = 0$.

Here is small example of how to achieve this with PuLP (for a unique value $c$ which is implicit in what follows):

import pulp
import random

sequence length


N = 9


problem definition


prob = pulp.LpProblem("first_one", pulp.LpMaximize)


variables


phi = pulp.LpVariable.dicts("sequence", [k for k in range(1,N+1)], cat=pulp.LpBinary)
x = pulp.LpVariable.dicts("index", [k for k in range(1,N+1)], lowBound=0, cat=pulp.LpContinuous)
z = pulp.LpVariable("z", lowBound=0, cat=pulp.LpContinuous)


objective function


prob += z


constraints


for k in x:
    # define the index of non zero phi variables
    prob += x[k] == kphi[k]
    # capture smallest index of non zero phi variable
    prob += z <= x[k] + N(1-phi[k])


randomly force 3 phi variables to take value 1


for _ in range(3):
    k = random.choice([_ for _ in range(1, N+1)])
    prob += phi[k] == 1


solve problem


prob.solve()


display phi variables


for k in phi:
    print(k,pulp.value(phi[k]))


display smallest index of non zero phi variable


print("smallest index: ",pulp.value(z))
Kuifje
  • 13,324
  • 1
  • 23
  • 56
  • I am very grateful for the response. I apologize for not describing the question very clearly. My question is a signal timing optimization problem: Phi[k, c] be a binary variable, where Phi[k, c] = 1 indicates that phase c is green in stage k, otherwise Phi[k, c] = 0. For a specific vehicle, the phase it enters the intersection is determined by a known parameter P[v]. After the vehicle arrives at the intersection, in multiple stages k, it may encounter situations where the phase is the same as the phase at which the vehicle entered the intersection, i.e., multiple k satisfy Phi[k, P[v]] = 1. – Liu Fan Dec 27 '23 at 13:54
  • For example, if k ∈ {1, 2, ..., 9}, for a specific vehicle v, Phi[k, P[v]] may be 0 0 0 1 0 0 1 0 1, indicating that the vehicle v can enter the intersection in stages k=4, k=7, and k=9. However, obviously, the vehicle v will only choose to enter the intersection in stage k=4 (min{4, 7, 9}). Therefore, I need to express the stage at which the vehicle enters the intersection earliest using a formula. – Liu Fan Dec 27 '23 at 13:58
  • Denoted as x[v], where x[v] = min{k | Phi[k, P[v]] = 1}. However, this doesn't seem to be a well-defined mathematical formula. I sincerely thank you and look forward to your response. This is my first time seeking help in Operations Research, and I'm not sure how to reply based on your response. There is a word limit for the "add comment" feature, so I've divided my question into three parts. I appreciate your understanding. – Liu Fan Dec 27 '23 at 14:02
  • I don't know if you can see the "add comment" section. I tested in AMPL based on your response, but there is still an issue. I'm not clear about the meanings of the additional variables z[c] and Delta[k, c] that you introduced. Could you provide an explanation based on my previous three "add comment" sections? – Liu Fan Dec 27 '23 at 14:43
  • $z_c$ is your $k_{min}(c)$. Try with only constraints $(1)$ and $(2)$, and by maximizing $z_c$. – Kuifje Dec 27 '23 at 18:14
  • @LiuFan I have added a small example in order to clarify my answer. – Kuifje Dec 27 '23 at 20:03
0

lets suppose $x_c$ is the variable we need is an integer between [1,9]
assume $\beta_{kc}$ is binary, this will start taking value 1 from the first occurance of $\Phi_{kc}=1$ till end
cons 1: $$ \beta_{kc} \leq \sum_1^k\Phi_{kc} \hspace{1 cm} \forall k,c$$
cons 2: $$ \Phi_{kc}\leq 9\beta_{kc} \hspace{1 cm} \forall k,c$$
cons 3: $$ x_c \leq k\beta_{kc} + 9(1-\beta_{kc}) \hspace{1 cm} \forall k,c$$
cons 4: $$ 1+k(1-\beta_{kc}) \leq x_c \hspace{1 cm} \forall k,c$$

for your example $\Phi_{kc}$ taking values 000100101
$\beta_{kc}$ will be 000111111
$x_c$ is forced to take 4 because of constraints 3,4

tarun raj
  • 1
  • I agree with your constraints 3 and 4. But why do you need constraints 1 and 2? It seems that you can simply use 3 and 4, replacing $\beta_{k,c}$ by $\phi_{k,c}$. – Kuifje Dec 31 '23 at 15:29
0

Another way is to get a $k$ series of binary variables, say $z_{k,c}$ that will have $1$ only for the smallest $k$ $\phi_{k,c}=1$

Constraints
$ z_{k,c} \le \phi_{k,c}$
$ \phi_{k,c} - \sum_{j \le k} \phi_{j,c} \le z_{k,c} \le 1 - \sum_{j \le k}z_{j,c} \quad \forall k,c$

Then $ \sum_k kz_{k,c} \quad \forall c$ gives you the smallest $k$

Sutanu Majumdar
  • 3,461
  • 1
  • 2
  • 11