求解二次分配问题的拉格朗日松弛新方法

以改进的拉格朗日松弛(Lagrangian relaxation,LR)方法和二次分配问题(quadratic assignment problem,QAP)的线性化模型为基础,给出了求解QAP的拉格朗日松弛新方法,这为有效求解QAP提供了一种新的解决方案.通过求解二次分配基准问题库(QAPLIB)中的实际算例,从实验的角度说明了拉格朗日松弛新方法求解QAP的可行性及存在的不足之处,并对今后进一步的研究工作指明了方向.     

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.     

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.     

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.     

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.     

Surrogate Gradient Algorithm for Lagrangian Relaxation

The subgradient method is used frequently to optimize dual functions in Lagrangian relaxation for separable integer programming problems. In the method, all subproblems must be solved optimally to obtain a subgradient direction. In this paper, the surrogate subgradient method is developed, where a proper direction can be obtained without solving optimally all the subproblems. In fact, only an approximate optimization of one subproblem is needed to get a proper surrogate subgradient direction, and the directions are smooth for problems of large size. The convergence of the algorithm is proved. Compared with methods that take effort to find better directions, this method can obtain good directions with much less effort and provides a new approach that is especially powerful for problems of very large size.     

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.     

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.     

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.     

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

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

Solving the p-Median Problem with a Semi-Lagrangian Relaxation

Lagrangian relaxation is commonly used in combinatorial optimization to generate lower bounds for a minimization problem. We study a modified Lagrangian relaxation which generates an optimal integer solution. We call it semi-Lagrangian relaxation and illustrate its practical value by solving large-scale instances of the p-median problem. This work was partially supported by the Fonds National Suisse de la Recherche Scientifique, grant 12-57093.99 and the Spanish government, MCYT subsidy dpi2002-03330.     

A Lagrangian Based Branch-and-Bound Algorithm for Production-transportation Problems

We propose a branch-and-bound algorithm of Falk–Soland's type for solving the minimum cost production-transportation problem with concave production costs. To accelerate the convergence of the algorithm, we reinforce the bounding operation using a Lagrangian relaxation, which is a concave minimization but yields a tighter bound than the usual linear programming relaxation in O(mn log n) additional time. Computational results indicate that the algorithm can solve fairly large scale problems.     

Sequential Lagrangian Conditions for Convex Programs with Applications to Semidefinite Programming

In this paper it is shown that, in the absence of any regularity condition, sequential Lagrangian optimality conditions as well as a sequential duality results hold for abstract convex programs. The significance of the results is that they yield the standard optimality and duality results for convex programs under a simple closed-cone condition that is much weaker than the well-known constraint qualifications. As an application, a sequential Lagrangian duality, saddle-point conditions, and stability results are derived for convex semidefinite programs.The authors are grateful to the referee and Professor Franco Giannessi for valuable comments and constructive suggestions which have contributed to the final preparation of the paper.     

Cost Based Filtering for the Constrained Knapsack Problem

We present cost based filtering methods for Knapsack Problems (KPs). Cost based filtering aims at fixing variables with respect to the objective function. It is an important technique when solving complex problems such as Quadratic Knapsack Problems, or KPs with additional constraints (Constrained Knapsack Problems (CKPs)). They evolve, e.g., when Constraint Based Column Generation is applied to appropriate optimization problems. We develop new reduction algorithms for KP. They are used as propagation routines for the CKP with (nlogn) preprocessing time and (n) time per call. This sums up to an amortized time (n) for (logn) incremental calls where the subsequent problems may differ with respect to arbitrary sets of necessarily included and excluded items.     

A Constraint Programming Approach to Extract the Maximum Number of Non-Overlapping Test Forms

This paper introduces a novel approach for extracting the maximum number of non-overlapping test forms from a large collection of overlapping test sections assembled from a given item bank. The approach involves solving maximum set packing problems (MSPs). A branch-and-bound MSP algorithm is developed along with techniques adapted from constraint programming to estimate lower and upper bounds on the optimal MSP solution. The algorithm is general and can be applied in other applications including combinatorial auctions. The results of computer simulations and experiments with an operational item bank are presented. An erratum to this article is available at .     

稠密k-子图问题的双非负松弛

稠密k-子图问题是组合优化里面一类经典的优化问题,其在通常情况下是非凸且NP-难的。本文给出了求解该问题的一个新凸松弛方法-双非负松弛方法,并建立了问题的相应双非负松弛模型,而且证明了其在一定的条件下等价于一个新的半定松弛模型。最后,我们使用一些随机例子对这些模型进行了数值测试,测试的结果表明双非负松弛的计算效果要优于等价的半定松弛。     

多约束非线性整数规划的一种改进的算法

多约束非线性整数规划是一类非常重要的问题,非线性背包问题是它的一类特殊而重要的问题.定义在有限整数集上极大化一个可分离非线性函数的多约束最优化问题.这类问题常常用于资源分配、工业生产及计算机网络的最优化模型中,运用一种新的割平面法来求解对偶问题以得到上界,不仅减少了对偶间隙,而且保证了算法的收敛性.利用区域割丢掉某些整数箱子,并把剩下的区域划分为一些整数箱子的并集,以便使拉格朗日松弛问题能有效求解,且使算法在有限步内收敛到最优解.算法把改进的割平面法用于求解对偶问题并与区域分割有效结合解决了多约束非线性背包问题的求解.数值结果表明了改进的割平面方法对对偶搜索更加有效.     

Constraint Programming Based Column Generation for Crew Assignment

Airline crew assignment problems are large-scale optimization problems which can be adequately solved by column generation. The subproblem is typically a so-called constrained shortest path problem and solved by dynamic programming. However, complex airline regulations arising frequently in European airlines cannot be expressed entirely in this framework and limit the use of pure column generation. In this paper, we formulate the subproblem as a constraint satisfaction problem, thus gaining high expressiveness. Each airline regulation is encoded by one or several constraints. An additional constraint which encapsulates a shortest path algorithm for generating columns with negative reduced costs is introduced. This constraint reduces the search space of the subproblem significantly. Resulting domain reductions are propagated to the other constraints which additionally reduces the search space. Numerical results based on data of a large European airline are presented and demonstrate the potential of our approach.