On the Surrogate Gradient Algorithm for Lagrangian Relaxation

When applied to large-scale separable optimization problems, the recently developed surrogate subgradient method for Lagrangian relaxation (Zhao et al.: J. Optim. Theory Appl. 100, 699–712, 1999) does not need to solve optimally all the subproblems to update the multipliers, as the traditional subgradient method requires. Based on it, the penalty surrogate subgradient algorithm was further developed to address the homogenous solution issue (Guan et al.: J. Optim. Theory Appl. 113, 65–82, 2002; Zhai et al.: IEEE Trans. Power Syst. 17, 1250–1257, 2002). There were flaws in the proofs of Zhao et al., Guan et al., and Zhai et al.: for problems with inequality constraints, projection is necessary to keep the multipliers nonnegative; however, the effects of projection were not properly considered. This note corrects the flaw, completes the proofs, and asserts the correctness of the methods. This work is supported by the NSFC Grant Nos. 60274011, 60574067, the NCET program (No. NCET-04-0094) of China. The third author was supported in part by US National Science Foundation under Grants ECS-0323685 and DMI-0423607.     

Comments on “Surrogate Gradient Algorithm for Lagrangian Relaxation”

This note presents not only a surrogate subgradient method, but also a framework of surrogate subgradient methods. Furthermore, the framework can be used not only for separable problems, but also for coupled subproblems. The note delineates such a framework and shows that the algorithm can converges for a larger stepsize. The author thanks Professor Ching-An Lin from the Department of Electrical and Control Engineering of National Chiao Tung University, Hsinchu, Taiwan for valuable discussions.     

New Lagrangian Relaxation Based Algorithm for Resource Scheduling with Homogeneous Subproblems

Solution oscillations, often caused by identical solutions to the homogeneous subproblems, constitute a severe and inherent disadvantage in applying Lagrangian relaxation based methods to resource scheduling problems with discrete decision variables. In this paper, the solution oscillations caused by homogeneous subproblems in the Lagrangian relaxation framework are identified and analyzed. Based on this analysis, the key idea to alleviate the homogeneous oscillations is to differentiate the homogeneous subproblems. A new algorithm is developed to solve the problem under the Lagrangian relaxation framework. The basic idea is to introduce a second-order penalty term in the Lagrangian. Since the dual cost function is no longer decomposable, a surrogate subgradient is used to update the multiplier at the high level. The homogeneous subproblems are not solved simultaneously, and the oscillations can be avoided or at least alleviated. Convergence proofs and properties of the new dual cost function are presented in the paper. Numerical testing for a short-term generation scheduling problem with two groups of identical units demonstrates that solution oscillations are greatly reduced and thus the generation schedule is significantly improved.     

Generalized Nonlinear Lagrangian Formulation for Bounded Integer Programming

Several nonlinear Lagrangian formulations have been recently proposed for bounded integer programming problems. While possessing an asymptotic strong duality property, these formulations offer a success guarantee for the identification of an optimal primal solution via a dual search. Investigating common features of nonlinear Lagrangian formulations in constructing a nonlinear support for nonconvex piecewise constant perturbation function, this paper proposes a generalized nonlinear Lagrangian formulation of which many existing nonlinear Lagrangian formulations become special cases.     

New Bundle Methods for Solving Lagrangian Relaxation Dual Problems

Bundle methods have been used frequently to solve nonsmooth optimization problems. In these methods, subgradient directions from past iterations are accumulated in a bundle, and a trial direction is obtained by performing quadratic programming based on the information contained in the bundle. A line search is then performed along the trial direction, generating a serious step if the function value is improved by or a null step otherwise. Bundle methods have been used to maximize the nonsmooth dual function in Lagrangian relaxation for integer optimization problems, where the subgradients are obtained by minimizing the performance index of the relaxed problem. This paper improves bundle methods by making good use of near-minimum solutions that are obtained while solving the relaxed problem. The bundle information is thus enriched, leading to better search directions and less number of null steps. Furthermore, a simplified bundle method is developed, where a fuzzy rule is used to combine linearly directions from near-minimum solutions, replacing quadratic programming and line search. When the simplified bundle method is specialized to an important class of problems where the relaxed problem can be solved by using dynamic programming, fuzzy dynamic programming is developed to obtain efficiently near-optimal solutions and their weights for the linear combination. This method is then applied to job shop scheduling problems, leading to better performance than previously reported in the literature.     

Exact Algorithm for the Surrogate Dual of an Integer Programming Problem: Subgradient Method Approach

One of the critical issues in the effective use of surrogate relaxation for an integer programming problem is how to solve the surrogate dual within a reasonable amount of computational time. In this paper, we present an exact and efficient algorithm for solving the surrogate dual of an integer programming problem. Our algorithm follows the approach which Sarin et al. (Ref. 8) introduced in their surrogate dual multiplier search algorithms. The algorithms of Sarin et al. adopt an ad-hoc stopping rule in solving subproblems and cannot guarantee the optimality of the solutions obtained. Our work shows that this heuristic nature can actually be eliminated. Convergence proof for our algorithm is provided. Computational results show the practical applicability of our algorithm.     

Lagrangian relaxation based algorithm for trigeneration planning with storages

Trigeneration is a booming power production technology where three energy commodities are simultaneously produced in a single integrated process. Electric power, heat (e.g. hot water) and cooling (e.g. chilled water) are three typical energy commodities in the trigeneration system. The production of three energy commodities follows a joint characteristic. This paper presents a Lagrangian relaxation (LR) based algorithm for trigeneration planning with storages based on deflected subgradient optimization method. The trigeneration planning problem is modeled as a linear programming (LP) problem. The linear cost function poses the convergence challenge to the LR algorithm and the joint characteristic of trigeneration plants makes the operating region of trigeneration system more complicated than that of power-only generation system and that of combined heat and power (CHP) system. We develop an effective method for the long-term planning problem based on the proper strategy to form Lagrangian subproblems and solve the Lagrangian dual (LD) problem based on deflected subgradient optimization method. We also develop a heuristic for restoring feasibility from the LD solution. Numerical results based on realistic production models show that the algorithm is efficient and near-optimal solutions are obtained.     

pth Power Lagrangian Method for Integer Programming

When does there exist an optimal generating Lagrangian multiplier vector (that generates an optimal solution of an integer programming problem in a Lagrangian relaxation formulation), and in cases of nonexistence, can we produce the existence in some other equivalent representation space? Under what conditions does there exist an optimal primal-dual pair in integer programming? This paper considers both questions. A theoretical characterization of the perturbation function in integer programming yields a new insight on the existence of an optimal generating Lagrangian multiplier vector, the existence of an optimal primal-dual pair, and the duality gap. The proposed pth power Lagrangian method convexifies the perturbation function and guarantees the existence of an optimal generating Lagrangian multiplier vector. A condition for the existence of an optimal primal-dual pair is given for the Lagrangian relaxation method to be successful in identifying an optimal solution of the primal problem via the maximization of the Lagrangian dual. The existence of an optimal primal-dual pair is assured for cases with a single Lagrangian constraint, while adopting the pth power Lagrangian method. This paper then shows that an integer programming problem with multiple constraints can be always converted into an equivalent form with a single surrogate constraint. Therefore, success of a dual search is guaranteed for a general class of finite integer programming problems with a prominent feature of a one-dimensional dual search.     

基于异步次梯度法的LR算法及其在多阶段HFSP的应用

为降低求解复杂度和缩短计算时间,针对多阶段混合流水车间总加权完成时间问题,提出了一种结合异步次梯度法的改进拉格朗日松弛算法。建立综合考虑有限等待时间和工件释放时间的整数规划数学模型,将异步次梯度法嵌入到拉格朗日松弛算法中,从而通过近似求解拉格朗日松弛问题得到一个合理的异步次梯度方向,沿此方向进行搜索,逐渐降低到最优点的距离。通过仿真实验,验证了所提算法的有效性。对比所提算法与传统的基于次梯度法的拉格朗日松弛算法,结果表明,就综合解的质量和计算效率而言,所提算法能在较短的计算时间内获得更好的近优解,尤其是对大规模问题。     

A New Lagrangian Relaxation Based Algorithm for a Class of Multidimensional Assignment Problems

Large classes of data association problems in multiple targettracking applications involving both multiple and single sensorsystems can be formulated as multidimensional assignment problems.These NP-hard problems are large scale and sparse with noisyobjective function values, but must be solved inreal-time. Lagrangian relaxation methods have proven to beparticularly effective in solving these problems to the noise levelin real-time, especially for dense scenarios and for multiple scansof data from multiple sensors. This work presents a new class ofconstructive Lagrangian relaxation algorithms that circumvent some ofthe deficiencies of previous methods. The results of severalnumerical studies demonstrate the efficiency and effectiveness of thenew algorithm class.     

A Lagrangian decomposition approach for the pump scheduling problem in water networks

Dynamic pricing has become a common form of electricity tariff, where the price of electricity varies in real time based on the realized electricity supply and demand. Hence, optimizing industrial operations to benefit from periods with low electricity prices is vital to maximizing the benefits of dynamic pricing. In the case of water networks, energy consumed by pumping is a substantial cost for water utilities, and optimizing pump schedules to accommodate for the changing price of energy while ensuring a continuous supply of water is essential. In this paper, a Mixed-Integer Non-linear Programming (MINLP) formulation of the optimal pump scheduling problem is presented. Due to the non-linearities, the typical size of water networks, and the discretization of the planning horizon, the problem is not solvable within reasonable time using standard optimization software. We present a Lagrangian decomposition approach that exploits the structure of the problem leading to smaller problems that are solved independently. The Lagrangian decomposition is coupled with a simulation-based, improved limited discrepancy search algorithm that is capable of finding high quality feasible solutions. The proposed approach finds solutions with guaranteed upper and lower bounds. These solutions are compared to those found by a mixed-integer linear programming approach, which uses a piecewise-linearization of the non-linear constraints to find a global optimal solution of the relaxation. Numerical testing is conducted on two real water networks and the results illustrate the significant costs savings due to optimizing pump schedules.     

Convex relaxation and Lagrangian decomposition for indefinite integer quadratic programming

We study lower bounding methods for indefinite integer quadratic programming problems. We first construct convex relaxations by D.C. (difference of convex functions) decomposition and linear underestimation. Lagrangian bounds are then derived by applying dual decomposition schemes to separable relaxations. Relationships between the convex relaxation and Lagrangian dual are established. Finally, we prove that the lower bound provided by the convex relaxation coincides with the Lagrangian bound of the orthogonally transformed problem.     

A nonlinear Lagrangian dual for integer programming

Nonlinear Lagrangian theory offers a success guarantee for the dual search via construction of a nonlinear support of the perturbation function at the optimal point. In this paper, a new nonlinear dual formulation of an exponential form is proposed for bounded integer programming. This new formulation possesses an asymptotic strong duality property and guarantees a success in identifying a primal optimum solution. No actual dual search is needed in the solution process when the parameter of the nonlinear Lagrangian formulation is set to be large enough.     

Elastic Constraint Branching, the Wedelin/Carmen Lagrangian Heuristic and Integer Programming for Personnel Scheduling

The Wedelin algorithm is a Lagrangian based heuristic that is being successfully used by Carmen Systems to solve large crew pairing problems within the airline industry. We extend the Wedelin approach by developing an implementation for personnel scheduling problems (also termed staff rostering problems) that exploits the special structure of these problems. We also introduce elastic constraint branching with the twin aims of improving the performance of our new approach and making it more column generation friendly. Numerical results show that our approach can outperform the commercial solver CPLEX on difficult commercial rostering problems.     

Stochastic Lagrangian Relaxation Applied to Power Scheduling in a Hydro-Thermal System under Uncertainty

A dynamic (multi-stage) stochastic programming model for the weekly cost-optimal generation of electric power in a hydro-thermal generation system under uncertain demand (or load) is developed. The model involves a large number of mixed-integer (stochastic) decision variables and constraints linking time periods and operating power units. A stochastic Lagrangian relaxation scheme is designed by assigning (stochastic) multipliers to all constraints coupling power units. It is assumed that the stochastic load process is given (or approximated) by a finite number of realizations (scenarios) in scenario tree form. Solving the dual by a bundle subgradient method leads to a successive decomposition into stochastic single (thermal or hydro) unit subproblems. The stochastic thermal and hydro subproblems are solved by a stochastic dynamic programming technique and by a specific descent algorithm, respectively. A Lagrangian heuristics that provides approximate solutions for the first stage (primal) decisions starting from the optimal (stochastic) multipliers is developed. Numerical results are presented for realistic data from a German power utility and for numbers of scenarios ranging from 5 to 100 and a time horizon of 168 hours. The sizes of the corresponding optimization problems go up to 200000 binary and 350000 continuous variables, and more than 500000 constraints.     

A Lagrangian heuristic algorithm for a real-world train timetabling problem

The train timetabling problem (TTP) aims at determining an optimal timetable for a set of trains which does not violate track capacities and satisfies some operational constraints.In this paper, we describe the design of a train timetabling system that takes into account several additional constraints that arise in real-world applications. In particular, we address the following issues:

•

Manual block signaling for managing a train on a track segment between two consecutive stations.

•

Station capacities, i.e., maximum number of trains that can be present in a station at the same time.

•

Prescribed timetable for a subset of the trains, which is imposed when some of the trains are already scheduled on the railway line and additional trains are to be inserted.

•

Maintenance operations that keep a track segment occupied for a given period.

We show how to incorporate these additional constraints into a mathematical model for a basic version of the problem, and into the resulting Lagrangian heuristic. Computational results on real-world instances from Rete Ferroviaria Italiana (RFI), the Italian railway infrastructure management company, are presented.     

Maximizing the Net Present Value of a Project Under Resource Constraints Using a Lagrangian Relaxation Based Heuristic with Tight Upper Bounds

Resource-constrained project scheduling under a net present value objective attracts growing interest. Because this is an NP-hard problem, it is unlikely that optimum solutions can be computed for large instances within reasonable computation time. Thus, heuristics have become a popular research field. Up to now, however, upper bounds are not well researched. Therefore, most researchers evaluate their heuristics on the basis of a best known lower bound, but it is unclear how good the performance really is. With this contribution we close this gap and derive tight upper bounds on the basis of a Lagrangian relaxation of the resource constraints. We also use this approach as a basis for a heuristic and show that our heuristic as well as the cash flow weight heuristic proposed by Baroum and Patterson yield solutions very close to the optimum result. Furthermore, we discuss the proper choice of a test-bed and emphasize that discount rates must be carefully chosen to give realistic instances.     

Unit Commitment by Augmented Lagrangian Relaxation: Testing Two Decomposition Approaches

One of the main drawbacks of the augmented Lagrangian relaxation method is that the quadratic term introduced by the augmented Lagrangian is not separable. We compare empirically and theoretically two methods designed to cope with the nonseparability of the Lagrangian function: the auxiliary problem principle method and the block coordinated descent method. Also, we use the so-called unit commitment problem to test both methods. The objective of the unit commitment problem is to optimize the electricity production and distribution, considering a short-term planning horizon.     

Comment on “A nonlinear Lagrangian dual for integer programming”

We present a counterexample and correction to the contention by Xu and Li that the nonlinear Lagrangian dual problem they propose [Oper. Res. Lett. 30 (2002) 401] asymptotically has no duality gap.     

不可分离凸背包问题的拉格朗日分解和区域分割方法

本文对线性约束不可分离凸背包问题给出了一种精确算法．该算法是拉格朗日分解和区域分割结合起来的一种分枝定界算法．利用拉格朗日分解方法可以得到每个子问题的一个可行解，一个不可行解，一个下界和一个上界．区域分割可以把一个整数箱子分割成几个互不相交的整数子箱子的并集，每个整数子箱子对应一个子问题．通过区域分割可以逐步减小对偶间隙并最终经过有限步迭代找到原问题的最优解．数值结果表明该算法对不可分离凸背包问题是有效的．