Skip to main content

Find minimum of decision variable, satisfying conditions

Ongoing
MAU15
  • Edited
Gurobi-versary
First Comment
First Question

Hello! I have a question on modelling a minimum constraint in combination with an imposed condition:

I have a set of decision variables representing time, \(\texttt{T={T_1,T_2...T_n}}\). For each value \(\texttt{tau_m}\) in another set, I need to find the smallest value in \(\texttt{T}\) that is non-zero ánd larger than \(\texttt{tau_m}\).

So 

for each tau_m:
     find a=min(T)
     satisfying:     
          a > tau_m
          a =/= 0

How can I do this? 

I tried to use a min_ constraint and utilise the two conditions to generate the correct linear expression in the function, but could not get this to work. 

0

Comments

6 comments

Date Votes
  • Official comment
    Simranjit Kaur
    Gurobi Staff Gurobi Staff
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Jaromił Najman
    Gurobi Staff Gurobi Staff
    • Edited

    Hi,

    Could you elaborate more on what actually you are trying to model in your problem? Are \(\texttt{tau_m}\) constant values? Are these positive? In best case, please provide a small example showing one constraint you are trying to produce. Could you share your code where you try to implement the constraints?

    Best regards,
    Jaromił

    0
  • MAU15
    Gurobi-versary
    First Comment
    First Question

    I am trying to model recurring vehicle visits to the same location. For each visit at a specific location, the vehicle has an entry and an exit node and for these nodes, the corresponding times are known. My problem is that I need to find the combination of entry and exit time for each visit. 

    Let's say the set Tau is the entry time and set T is the exit time. There is no direct relation between the entry and the exit nodes indices, so my strategy was to, for each value of Tau, take the minimum value of the the values of variable T, which should obviously be larger than tau and 0. This would then match the correct exit time with a certain entry time.

    Both Tau and T are positive, integer decision variables. 

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff
    • Edited

    Hi,

    You could try starting from this point

    import gurobipy as gp
    from gurobipy import GRB

    m = gp.Model("myModel")

    [...]

    indices = [0,1,2,3]
    T = m.addVars(indices,vtype=GRB.INTEGER, lb=1, ub = 10, name="T")
    tau_m = m.addVars(indices,vtype=GRB.INTEGER, lb=0, ub = 9, name="tau_m")
    a = m.addVars(indices,vtype=GRB.INTEGER,lb=1,ub=10,name="a")

    m.addConstrs((a[i] == gp.min_(T[j] for j in indices) for i in indices ),"min_constraints")
    m.addConstrs((a[i] >= tau_m[i]+1 for i in indices),"tau_constraints")

    [...]

    m.write("myMIP.lp")

    Note that strict inequalities are not allowed in (mixed-integer) linear programming due to compactness assumptions. Thus, when the \(\texttt{tau}\) variables are integer, you can use a \(\geq\) relation. If the \(\texttt{tau}\) variables are continuous, you can add a small \(\epsilon\) to it instead of \(1\). Obviously, you have to adjust the lower and upper bounds of the variables to fit our actual problem, but I think the above should provide you a good starting point. You can use the \(\texttt{write}\) function to write the problem to a readable format, \(\texttt{myMIP.lp}\) in the above case, and analyze whether the constraints are the ones you have in mind.


    Best regards,
    Jaromił

    0
  • MAU15
    Gurobi-versary
    First Comment
    First Question

    Thanks for your response. This was also my initial approach. However, this method proves to be unfeasible. Most likely the min constraint is incompatible with the inequality constraint because the minimum constraint only outputs the absolute minimum value in the set. 

    Is there a way to circumvent this by first determining the set of decision variables that satisfy the inequality constraints and then parsing that set to the minimum constraint? 

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi,

    Regarding the infeasibility, you could try to determine which (in)equalities make your problem infeasible. From there on, you could try adapting your model. The Knowledge Base article How do I determine why my model is infeasible? should be helpful in this case.

    You could also try to model the conditions with an additional binary variable and indicator constraints.

    Best regards,
    Jaromił

    0

Post is closed for comments.

Didn't find what you were looking for?

New post