Skip to main content

Programming sequence with combined constraints, min_() or or_()

Answered
Antoine Gros
  • Gurobi-versary
  • First Comment
  • First Question

Hello everyone,

I've almost finished my model and results look good ! There is a last constraint I'm trying to implement.

It concerns the location of n tools on a line (I quite transformed the terms to be more understandable, there's few tools to me ;) ). I did some funny stuff with swapping, having the good interfaces in-between...

I'm struggling with programming the few known sequences I want to input in my model : for instance "I know that t1 must be next to t5 which must be next to t21", independantly of the location of the three in the line. My variable is a binary linking a tool to a location.

t_ids = [t.id for t in tools] # t_ids ~ t1 t2 t3 t4
l_ids = [l.id for l in locations] # l_ids ~ l1 l2 l3 l4
x = m.addVars( t_ids, l_ids, vtype=gp.GRB.BINARY, name='assign')

# At least one tool per location, All tools located
non1 = m.addConstrs( (gp.quicksum( x[t,l] for t in t_ids ) <= 1 for l in l_ids), name='nsup-e')
non2 = m.addConstrs( (gp.quicksum( x[t,l] for l in l_ids ) == 1 for t in t_ids), name='nsup-c')

series = [['t2', 't4', 't7'], ['t1', 't5', 't21']]

Initially I modelled it with a multiplication,

 
for s in series:
    m.addConstr( gp.quicksum( (x[s[0], l_ids[j]] * x[s[1], l_ids[j+1]] * x[s[2], l_ids[j+2]] for j in range(0, len(l_ids)-len(s)))) >= 1, name='sequence-mul')
# ERROR: gurobipy.GurobiError: Invalid argument to QuadExpr multiplication

then with a min_

for s in series:
    m.addConstr( sum( ( gp.min_(x[s[0], l_ids[j]], x[s[1], l_ids[j+1]], x[s[2], l_ids[j+2]]) for j in range(0, len(l_ids)-len(s)))) >= 1, name='sequence-min')
# ERROR : gurobipy.GurobiError: Unsupported type (<class 'gurobipy.GenExprMin'>) for LinExpr addition argument

even with a floor !

for s in series: 
    m.addConstr( gp.quicksum(math.floor(x[s[0],l_ids[j]]/3 + x[s[1], l_ids[j+1]]/3 + x[s[2], l_ids[j+2]]/3) for j in range(0, len(l_ids)-len(s))) >= 1, name='sequence-floor')
# TypeError: must be real number, not gurobipy.LinExp

then I looked over the posts like this one, and wondering if it's possible even with using more complicated constraints like sos or or_

Best regards,
Antoine

0

Comments

3 comments

Date Votes
  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    Edited
    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?.
  • Maliheh Aramon
    • Gurobi Staff

    Hi Antoine, 

    • The first error occurs because Gurobi does not directly support multiplication of three variables. Please have a look at How do I model multilinear terms in Gurobi? article that explains an indirect approach to represent constraints containing general multilinear terms.
    •  The second error occurs because it is not possible to sum over GenExpr() objects. To do so, each min_() general expression needs to be assigned to an auxiliary Gurobi Var() object and the sum() can then be defined over auxiliary variables.
    • The third error occurs because the Python math.floor() function takes a real number as an input and not a Gurobi LinExpr(). 

    That being said, for every pair of \((t_i, t_j)\) tools in set \(S\) that needs to be placed in adjacent locations, you can represent the constraint as below where \(L\) is the number of locations.

    \[x_{t_il} \leq x_{t_j(l+1)}, ~~ l = 1, ..., L -1; ~~ (t_i, t_j) \in S \]

    The above constraint guarantees that if tool \(t_i\) is assigned to location \(l\), tool \(t_j\) is then assigned to location \(l+1\). The code snippet below shows how to implement this:

    for s in series:
        for ti, tj in zip(s[:-1], s[1:]):
             m.addConstrs(
                 (x[ti, l] <= x[tj, l + 1] for l in range(len(l_ids) - 1)),
                 name="ordering",
             )

    Best regards,

    Maliheh

    1
  • Antoine Gros
    • Gurobi-versary
    • First Comment
    • First Question

    Hi Maliheh,

    Thanks for the input and the clarification of the errors outputed. Your solution and a discussion I had this morning with a fellow theorist helped me understand how I was looking for something too complicated ... for something that seems to me - rather - simple after all !

    Glad to have an answer as precise and as soon !

    Best regards,
    Antoine

    0

Post is closed for comments.

Didn't find what you were looking for?

New post