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.

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.

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.

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.

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.

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.

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

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

新的Lagrangian松弛法求解CLSP问题

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

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

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

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

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

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

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

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

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

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

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

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

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

LR方法基于车间调度问题的面向对象设计

针对拉格朗日松弛方法解决不同车间调度问题时,对问题的依赖性强,算法实现复杂的情况,通过分析拉格朗日方法解决不同车间调度问题的特点,提出了拉格朗日算法面向时象的设计方法,并开发了通用的类模块;面向对象的模块关系和类层次使得算法可扩展性强,便于改进。仿真结果表明,用户可以方便地实现拉格朗日方法对多种车间调度问题的仿真,大大提高了代码的可重用性和软件的通用性。

Matrix decomposition and Lagrangian dual method for discrete portfolio optimization under concave transaction costs

In this paper, the discrete mean-variance model is considered for portfolio selection under concave transaction costs. By using the Cholesky decomposition technique, the convariance matrix to obtain a separable mixed integer nonlinear optimization problem is decomposed. A brand-and-bound algorithm based on Lagrangian relaxation is then proposed. Computational results are reported for test problems with the data randomly generated and those from the US stock market.

Relaxation-strategy-based Modification Branch-and-Bound Algorithm for Solving a Class of Transportation-production Problems

In this paper,a new algorithm relaxation-strategy-based modification branchand-bound algorithm is developed for a type of solving the minimum cost transportationproduction problem with concave production costs.The major improvement of the proposed new method is that modification algorithm reinforces the bounding operation using a Lagrangian relaxation,which is a concave minimization but obtains a tighter bound than the usual linear programming relaxation.Some computational results are included.Computation results indicate that the algorithm can solve fairly large scale problems.

Long-Time Relaxation and Residual Conductivity in GaP Irradiated by High-Energy Electrons

This paper presents the results of a study of long-time relaxation (LR) and residual conductivity in n-type gallium phosphide (GaP) crystals irradiated by 50 MeV electrons. A manifold increase in photosensitivity and quenching of residual conductivity was found as a result of irradiation. It is shown that LR in GaP is due to disordered regions (generated by electron irradiation) which have conductivity close to self one. The Fermi level in the disordered regions is determined by which is located deep in the forbidden band (Ее - 1.0 eV). LR effect is mainly explained by a spatial separation of electrons and holes, recombination of which is prevented by potential barriers. The observed increase in conductivity is associated with the increase in the concentration of minority carriers as well as with increase of the Hall mobility at the sample illumination.

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

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