共查询到20条相似文献,搜索用时 0 毫秒
1.
Researchers first examined the problem of separable concave programming more than thirty years ago, making it one of the earliest branches of nonlinear programming to be explored. This paper proposes a new algorithm that finds the exact global minimum of this problem in a finite number of iterations. In addition to proving that our algorithm terminates finitely, the paper extends a guarantee of finiteness to all branch-and-bound algorithms for concave programming that (1) partition exhaustively using rectangular subdivisions and (2) branch on the incumbent solution when possible. The algorithm uses domain reduction techniques to accelerate convergence; it solves problems with as many as 100 nonlinear variables, 400 linear variables and 50 constraints in about five minutes on an IBM RS/6000 Power PC. An industrial application with 152 nonlinear variables, 593 linear variables, and 417 constraints is also solved in about ten minutes. 相似文献
2.
Hong-gangXue Cheng-xianXu Feng-minXu 《计算数学(英文版)》2004,22(6):895-904
In this paper, we propose a new branch and bound algorithm for the solution of large scale separable concave programming problems. The largest distance bisection (LDB) technique is proposed to divide rectangle into sub-rectangles when one problem is branched into two subproblems. It is proved that the LDB method is a normal rectangle subdivision(NRS). Numerical tests on problems with dimensions from 100 to 10000 show that the proposed branch and bound algorithm is efficient for solving large scale separable concave programming problems, and convergence rate is faster than ω-subdivision method. 相似文献
3.
Christophe Meyer 《Journal of Global Optimization》2000,18(4):357-365
In 1964, in a seminal paper, Tuy proposed a simple algorithm for concave minimization over a polytope. This algorithm was shown to cycle some years later. Recently however it has been shown that despite this possibility of cycling, Tuy's algorithm always finds the optimal solution of the problem. We present a modification of it which simplifies the cycle detection. 相似文献
4.
Marcus Porembski 《Journal of Global Optimization》2002,24(1):89-107
In this paper we are concerned with pure cutting plane algorithms for concave minimization. One of the most common types of cutting planes for performing the cutting operation in such algorithm is the concavity cut. However, it is still unknown whether the finite convergence of a cutting plane algorithm can be enforced by the concavity cut itself or not. Furthermore, computational experiments have shown that concavity cuts tend to become shallower with increasing iteration. To overcome these problems we recently proposed a procedure, called cone adaptation, which deepens concavity cuts in such a way that the resulting cuts have at least a certain depth with 0, where is independent of the respective iteration, which enforces the finite convergence of the cutting plane algorithm. However, a crucial element of our proof that these cuts have a depth of at least was that we had to confine ourselves to -global optimal solutions, where is a prescribed strictly positive constant. In this paper we examine possible ways to ensure the finite convergence of a pure cutting plane algorithm for the case where = 0. 相似文献
5.
A general class of branch and bound algorithms forsolving a wide class of nonlinear programs with branching only in asubset of the problem variables is presented. By reducing the dimension of thesearch space, this technique may dramatically reduce the number ofiterations and time required for convergence to tolerancewhile retaining proven exact convergence in the infinite limit. Thispresentation includes specifications of the class of nonlinearprograms, a statement of a class of branch and bound algorithms, aconvergence proof, and motivating examples with results. 相似文献
6.
Juan F. R. Herrera José M. G. Salmerón Eligius M. T. Hendrix Rafael Asenjo Leocadio G. Casado 《Journal of Global Optimization》2017,69(3):547-560
Branch and Bound (B&B) algorithms are known to exhibit an irregularity of the search tree. Therefore, developing a parallel approach for this kind of algorithms is a challenge. The efficiency of a B&B algorithm depends on the chosen Branching, Bounding, Selection, Rejection, and Termination rules. The question we investigate is how the chosen platform consisting of programming language, used libraries, or skeletons influences programming effort and algorithm performance. Selection rule and data management structures are usually hidden to programmers for frameworks with a high level of abstraction, as well as the load balancing strategy, when the algorithm is run in parallel. We investigate the question by implementing a multidimensional Global Optimization B&B algorithm with the help of three frameworks with a different level of abstraction (from more to less): Bobpp, Threading Building Blocks (TBB), and a customized Pthread implementation. The following has been found. The Bobpp implementation is easy to code, but exhibits the poorest scalability. On the contrast, the TBB and Pthread implementations scale almost linearly on the used platform. The TBB approach shows a slightly better productivity. 相似文献
7.
O. Barrientos R. Correa P. Reyes A. Valdebenito 《Computational Optimization and Applications》2003,26(2):155-171
A branch and bound algorithm is proposed for solving integer separable concave problems. The method uses Lagrangian duality to obtain lower and upper bounds. We show that the dual program of a separable concave problem is a linear program. Moreover, we identify an excellent candidate to test on each region of the branch and we show an optimality sufficient condition for this candidate. Preliminary computational results are reported. 相似文献
8.
Volker Stix 《Journal of Global Optimization》2003,26(3):261-277
We introduce a very simple but efficient idea for branch and bound (&) algorithms in global optimization (GO). As input for our generic algorithm, we need an upper bound algorithm for the GO maximization problem and a branching rule. The latter reduces the problem into several smaller subproblems of the same type. The new & approach delivers one global optimizer or, if stopped before finished, improved upper and lower bounds for the problem. Its main difference to commonly used & techniques is its ability to approximate the problem from above and from below while traversing the problem tree. It needs no supplementary information about the system optimized and does not consume more time than classical & techniques. Experimental results with the maximum clique problem illustrate the benefit of this new method. 相似文献
9.
10.
11.
In this article, we introduce a global optimization algorithm that integrates the basic idea of interval branch and bound,
and new local sampling strategies along with an efficient data structure. Also included in the algorithm are procedures that
handle constraints. The algorithm is shown to be able to find all the global optimal solutions under mild conditions. It can
be used to solve various optimization problems. The local sampling (even if done stochastically) is used only to speed up
the convergence and does not affect the fact that a complete search is done. Results on several examples of various dimensions
ranging from 1 to 100 are also presented to illustrate numerical performance of the algorithm along with comparison with another
interval method without the new local sampling and several noninterval methods. The new algorithm is seen as the best performer
among those tested for solving multi-dimensional problems. 相似文献
12.
Gilbert Laporte Hélène Mercure Yves Nobert 《The Journal of the Operational Research Society》1992,43(5):469-481
This paper describes a branch and bound algorithm for a general class of asymmetrical vehicle routeing problems. Vehicle routes start and end at a central depot. Visits are made to nodes grouped into clusters: every cluster must receive a minimum number of visits. But not all nodes must be visited: there are specified nodes and non-specified nodes. Vehicle routes are also constrained by capacity and distance restrictions. The problem is formulated as an integer linear program. It is then solved by a branch and bound algorithm which exploits the unimodular structure of the subproblems. Computational results are reported. 相似文献
13.
14.
对一类新的非线性比式和问题(SNR)提出分枝定界算法,该问题的研究还很少.首先,通过两层线性化技术,构造一个松弛线性规划,求解该线性规划问题,得到问题(SNR)最优值的下界.其次,介绍新的下界更新技术,证明所给算法的收敛性.数值试验显示了算法的可行性和有效性 相似文献
15.
GF(q)是q个元的有限域,q是素数的方幂,n是正整数,GF(q~n)为GF(q)的n次扩张.用指数和估计的方法给出了3种情形下幂剩余正规元存在的充分条件,即(1)GF(q~n)中存在元ξ为GF(q)上的幂剩余正规元;(2)GF(q~n)中存在元ξ与ξ~(-1)同时为GF(q)上幂剩余正规元;(3)对GF(q~n)~*中任意给定的非零元a和b,GF(q~n)中存在元ξ与ξ~(-1)同时为GF(q)上d次幂剩余正规元,且满足Tr(ξ)=a,Tr(ξ~(-1))=b. 相似文献
16.
本文提出了一类新的带整数交易手数和凹型交易费用的均值绝对偏差模型(MAD)和极大极小投资组合模型(Minmax),并给出了离散模型的分枝定界算法.我们分别用随机产生的数据和Nasdaq股票市场的真实数据进行了数值实验,数值分析表明在一定的收益水平下均值绝对偏差离散模型风险控制上优于极大极小投资组合离散模型,而计算效率上极大极小投资组合离散模型优于期望绝对偏差离散模型. 相似文献
17.
GF(q)是q个元的有限域,q是素数的方幂,n是正整数,GF(qn)为GF(q)的n次扩张.用指数和估计的方法给出了3种情形下幂剩余正规元存在的充分条件,即(1)GF(qn)中存在元ξ为GF(q)上的幂剩余正规元;(2)GF(qn)中存在元ξ与ξ-1同时为GF(q)上幂剩余正规元;(3)对GF(qn)*中任意给定的非零元a和b,GF(qn)中存在元ξ与ξ-1同时为GF(q)上d次幂剩余正规元,且满足Tr(ξ)=a,Tr(ξ-1)=b. 相似文献
18.
Dimitris Gatzouras Giannopoulos Apostolos Nikolaos Markoulakis 《Discrete and Computational Geometry》2005,34(2):331-349
Let $f_{n-1}(P)$ denote the number of facets of a
polytope $P$ in ${\Bbb R}^n$. We show that there exist 0/1
polytopes $P$ with $$f_{n-1}(P)\geq\left (\frac{cn}{\log^2
n}\right )^{n/2},$$ where $c>0$ is an absolute constant. This
improves earlier work of Barany and Por on a question
of Fukuda and Ziegler. 相似文献
19.
Marcus Porembski 《Journal of Global Optimization》2004,29(2):191-224
In this paper we propose a new partition algorithm for concave minimization. The basic structure of the algorithm resembles that of conical algorithms. However, we make extensive use of the cone decomposition concept and derive decomposition cuts instead of concavity cuts to perform the bounding operation. Decomposition cuts were introduced in the context of pure cutting plane algorithms for concave minimization and has been shown to be superior to concavity cuts in numerical experiments. Thus by using decomposition cuts instead of concavity cuts to perform the bounding operation, unpromising parts of the feasible region can be excluded from further explorations at an earlier stage. The proposed successive partition algorithm finds an -global optimal solution in a finite number of iterations. 相似文献
20.
本文提出了一种求解带二次约束和线性约束的二次规划的分支定界算法.在算法中,我们运用Lipschitz条件来确定目标函数和约束函数的在每个n矩形上的上下界,对于n矩形的分割,我们采用选择n矩形最长边的二分法,同时我们采用了一些矩形删除技术,在不大幅增加计算量的前提下,起到了加速算法收敛的效果.从理论上我们证明了算法的收敛性,同时数值实验表明该算法是有效的. 相似文献