A state space relaxation approach

This paper reports on a lower bound technique based on state space relaxation for a dynamic program associated with a particular class of covering problems, namely covering problems related with crew scheduling. Both, the dynamic program and the state space relaxation are general but the latter revealed a very interesting behavior for this current application. Some reduction and dominance tests were derived from the relaxation. Two additional tests were developed in order to speed up the process. These tests are based on conditions that state whether some stages or some states in a particular stage can be ignored. The state space relaxation was combined with Lagrangean relaxation and both were imbedded in a subgradient optimization scheme. Some computational results from real life applications are presented together with possible improvements on the technique. The inclusion of the tests described in this paper produces significant reduction on the dimension of the original problems and also on the computing times.