1
$\begingroup$

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$.

$\endgroup$
3
  • 2
    $\begingroup$ Does this answer your question? How to find the index of the item, the first time appears? $\endgroup$
    – RobPratt
    Dec 27, 2023 at 14:52
  • 1
    $\begingroup$ 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.) $\endgroup$
    – 4er
    Dec 27, 2023 at 15:41
  • $\begingroup$ @4er what you suggest is very similar to my answer :) $\endgroup$
    – Kuifje
    Dec 27, 2023 at 16:26

3 Answers 3

0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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}$. $\endgroup$
    – Kuifje
    Dec 31, 2023 at 15:29
0
$\begingroup$

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] == k*phi[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))
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Liu Fan
    Dec 27, 2023 at 13:54
  • $\begingroup$ 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. $\endgroup$
    – Liu Fan
    Dec 27, 2023 at 13:58
  • $\begingroup$ 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. $\endgroup$
    – Liu Fan
    Dec 27, 2023 at 14:02
  • $\begingroup$ 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? $\endgroup$
    – Liu Fan
    Dec 27, 2023 at 14:43
  • $\begingroup$ $z_c$ is your $k_{min}(c)$. Try with only constraints $(1)$ and $(2)$, and by maximizing $z_c$. $\endgroup$
    – Kuifje
    Dec 27, 2023 at 18:14
0
$\begingroup$

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$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.