直运越库物流的精确算法研究

多车辆直运越库调度问题的目标是最小化所有客户中的最晚到货时间.首先,建立了描述该问题的混合整数线性规划模型,并使用运筹优化工具ILOG CPLEX进行求解;其次,构造了基于LPT规则的启发式算法,为精确算法提供了初始可行解,并对分支定界算法进行详细的分析;最后,在数值实验部分,通过数学模型与分支定界的比较及算法性能的分析后,得出分支定界算法具有更高的效率,该分支定界算法在合理的时间内能够求解到11个供应商规模的问题.     

带有二次约束二次规划问题的分枝定界方法

提出了一种解带有二次约束二次规划问题的新的分枝定界算法对该算法进行了收敛性分析。这种方法是用新的线性规划松弛定界技术确定最优值的下界，并且把分枝定界技术和外逼近方法有机地结合起来。     

一类带有常系数线性乘积规划问题的分支定界缩减方法

本文给出了一种求解带有常系数线性乘积规划问题的分支定界缩减算法.我们首先利用两个变量乘积的凸包络技术,分别得到目标函数与约束函数中乘积的上界与下界估计,由此构造出原问题的一个松弛凸规划问题.在此基础之上,借助超矩形的缩减技术,提出了确定原问题全局最优值下界的分支定界缩减算法,并从理论上分析了算法的收敛性.最后,利用数值实验验证了算法的有效性与可行性.     

多用户检测问题的半定规划方法

在码分多址系统中，求解多用户检测问题是重要环节，介绍了多用户检测问题的应用背景和发展现状，重点综述基于半定规划模型寻求多用户的检测问题次优解的几种重要方法，包括随机扰动法，坐标下降法，半定规划的割平面法和二次规划的分枝定界法等，结合数值实验，评价比较了这些方法的优缺点。     

车联网中基于服务的虚拟网络功能放置算法

为满足车联网中海量数据的采集、传输以及对这些数据的快速处理的需求,可采用移动边缘计算(MEC)技术。本文考虑移动边缘计算中基站连接方式和物理资源的特点,对边缘服务器的部署问题进行了分析,以部署成本和网络时延为优化目标,划分基站集群,并使用整数线性规划(ILP)建立模型。为了获得运行效率更高的边缘服务器部署方案,本文使用分支定界算法和启发式贪婪算法获得优化模型的近似最优解。实验评估结果显示,分支定界算法和启发式贪婪算法最高可以把边缘服务器部署算法运行时间减少37.6%。此外,本文分析了用户服务器请求数量和用户服务优先级对算法运行时间和边缘服务器运行成本的影响。     

带装载组合约束的汽车出厂物流组合装箱问题的模型和分支定界算法研究

研究带装载组合约束的出厂物流装箱问题的精确算法和启发式算法,问题的优化目标是最大化装载商品车数量的同时最小化使用承运车数量,其中装载组合约束是指每辆承运车所能装载商品车的类型和数量是给定的。数值实验和案例分析表明,设计的分支定界算法都能够有效提高求解效率并应用于实际情况。     

带非凸二次约束的二次规划问题的全局优化方法

利用二次函数的线形下界函数对带有非凸二次约束的二次规划(QP)提出一种新的求其全局最优解的分支定界算法.为改进算法的收敛性,根据问题的最优性和可行性提出一新的区域剪枝准则以排除(QP)的可行域中不存在全局解的部分.数值算例表明该准则能有效地加速算法的收敛性.     

分枝定界MIMO检测算法的推广及改进

将分枝定界这种优化搜索算法用在MIMO系统中,并且推广到非二进制高阶调制的情况,在基本算法的基础上提出了对信号排序和候选节点排序的改进算法.仿真结果表明,分枝定界算法是一种最大似然检测算法,提出的改进算法加快了收敛速度,降低了计算复杂度和对存储空间的要求,从而证明了改进算法的有效性.     

面向节能无关联平行机调度模型及分支定界法

工业企业,特别是高耗能行业,不仅要满足交货期和缩小生产周期的要求,而且不断优化能源配置,降低能耗。研究一类新的以延迟和能源消耗的加权最小为目标的生产调度问题。首先,描述问题并分析问题的复杂性。其次,建立混合整数线性规划模型。进一步,我们提出求解该问题的分支定界算法。最后,通过数值实验和数值试验,验证算法的有效性和高效性。     

空箱资源约束调度的列生成算法研究

研究了可重用空箱资源约束下的入厂物流车辆运输调度问题。首先对该问题进行数学描述,建立混合整数线性规划模型。鉴于问题的NP难解性,研究求解该问题的列生成方法,提出虚工件等技巧,建立适合序列依赖的可重用资源约束调度的列生成主问题模型以及基于检验数求解的子问题模型,并研究求解子问题的动态规划算法。进一步采用分支定界技巧,最终提出适合本问题求解的列生成算法。数值实验表明方法的有效性与高效性。     

Solving personnel tour scheduling problems using the dual all-integer cutting plane

Personnel tour scheduling problems are highly relevant to service organizations and have recently received considerable attention in both theory and practice. The inherent complexity of generalized set-covering formulations (GSCFs) of personnel tour scheduling problems has often resulted in the deployment of LP-based and local-search heuristic procedures, even for relatively small problems. This paper evaluates the performance of the dual all-integer cutting plane for solving such problems. A computational study revealed that the cutting plane, enhanced by an LP objective cut and sophisticated source row selection rule, substantially outperformed a commercial branch and bound code across four sets of test problems. The study also showed that an advanced starting solution based on the LP relaxation of the GSCF generally provided more rapid convergence of the algorithm.     

SEARCH FOR THE GLOBAL OPTIMUM OF LEAST VOLUME TRUSSES

This paper describes two types of strategies that find the global optimum of structures designed for minimum volume consumption. This bilinearly constrained problem may present multiple optima and some examples of this nonconvex behaviour are given. In the first method two branch and bound ( B & B) based approaches are presented associated with suitable convex underestimating functions. The second is a cutting plane method and is derived as a generalization of Bender's algorithm; although the relaxed problems yielded are still nonconvex, they are amenable by standard codes for 0-1 mixed LP. Frequently structural engineers are confronted with only a limited set of discrete alternatives; both solution techniques presented here are combinatorial in nature and suitable to be cast into a discrete variable model, for which the algorithms converge to the global optimum in a much smaller number of steps.     

带有界约束非凸二次规划问题的整体优化方法

通过研究带有界约束非凸二次规划问题，给出了求解该问题的整体最优 解的分枝定界方法及其收敛性，提出了定界的紧，松驰策略，把球约束二次规划问题作为子问题来确定原问题的整体最优值下界和上界，应用分枝定界方法达到了对原问题的求解。     

寻求平面上线段集凸壳的算法

首先证明寻求平面上线段集凸壳问题的下界是O（nlogn)，其方法是将平面上线段集凸壳问题与排序问题联系起来，由排序问题的下界推得平面上线段集凸壳问题的下界。然后提出一个算法，计算平面上线段集凸壳问题，其基本思想是将线段集中的线段转换成平面上的简单多边形链，接着计算该简单多边形链的凸壳即得到所要求的凸壳。该算法的时间复杂性是O（nlogn)。     

制图标准中剖切面后结构画法的探讨

针对机械制图标准中有关旋转剖视图画法的规定,围绕剖视图中剖切面后结构的画法,提出了"剖切面后的其他结构"和"剖切结构及其有关部分"的具体界限,当一些结构没有直接被剖切到时,若它所在的形体的轴线为两剖切面的交线,应按剖切面后的其他结构,按原来的位置投射;否则应按照"剖切结构及其有关部分",随其所在结构旋转到新的位置,使画法进一步明确。针对有些学者建议,删去制图标准中"剖切面后面的其他结构,应按原位置投射"的规定,认为不能删去,并证明了自己的观点。     

A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows

A branch and bound algorithm is described for optimal cyclic scheduling in a robotic cell with processing time windows. The objective is to minimise the cycle time by determining the exact processing time on each machine which is limited within a time window. The problem is formulated as a set of prohibited intervals of the cycle time, which is usually applied in the robotic cyclic scheduling problem with fixed processing times. Since both bounds of these prohibited intervals are linear expressions of the processing times, we divide these prohibited intervals into a series of the subsets and transform the problem into enumerating the non-prohibited intervals of cycle time in each subset. This enumeration procedure is completed by an efficient branch and bound algorithm, which could find an optimal solution by enumerating partial non-prohibited intervals. Computational results on the benchmark instances and randomly generated test instances indicate that the algorithm is effective.     

A new deterministic global optimization method for general twice-differentiable constrained nonlinear programming problems

A deterministic global optimization method that is applicable to general nonlinear programming problems composed of twice-differentiable objective and constraint functions is proposed. The method hybridizes the branch-and-bound algorithm and a convex cut function (CCF). For a given subregion, the difference of a convex underestimator that does not need an iterative local optimizer to determine the lower bound of the objective function is generated. If the obtained lower bound is located in an infeasible region, then the CCF is generated for constraints to cut this region. The cutting region generated by the CCF forms a hyperellipsoid and serves as the basis of a discarding rule for the selected subregion. However, the convergence rate decreases as the number of cutting regions increases. To accelerate the convergence rate, an inclusion relation between two hyperellipsoids should be applied in order to reduce the number of cutting regions. It is shown that the two-hyperellipsoid inclusion relation is determined by maximizing a quadratic function over a sphere, which is a special case of a trust region subproblem. The proposed method is applied to twelve nonlinear programming test problems and five engineering design problems. Numerical results show that the proposed method converges in a finite calculation time and produces accurate solutions.     

寻求平面上线段集凸壳的扫描算法

首先证明寻求平面上线段集凸壳问题的下界是O(nlogn)，其方法是将平面上线段集凸壳问题与排序问题联系起来，由排序问题的下界推得平面上线段集凸壳问题的下界。然后提出一个算法，计算平面上线段集凸壳问题，其基本思想是将不交线段集中的线段按其端点的x，y坐标排序，并重排线段序。然后用平面扫描方法分段完成凸壳的构造。该算法的时间复杂性是O(nlogn)。     

Integrated design of supply chain networks with three echelons, multiple commodities and technology selection

We consider a strategic supply chain design problem with three echelons, multiple commodities and technology selection. We model the problem as a tri-echelon, capacitated facility location problem that decides on the location of plants and warehouses, their capacity and technology planning, the assignment of commodities to plants and the flow of commodities to warehouses and customer zones. We use a mixed-integer programming formulation strengthened by valid but redundant constraints and apply Lagrangean relaxation to decompose the problem by echelon. Lagrangean relaxation provides a lower bound that is calculated using an interior-point cutting plane method. Feasible solutions are generated using a primal heuristic that uses the solution of the subproblems. Unlike common practice in the literature, the decomposition does not aim at getting easy subproblems, but rather at getting subproblems that preserve most of the characteristics of the original problem. Not only does this provide a sharp lower bound but also leads to a simple and efficient primal heuristic. We can afford to have relatively difficult subproblems because the interior-point cutting plane method used to solve the Lagrangean dual makes clever and selective choices of the Lagrangean multipliers leading to fewer calls to the subproblems. Computational results indicate the efficiency of the approach in providing a sharp bound and in generating feasible solutions that are of high quality.