A novel Lagrangian relaxation level approach for scheduling steelmaking-refining-continuous casting production

A Lagrangian relaxation(LR) approach was presented which is with machine capacity relaxation and operation precedence relaxation for solving a flexible job shop(FJS) scheduling problem from the steelmaking-refining-continuous casting process. Unlike the full optimization of LR problems in traditional LR approaches, the machine capacity relaxation is optimized asymptotically, while the precedence relaxation is optimized approximately due to the NP-hard nature of its LR problem. Because the standard subgradient algorithm(SSA) cannot solve the Lagrangian dual(LD) problem within the partial optimization of LR problem, an effective deflected-conditional approximate subgradient level algorithm(DCASLA) was developed, named as Lagrangian relaxation level approach. The efficiency of the DCASLA is enhanced by a deflected-conditional epsilon-subgradient to weaken the possible zigzagging phenomena. Computational results and comparisons show that the proposed methods improve significantly the efficiency of the LR approach and the DCASLA adopting capacity relaxation strategy performs best among eight methods in terms of solution quality and running time.

A Quick Method for Judging the Feasibility of Security-Constrained Unit Commitment Problems within Lagrangian Relaxation Framework

Generally, the procedure for Solving Security constrained unit commitment (SCUC) problems within Lagrangian Relaxation framework is partitioned into two stages: one is to obtain feasible SCUC states;the other is to solve the economic dispatch of generation power among all the generating units. The core of the two stages is how to determine the feasibility of SCUC states. The existence of ramp rate constraints and security constraints increases the difficulty of obtaining an analytical necessary and sufficient condition for determining the quasi-feasibility of SCUC states at each scheduling time. However, a numerical necessary and sufficient numerical condition is proposed and proven rigorously based on Benders Decomposition Theorem. Testing numerical example shows the effectiveness and efficiency of the condition.

Lagrangian Relaxation-Based Unit Commitment Considering Fast Response Reserve Constraints

Unit commitment (UC) is to determine the optimal unit status and generation level during each time interval of the scheduled period. The purpose of UC is to minimize the total generation cost while satisfying system demand, reserve requirements, and unit constraints. Among the UC constraints, an adequate provision of reserve is important to ensure the security of power system and the fast-response reserve is essential to bring system frequency back to acceptable level following the loss of an online unit within a few seconds. In this paper, the authors present and solve a UC problem including the frequency-based reserve constraints to determine the optimal FRR requirements and unit MW schedules. The UC problem is solved by using Lagrangian Relaxation-based approach and compared with the actual system schedules. It is observed that favorable reserve and unit MW schedules are obtained by the proposed method while the system security is maintained.

Improvement of Lagrangian relaxation performance for open pit mines constrained long-term production scheduling problem

Constrained long-term production scheduling problem(CLTPSP) of open pit mines has been extensively studied in the past few decades due to its wide application in mining projects and the computational challenges it poses become an NP-hard problem.This problem has major practical significance because the effectiveness of the schedules obtained has strong economical impact for any mining project.Despite of the rapid theoretical and technical advances in this field,heuristics is still the only viable approach for large scale industrial applications.This work presents an approach combining genetic algorithms(GAs) and Lagrangian relaxation(LR) to optimally determine the CLTPSP of open pit mines.GAs are stochastic,parallel search algorithms based on the natural selection and the process of evolution.LR method is known for handling large-scale separable problems; however,the convergence to the optimal solution can be slow.The proposed Lagrangian relaxation and genetic algorithms(LR-GAs) combines genetic algorithms into Lagrangian relaxation method to update the Lagrangian multipliers.This approach leads to improve the performance of Lagrangian relaxation method in solving CLTPSP.Numerical results demonstrate that the LR method using GAs to improve its performance speeding up the convergence.Subsequently,highly near-optimal solution to the CLTPSP can be achieved by the LR-GAs.

Solution to the quadratic assignment problem usingsemi-Lagrangian relaxation

The semi-Lagrangian relaxation （SLR）, a new exactmethod for combinatorial optimization problems with equality constraints,is applied to the quadratic assignment problem （QAP）.A dual ascent algorithm with finite convergence is developed forsolving the semi-Lagrangian dual problem associated to the QAP.We perform computational experiments on 30 moderately difficultQAP instances by using the mixed integer programming solvers,Cplex, and SLR＋Cplex, respectively. The numerical results notonly further illustrate that the SLR and the developed dual ascentalgorithm can be used to solve the QAP reasonably, but also disclosean interesting fact： comparing with solving the unreducedproblem, the reduced oracle problem cannot be always effectivelysolved by using Cplex in terms of the CPU time.

Lagrangian Relaxation Method for Multiobjective Optimization Methods: Solution Approaches

This paper introduces the Lagrangian relaxation method to solve multiobjective optimization problems. It is often required to use the appropriate technique to determine the Lagrangian multipliers in the relaxation method that leads to finding the optimal solution to the problem. Our analysis aims to find a suitable technique to generate Lagrangian multipliers, and later these multipliers are used in the relaxation method to solve Multiobjective optimization problems. We propose a search-based technique to generate Lagrange multipliers. In our paper, we choose a suitable and well-known scalarization method that transforms the original multiobjective into a scalar objective optimization problem. Later, we solve this scalar objective problem using Lagrangian relaxation techniques. We use Brute force techniques to sort optimum solutions. Finally, we analyze the results, and efficient methods are recommended.

Collaborative production planning between supply chain partners by Lagrangian relaxation

A collaborative planning framework based on the Lagrangian Relaxation was developed to coordinate and optimize the production planning of independent partners in multiple tier supply chains. Linking constraints and dependent demand constraints were added to the monolithic Multi-Level, multi-item Capacitated Lot Sizing Problem (MLCLSP). MLCLSP was Lagrangian relaxed and decomposed into facility-separable subproblems. Surrogate gradient algorithm was used to update Lagrangian multipliers, which coordinate decentralized decisions of the facilities. Production planning of independent partners could be appropriately coordinated and optimized by this framework without intruding their decisionities and private information. Experimental results show that the proposed coordination mechanism and procedure come close to optimal results as obtained by central coordination.

考虑出行成本不确定性的路网交通疏散策略

为提高应急管理水平,考虑突发事件影响下的交通出行成本不确定性,对城市交通疏散问题进行研究。首先,根据交通疏散问题的时空特性创建时空耦合网络图,并且结合行程时间成本和冲突风险成本,提出了城市交通路网出行成本的量化方法。进一步考虑路段资源权重上限的影响,通过增加边际约束,构建基于预算不确定集的先验疏散策略的鲁棒优化模型,以最小化路网疏散过程的总交通出行成本。然后运用模型重构技术,将搭建的鲁棒模型转化为混合整数线性规划模型,并设计改进的拉格朗日松弛方法进行解耦求解。最后以SiouxFalls网络进行算例分析,数值结果表明,随着不确定集和模型规模的增大,行程时间成本和冲突风险成本的增速分别提高约29.13%和236.46%,模型预算参数控制在一定的区间,能够较好地权衡解的鲁棒性与最优性。通过南京部分区域路网案例测试验证所述方法在更大规模网络算例的适用性,研究结果表明:相比于传统拉格朗日松弛方法,所提出的改良方法可以在较少的迭代次数内得到高质量的可行解。研究结果可以为应急指挥部门制定可靠的交通疏散策略提供思路。

一种基于拉格朗日与时间解耦的超大规模SCUC求解框架

安全约束机组组合(security constrained unit commitment,SCUC)是电网出清场景中最为广泛使用的一类模型。建立了一种针对超大规模SCUC现货市场出清问题的求解框架,首先提出了SCUC问题的时间解耦求解方法,通过缩小问题的规模来加快求解速度;其次针对时间解耦后模型的子问题提出了拉格朗日松弛求解技术,在不影响求解准确度的情况下,有效降低了关键困难约束的求解难度。数值实验证明,所提出的框架极大地提升了求解效率,且十分稳定。

用Lagrangian松弛法解化工批处理调度问题

研究基于Ｌａｇｒａｎｇｉａｎ松弛法的化工批处理过程的调度方法．建立了化工批处理过程调度问题的一种混合整数规划（ＭＩＬＰ）模型，并通过松弛离散变量和连续变量共存的约束，将问题分解为一个两层次的优化问题，其中上层是原问题的对偶问题，下层由两个子问题构成：一个与产品批量有关，另一个确定操作时间表，分别用线性规划和动态规划方法解这两个子问题．然后从对偶问题的解构作原问题的可行解．数值试验结果证明了该方法的有效性．

新的Lagrangian松弛法求解CLSP问题

ＣＬＳＰ（ｃａｐａｃｉｔａｔｅｄｓｉｎｇｌｅ－ｌｅｖｅｌｌｏｔ－ｓｉｚｉｎｇｐｒｏｂｌｅｍ）是在受能力约束限制下，确定Ｎ种不同的项目在给定的计划范围Ｔ内的每一个时间段批量，使得在整个计划范围内（ｐｌａｎｎｉｎｇｈｏｒｉｚｏｎ）项目总的调整费用和库存保管费用以及生产费用之和最小．本文基于Ｌａｇｒａｎｇｉａｎ松弛法和新的启发式算法相结合求解ＣＬＳＰ问题，通过测试１０个问题，仿真实验表明，平均对偶误差可达到２％以内．

一种基于Lagrangian松弛法求解化工批处理过程调度的方法

提出一种快速求取化工批处理过程次优调度的方法。通过约束变换、引入操作批量的函数和松弛物料存贮能力约束,将调度问题分解为一个两层次的优化问题。用动态规划求解下层问题,用次梯度法求解上层对偶问题。然后依据对偶问题的解,以启发式方法构作原问题的可行解。数值测试结果证明了读方法的有效性和实用性。

考虑线路能力协调利用的车流径路与配空组织优化模型

为提高铁路整体通过能力,均衡利用路网中各线路,应对愈发波动的运输市场,开展考虑线路能力协调利用的重空车流协调优化模型研究。首先,对线路能力协调利用的实现机理进行研究,在考虑流平衡约束、配空约束、线路能力约束基础上,增加考虑铁路线路能力协调利用约束,同时在优化目标中增加紧张线路的使用成本,构建考虑线路能力协调利用的重空车流组织优化模型,以实现在优化车流径路与空车调配方案的同时兼顾铁路线路的协调利用。其次,在此基础上设计拉格朗日松弛算法,对线路能力约束与能力协调性约束松弛,将原问题分解为车流径路子问题、空车调配子问题和虚拟车流量子问题,进而降低了问题求解难度。再次,通过5组算例对算法的有效性进行验证,案例结果说明,设计的拉格朗日松弛算法在求解大规模算例时效率优于商业求解软件Gurobi。最后,设计了包含36个车站56条线路的实际案例,算法求解耗时4757.7 s,运输组织综合成本为29535803元,通过对求解结果分析,与传统优化模型相比该模型优化结果在运输成本仅增加1.56%的前提下能力紧张的线路数量由17条缩减至12条,降低了29.4%,同时空车调配符合就近配空的原则。研究结果表明,该模型可以有效缓解铁路能力紧张情况,促进铁路线路能力的协调利用。

基于拉格朗日松弛的产能共享讨价还价研究

以制造业产能共享为背景,考虑自利的产能提供方与需求方诉求不一致和市场关系不对等因素,采用Nash讨价还价理论研究共享产能分配策略。为此,首先将传统调度模型与非对称Nash讨价还价模型相结合,构建出本质为非线性整数规划的产能共享模型。继而,设计了基于拉格朗日松弛的求解算法,给出了产能共享的讨价还价分配结果。仿真分析表明,本文方法在大部分情况下能够获得理想的讨价还价结果。当产能提供方目标为min-sum型,其关注所有客户的自利且异质的时效要求,其与客户方的冲突尤其显著;随着其讨价还价能力的增强,其改善是以牺牲客户时效要求为代价的。然而当其讨价还价能力再继续增加,反而导致系统整体效益的波动。因此,博弈各方需要保持合理的讨价还价强度。

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

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

联合更换策略的机会性Lagrangian松弛方法

零部件的联合更换是通过协调不同零部件的更换决策使其尽可能共享资源以节约费用的优化问题.这类随机组合策略优化问题在实际中大量存在,对生产生活的经济性起着重要影响.由于随机因素和组合效应,其有限阶段的策略求解非常困难.本文针对飞机引擎维护中的零部件联合更换问题,利用问题中随机耦合约束的特征,给出了一个可分解的模型及相应的分解协调方法机会性Lagrangian松弛(Opportunistic Lagrangian relaxation,OLR).与现有的两种利用先验最优策略规则的方法相比,OLR方法可在无先验知识的情况下直接得到更佳的协调效果.

轧钢切断阶段动态HFS调度模型和LR算法研究

以钢管生产为背景,在分析钢管切割工艺的基础上,提炼出第一阶段具有批处理特征的动态HFS调度问题,建立了数学规划模型,目标是最小化所有工件的加权完成时间.针对该模型,构造了改进的拉格朗日松弛算法(lagrangian relaxation,LR)的求解过程,设计了求解批级子问题的动态规划算法和构造可行解的启发式算法.

多目标数据关联的多维Lagrangian松驰法

将多目标跟踪中的数据关联问题提成为一个离散最优化问题 ,并采用 L agrangian松驰算法来克服该问题面临的计算困难 ,这是目前多祯多目标测量数据关联研究发展的重要方向。首先将多祯多目标数据关联问题建立为一个带约束的多维分配问题 ;并在维数大于 2时 ,采用 L agrangian松驰算法来松驰约束条件 ,使问题降维为计算上可接受的二维分配问题。

非负拉格朗日松弛优化的子空间聚类算法

传统的子空间聚类和谱聚类中普遍使用谱松弛方法聚类,需要先计算拉普拉斯矩阵的特征向量。特征向量中包含负数,根据元素的正负可以直接得到二类聚类的结果。对于多类聚类问题,需要递归地进行二划分,或在特征向量空间中使用k-means算法聚类,分配类簇标签是间接的,这种后处理的聚类方式会增加聚类结果的不稳定性。针对谱松弛的问题,提出了一种非负拉格朗日松弛优化的子空间聚类算法,在目标函数中集成了自表示学习和秩约束。通过非负拉格朗日松弛来求解相似性矩阵和隶属矩阵,并保持隶属矩阵的非负性。在这种情况下,原来的隶属矩阵就变成了类簇的后验概率,当算法收敛时,只需将数据点分配给具有最大后验概率的类簇,即可得到聚类结果。与已有的子空间聚类和谱聚类方法相比,所提出的算法设计了新的优化规则,可以实现类簇标签的直接分配,不需要额外的聚类步骤。最后,给出了算法的收敛性证明。在5个基准聚类数据集上的大量实验表明,所提算法的聚类性能优于近几年来的子空间聚类方法。

逐步次梯度法在基于LR的调度算法中的应用

在基于拉格朗日松弛法(LR)的优化调度算法中,对偶问题的求解广泛采用的一种方法是次梯度法。在这个方法中,为了得到一个次梯度方向,相应松弛问题的所有的子问题都必须精确求解,当问题规模较大时求解时间过长。讨论了逐步次梯度法求解对偶问题的具体实现方法。将对偶函数化为多个子项和的形式,每求解一个子问题,就构造对应对偶函数一个子项的次梯度,逐步沿这些次梯度方向更新乘子。仿真结果显示,其收敛速度较原始的次梯度法有明显的提高。