The Experts below are selected from a list of 9819 Experts worldwide ranked by ideXlab platform
Ali Diabat - One of the best experts on this subject based on the ideXlab platform.
-
A Lagrangian Relaxation-based heuristic for the multi-ship quay crane scheduling problem with ship stability constraints
Annals of Operations Research, 2017Co-Authors: Noura Al-dhaheri, Ali DiabatAbstract:The quay crane scheduling problem is one of the major problems of quayside operational planning in container terminals. The operational efficiency of quay cranes is a large determinant of the overall container terminal efficiency; thus, in an effort to maximize throughput, more and more emphasis is placed on systematically addressing and improving quay crane operations. However, the resulting formulations are highly complex and thus not solvable using commercial software. In the first part of the present paper, we develop a formulation that overcomes this challenge. This allows for solving the model using CPLEX, even for large size instances, which other notable work from the literature fails to solve. The second part of this paper addresses a crucial point which has rarely been accounted for, which is ship stability. A heuristic is developed to solve the extended problem, as it is no longer solvable in CPLEX. The remaining objective of this work is to extend this problem to the multi-ship case. However, once again the problem is insolvable for large instances using CPLEX, even without accounting for stability constraints. We develop a Lagrangian Relaxation based algorithm that decomposes the problem by ship, which is solved efficiently as a single ship case. The Lagrangian multipliers are updated using the cutting plane method and the solution of the Lagrangian master problem provides an upper bound on the optimal value of the Lagrangian lower bound. Upper bounds on the optimal value of the original problem are obtained using a constructive heuristic, and through computational experiments we demonstrate the performance of the Lagrangian Relaxation-based procedures.
-
an integrated supply chain problem a nested Lagrangian Relaxation approach
Annals of Operations Research, 2015Co-Authors: Ali Diabat, Jeanphilippe P RichardAbstract:The integration of tactical-level with strategic-level decisions in the supply chain represents an opportunity for substantial cost savings and provides a means for companies to gain a competitive advantage. Much of the previous research on supply chain network design has handled facility location decisions and inventory management decisions independently. In this paper, we develop a new joint facility location inventory model that is based on an approximate one-warehouse multi-retailer inventory model for each warehouse, and on the uncapacitated facility location problem. The proposed integer programming model simultaneously makes decisions pertaining to location and inventory policies on two echelons of the supply chain, the warehouse and the retailers. We develop two Lagrangian-Relaxation-based algorithms to solve this model, and compare their performance to that of a conventional branch-and-bound algorithm on randomly generated problems.
-
a Lagrangian Relaxation approach for solving the integrated quay crane assignment and scheduling problem
Applied Mathematical Modelling, 2015Co-Authors: Ali DiabatAbstract:Abstract Decisions on the quay crane assignment problem and the quay crane scheduling problem are typically made independently. However, the efficiency of container terminals can be increased when these decisions are made simultaneously due to the interrelation between quay crane assignment and scheduling. A mathematical formulation for the integrated quay crane assignment and scheduling problem (QCASP) is developed in this paper. Practical considerations are incorporated in the model, such as quay crane (QC) interference. A Lagrangian Relaxation is proposed for the model. Feasible solutions are then obtained from the proposed heuristic. Computational results are provided for the proposed Lagrangian Relaxation.
-
An improved Lagrangian Relaxation-based heuristic for a joint location-inventory problem
Computers and Operations Research, 2014Co-Authors: Ali Diabat, Olga Battaïa, Dima NazzalAbstract:We consider a multi-echelon joint inventory-location (MJIL) problem that makes location, order assignment, and inventory decisions simultaneously. The model deals with the distribution of a single commodity from a single manufacturer to a set of retailers through a set of sites where distribution centers can be located. The retailers face deterministic demand and hold working inventory. The distribution centers order a single commodity from the manufacturer at regular intervals and distribute the product to the retailers. The distribution centers also hold working inventory representing product that has been ordered from the manufacturer but has not been yet requested by any of the retailers. Lateral supply among the distribution centers is not allowed. The problem is formulated as a nonlinear mixed-integer program, which is shown to be NP-hard. This problem has recently attracted attention, and a number of different solution approaches have been proposed to solve it. In this paper, we present a Lagrangian Relaxation-based heuristic that is capable of efficiently solving large-size instances of the problem. A computational study demonstrates that our heuristic solution procedure is efficient, and yields optimal or near-optimal solutions.
-
a Lagrangian Relaxation approach to simultaneous strategic and tactical planning in supply chain design
Annals of Operations Research, 2013Co-Authors: Ali Diabat, Jeanphilippe P Richard, Craig W CodringtonAbstract:We study a multi-echelon joint inventory-location model that simultaneously determines the location of warehouses and inventory policies at the warehouses and retailers. The model is formulated as a nonlinear mixed-integer program, and is solved using a Lagrangian Relaxation-based approach. The efficiency of the algorithm and benefits of integration are evaluated through a computational study. Copyright The Author(s) 2013
Antonio J Conejo - One of the best experts on this subject based on the ideXlab platform.
-
decentralized state estimation and bad measurement identification an efficient Lagrangian Relaxation approach
IEEE Transactions on Power Systems, 2011Co-Authors: Eduardo Caro, Antonio J Conejo, R MinguezAbstract:This paper proposes a decentralized state-estimation approach that relies on an elaborated instance of the Lagrangian Relaxation decomposition technique. The proposed algorithm does not require a central coordinator but just to moderate interchanges of information among neighboring regions, and exploits the structure of the problem to achieve a fast and accurate convergence. Additionally, a decentralized bad measurement identification procedure is developed, which is efficient and robust in terms of identifying bad measurements within regions and in border tie-lines. The accuracy and efficiency of the proposed procedures are assessed by a large number of simulations, which allows drawing statistically sound conclusions.
-
short term hydro thermal coordination by Lagrangian Relaxation solution of the dual problem
IEEE Transactions on Power Systems, 1999Co-Authors: N J Redondo, Antonio J ConejoAbstract:This paper addresses the short-term hydrothermal coordination problem. This problem is large-scale, combinatorial and nonlinear. It is usually solved using a Lagrangian Relaxation approach. In the framework of the Lagrangian Relaxation, this paper provides a novel, nonoscillating and efficient multiplier updating procedure. This procedure advantageously compares with previously reported procedures such us subgradient and bundle methods. A realistic large-scale case study is used to illustrate the behavior of the proposed procedure.
Stefan Canzar - One of the best experts on this subject based on the ideXlab platform.
-
a Lagrangian Relaxation approach for the multiple sequence alignment problem
Journal of Combinatorial Optimization, 2008Co-Authors: Ernst Althaus, Stefan CanzarAbstract:We present a branch-and-bound (bb) algorithm for the multiple sequence alignment problem (MSA), one of the most important problems in computational biology. The upper bound at each bb node is based on a Lagrangian Relaxation of an integer linear programming formulation for MSA. Dualizing certain inequalities, the Lagrangian subproblem becomes a pairwise alignment problem, which can be solved efficiently by a dynamic programming approach. Due to a reformulation w.r.t. additionally introduced variables prior to Relaxation we improve the convergence rate dramatically while at the same time being able to solve the Lagrangian problem efficiently. Our experiments show that our implementation, although preliminary, outperforms all exact algorithms for the multiple sequence alignment problem. Furthermore, the quality of the alignments is among the best computed so far.
-
a Lagrangian Relaxation approach for the multiple sequence alignment problem
Conference on Combinatorial Optimization and Applications, 2007Co-Authors: Ernst Althaus, Stefan CanzarAbstract:We present a branch-and-bound (bb) algorithm for the multiple sequence alignment problem (MSA), one of the most important problems in computational biology. The upper bound at each bb node is based on a Lagrangian Relaxation of an integer linear programming formulation for MSA. Dualizing certain inequalities, the Lagrangian subproblem becomes a pairwise alignment problem, which can be solved efficiently by a dynamic programming approach. Due to a reformulation w.r.t. additionally introduced variables prior to Relaxation we improve the convergence rate dramatically while at the same time being able to solve the Lagrangian problem efficiently. Our experiments show that our implementation, although preliminary, outperforms all exact algorithms for the multiple sequence alignment problem.
Tao Ding - One of the best experts on this subject based on the ideXlab platform.
-
conic programming based Lagrangian Relaxation method for dcopf with transmission losses and its zero gap sufficient condition
IEEE Transactions on Power Systems, 2017Co-Authors: Tao Ding, Chaoyue Zhao, Tianen Chen, Ruifeng LiuAbstract:This paper presents a fast optimization approach framework for the DC optimal power flow (DCOPF) with the consideration of transmission losses, which is confronted with nonconvex quadratically constrained quadratic programming. Specifically, a second-order cone programming-based Lagrangian Relaxation method is employed to obtain the lower bound of the original DCOPF. Furthermore, a sufficient condition for the zero-gap Relaxation is derived, which is easy to be satisfied in practice. Finally, the comparison with existing DCOPF solvers shows that the proposed method could achieve the global optimal solution and jump out of the local optimality. Also, the comparison with the widely used semidefinite programming Relaxation approach indicates that the proposed Relaxation method needs less dummy variables, and thus can be more efficiently solved and more applicable for large-scale power systems.
-
Parallel Augmented Lagrangian Relaxation for Dynamic Economic Dispatch Using Diagonal Quadratic Approximation Method
IEEE Transactions on Power Systems, 2017Co-Authors: Tao DingAbstract:Dynamic economic dispatch (DED) over multiple time periods is a large-scale coupled spatial-temporal optimization problem. Therefore, the Lagrangian Relaxation method has been widely used to split the large-scale optimization problem with coupled structure into several small sub-problems. In order to bring robustness for updating the dual multipliers and yielding convergence without strong assumptions, the augmented Lagrangian Relaxation method is introduced in this paper. However, the added penalty term in an augmented Lagrangian function is non-separable, which leads to the difficulty in achieving full decomposition for parallel computation. To address this problem, a diagonal quadratic approximation method is employed to yield an approximated block separation of the non-separable penalty term. Furthermore, the ramp rate constraints are relaxed in this paper, so that the DED model is decomposed into several single-period economic dispatch models that can be efficiently handled in parallel, called the parallel augmented Lagrangian Relaxation method. Particularly, the proposed Relaxation strategy has a high separability feature which theoretically leads to sound convergence property. Numerical results on the IEEE 118-bus and a practical Polish 2383-bus test system over a different number of time periods show the effectiveness of the proposed method. In addition, the proposed method can be extended to other coupled spatial-temporal scheduling problems in power systems, such as energy storage dispatch.
Peter B Luh - One of the best experts on this subject based on the ideXlab platform.
-
event based optimization within the Lagrangian Relaxation framework for energy savings in hvac systems
IEEE Transactions on Automation Science and Engineering, 2015Co-Authors: Biao Sun, Peter B Luh, Qingshan Jia, Bing YanAbstract:Optimizing HVAC operation becomes increasingly important because of the rising energy cost and comfort requirements. In this paper, an innovative event-based approach is developed within the Lagrangian Relaxation framework to minimize an HVAC's day-ahead energy cost. To solve the HVAC optimization problem based on events is challenging since with time-dependent uncertainties in weather, cooling load, etc., the optimal policy is not stationary. The nonstationary policy space is extremely large, and it is time consuming to find the optimal policy. To overcome the challenge, we develop an event-based approach to make the nonstationary optimal policy stationary in the planning horizon. The key idea is to augment state variables to include the time-dependent variables that make the optimal policy nonstationary and then define events based on the extended state variables. In addition, we develop within the Lagrangian Relaxation framework a Q-learning method where Q-factors are used to evaluate event-action pairs and to obtain the optimal policy. Numerical results demonstrate that, as compared with time-based approaches, the event-based approach maintains similar levels of energy costs and human comfort, but reduces computational efforts significantly and has a much faster response to events.
-
convergence of the surrogate Lagrangian Relaxation method
Journal of Optimization Theory and Applications, 2015Co-Authors: Mikhail A Bragin, Peter B Luh, Joseph H Yan, Gary A SternAbstract:Studies have shown that the surrogate subgradient method, to optimize non-smooth dual functions within the Lagrangian Relaxation framework, can lead to significant computational improvements as compared to the subgradient method. The key idea is to obtain surrogate subgradient directions that form acute angles toward the optimal multipliers without fully minimizing the relaxed problem. The major difficulty of the method is its convergence, since the convergence proof and the practical implementation require the knowledge of the optimal dual value. Adaptive estimations of the optimal dual value may lead to divergence and the loss of the lower bound property for surrogate dual values. The main contribution of this paper is on the development of the surrogate Lagrangian Relaxation method and its convergence proof to the optimal multipliers, without the knowledge of the optimal dual value and without fully optimizing the relaxed problem. Moreover, for practical implementations, a stepsizing formula that guarantees convergence without requiring the optimal dual value has been constructively developed. The key idea is to select stepsizes in a way that distances between Lagrange multipliers at consecutive iterations decrease, and as a result, Lagrange multipliers converge to a unique limit. At the same time, stepsizes are kept sufficiently large so that the algorithm does not terminate prematurely. At convergence, the lower-bound property of the surrogate dual is guaranteed. Testing results demonstrate that non-smooth dual functions can be efficiently optimized, and the new method leads to faster convergence as compared to other methods available for optimizing non-smooth dual functions, namely, the simple subgradient method, the subgradient-level method, and the incremental subgradient method.
-
surrogate Lagrangian Relaxation and branch and cut for unit commitment with combined cycle units
Power and Energy Society General Meeting, 2014Co-Authors: Mikhail A Bragin, Peter B Luh, Joseph H Yan, Gary A SternAbstract:Combined cycle (CC) units are efficient because heat from combustion turbines is not wasted but is used for steam turbines. However, when state transitions are followed, CC units complicate the unit commitment and economic dispatch (UCED) problem. While branch-and-cut has been successful in solving UCED problems without considering CC units, transitions in one such unit affect the entire problem. Therefore, the convex hull is difficult to obtain and the UCED problem with CC units is difficult to solve. To efficiently solve the problem, we exploit linearity as well as separability. To decompose the problem into subproblems associated with conventional and CC units, our recently developed surrogate Lagrangian Relaxation will be used to relax coupling system-wide constraints, and each subproblem will then be solved by using branch-and-cut. Constraints as well as transitions within a CC unit are handled locally and no longer affect the entire problem. Moreover, we will demonstrate that branch-and-cut can handle individual subproblems much more efficiently as compared to the original problem. The linear structure of coupling constraints is then exploited to obtain feasible costs. Numerical results demonstrate that the new approach is computationally efficient and generates good feasible solutions.
-
synergy of Lagrangian Relaxation and constraint programming for manufacturing scheduling
World Congress on Intelligent Control and Automation, 2006Co-Authors: R Buil, Peter B Luh, Bo XiongAbstract:Scheduling is a key factor for manufacturing productivity due to the penalties of not delivering orders on time. Since manufacturing scheduling problems are NP-hard, there is a need of improving scheduling methodologies to get good solutions within low computation time. Lagrangian Relaxation (LR) is known for handling large-scale separable problems because of the exploiting problem separability, however, the convergence can be slow and the final feasible solutions may not be good. Constraint Programming (CP) is also effective in solving large problems, especially in the area of planning, however, it may not take advantage of the problem structure. In this paper, we combine LR and CP to establish a new methodology capable of obtaining better solutions than the current methodologies and with less computation time. Using the LR approach, the divide and conquer idea is applied through decomposition and coordination. The original NP-hard problem is decomposed into smaller non NP-hard subproblems by using Lagrange multipliers. These subproblems can be solved efficiently, and the multipliers are then iteratively adjusted to maximize the dual function. The convergence, however, may be slow. CP is used in certain iterations to obtain better step sizes to speed up convergence. When the iterative method stops, the result is an infeasible schedule for the original problem. Time windows around this solution are constructed and CP is used to find the best solution within them. Testing results show that the approach can generate good results with a low computation time.
-
an alternative framework to Lagrangian Relaxation approach for job shop scheduling
European Journal of Operational Research, 2003Co-Authors: Haoxun Chen, Peter B LuhAbstract:Abstract A new Lagrangian Relaxation (LR) approach is developed for job shop scheduling problems. In the approach, operation precedence constraints rather than machine capacity constraints are relaxed. The relaxed problem is decomposed into single or parallel machine scheduling subproblems. These subproblems, which are NP-complete in general, are approximately solved by using fast heuristic algorithms. The dual problem is solved by using a recently developed “surrogate subgradient method” that allows approximate optimization of the subproblems. Since the algorithms for subproblems do not depend on the time horizon of the scheduling problems and are very fast, our new LR approach is efficient, particularly for large problems with long time horizons. For these problems, the machine decomposition-based LR approach requires much less memory and computation time as compared to a part decomposition-based approach as demonstrated by numerical testing.
