排序方式: 共有6条查询结果,搜索用时 15 毫秒
1
1.
In this paper, we point out a theoretical flaw in Kuno [(2002)Journal of Global Optimization 22, 155–174] which deals with the linear sum-of-ratios problem, and show that the proposed branch-and-bound algorithm works
correctly despite the flaw. We also note a relationship between a single ratio and the overestimator used in the bounding
operation, and develop a procedure for tightening the upper bound on the optimal value. The procedure is not expensive, but
the revised algorithms incorporating it improve significantly in efficiency. This is confirmed by numerical comparisons between
the original and revised algorithms.
The author was partially supported by the Grand-in-Aid for Scientific Research (C)(2) 15560048 from the Japan Society for
the Promotion of Science. 相似文献
2.
Paat Rusmevichientong Zuo-Jun Max Shen David B. Shmoys 《Operations Research Letters》2009,37(4):230-238
Motivated by an application in assortment planning under the nested logit choice model, we develop a polynomial-time approximation scheme for the sum-of-ratios optimization problem with a capacity constraint and a fixed number of product groups. 相似文献
3.
This paper presents an efficient branch and bound algorithm for globally solving sum of geometric fractional functions under geometric constraints, which arise in various practical problems. By using an equivalent transformation and a new linear relaxation technique, a linear relaxation programming problem of the equivalent problem is obtained. The proposed algorithm is convergent to the global optimal solution by means of the subsequent solutions of a series of linear programming problems. Numerical results are reported to show the feasibility of our algorithm. 相似文献
4.
In spite of the recent progress in fractional programming, the sum-of-ratios problem remains untoward. Freund and Jarre proved
that this is an NP-complete problem. Most methods overcome the difficulty using the deterministic type of algorithms, particularly,
the branch-and-bound method. In this paper, we propose a new approach by applying the stochastic search algorithm introduced
by Birbil, Fang and Sheu to a transformed image space. The algorithm then computes and moves sample particles in the q − 1 dimensional image space according to randomly controlled interacting electromagnetic forces. Numerical experiments on
problems up to sum of eight linear ratios with a thousand variables are reported. The results also show that solving the sum-of-ratios
problem in the image space as proposed is, in general, preferable to solving it directly in the primal domain. 相似文献
5.
In this article, we present and validate a simplicial branch and bound duality-bounds algorithm for globally solving the linear sum-of-ratios fractional program. The algorithm computes the lower bounds called for during the branch and bound search by solving ordinary linear programming problems. These problems are derived by using Lagrangian duality theory. The algorithm applies to a wide class of linear sum-of-ratios fractional programs. Two sample problems are solved, and the potential practical and computational advantages of the algorithm are indicated. 相似文献
6.
Majid Jaberipour Esmaile Khorram 《Journal of Computational and Applied Mathematics》2010,234(3):733-2578
The sum-of-ratios problems have numerous applications in economy and engineering. The sum-of-ratios problems are considered to be difficult, as these functions are highly nonconvex and multimodal. In this study, we propose a harmony search algorithm for solving a sum-of-ratios problem. Numerical examples are also presented to demonstrate the effectiveness and robustness of the proposed method. In all cases, the solutions obtained using this method are superior to those obtained from other methods. 相似文献
1