Using independent set / maximal clique cuts for EVRPTW in Gurobi

Answered

Lelisa Kebena Bijiga

April 14, 2026 07:51

• 
• 

I am working on the Electric Vehicle Routing Problem with Time Windows (EVRPTW). I would like to know:

- Can Gurobi automatically identify and apply independent set or maximal clique cuts?

- If not, how can we tailor such cuts to the EVRPTW setting (including charging stations, time windows, and energy constraints) using Gurobi’s callback or lazy constraints?

Any pointers or examples would be appreciated.

Related to

• Cuts
• VRP

0

• 

  Mario Ruthmair

  • Gurobi Staff

  April 16, 2026 05:59

  Hi Lelisa,

  Gurobi can detect clique cuts based on the existing variables and constraints. Here is a very simple example: If you have binary variables x1, x2, x3, and constraints

  x1 + x2 <= 1
  x1 + x3 <= 1
  x2 + x3 <= 1

  then Gurobi can deduce the clique cut

  x1 + x2 + x3 <= 1

  However, those cuts are only used to improve the dual bound, and you cannot be sure whether they are actually generated during a run. Sometimes, it is not worth the effort, and since they are not required for model feasibility, they might be skipped.

  Note that Gurobi does not attempt to detect your problem type (i.e., the EVRPTW) and thus does not add specific cuts from this domain.
  Also, if you need the cuts for the feasibility of your model, you MUST add them either a priori to the model (if there are not too many) or as lazy constraints. We have a small example for the latter: TSP with subtour elimination constraints (although the cut separation is not super efficient).

  If you know that the cuts you have in mind are not required for feasibility but significantly improve the dual bound, then you should add them in a cut callback to have full control of what is happening.

  Mario

  0
• 

  Lelisa Kebena Bijiga

  April 17, 2026 12:15

  • 
  • 

  Hi Mario,

  Thank you very much!

  Best,

  Lelisa

  0

Please sign in to leave a comment.