Payment cost minimization using Lagrangian relaxation and modified surrogate optimization approach

In the Payment Cost Minimization (PCM) mechanism [4] payment costs are minimized directly, thus the payment costs that results from selected offers can be significantly reduced compared to the costs obtained by minimizing total bid costs. The PCM can be solved efficiently using standard LP software packages (e.g., CPLEX) only for a limited number of offers. Lagrangian relaxation (LR) has been a powerful technique to solve discrete and mixed-integer optimization problems. For complex problems, such as the PCM, the surrogate subgradient method is frequently used within Lagrangian relaxation approach to update multipliers (e.g., [6], [4]). In the surrogate subgradient approach a proper direction is obtained without fully minimizing the relaxed problem. This paper presents a modified Lagrangian relaxation and the surrogate optimization approach for obtaining a good feasible solution within a reasonable CPU time. The difficulty of the standard surrogate optimization method primarily arises due to the lack of prior knowledge about the optimal dual value, which is used in the definition of a step size. In order to overcome this difficulty, a new method is proposed. The main purpose of the modified surrogate subgradient approach is to obtain a “good” direction quickly and independently of the optimal dual value at each iteration. In this paper it is achieved by introducing a formula for updating the multipliers such that the exact minimization of the Lagrangian leads to a convergent result. Then an approximate formula for updating the multipliers is developed so that the exact optimization of the Lagrangian leads to a convergent result under certain optimality conditions. Lastly, the notion of the surrogate subgradient is used for ensuring the convergence within the reasonable CPU time. An analogue of the surrogate subgradient condition guarantees the convergence on the surrogate subgradient method. Numerical examples are provided to demonstrate the method's effectiveness.