Determining constraint relevance in crew scheduling problem

Question

I am working on a crew scheduling problem formulated as a MIP binary optimization where each employee is represented by a binary variable $X_{ids}$ s.t. $i \in I$ is $i$th employee, $d \in D$ is the day number and $s \in S$ is the shift (ex: 9AM-12PM) and if the employee is scheduled to work on that day at that shift the variable is 1 otherwise 0. The constraints are various taking into account supply > demand at each hour, employee shift preferences, lunch hour, consecutive days worked limits, etc.

Because this is a MIP there is no duality here to study the shadow prices of the constraints. I'm thus wondering what are some options to determine how to rank the constraints in terms of importance on their impacts on the objective function, which is a cost minimization? Should I relax integrality constraints and analyze shadow prices of the constraints, or run various sensitivity analyses via scenarios removing different constraints from the optimization to get an estimate of the overall impact to the objective function?

Answer 1

This is tricky for a variety of reasons, including the fact that relaxing a constraint that is nonbinding at the optimal solution could cause the optimum to improve. I don't think the duals of the LP relaxation will typically be all that helpful. Rather than dropping constraints, I would consider relaxing constraints a bit at a time (either individually or possibly in groups, depending on the context of the model). This assumes that solutions times are reasonably short.