Optimizing away dummy binary variables with values determined by other variables?

Answered

Tobias Völk

• May 26, 2022 11:50

Hi all,

we have the following part of our problem formulation:

x_t = 1 IFF machine is on at time t ELSE 0

u_t = 1 IFF machine was started (u)p, meaning x_(t-1) = 0 AND x_t = 1 ELSE 0

d_t = 1 IFF machine was shut (d)own, meaning x_(t-1) = 1 AND x_t = 0 ELSE 0

Currently we have:

x_t - x_(t-1) + u_t - d_t <= 0

u_t + d_t <= 1

The variables u and d are dummy variables and their values completely determined by the values of x. Do we have to worry that Gurobi will not eliminate them and branch over them needlessly? Or is there a way (with AND/OR constraints) to let Gurobi know that it can safely conclude the value from assigned variables? Does Gurobi figure this out automatically based on above constraints and the fact that the variables are binary? Or is there a smart way to replace d and u with x?

Best regards,

Tobi

0

• 

  Jaromił Najman

  Gurobi Staff

  • May 30, 2022 08:10
  • Edited

  Hi Tobi,

  Usually, Gurobi's presolve algorithm and probing procedures should detect such implications. Of course, there can be exceptions. If you really want to make sure that no implication is missed, you could experiment with using Gurobi's and constraints and compare solver's performance. Since the and constraints take only single variables as input, you will have to add auxiliary variables \(x^n_{t} = 1- x_{t}\).

  Best regards, 
  Jaromił

   

  0

Please sign in to leave a comment.