Challenges in conditional constraints in a VRP variant

回答済み

Noah Miller

• 2025年01月26日 21:34

Hello!

I am working on a VRP variant that is a little odd so I will try to tiptoe around the specifics. In short, I want to track when a node is active using some variables I have such as start time s[i] and departure time d[i]. 

What I have done is discretize time into sections with a start and end time. I am hoping to leverage the start and departure time for each node to identify what timesteps have activity at the node in them.

CL_time_bin[i , t] is a binary decision variable that indicates if there is activity at node i during time step t.

I have found that if I use big-M constraints like so,

model.addConstr(s[i] <= t_end + M * (1 - CL_time_bin[i, (t_start, t_end)]))

They do not "force" activation if the conditional s[i] <= t_end is true.

I also tried indicator constraints,

model.addGenConstrIndicator(CL_time_bin[i, (t_start, t_end)], True, s[i] <= t_end)

But I realized that it functions similarly, as it would enforce the conditional if the binary decision variable was true, but I want the opposite.

I also tried a different format that I found searching for modeling conditionals on the forum

 

model.addConstr((CL_time_bin[i, t] == 1) >> (s[i] >= 0)

In summary, I need a way to force the binary decision to True in the event a conditional is True. Such as,

s[i] >= t_start  -> CL_time_bin == 1

 

Thank you for your time and patience, I am relatively new to Gurobi. If you need additional information please feel free to ask.

関連

• Big-M

0

• 

  Ryuta Tamura

  Gurobi Staff

  • 2025年01月27日 01:54

  Hi Noah,

  This article might be useful. This means that adding the constraint for the case of the binary variable is 0. For example:

  model.addGenConstrIndicator(CL_time_bin[i, (t_start, t_end)], True, s[i] <= t_end)
  model.addGenConstrIndicator(CL_time_bin[i, (t_start, t_end)], False, s[i] >= t_end + eps)

  Here, eps is a suitably small constant. Note that too small values (ex. <1e-6) may be ignored for Gurobi's tolerance. For your problem, the unit of time to be handled (1s, 1m, 1h, etc.),  may be sufficient.

  Thanks,
  Ryuta

  0
• 

  Noah Miller

  • 2025年01月27日 16:33

  

  

  Hi Ryuta,

  I appreciate the insight. I wasn't properly understanding the meaning of that article and how it can apply to the general indicator constraints. 

  Thanks,

  Noah

  0

サインインしてコメントを残してください。