An efficient surrogate subgradient method within Lagrangian relaxation for the Payment Cost Minimization problem

Studies have shown that for a given set of bids, Payment Cost Minimization leads to lower customer payments as compared to Bid Cost Minimization. In order to provide a thorough analysis of the two mechanisms an efficient solution methodology is required. It has previously been shown that the surrogate optimization within the Lagrangian relaxation framework can lead to savings in the CPU time while ensuring a high-quality solution. This paper develops an efficient methodology to solve Payment Cost Minimization using the surrogate optimization framework and the branch-and-cut method. In the presented methodology the problem structure is exploited using Lagrangian relaxation and the relaxation of the integrality constraints is exploited using branch-and-cut. The resulting method is further improved by using additional cutting planes that reduce the search space and by the advanced start to reinitialize the decision variables at each iteration. For large Payment Cost Minimization problems, the method can find significantly better feasible solutions within less CPU time than that obtained by standard branch-and-cut methods implemented in commercial MIP solver. The methodology developed in this paper is generic and can be used for solving other optimization problems.