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

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

边界约束非凸二次规划问题的分枝定界方法

本文是研究带有边界约束非凸二次规划问题,我们把球约束二次规划问题和线性约束凸二次规划问题作为子问题,分明引用了它们的一个求整体最优解的有效算法,我们提出几种定界的紧、松驰策略,给出了求解原问题整体最优解的分枝定界算法,并证明了该算法的收敛性,不同的定界组合就可以产生不同的分枝定界算法,最后我们简单讨论了一般有界凸域上非凸二次规划问题求整体最优解的分枝与定界思想。     

离散单因素投资组合模型的对偶算法

本文研究金融优化中的离散单因素投资组合问题,该问题与传统投资组合模型的不同之处是决策变量为整数(交易手数),从而导致要求解一个二次整数规划问题．针对该模型的可分离性结构,我们提出了一种基于拉格朗日对偶和连续松弛的分枝定界算法。我们分别用美国股票市场的交易数据和随机产生的数据对算法进行了测试．数值结果表明该算法是有效的,可以求解多达150个风险证券的离散投资组合问题．     

平行机排序问题的列生成解法

基于整数规划的线性松弛,探讨求解大规模带权总完工时间排序问题的列生成算法的基本原理.然后,结合动态规划和分枝定界技术,对大规模排序问题P‖∑wiCj提出一类求解精确(最优)解的列生成算法.     

基于半定规划松弛的凸二层规划问题算法研究

提出使用凸松弛的方法求解二层规划问题,通过对一般带有二次约束的二次规划问题的半定规划松弛的探讨,研究了使用半定规划(SDP)松弛结合传统的分枝定界法求解带有凸二次下层问题的二层二次规划问题,相比常用的线性松弛方法,半定规划松弛方法可快速缩小分枝节点的上下界间隙,从而比以往的分枝定界法能够更快地获得问题的全局最优解.     

关于线性二层规划分枝定界方法的探讨

对求解线性二层规划的分枝定界方法进行了探讨.给出的一个例子表明,目前的分枝定界方法不能很好地解决上层带有任意线性形式约束的线性二层规划问题,进而在线性二层规划新定义的基础上提出了求解线性二层规划的扩展分枝定界方法.算例表明扩展分枝定界方法可以有效解决原分枝定界方法的不足.     

最大割问题的二次规划方法

本文给出了最大割问题的二次规划算法。这种算法通过求解最大割问题的二次规划松弛给出了一种较好的界，然后用分支定界法得到了最大割问题的解。数值结果表明这种算法是非常有效的。     

非凸二次规划的粒子群算法

给出了粒子群算法中惯性权值和学习因子的一种简单改进,并将其应用到非凸二次规划的求解中,通过数值试验与现有的求解非凸二次规划问题的分支定界法进行了比较,得到了较好的结果.     

线性约束0-1 二次规划的一个定界技术

本文给出确定线性约束0－1二次规划问题最优值下界的方法,该方法结合McBride和Yormark的思想和总体优化中定下界的方法,证明了所定的界较McBride和Yormark的要好．求解线性约束0－1二次规划问题的分支定界算法可以利用本文的定界技术．     

一类非负二次整数规划问题的分支定界缩减方法

针对一类非负整数二次规划问题,提出了一个新的分枝定界缩减方法.在这个方法里,使用了一个新的超矩形二分技术和一个新的线性规划松弛定下界技术,同时为了提高逼近程度和加快收敛速度,使用了超矩形缩减策略.数值结果表明所提出的算法是可行的和有效的.     

Two-stage quadratic integer programs with stochastic right-hand sides

We consider two-stage quadratic integer programs with stochastic right-hand sides, and present an equivalent reformulation using value functions. We propose a two-phase solution approach. The first phase constructs value functions of quadratic integer programs in both stages. The second phase solves the reformulation using a global branch-and-bound algorithm or a level-set approach. We derive some basic properties of value functions of quadratic integer programs and utilize them in our algorithms. We show that our approach can solve instances whose extensive forms are hundreds of orders of magnitude larger than the largest quadratic integer programming instances solved in the literature.     

Global Optimization of Multiplicative Programs

This paper develops global optimization algorithms for linear multiplicative and generalized linear multiplicative programs based upon the lower bounding procedure of Ryoo and Sahinidis [30] and new greedy branching schemes that are applicable in the context of any rectangular branch-and-bound algorithm. Extensive computational results are presented on a wide range of problems from the literature, including quadratic and bilinear programs, and randomly generated large-scale multiplicative programs. It is shown that our algorithms make possible for the first time the solution of large and complex multiplicative programs to global optimality.     

Global optimization of mixed-integer nonlinear programs: A theoretical and computational study

This work addresses the development of an efficient solution strategy for obtaining global optima of continuous, integer, and mixed-integer nonlinear programs. Towards this end, we develop novel relaxation schemes, range reduction tests, and branching strategies which we incorporate into the prototypical branch-and-bound algorithm. In the theoretical/algorithmic part of the paper, we begin by developing novel strategies for constructing linear relaxations of mixed-integer nonlinear programs and prove that these relaxations enjoy quadratic convergence properties. We then use Lagrangian/linear programming duality to develop a unifying theory of domain reduction strategies as a consequence of which we derive many range reduction strategies currently used in nonlinear programming and integer linear programming. This theory leads to new range reduction schemes, including a learning heuristic that improves initial branching decisions by relaying data across siblings in a branch-and-bound tree. Finally, we incorporate these relaxation and reduction strategies in a branch-and-bound algorithm that incorporates branching strategies that guarantee finiteness for certain classes of continuous global optimization problems. In the computational part of the paper, we describe our implementation discussing, wherever appropriate, the use of suitable data structures and associated algorithms. We present computational experience with benchmark separable concave quadratic programs, fractional 0–1 programs, and mixed-integer nonlinear programs from applications in synthesis of chemical processes, engineering design, just-in-time manufacturing, and molecular design.The research was supported in part by ExxonMobil Upstream Research Company, National Science Foundation awards DMII 95-02722, BES 98-73586, ECS 00-98770, and CTS 01-24751, and the Computational Science and Engineering Program of the University of Illinois.     

Minimizing the total completion time on a single machine with the learning effect and multiple availability constraints

This paper considers a single machine scheduling problem with the learning effect and multiple availability constraints that minimizes the total completion time. To solve this problem, a new binary integer programming model is presented, and a branch-and-bound algorithm is also developed for solving the given problem optimally. Since the problem is strongly NP-hard, to find the near-optimal solution for large-sized problems within a reasonable time, two meta-heuristics; namely, genetic algorithm and simulated annealing are developed. Finally, the computational results are provided to compare the result of the binary integer programming, branch-and-bound algorithm, genetic algorithm and simulated annealing. Then, the efficiency of the proposed algorithms is discussed.     

Extensions of Dinkelbach's algorithm for solving non-linear fractional programming problems

Dinkelbach's algorithm was developed to solve convex fractinal programming. This method achieves the optimal solution of the optimisation problem by means of solving a sequence of non-linear convex programming subproblems defined by a parameter. In this paper it is shown that Dinkelbach's algorithm can be used to solve general fractional programming. The applicability of the algorithm will depend on the possibility of solving the subproblems. Dinkelbach's extended algorithm is a framework to describe several algorithms which have been proposed to solve linear fractional programming, integer linear fractional programming, convex fractional programming and to generate new algorithms. The applicability of new cases as nondifferentiable fractional programming and quadratic fractional programming has been studied. We have proposed two modifications to improve the speed-up of Dinkelbachs algorithm. One is to use interpolation formulae to update the parameter which defined the subproblem and another truncates the solution of the suproblem. We give sufficient conditions for the convergence of these modifications. Computational experiments in linear fractional programming, integer linear fractional programming and non-linear fractional programming to evaluate the efficiency of these methods have been carried out.     

Heuristics for convex mixed integer nonlinear programs

In this paper, we describe the implementation of some heuristics for convex mixed integer nonlinear programs. The work focuses on three families of heuristics that have been successfully used for mixed integer linear programs: diving heuristics, the Feasibility Pump, and Relaxation Induced Neighborhood Search (RINS). We show how these heuristics can be adapted in the context of mixed integer nonlinear programming. We present results from computational experiments on a set of instances that show how the heuristics implemented help finding feasible solutions faster than the traditional branch-and-bound algorithm and how they help in reducing the total solution time of the branch-and-bound algorithm.     

The transportation problem with exclusionary side constraints and two branch-and-bound algorithms

The transportation problem with exclusionary side constraints, a practical distribution and logistics problem, is formulated as a 0–1 mixed integer programming model. Two branch-and-bound (B&B) algorithms are developed and implemented in this study to solve this problem. Both algorithms use the Driebeek penalties to strengthen the lower bounds so as to fathom some of the subproblems, to peg variables, and to guide the selection of separation variables. One algorithm also strongly exploits the problem structure in selecting separation variables in order to find feasible solutions sooner. To take advantage of the underlying network structure of the problem, the algorithms employ the primal network simplex method to solve network relaxations of the problem. A computational experiment was conducted to test the performance of the algorithms and to characterize the problem difficulty. The commercial mixed integer programming software CPLEX and an existing special purpose algorithm specifically designed for this problem were used as benchmarks to measure the performance of the algorithms. Computational results show that the new algorithms completely dominate the existing special purpose algorithm and run from two to three orders of magnitude faster than CPLEX.     

Pruning in column generation for service vehicle dispatching

Column generation techniques have become a widely used technique to successfully solve large (integer) linear programs. One of the keys to obtaining a practically efficient algorithm is to have a fast method to limit the pricing of new columns to a small set. We study a large scale real-world vehicle dispatching problem with soft time windows which can be modeled as an integer linear program of set partitioning type. We develop a new pruning scheme based on matchings in order to speed up the branch-and-bound enumeration in the column generation process. Computational results on real-world data illustrate the effectiveness of the new pruning scheme.     

An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints

In this paper, we propose a branch-and-bound algorithm for finding a global optimal solution for a nonconvex quadratic program with convex quadratic constraints (NQPCQC). We first reformulate NQPCQC by adding some nonconvex quadratic constraints induced by eigenvectors of negative eigenvalues associated with the nonconvex quadratic objective function to Shor’s semidefinite relaxation. Under the assumption of having a bounded feasible domain, these nonconvex quadratic constraints can be further relaxed into linear ones to form a special semidefinite programming relaxation. Then an efficient branch-and-bound algorithm branching along the eigendirections of negative eigenvalues is designed. The theoretic convergence property and the worst-case complexity of the proposed algorithm are proved. Numerical experiments are conducted on several types of quadratic programs to show the efficiency of the proposed method.