共查询到19条相似文献,搜索用时 312 毫秒
1.
2.
提出了求解一类线性乘积规划问题的分支定界缩减方法, 并证明了算法的收敛性.在这个方法中, 利用两个变量乘积的凸包络技术, 给出了目标函数与约束函数中乘积的下界, 由此确定原问题的一个松弛凸规划, 从而找到原问题全局最优值的下界和可行解. 为了加快所提算法的收敛速度, 使用了超矩形的缩减策略. 数值结果表明所提出的算法是可行的. 相似文献
3.
本文旨在针对线性比式和规划这一NP-Hard非线性规划问题提出新的全局优化算法.首先,通过引入p个辅助变量把原问题等价的转化为一个非线性规划问题,这个非线性规划问题的目标函数是乘积和的形式并给原问题增加了p个新的非线性约束,再通过构造凸凹包络的技巧对等价问题的目标函数和约束条件进行相应的线性放缩,构成等价问题的一个下界线性松弛规划问题,从而提出了一个求解原问题的分支定界算法,并证明了算法的收敛性.最后,通过数值结果比较表明所提出的算法是可行有效的. 相似文献
4.
在求解大规模NP-困难的最优化问题方法中,列生成技术越来越受到重视.本文研究工件带有与加工次序有关的安装时间的单机排序问题,首先构造它的时间标号模型,结合D-W分解技术和分支定界方法,给出它的列生成算法.其中时间标号模型的线性松弛为原问题提供了很好的下界,然后提出一个近似算法.通过实验数据表明,我们的算法对中等规模的排序问题1|t_(ij),r_j|∑w_jC_j是有效的. 相似文献
5.
本文研究了带有释放时间的单机双代理调度问题,目标函数为极小化最大完工时间和。为了便于利用优化软件求解,建立了混合整数规划模型。考虑到该问题具有NP困难性,因此采用近似与精确算法分别求解不同规模问题。针对大规模问题,提出了优势代理优先启发式算法,并证明了其渐近最优性。针对小规模问题,设计了分支定界法进行最优求解,其中基于释放时间的分支规则和基于加工中断的下界有效地减少了运算时间。最后,通过数值测试验证了分支定界算法的有效性以及启发式算法的收敛性。 相似文献
6.
研究带有准备时间的单机学习效应模型,其中工件加工时间具有指数时间学习效应,即工件的实际加工时间是已经排好的工件加工时间的指数函数。学习效应模型考虑工件的实际加工时间同时依赖于工件本身的加工时间和已加工工件的累计加工时间,目标函数为最小化总完工时间。这个问题是NP-难的,提出了一个数学规划模型来求解该问题的最优解。通过分析几个优势性质和下界,提出分支定界算法来求解此问题,并设计启发式算法改进分支定界算法的上界值。通过仿真实验验证了分支定界算法在求解质量和时间方面的有效性。 相似文献
7.
8.
本文给出确定线性约束0-1二次规划问题最优值下界的方法,该方法结合McBride和Yormark的思想和总体优化中定下界的方法,证明了所定的界较McBride和Yormark的要好.求解线性约束0-1二次规划问题的分支定界算法可以利用本文的定界技术. 相似文献
9.
本文给出混合0-1线性规划问题的一个代理约束定界方法,利用代理约束构造一个定界函数,计算量较小,并提出一个分支定界算法,数值计算表明算法是有效的. 相似文献
10.
11.
Hong-Xuan Huang Panos M. Pardalos Oleg A. Prokopyev 《Computational Optimization and Applications》2006,33(2-3):187-208
In this paper several equivalent formulations for the quadratic binary programming problem are presented. Based on these formulations
we describe four different kinds of strategies for estimating lower bounds of the objective function, which can be integrated
into a branch and bound algorithm for solving the quadratic binary programming problem. We also give a theoretical explanation
for forcing rules used to branch the variables efficiently, and explore several properties related to obtained subproblems.
From the viewpoint of the number of subproblems solved, new strategies for estimating lower bounds are better than those used
before. A variant of a depth-first branch and bound algorithm is described and its numerical performance is presented. 相似文献
12.
13.
In this paper we consider the optimization of a quadratic function subject to a linearly bounded mixed integer constraint set. We develop two types of piecewise affine convex underestimating functions for the objective function. These are used in a branch and bound algorithm for solving the original problem. We show finite convergence to a near optimal solution for this algorithm. We illustrate the algorithm with a small numerical example. Finally we discuss some modifications of the algorithm and address the question of extending the problem to include quadratic constraints.Supported by grants from the Danish Natural Science Research Council and the Danish Research Academy. 相似文献
14.
J. R. WillemsA. V. Cabot 《Mathematical and Computer Modelling》1995,21(12):75-84
In this paper, we present a branch and bound algorithm for solving the constrained entropy mathematical programming problem. Unlike other methods for solving this problem, our method solves more general problems with inequality constraints. The advantage of the proposed technique is that the relaxed problem solved at each node is a singly constrained network problem. The disadvantage is that the relaxed problem has twice as many variables as the original problem. An application to regional planning is given, and an example problem is solved. 相似文献
15.
Harold P. Benson 《Journal of Global Optimization》2002,22(1-4):343-364
This article presents a branch and bound algorithm for globally solving the nonlinear sum of ratios problem (P). The algorithm works by globally solving a sum of ratios problem that is equivalent to problem (P). In the algorithm, upper bounds are computed by maximizing concave envelopes of a sum of ratios function over intersections of the feasible region of the equivalent problem with rectangular sets. The rectangular sets are systematically subdivided as the branch and bound search proceeds. Two versions of the algorithm, with convergence results, are presented. Computational advantages of these algorithms are indicated, and some computational results are given that were obtained by globally solving some sample problems with one of these algorithms. 相似文献
16.
《European Journal of Operational Research》1999,116(3):667-680
A stratified random sampling plan is one in which the elements of the population are first divided into nonoverlapping groups, and then a simple random sample is selected from each group. In this paper, we focus on determining the optimal sample size of each group. We show that various versions of this problem can be transformed into a particular nonlinear program with a convex objective function, a single linear constraint, and bounded variables. Two branch and bound algorithms are presented for solving the problem. The first algorithm solves the transformed subproblems in the branch and bound tree using a variable pegging procedure. The second algorithm solves the subproblems by performing a search to identify the optimal Lagrange multiplier of the single constraint. We also present linearization and dynamic programming methods that can be used for solving the stratified sampling problem. Computational testing indicates that the pegging branch and bound algorithm is fastest for some classes of problems, and the linearization method is fastest for other classes of problems. 相似文献
17.
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. 相似文献
18.
Gregory P. White 《European Journal of Operational Research》1982,9(2):190-193
In [2] Gavish and Shlifer present an algorithm for solving a class of transportation scheduling problems which includes the delivery problem, the school bus problem, and others. Their algorithm is based on the ‘savings method’ of Clarke and Wright. By solving a sequence of assignment problems, upper bounds may be generated for the original problem and the optimal solution determined through a branch and bound procedure. However, for certain problems the CPU time becomes excessive. In this paper we show that the bounds may be improved by solving a related maximum matching problem instead of the assignment problem. The result is that fewer branches need to be investigated. Computational results are presented indicating that considerably less CPU time is needed to solve problems using this approach than with the approach of Gavish and Shlifer. 相似文献
19.
Marshall L. Fisher 《Mathematical Programming》1976,11(1):229-251
A branch and bound algorithm is presented for the problem of schedulingn jobs on a single machine to minimize tardiness. The algorithm uses a dual problem to obtain a good feasible solution and an extremely sharp lower bound on the optimal objective value. To derive the dual problem we regard the single machine as imposing a constraint for each time period. A dual variable is associated with each of these constraints and used to form a Lagrangian problem in which the dualized constraints appear in the objective function. A lower bound is obtained by solving the Lagrangian problem with fixed multiplier values. The major theoretical result of the paper is an algorithm which solves the Lagrangian problem in a number of steps proportional to the product ofn 2 and the average job processing time. The search for multiplier values which maximize the lower bound leads to the formulation and optimization of the dual problem. The bounds obtained are so sharp that very little enumeration or computer time is required to solve even large problems. Computational experience with 20-, 30-, and 50-job problems is presented. 相似文献