凹整数规划的分枝定界解法

凹整数规划是一类重要的非线性整数规划问题，也是在经济和管理中有着广泛应用的最优化问题．本文主要研究用分枝定界方法求解凹整数规划问题，这一方法的基本思想是对目标函数进行线性下逼近，然后用乘子搜索法求解连续松弛问题．数值结果表明，用这种分枝定界方法求解凹整数规划是有效的．     

不可分离凸背包问题的拉格朗日分解和区域分割方法

本文对线性约束不可分离凸背包问题给出了一种精确算法．该算法是拉格朗日分解和区域分割结合起来的一种分枝定界算法．利用拉格朗日分解方法可以得到每个子问题的一个可行解，一个不可行解，一个下界和一个上界．区域分割可以把一个整数箱子分割成几个互不相交的整数子箱子的并集，每个整数子箱子对应一个子问题．通过区域分割可以逐步减小对偶间隙并最终经过有限步迭代找到原问题的最优解．数值结果表明该算法对不可分离凸背包问题是有效的．     

A New Successive Partition Algorithm for Concave Minimization Based on Cone Decomposition and Decomposition Cuts

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.     

多约束非线性整数规划的一种改进的算法

多约束非线性整数规划是一类非常重要的问题,非线性背包问题是它的一类特殊而重要的问题.定义在有限整数集上极大化一个可分离非线性函数的多约束最优化问题.这类问题常常用于资源分配、工业生产及计算机网络的最优化模型中,运用一种新的割平面法来求解对偶问题以得到上界,不仅减少了对偶间隙,而且保证了算法的收敛性.利用区域割丢掉某些整数箱子,并把剩下的区域划分为一些整数箱子的并集,以便使拉格朗日松弛问题能有效求解,且使算法在有限步内收敛到最优解.算法把改进的割平面法用于求解对偶问题并与区域分割有效结合解决了多约束非线性背包问题的求解.数值结果表明了改进的割平面方法对对偶搜索更加有效.     

Heuristic and Exact Algorithms for the Precedence-Constrained Knapsack Problem

The knapsack problem (KP) is generalized taking into account a precedence relation between items. Such a relation can be represented by means of a directed acyclic graph, where nodes correspond to items in a one-to-one way. As in ordinary KPs, each item is associated with profit and weight, the knapsack has a fixed capacity, and the problem is to determine the set of items to be included in the knapsack. However, each item can be adopted only when all of its predecessors have been included in the knapsack. The knapsack problem with such an additional set of constraints is referred to as the precedence-constrained knapsack problem (PCKP). We present some dynamic programming algorithms that can solve small PCKPs to optimality, as well as a preprocessing method to reduce the size of the problem. Combining these, we are able to solve PCKPs with up to 2000 items in less than a few minutes of CPU time.     

带组约束可靠性网络最优化问题的精确算法

本文提出了一种求解带组约束串-并网络系统最优冗余问题的精确算法.该算法利用拉格朗日松驰和Dantzig-Wolfe分解法得到问题的上界,并结合动态规划求解子问题.算法采用一种有效的切割和剖分方法,以逐步缩小对偶间隙和保证收敛性.数值结果表明该算法对于求解带组约束可靠性最优化问题是很有效的.     

A Branch-and-Bound Algorithm for Concave Network Flow Problems

In this paper a Branch-and-Bound (BB) algorithm is developed to obtain an optimal solution to the single source uncapacitated minimum cost Network Flow Problem (NFP) with general concave costs. Concave NFPs are NP-Hard, even for the simplest version therefore, there is a scarcity of exact methods to address them in their full generality. The BB algorithm presented here can be used to solve optimally single source uncapacitated minimum cost NFPs with any kind of concave arc costs. The bounding is based on the computation of lower bounds derived from state space relaxations of a dynamic programming formulation. The relaxations, which are the subject of the paper (Fontes et al., 2005b) and also briefly discussed here, involve the use of non-injective mapping functions, which guarantee a reduction on the cardinality of the state space. Branching is performed by either fixing an arc as part of the final solution or by removing it from the final solution. Computational results are reported and compared to available alternative methods for addressing the same type of problems. It could be concluded that our BB algorithm has better performance and the results have also shown evidence that it has a sub-exponential time growth.     

A Finite Branch-and-Bound Algorithm for Linear Multiplicative Programming

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.     

Construction of Test Problems for Concave Minimization Under Linear and Nonlinear Constraints

This paper presents a method for constructing test problems with known global solutions for concave minimization under linear constraints with an additional convex constraint and for reverse convex programs with an additional convex constraint. The importance of such a construction can be realized from the fact that the well known d.c. programming problem can be formulated in this form. Then, the method is further extended to generate test problems with more than one convex constraint, tight or untight at the global solution.     

自适应有限元方法在凹角域线性椭圆方程的应用(续)

作为序列文章自适应有限元方法在凹角域线性椭圆方程的应用的第三篇,在本文我们将给出并详细论证一个重要结论即 |?(u(x)-U(x))|≤Ch(x)|x|^β-2,|x|≥C′h且进一步分析说明在本序列文章的第一部分和地二部分得出方法都是以此为基础作出的。     

Exact Algorithms for Large-Scale Unconstrained Two and Three Staged Cutting Problems

In this paper we propose two exact algorithms for solving both two-staged and three staged unconstrained (un)weighted cutting problems. The two-staged problem is solved by applying a dynamic programming procedure originally developed by Gilmore and Gomory [Gilmore and Gomory, Operations Research, vol. 13, pp. 94–119, 1965]. The three-staged problem is solved by using a top-down approach combined with a dynamic programming procedure. The performance of the exact algorithms are evaluated on some problem instances of the literature and other hard randomly-generated problem instances (a total of 53 problem instances). A parallel implementation is an important feature of the algorithm used for solving the three-staged version.     

Reliability in the acquisitions process: Douglas J. DePRIEST and Robert L. LAUNER (eds.) Volume 4 in: Lecture Notes in Statistics,Marcel Dekker,New York, 1983, viii + 199 pages

We correct a mistake in the Martello-Toth algorithm for the general one-dimensional knapsack problem.     

离散线性投资组合模型的分枝定界算法

本文提出了一类新的带整数交易手数和凹型交易费用的均值绝对偏差模型(MAD)和极大极小投资组合模型(Minmax),并给出了离散模型的分枝定界算法.我们分别用随机产生的数据和Nasdaq股票市场的真实数据进行了数值实验,数值分析表明在一定的收益水平下均值绝对偏差离散模型风险控制上优于极大极小投资组合离散模型,而计算效率上极大极小投资组合离散模型优于期望绝对偏差离散模型.     

A branch and search algorithm for a class of nonlinear knapsack problems

This paper discusses a class of nonlinear knapsack problems where the objective function is quadratic. The method is a branch and search procedure which includes an efficient algorithm to find the continuous (relaxed) solution and a reduction rule which computes tight lower and upper bounds on the integer variables.     

Discrete Filled Function Method for Discrete Global Optimization

A discrete filled function method is developed in this paper to solve discrete global optimization problems over strictly pathwise connected domains. Theoretical properties of the proposed discrete filled function are investigated and a solution algorithm is proposed. Numerical experiments reported in this paper on several test problems with up to 200 variables have demonstrated the applicability and efficiency of the proposed method.     

Cone Adaptation Strategies for a Finite and Exact Cutting Plane Algorithm for Concave Minimization

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.     

关于存在多组最优解的整数线性规划问题的割平面法的研究

利用割平面法求解具有多组最优解情形的整数线性规划问题时,会出现不能求出全部最优解的现象,这是割平面法的一个缺陷.针对割平面法的这种缺陷,基于构造非线性标量化函数时引入凸锥的思想,提出了一种割平面一线性交叉搜索方法,这种割平面一线性交叉搜索方法可以解决利用割平面法求解整数线性规划问题时出现的缺陷.最后,通过数值例验证了割平面一线性交叉搜索方法的可行性与有效性.     

切割定界与整数分枝结合求解整数线性规划

把一种改进的割平面方法和分枝定界的思想结合起来求解整数线性规划 ( ILP)问题 .它利用目标函数等值面的移动来切去相应 ( LP)的可行域中含其非整数最优解但不含 ( ILP)可行解的“无用部分”,并将对应的目标函数值作为 ( ILP)目标最优值的一个上界 ;最后 ,通过 ( LP)最优解中非整数基变量的整数分枝来获得整数线性规划的最优解 .     

无穷凹角区域各向异性问题的自然边界元法

本文研究无穷凹角区域上一类各向异性问题的自然边界元法.利用自然边界归化原理,获得该问题的Poisson积分公式和自然积分方程,给出了自然积分方程的数值方法,以及逼近解的收敛性和误差估计,最后给出了数值例子,以示方法的可行性和有效性.     

New Branch-and-Cut Algorithm for Bilevel Linear Programming

Linear mixed 0–1 integer programming problems may be reformulated as equivalent continuous bilevel linear programming (BLP) problems. We exploit these equivalences to transpose the concept of mixed 0–1 Gomory cuts to BLP. The first phase of our new algorithm generates Gomory-like cuts. The second phase consists of a branch-and-bound procedure to ensure finite termination with a global optimal solution. Different features of the algorithm, in particular, the cut selection and branching criteria are studied in details. We propose also a set of algorithmic tests and procedures to improve the method. Finally, we illustrate the performance through numerical experiments. Our algorithm outperforms pure branch-and-bound when tested on a series of randomly generated problems. Work of the authors was partially supported by FCAR, MITACS and NSERC grants.