共查询到20条相似文献,搜索用时 15 毫秒
1.
Global Optimization Techniques for Solving the General Quadratic Integer Programming Problem 总被引:3,自引:0,他引:3
Nguyen Van Thoai 《Computational Optimization and Applications》1998,10(2):149-163
We consider the problem of minimizing a general quadratic function over a polytope in the n-dimensional space with integrality restrictions on all of the variables. (This class of problems contains, e.g., the quadratic 0-1 program as a special case.) A finite branch and bound algorithm is established, in which the branching procedure is the so-called integral rectangular partition, and the bound estimation is performed by solving a concave programming problem with a special structure. Three methods for solving this special concave program are proposed. 相似文献
2.
The problem Q of optimizing a linear function over the efficient set of a multiple objective linear program serves several useful purposes in multiple criteria decision making. However, Q is in itself a difficult global optimization problem, whose local optima, frequently large in number, need not be globally optimal. Indeed, this is due to the fact that the feasible region of Q is, in general, a nonconvex set. In this paper we present a monotonically increasing algorithm that finds an exact, globally-optimal solution for Q. Our approach does not require any hypothesis on the boundedness of neither the efficient set EP nor the optimal objective value. The proposed algorithm relies on a simplified disjoint bilinear program that can be solved through the use of well-known specifically designed methods within nonconvex optimization. The algorithm has been implemented in C and preliminary numerical results are reported. 相似文献
3.
H. P. Benson 《Journal of Optimization Theory and Applications》2008,137(1):105-120
This article presents a branch-and-bound algorithm for globally solving the problem (P) of maximizing a generalized concave
multiplicative function over a compact convex set. Since problem (P) does not seem to have been studied previously, the algorithm
is apparently the first algorithm to be proposed for solving this problem. It works by globally solving a problem (P1) equivalent
to problem (P). The branch-and-bound search undertaken by the algorithm uses rectangular partitioning and takes place in a
space which typically has a much smaller dimension than the space to which the decision variables of problem (P) belong. Convergence
of the algorithm is shown; computational considerations and benefits for users of the algorithm are given. A sample problem
is also solved. 相似文献
4.
5.
针对一类多乘积规划问题(MP),给出一个加速算法.首先导出一个与(MP)等价的逆凸问题(RCP),然后构造问题(RCP)的线性松弛化问题.算法的主要特点是提出了两个加速技巧,这些技巧可以用于改善算法的收敛速度.数值算例表明算法是可行的. 相似文献
6.
Harold P. Benson 《Journal of Global Optimization》1999,15(4):315-342
This article presents a new global solution algorithm for Convex Multiplicative Programming called the Outcome Space Algorithm. To solve a given convex multiplicative program (PD), the algorithm solves instead an equivalent quasiconcave minimization problem in the outcome space of the original problem. To help accomplish this, the algorithm uses branching, bounding and outer approximation by polytopes, all in the outcome space of problem (PD). The algorithm economizes the computations that it requires by working in the outcome space, by avoiding the need to compute new vertices in the outer approximation process, and, except for one convex program per iteration, by requiring for its execution only linear programming techniques and simple algebra. 相似文献
7.
首先将一个具有多个约束的规划问题转化为一个只有一个约束的规划问题,然后通过利用这个单约束的规划问题,对原来的多约束规划问题提出了一些凸化、凹化的方法,这样这些多约束的规划问题可以被转化为一些凹规划、反凸规划问题.最后,还证明了得到的凹规划和反凸规划的全局最优解就是原问题的近似全局最优解. 相似文献
8.
This article presents an outcome-space pure cutting-plane algorithm for globally solving the linear multiplicative programming problem. The framework of the algorithm is taken from a pure cutting-plane decision set-based method developed by Horst and Tuy for solving concave minimization problems. By adapting this method to an outcome-space reformulation of the linear multiplicative programming problem, rather than applying directly the method to the original decision-set formulation, it is expected that considerable computational savings can be obtained. Also, we show how additional computational benefits might be obtained by implementing the new algorithm appropriately. To illustrate the new algorithm, we apply it to the solution of a sample problem. 相似文献
9.
We present a new method for minimizing the sum of a convex function and aproduct of k nonnegative convex functions over a convex set. This problem isreduced to a k-dimensional quasiconcave minimization problem which is solvedby a conical branch-and-bound algorithm. Comparative computational results areprovided on test problems from the literature. 相似文献
10.
Takahito Kuno 《Computational Optimization and Applications》2001,20(2):119-135
On the basis of Soland's rectangular branch-and-bound, we develop an algorithm for minimizing a product of p (2) affine functions over a polytope. To tighten the lower bound on the value of each subproblem, we install a second-stage bounding procedure, which requires O(p) additional time in each iteration but remarkably reduces the number of branching operations. Computational results indicate that the algorithm is practical if p is less than 15, both in finding an exact optimal solution and an approximate solution. 相似文献
11.
Walter Murray 《Computational Optimization and Applications》1997,7(1):127-142
Sequential quadratic (SQP) programming methodsare the method of choice when solving small or medium-sized problems. Sincethey are complex methods they are difficult (but not impossible) to adapt tosolve large-scale problems. We start by discussing the difficulties that needto be addressed and then describe some general ideas that may be used toresolve these difficulties. A number of SQP codes have been written to solve specific applications and there is a general purposed SQP code called SNOPT,which is intended for general applications of a particular type. These aredescribed briefly together with the ideas on which they are based. Finally wediscuss new work on developing SQP methods using explicit second derivatives. 相似文献
12.
A Branch and Bound Algorithm for Solving Low Rank Linear Multiplicative and Fractional Programming Problems 总被引:6,自引:0,他引:6
This paper is concerned with a practical algorithm for solving low rank linear multiplicative programming problems and low rank linear fractional programming problems. The former is the minimization of the sum of the product of two linear functions while the latter is the minimization of the sum of linear fractional functions over a polytope. Both of these problems are nonconvex minimization problems with a lot of practical applications. We will show that these problems can be solved in an efficient manner by adapting a branch and bound algorithm proposed by Androulakis–Maranas–Floudas for nonconvex problems containing products of two variables. Computational experiments show that this algorithm performs much better than other reported algorithms for these class of problems. 相似文献
13.
In this paper, we will propose an efficient heuristic algorithm for solving concave quadratic programming problems whose rank of the objective function is relatively small. This algorithm is a combination of Tuy's cutting plane to eliminate the feasible region and a kind of tabu-search method to find a good vertex. We first generate a set of V of vertices and select one of these vertices as a starting point at each step, and apply tabu-search and Tuy's cutting plane algorithm where the list of tabu consists of those vertices eliminated by cutting planes and those newly generated vertices by cutting planes. When all vertices of the set V are eliminated, the algorithm is terminated. This algorithm need not converge to a global minimum, but it can work very well when the rank is relatively small (up to seven). The incumbent solutions are in fact globally optimal for all tested problems. We also propose an alternative algorithm by incorporating Rosen's hyperrectangle cut. This algorithm is more efficient than the combination of Tuy's cutting plane and tabu-search. 相似文献
14.
Various difficulties have been encountered in using decision set-based vector maximization methods to solve a multiple-objective linear programming problem (MOLP). Motivated by these difficulties, Benson recently developed a finite, outer-approximation algorithm for generating the set of all efficient extreme points in the outcome set, rather than in the decision set, of problem (MOLP). In this article, we show that the Benson algorithm also generates the set of all weakly efficient points in the outcome set of problem (MOLP). As a result, the usefulness of the algorithm as a decision aid in multiple objective linear programming is further enhanced. 相似文献
15.
We are concerned with concave programming or the convex maximization problem. In this paper, we propose a method and algorithm
for solving the problem which are based on the global optimality conditions first obtained by Strekalovsky (Soviet Mathematical
Doklady, 8(1987)). The method continues approaches given in (Journal of global optimization, 8(1996); Journal of Nolinear
and convex Analyses 4(1)(2003)). Under certain assumptions a convergence property of the proposed method has been established.
Some computational results are reported. Also, it has been shown that the problem of finding the largest eigenvalue can be
found by the proposed method. 相似文献
16.
基于粒子群算法的非线性二层规划问题的求解算法 总被引:3,自引:0,他引:3
粒子群算法(Particle Swarm Optimization,PSO)是一种新兴的优化技术,其思想来源于人工生命和演化计算理论。PSO通过粒子追随自己找到的最好解和整个群的最好解来完成优化。该算法简单易实现,可调参数少,已得到了广泛研究和应用。本文根据该算法能够有效的求出非凸数学规划全局最优解的特点,对非线性二层规划的上下层问题求解,并根据二层规划的特点,给出了求解非线性二层规划问题全局最优解的有效算法。数值计算结果表明该算法有效。 相似文献
17.
The problem of estimating the global optimal values of intractable combinatorial optimization problems is of interest to researchers developing and evaluating heuristics for these problems. In this paper we present a method for combining statistical optimum prediction techniques with local search methods such as simulated annealing and tabu search and illustrate the approach on a single machine scheduling problem. Computational experiments show that the approach yields useful estimates of optimal values with very reasonable computational effort. 相似文献
18.
19.
We develop a branch-and-bound algorithm to solve a nonlinear class of 0–1 knapsack problems. The objective function is a product of m2 affine functions, whose variables are mutually exclusive. The branching procedure in the proposed algorithm is the usual one, but the bounding procedure exploits the special structure of the problem and is implemented through two stages: the first stage is based on linear programming relaxation; the second stage is based on Lagrangian relaxation. Computational results indicate that the algorithm is promising. 相似文献