Fuzzy gradient method in Lagrangian relaxation for integer programming problems

A major challenge in Lagrangian relaxation for integer programming problems is to effectively maximize the dual function which is concave, piece-wise linear, and consists of many facets. Available methods include the subgradient method, the bundle method, and the surrogate subgradient method. Each of these methods, however, has its own limitations. Based on the insights obtained from these methods, the paper develops the “fuzzy gradient method” that makes good use of all the information obtained from solving the “relaxed problem”-not just the optimal solution, but also near optimal solutions. In the method, the “fuzzy gradient direction” is obtained by combining subgradient directions from near optimal solutions following a simple fuzzy rule. The resulting direction is continuous with respect to multipliers, thereby significantly reducing the solution zigzagging difficulty, and is obtained without much additional computational requirements. The convergence of the method is proved, and a general framework for maximizing the dual function is established where many other methods can be viewed as special cases. The fuzzy gradient method is then applied to job shop scheduling problems, and fuzzy dynamic programming is developed to effectively obtain fuzzy gradients. Test results show that the method leads to significant improvement over the frequently used subgradient method