This paper presents an efficient algorithm for globally solving a generalized linear fractional programming problem.For establishing this algorithm,we firstly construct a two-level linear relaxation method,and by util...This paper presents an efficient algorithm for globally solving a generalized linear fractional programming problem.For establishing this algorithm,we firstly construct a two-level linear relaxation method,and by utilizing the method,we can convert the initial generalized linear fractional programming problem and its subproblems into a series of linear programming relaxation problems.Based on the branch-and-bound framework and linear programming relaxation problems,a branch-and-bound algorithm is presented for globally solving the generalized linear fractional programming problem,and the computational complexity of the algorithm is given.Finally,numerical experimental results demonstrate the feasibility and efficiency of the proposed algorithm.展开更多
The scheduling of gasoline-blending operations is an important problem in the oil refining industry. Thisproblem not only exhibits the combinatorial nature that is intrinsic to scheduling problems, but alsonon-convex ...The scheduling of gasoline-blending operations is an important problem in the oil refining industry. Thisproblem not only exhibits the combinatorial nature that is intrinsic to scheduling problems, but alsonon-convex nonlinear behavior, due to the blending of various materials with different quality properties.In this work, a global optimization algorithm is proposed to solve a previously published continuous-timemixed-integer nonlinear scheduling model for gasoline blending. The model includes blend recipe optimi-zation, the distribution problem, and several important operational features and constraints. The algorithmemploys piecewise McCormick relaxation （PMCR） and normalized multiparametric disaggregation tech-nique （NMDT） to compute estimates of the global optimum. These techniques partition the domain of oneof the variables in a bilinear term and generate convex relaxations for each partition. By increasing the num-ber of partitions and reducing the domain of the variables, the algorithm is able to refine the estimates ofthe global solution. The algorithm is compared to two commercial global solvers and two heuristic methodsby solving four examples from the literature. Results show that the proposed global optimization algorithmperforms on par with commercial solvers but is not as fast as heuristic approaches.展开更多
In this paper,we consider the metric uncapacitated facility location game with service installation costs. Our main result is an 11-approximate cross-monotonic cost-sharing method under the assumption that the install...In this paper,we consider the metric uncapacitated facility location game with service installation costs. Our main result is an 11-approximate cross-monotonic cost-sharing method under the assumption that the installation cost depends only on the service type.展开更多
基金the National Natural Science Foundation of China(Nos.11871196,12071133 and 12071112)the China Postdoctoral Science Foundation(No.2017M622340)+1 种基金the Key Scientific and Technological Research Projects of Henan Province(Nos.202102210147 and 192102210114)the Science and Technology Climbing Program of Henan Institute of Science and Technology(No.2018JY01).
文摘This paper presents an efficient algorithm for globally solving a generalized linear fractional programming problem.For establishing this algorithm,we firstly construct a two-level linear relaxation method,and by utilizing the method,we can convert the initial generalized linear fractional programming problem and its subproblems into a series of linear programming relaxation problems.Based on the branch-and-bound framework and linear programming relaxation problems,a branch-and-bound algorithm is presented for globally solving the generalized linear fractional programming problem,and the computational complexity of the algorithm is given.Finally,numerical experimental results demonstrate the feasibility and efficiency of the proposed algorithm.
基金Support by Ontario Research FoundationMc Master Advanced Control ConsortiumFundacao para a Ciência e Tecnologia(Investigador FCT 2013 program and project UID/MAT/04561/2013)
文摘The scheduling of gasoline-blending operations is an important problem in the oil refining industry. Thisproblem not only exhibits the combinatorial nature that is intrinsic to scheduling problems, but alsonon-convex nonlinear behavior, due to the blending of various materials with different quality properties.In this work, a global optimization algorithm is proposed to solve a previously published continuous-timemixed-integer nonlinear scheduling model for gasoline blending. The model includes blend recipe optimi-zation, the distribution problem, and several important operational features and constraints. The algorithmemploys piecewise McCormick relaxation （PMCR） and normalized multiparametric disaggregation tech-nique （NMDT） to compute estimates of the global optimum. These techniques partition the domain of oneof the variables in a bilinear term and generate convex relaxations for each partition. By increasing the num-ber of partitions and reducing the domain of the variables, the algorithm is able to refine the estimates ofthe global solution. The algorithm is compared to two commercial global solvers and two heuristic methodsby solving four examples from the literature. Results show that the proposed global optimization algorithmperforms on par with commercial solvers but is not as fast as heuristic approaches.
基金supported by National Natural Science Foundation of China (Grant Nos. 60773185, 10401038)Program for Beijing Excellent Talents (Grant No. 20071D050150020S)
文摘In this paper,we consider the metric uncapacitated facility location game with service installation costs. Our main result is an 11-approximate cross-monotonic cost-sharing method under the assumption that the installation cost depends only on the service type.
