In this paper,we study a class of Linear Fractional Programming on a nonempty bounded set,called the Problem(LFP),and design a branch and bound algorithm to find the global optimal solution of the problem(LFP).First,w...In this paper,we study a class of Linear Fractional Programming on a nonempty bounded set,called the Problem(LFP),and design a branch and bound algorithm to find the global optimal solution of the problem(LFP).First,we convert the problem(LFP)to the equivalent problem(EP2).Secondly,by applying the linear relaxation technique to the problem(EP2),the linear relaxation programming problem(LRP2Y)was obtained.Then,the overall framework of the algorithm is given,and the convergence and complexity of the algorithm are analyzed.Finally,experimental results are listed to illustrate the effectiveness of the algorithm.展开更多
Considering the decision-making variables of the capacities of branch roads and the optimization targets of lowering the saturation of arterial roads and the reconstruction expense of branch roads, the bi-level progra...Considering the decision-making variables of the capacities of branch roads and the optimization targets of lowering the saturation of arterial roads and the reconstruction expense of branch roads, the bi-level programming model for reconstructing the branch roads was set up. The upper level model was for determining the enlarged capacities of the branch roads, and the lower level model was for calculating the flows of road sections via the user equilibrium traffic assignment method. The genetic algorithm for solving the bi-level model was designed to obtain the reconstruction capacities of the branch roads. The results show that by the bi-level model and its algorithm, the optimum scheme of urban branch roads reconstruction can be gained, which reduces the saturation of arterial roads apparently, and alleviates traffic congestion. In the data analysis the arterial saturation decreases from 1.100 to 0.996, which verifies the micro-circulation transportation's function of urban branch road network.展开更多
Most real-world optimization problems are hierarchical involving non-cooperative objectives. Many of these problems can be formulated in terms of the first（upper level） objective function being minimized over the so...Most real-world optimization problems are hierarchical involving non-cooperative objectives. Many of these problems can be formulated in terms of the first（upper level） objective function being minimized over the solution set mapping of the second（lower level） optimization problem. Often the upper level decision maker is risk-averse. The resulting class of problem is named weak bilevel programming problem. This paper presents a new algorithm which embeds a penalty function method into a branch and bound algorithm to deal with a weak linear bilevel programming problem. An example illustrates the feasibility of the proposed algorithm.展开更多
In this paper,we study the minimax linear fractional programming problem on a non-empty bounded set,called problem(MLFP),and we design a branch and bound algorithm to find a globally optimal solution of(MLFP).Firstly,...In this paper,we study the minimax linear fractional programming problem on a non-empty bounded set,called problem(MLFP),and we design a branch and bound algorithm to find a globally optimal solution of(MLFP).Firstly,we convert the problem(MLFP)to a problem(EP2)that is equivalent to it.Secondly,by applying the convex relaxation technique to problem(EP2),a convex quadratic relaxation problem(CQRP)is obtained.Then,the overall framework of the algorithm is given and its convergence is proved,the worst-case iteration number is also estimated.Finally,experimental data are listed to illustrate the effectiveness of the algorithm.展开更多
The general m-machine permutation flowshop problem with the total flow-time objective is known to be NP-hard for m ≥ 2. The only practical method for finding optimal solutions has been branch-and-bound algorithms. In...The general m-machine permutation flowshop problem with the total flow-time objective is known to be NP-hard for m ≥ 2. The only practical method for finding optimal solutions has been branch-and-bound algorithms. In this paper, we present an improved sequential algorithm which is based on a strict alternation of Generation and Exploration execution modes as well as Depth-First/Best-First hybrid strategies. The experimental results show that the proposed scheme exhibits improved performance compared with the algorithm in [1]. More importantly, our method can be easily extended and implemented with lightweight threads to speed up the execution times. Good speedups can be obtained on shared-memory multicore systems.展开更多
A discrete differential evolution algorithm combined with the branch and bound method is developed to solve the integer linear bilevel programming problems, in which both upper level and lower level variables are forc...A discrete differential evolution algorithm combined with the branch and bound method is developed to solve the integer linear bilevel programming problems, in which both upper level and lower level variables are forced to be integer. An integer coding for upper level variables is adopted, and then a discrete differential evolution algorithm with an improved feasibility-based comparison is developed to directly explore the integer solution at the upper level. For a given upper level integer variable, the lower level integer programming problem is solved by the existing branch and bound algorithm to obtain the optimal integer solution at the lower level. In the same framework of the algorithm, two other constraint handling methods, i.e. the penalty function method and the feasibility-based comparison method are also tested. The experimental results demonstrate that the discrete differential evolution algorithm with different constraint handling methods is effective in finding the global optimal integer solutions, but the improved constraint handling method performs better than two compared constraint handling methods.展开更多
The West China University of MedicalSciences (WCUMS),founded in 1910 and form-erly named West China Union University,wasdesignated as a branch of CAMS in a ceremonyheld on the 29th of November,1989.WCUMS.one of the ke...The West China University of MedicalSciences (WCUMS),founded in 1910 and form-erly named West China Union University,wasdesignated as a branch of CAMS in a ceremonyheld on the 29th of November,1989.WCUMS.one of the key medical universities directed bythe Ministry of Public Health (MPH),incor-porates eight schools,namely:Schools of BasicMedical Sciences,Medicine,Stomatology,PublicHealth,Pharmacy,Forensic Medicine,ForeignLanguages,and Social Sciences.The Universityoffers 12 special programs on medicine。展开更多
Efficient solvers for optimization problems are based on linear and semidefinite relaxations that use floating point arithmetic. However, due to the rounding errors, relaxation thus may overestimate, or worst, underes...Efficient solvers for optimization problems are based on linear and semidefinite relaxations that use floating point arithmetic. However, due to the rounding errors, relaxation thus may overestimate, or worst, underestimate the very global optima. The purpose of this article is to introduce an efficient and safe procedure to rigorously bound the global optima of semidefinite program. This work shows how, using interval arithmetic, rigorous error bounds for the optimal value can be computed by carefully post processing the output of a semidefinite programming solver. A lower bound is computed on a semidefinite relaxation of the constraint system and the objective function. Numerical results are presented using the SDPA (SemiDefinite Programming Algorithm), solver to compute the solution of semidefinite programs. This rigorous bound is injected in a branch and bound algorithm to solve the optimisation problem.展开更多
线性乘积和规划已出现在工程实践和管理科学等领域,是一类NP-难问题。针对该问题目标函数的特殊结构,将其重构为一个D.C.(difference of convex functions)规划问题。再利用凹函数的凸包络,构造出了一种D.C.松弛问题,并将其分解为两个...线性乘积和规划已出现在工程实践和管理科学等领域,是一类NP-难问题。针对该问题目标函数的特殊结构,将其重构为一个D.C.(difference of convex functions)规划问题。再利用凹函数的凸包络,构造出了一种D.C.松弛问题,并将其分解为两个凸子问题。然后将该D.C.松弛与超矩形的标准二分法相结合,设计了新的分支定界算法,并分析了其理论收敛性和计算复杂度。最后,借助大量数值实验验证了该算法的有效性。展开更多
基金Supported by the National Natural Science Foundation of China(Grant Nos.12571317 and 12071133).
文摘In this paper,we study a class of Linear Fractional Programming on a nonempty bounded set,called the Problem(LFP),and design a branch and bound algorithm to find the global optimal solution of the problem(LFP).First,we convert the problem(LFP)to the equivalent problem(EP2).Secondly,by applying the linear relaxation technique to the problem(EP2),the linear relaxation programming problem(LRP2Y)was obtained.Then,the overall framework of the algorithm is given,and the convergence and complexity of the algorithm are analyzed.Finally,experimental results are listed to illustrate the effectiveness of the algorithm.
基金Project(2006CB705507) supported by the National Basic Research and Development Program of ChinaProject(20060533036) supported by the Specialized Research Foundation for the Doctoral Program of Higher Education of China
文摘Considering the decision-making variables of the capacities of branch roads and the optimization targets of lowering the saturation of arterial roads and the reconstruction expense of branch roads, the bi-level programming model for reconstructing the branch roads was set up. The upper level model was for determining the enlarged capacities of the branch roads, and the lower level model was for calculating the flows of road sections via the user equilibrium traffic assignment method. The genetic algorithm for solving the bi-level model was designed to obtain the reconstruction capacities of the branch roads. The results show that by the bi-level model and its algorithm, the optimum scheme of urban branch roads reconstruction can be gained, which reduces the saturation of arterial roads apparently, and alleviates traffic congestion. In the data analysis the arterial saturation decreases from 1.100 to 0.996, which verifies the micro-circulation transportation's function of urban branch road network.
基金Supported by the National Natural Science Foundation of China(11501233)the Natural Science Research Project of Universities of Anhui Province(KJ2018A0390)
文摘Most real-world optimization problems are hierarchical involving non-cooperative objectives. Many of these problems can be formulated in terms of the first（upper level） objective function being minimized over the solution set mapping of the second（lower level） optimization problem. Often the upper level decision maker is risk-averse. The resulting class of problem is named weak bilevel programming problem. This paper presents a new algorithm which embeds a penalty function method into a branch and bound algorithm to deal with a weak linear bilevel programming problem. An example illustrates the feasibility of the proposed algorithm.
基金Supported by the National Natural Science Foundation of China(Grant Nos.12071133 and 11871196).
文摘In this paper,we study the minimax linear fractional programming problem on a non-empty bounded set,called problem(MLFP),and we design a branch and bound algorithm to find a globally optimal solution of(MLFP).Firstly,we convert the problem(MLFP)to a problem(EP2)that is equivalent to it.Secondly,by applying the convex relaxation technique to problem(EP2),a convex quadratic relaxation problem(CQRP)is obtained.Then,the overall framework of the algorithm is given and its convergence is proved,the worst-case iteration number is also estimated.Finally,experimental data are listed to illustrate the effectiveness of the algorithm.
文摘The general m-machine permutation flowshop problem with the total flow-time objective is known to be NP-hard for m ≥ 2. The only practical method for finding optimal solutions has been branch-and-bound algorithms. In this paper, we present an improved sequential algorithm which is based on a strict alternation of Generation and Exploration execution modes as well as Depth-First/Best-First hybrid strategies. The experimental results show that the proposed scheme exhibits improved performance compared with the algorithm in [1]. More importantly, our method can be easily extended and implemented with lightweight threads to speed up the execution times. Good speedups can be obtained on shared-memory multicore systems.
基金supported by the Natural Science Basic Research Plan in Shaanxi Province of China(2013JM1022)the Fundamental Research Funds for the Central Universities(K50511700004)
文摘A discrete differential evolution algorithm combined with the branch and bound method is developed to solve the integer linear bilevel programming problems, in which both upper level and lower level variables are forced to be integer. An integer coding for upper level variables is adopted, and then a discrete differential evolution algorithm with an improved feasibility-based comparison is developed to directly explore the integer solution at the upper level. For a given upper level integer variable, the lower level integer programming problem is solved by the existing branch and bound algorithm to obtain the optimal integer solution at the lower level. In the same framework of the algorithm, two other constraint handling methods, i.e. the penalty function method and the feasibility-based comparison method are also tested. The experimental results demonstrate that the discrete differential evolution algorithm with different constraint handling methods is effective in finding the global optimal integer solutions, but the improved constraint handling method performs better than two compared constraint handling methods.
文摘The West China University of MedicalSciences (WCUMS),founded in 1910 and form-erly named West China Union University,wasdesignated as a branch of CAMS in a ceremonyheld on the 29th of November,1989.WCUMS.one of the key medical universities directed bythe Ministry of Public Health (MPH),incor-porates eight schools,namely:Schools of BasicMedical Sciences,Medicine,Stomatology,PublicHealth,Pharmacy,Forensic Medicine,ForeignLanguages,and Social Sciences.The Universityoffers 12 special programs on medicine。
文摘Efficient solvers for optimization problems are based on linear and semidefinite relaxations that use floating point arithmetic. However, due to the rounding errors, relaxation thus may overestimate, or worst, underestimate the very global optima. The purpose of this article is to introduce an efficient and safe procedure to rigorously bound the global optima of semidefinite program. This work shows how, using interval arithmetic, rigorous error bounds for the optimal value can be computed by carefully post processing the output of a semidefinite programming solver. A lower bound is computed on a semidefinite relaxation of the constraint system and the objective function. Numerical results are presented using the SDPA (SemiDefinite Programming Algorithm), solver to compute the solution of semidefinite programs. This rigorous bound is injected in a branch and bound algorithm to solve the optimisation problem.
文摘线性乘积和规划已出现在工程实践和管理科学等领域,是一类NP-难问题。针对该问题目标函数的特殊结构,将其重构为一个D.C.(difference of convex functions)规划问题。再利用凹函数的凸包络,构造出了一种D.C.松弛问题,并将其分解为两个凸子问题。然后将该D.C.松弛与超矩形的标准二分法相结合,设计了新的分支定界算法,并分析了其理论收敛性和计算复杂度。最后,借助大量数值实验验证了该算法的有效性。
