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-co...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.展开更多
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 so...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.展开更多
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 d...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.展开更多
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 pos...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.展开更多
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 co...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.展开更多
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 met...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.展开更多
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 de...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.展开更多
安全约束机组组合(security constrained unit commitment,SCUC)是电网出清场景中最为广泛使用的一类模型。建立了一种针对超大规模SCUC现货市场出清问题的求解框架,首先提出了SCUC问题的时间解耦求解方法,通过缩小问题的规模来加快求...安全约束机组组合(security constrained unit commitment,SCUC)是电网出清场景中最为广泛使用的一类模型。建立了一种针对超大规模SCUC现货市场出清问题的求解框架,首先提出了SCUC问题的时间解耦求解方法,通过缩小问题的规模来加快求解速度;其次针对时间解耦后模型的子问题提出了拉格朗日松弛求解技术,在不影响求解准确度的情况下,有效降低了关键困难约束的求解难度。数值实验证明,所提出的框架极大地提升了求解效率,且十分稳定。展开更多
基金Projects(51435009,51575212,61573249,61371200)supported by the National Natural Science Foundation of ChinaProjects(2015T80798,2014M552040,2014M561250,2015M571328)supported by Postdoctoral Science Foundation of ChinaProject(L2015372)supported by Liaoning Province Education Administration,China
文摘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.
文摘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.
文摘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.
文摘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.
基金supported by the National Natural Science Foundation of China(71401106)the Innovation Program of Shanghai Municipal Education Commission(14YZ090)+4 种基金the Shanghai Natural Science Foundation(14ZR1418700)the Shanghai First-class Academic Discipline Project(S1201YLXK)the Hujiang Foundation of China(A14006)the grant S2009/esp-1594 from the Comunidad de Madrid(Spain)the grant MTM2012-36163-C06-06 from the Spanish government
文摘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.
文摘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.
文摘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.
文摘安全约束机组组合(security constrained unit commitment,SCUC)是电网出清场景中最为广泛使用的一类模型。建立了一种针对超大规模SCUC现货市场出清问题的求解框架,首先提出了SCUC问题的时间解耦求解方法,通过缩小问题的规模来加快求解速度;其次针对时间解耦后模型的子问题提出了拉格朗日松弛求解技术,在不影响求解准确度的情况下,有效降低了关键困难约束的求解难度。数值实验证明,所提出的框架极大地提升了求解效率,且十分稳定。