In this paper, an absorbing Fictitious Boundary Condition (FBC) is presented to generate an iterative Domain Decomposition Method (DDM) for analyzing waveguide problems.The relaxed algorithm is introduced to improve t...In this paper, an absorbing Fictitious Boundary Condition (FBC) is presented to generate an iterative Domain Decomposition Method (DDM) for analyzing waveguide problems.The relaxed algorithm is introduced to improve the iterative convergence. And the matrix equations are solved using the multifrontal algorithm. The resulting CPU time is greatly reduced.Finally, a number of numerical examples are given to illustrate its accuracy and efficiency.展开更多
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.展开更多
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 maj...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.展开更多
The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,and each knapsack i has a ca...The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,and each knapsack i has a capacity Ci.The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks.MKP(B,S,m,n) is strongly NP- Complete and no polynomial- time approximation algorithm can have an approxima- tion ratio better than0 .5 .In the last ten years,semi- definite programming has been empolyed to solve some combinatorial problems successfully.This paper firstly presents a semi- definite re- laxation algorithm (MKPS) for MKP (B,S,m,n) .It is proved that MKPS have a approxima- tion ratio better than 0 .5 for a subclass of MKP (B,S,m,n) with n≤ 1 0 0 ,m≤ 5 and maxnj=1{ wj} minmi=1{ Ci} ≤ 2 3 .展开更多
The purpose of this paper is to investigate the problem of finding the common element of the set of common fixed points of a countable family of nonexpansive mappings, the set of an equilibrium problem and the set of ...The purpose of this paper is to investigate the problem of finding the common element of the set of common fixed points of a countable family of nonexpansive mappings, the set of an equilibrium problem and the set of solutions of the variational inequality prob- lem for a relaxed cocoercive and Lipschitz continuous mapping in Hilbert spaces. Then, we show that the sequence converges strongly to a common element of the above three sets under some parameter controlling conditions, which are connected with Yao, Liou, Yao[17], Takahashi[12] and many others.展开更多
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.展开更多
The multisplitting algorithm for solving large systems of ordinary differential equations on parallel computers was introduced by Jeltsch and Pohl in [1]. On fixed time intervals conver gence results could be derived ...The multisplitting algorithm for solving large systems of ordinary differential equations on parallel computers was introduced by Jeltsch and Pohl in [1]. On fixed time intervals conver gence results could be derived if the subsystems are solving exactly.Firstly,in theis paper,we deal with an extension of the waveform relaxation algorithm by us ing multisplittin AOR method based on an overlapping block decomposition. We restricted our selves to equidistant timepoints and dealed with the case that an implicit integration method was used to solve the subsystems numerically in parallel. Then we have proved convergence of multi splitting AOR waveform relaxation algorithm on a fixed window containing a finite number of timepoints.展开更多
Abstract In this paper,a class of generalized parallel matrix multisplitting relaxation methods for solving linear complementarity problems on the high speed multiprocessor systems is set up.This class of methods not ...Abstract In this paper,a class of generalized parallel matrix multisplitting relaxation methods for solving linear complementarity problems on the high speed multiprocessor systems is set up.This class of methods not only includes all the existing relaxation methods for the linear complementarity problems,but also yields a lot of novel ones in the sense of multisplitting.We establish the convergence theories of this class of generalized parallel multisplitting relaxation methods under the condition that the system matrix is an H matrix with positive diagonal elements.展开更多
In this article, we derive the intrinsic equations for a generalized relaxed elastic line on an oriented surface in the Galilean 3-dimensional space G3. These equations will give direct and more geometric approach to ...In this article, we derive the intrinsic equations for a generalized relaxed elastic line on an oriented surface in the Galilean 3-dimensional space G3. These equations will give direct and more geometric approach to questions concerning about generalized relaxed elastic lines on an oriented surface in G3.展开更多
Multi-dimensional nonlinear knapsack problem is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to multiple separable nondecreasing constraints. This problem i...Multi-dimensional nonlinear knapsack problem is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to multiple separable nondecreasing constraints. This problem is often encountered in resource allocation, industrial planning and computer network. In this paper, a new convergent Lagrangian dual method was proposed for solving this problem. Cutting plane method was used to solve the dual problem and to compute the Lagrangian bounds of the primal problem. In order to eliminate the duality gap and thus to guarantee the convergence of the algorithm, domain cut technique was employed to remove certain integer boxes and partition the revised domain to a union of integer boxes. Extensive computational results show that the proposed method is efficient for solving large-scale multi-dimensional nonlinear knapsack problems. Our numerical results also indicate that the cutting plane method significantly outperforms the subgradient method as a dual search procedure.展开更多
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.展开更多
In this work, the Lagrangean Relaxation method has been discussed to solve different sizes of capacitated facility location problem (CFLP). A good lower bound has been achieved on the solution of the CFLP considered i...In this work, the Lagrangean Relaxation method has been discussed to solve different sizes of capacitated facility location problem (CFLP). A good lower bound has been achieved on the solution of the CFLP considered in this paper. This lower bound has been improved by using the Volume algorithm. The methods of setting two important parameters in heuristic have been given. The approaches used to gain the lower bound have been explained. The results of this work have been compared with the known results given by Beasley.展开更多
In this paper, a branch-and-bound method for solving multi-dimensional quadratic 0-1 knapsack problems was studied. The method was based on the Lagrangian relaxation and the surrogate constraint technique for finding ...In this paper, a branch-and-bound method for solving multi-dimensional quadratic 0-1 knapsack problems was studied. The method was based on the Lagrangian relaxation and the surrogate constraint technique for finding feasible solutions. The Lagrangian relaxations were solved with the maximum-flow algorithm and the Lagrangian bounds was determined with the outer approximation method. Computational results show the efficiency of the proposed method for multi-dimensional quadratic 0-1 knapsack problems.展开更多
We study a Dirichlet optimal design problem for a quasi-linear monotone p-biharmonic equation with control and state constraints. We take the coefficient of the p-biharmonic operator as a design variable in . In this ...We study a Dirichlet optimal design problem for a quasi-linear monotone p-biharmonic equation with control and state constraints. We take the coefficient of the p-biharmonic operator as a design variable in . In this article, we discuss the relaxation of such problem.展开更多
The multivalued general mixed implicit equilibrium-like problems are introduced and studied. To solve these problems, a new predictor-corrector iterative algorithm is proposed and analyzed using the auxiliary principl...The multivalued general mixed implicit equilibrium-like problems are introduced and studied. To solve these problems, a new predictor-corrector iterative algorithm is proposed and analyzed using the auxiliary principle technique. The convergence of the suggested algorithm is also proved in weaker conditions.展开更多
Single Stage Capacitated Warehouse Location Problem (SSCWLP) has been attempted by few researchers in the past. These are Geoffrion and Graves [1], Sharma [2], Sharma [3] and Sharma and Berry [4]. In this paper we giv...Single Stage Capacitated Warehouse Location Problem (SSCWLP) has been attempted by few researchers in the past. These are Geoffrion and Graves [1], Sharma [2], Sharma [3] and Sharma and Berry [4]. In this paper we give a “vertical decomposition” approach to solve SSCWLP that uses Lagrangian relaxation. This way SSCWLP is broken into two versions of capacitated plant location problem (the CPLP_L and CPLP_R) by relaxing the flow balance constraints. For CPLP_R, we use well known Lagrangian relaxations given in literature (Christofides and Beasley [5] and Nauss [6]);and adopt them suitably for solving CPLP_L. We show theoretically in this paper that SSCWLP can be more efficiently solved by techniques of vertical decomposition developed in this paper than the method available in literature (Sharma and Berry [4]). Encouraging computational study is reported in this paper.展开更多
In this paper, we investigate the elementary wave interactions for the Suliciu relaxation system and construct uniquely the solution by the characteristic analysis method in the phase plane. We find that the elementar...In this paper, we investigate the elementary wave interactions for the Suliciu relaxation system and construct uniquely the solution by the characteristic analysis method in the phase plane. We find that the elementary wave interactions have a much simpler structure for the Temple class than the general systems of conservation laws. It is observed that the Riemann solutions of the Suliciu relaxation system are stable under the small perturbation on the Riemann initial data.展开更多
In this paper,the relaxation algorithm and two Uzawa type algorithms for solving discretized variational inequalities arising from the two-phase Stefan type problem are proposed.An analysis of their convergence is pre...In this paper,the relaxation algorithm and two Uzawa type algorithms for solving discretized variational inequalities arising from the two-phase Stefan type problem are proposed.An analysis of their convergence is presented and the upper bounds of the convergence rates are derived.Some numerical experiments are shown to demonstrate that for the second Uzawa algorithm which is an improved version of the first Uzawa algorithm,the convergence rate is uniformly bounded away from 1 if τh^-2 is kept bounded,where τ is the time step size and h the space mesh size.展开更多
文摘In this paper, an absorbing Fictitious Boundary Condition (FBC) is presented to generate an iterative Domain Decomposition Method (DDM) for analyzing waveguide problems.The relaxed algorithm is introduced to improve the iterative convergence. And the matrix equations are solved using the multifrontal algorithm. The resulting CPU time is greatly reduced.Finally, a number of numerical examples are given to illustrate its accuracy and efficiency.
文摘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.
基金Foundation item: Supported by the National Natural Science Foundation of China(10726016) Supported by the Hubei Province Natural Science Foundation Project(T200809 D200613002)
文摘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.
基金Supported by the National Natural Science Foundation of China(1 9971 0 78)
文摘The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,and each knapsack i has a capacity Ci.The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks.MKP(B,S,m,n) is strongly NP- Complete and no polynomial- time approximation algorithm can have an approxima- tion ratio better than0 .5 .In the last ten years,semi- definite programming has been empolyed to solve some combinatorial problems successfully.This paper firstly presents a semi- definite re- laxation algorithm (MKPS) for MKP (B,S,m,n) .It is proved that MKPS have a approxima- tion ratio better than 0 .5 for a subclass of MKP (B,S,m,n) with n≤ 1 0 0 ,m≤ 5 and maxnj=1{ wj} minmi=1{ Ci} ≤ 2 3 .
基金Supported by King Mongkut's University of Technology Thonburi.KMUTT,(CSEC Project No.E01008)supported by the Faculty of Applied Liberal Arts RMUTR Research Fund and King Mongkut's Diamond scholarship for fostering special academic skills by KMUTT
文摘The purpose of this paper is to investigate the problem of finding the common element of the set of common fixed points of a countable family of nonexpansive mappings, the set of an equilibrium problem and the set of solutions of the variational inequality prob- lem for a relaxed cocoercive and Lipschitz continuous mapping in Hilbert spaces. Then, we show that the sequence converges strongly to a common element of the above three sets under some parameter controlling conditions, which are connected with Yao, Liou, Yao[17], Takahashi[12] and many others.
基金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.
文摘The multisplitting algorithm for solving large systems of ordinary differential equations on parallel computers was introduced by Jeltsch and Pohl in [1]. On fixed time intervals conver gence results could be derived if the subsystems are solving exactly.Firstly,in theis paper,we deal with an extension of the waveform relaxation algorithm by us ing multisplittin AOR method based on an overlapping block decomposition. We restricted our selves to equidistant timepoints and dealed with the case that an implicit integration method was used to solve the subsystems numerically in parallel. Then we have proved convergence of multi splitting AOR waveform relaxation algorithm on a fixed window containing a finite number of timepoints.
文摘Abstract In this paper,a class of generalized parallel matrix multisplitting relaxation methods for solving linear complementarity problems on the high speed multiprocessor systems is set up.This class of methods not only includes all the existing relaxation methods for the linear complementarity problems,but also yields a lot of novel ones in the sense of multisplitting.We establish the convergence theories of this class of generalized parallel multisplitting relaxation methods under the condition that the system matrix is an H matrix with positive diagonal elements.
文摘In this article, we derive the intrinsic equations for a generalized relaxed elastic line on an oriented surface in the Galilean 3-dimensional space G3. These equations will give direct and more geometric approach to questions concerning about generalized relaxed elastic lines on an oriented surface in G3.
文摘Multi-dimensional nonlinear knapsack problem is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to multiple separable nondecreasing constraints. This problem is often encountered in resource allocation, industrial planning and computer network. In this paper, a new convergent Lagrangian dual method was proposed for solving this problem. Cutting plane method was used to solve the dual problem and to compute the Lagrangian bounds of the primal problem. In order to eliminate the duality gap and thus to guarantee the convergence of the algorithm, domain cut technique was employed to remove certain integer boxes and partition the revised domain to a union of integer boxes. Extensive computational results show that the proposed method is efficient for solving large-scale multi-dimensional nonlinear knapsack problems. Our numerical results also indicate that the cutting plane method significantly outperforms the subgradient method as a dual search procedure.
文摘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.
文摘In this work, the Lagrangean Relaxation method has been discussed to solve different sizes of capacitated facility location problem (CFLP). A good lower bound has been achieved on the solution of the CFLP considered in this paper. This lower bound has been improved by using the Volume algorithm. The methods of setting two important parameters in heuristic have been given. The approaches used to gain the lower bound have been explained. The results of this work have been compared with the known results given by Beasley.
基金Project supported by the National Natural Science Foundation of China (Grant No.10571116)
文摘In this paper, a branch-and-bound method for solving multi-dimensional quadratic 0-1 knapsack problems was studied. The method was based on the Lagrangian relaxation and the surrogate constraint technique for finding feasible solutions. The Lagrangian relaxations were solved with the maximum-flow algorithm and the Lagrangian bounds was determined with the outer approximation method. Computational results show the efficiency of the proposed method for multi-dimensional quadratic 0-1 knapsack problems.
文摘We study a Dirichlet optimal design problem for a quasi-linear monotone p-biharmonic equation with control and state constraints. We take the coefficient of the p-biharmonic operator as a design variable in . In this article, we discuss the relaxation of such problem.
基金Project supported by the National Natural Science Foundation of China(No.10771173)
文摘The multivalued general mixed implicit equilibrium-like problems are introduced and studied. To solve these problems, a new predictor-corrector iterative algorithm is proposed and analyzed using the auxiliary principle technique. The convergence of the suggested algorithm is also proved in weaker conditions.
文摘Single Stage Capacitated Warehouse Location Problem (SSCWLP) has been attempted by few researchers in the past. These are Geoffrion and Graves [1], Sharma [2], Sharma [3] and Sharma and Berry [4]. In this paper we give a “vertical decomposition” approach to solve SSCWLP that uses Lagrangian relaxation. This way SSCWLP is broken into two versions of capacitated plant location problem (the CPLP_L and CPLP_R) by relaxing the flow balance constraints. For CPLP_R, we use well known Lagrangian relaxations given in literature (Christofides and Beasley [5] and Nauss [6]);and adopt them suitably for solving CPLP_L. We show theoretically in this paper that SSCWLP can be more efficiently solved by techniques of vertical decomposition developed in this paper than the method available in literature (Sharma and Berry [4]). Encouraging computational study is reported in this paper.
文摘In this paper, we investigate the elementary wave interactions for the Suliciu relaxation system and construct uniquely the solution by the characteristic analysis method in the phase plane. We find that the elementary wave interactions have a much simpler structure for the Temple class than the general systems of conservation laws. It is observed that the Riemann solutions of the Suliciu relaxation system are stable under the small perturbation on the Riemann initial data.
基金supported by the National Natural Science Foundation (10871179) of China
文摘In this paper,the relaxation algorithm and two Uzawa type algorithms for solving discretized variational inequalities arising from the two-phase Stefan type problem are proposed.An analysis of their convergence is presented and the upper bounds of the convergence rates are derived.Some numerical experiments are shown to demonstrate that for the second Uzawa algorithm which is an improved version of the first Uzawa algorithm,the convergence rate is uniformly bounded away from 1 if τh^-2 is kept bounded,where τ is the time step size and h the space mesh size.