Matlab语言在整数规划中的应用

该文提出了用枚举法解决线性函数中的整数规划问题。应用Matlab语言的线性规划函数linprog,先取消整数限制求解;因目标函数为线性函数,它具有一致倾斜性,再求出整数规划的最优解。由于文章所提算法可以很便捷算出整数规划的最优解,因而避免了原有算法的一些困境。     

线性规划的初等矩阵解法

由于线性规划的初等矩阵解法的计算量一般并不比单纯形法的计算量大,而且它可以方便地得出全部最优解的表达式,所以它不失为一个好方法。在这篇文章中,我们借助于初等矩阵方法把任何一个有解的线性规划问题都化成最多只含有一个约束条件的问     

求不相交QoS路由的一种整数线性规划方法

提出求解不相交QoS路由问题的一种整数线性规划方法.首先,利用一个0-1变量集合来表示不相交路由和路由的QoS需求;然后,通过拉格朗日乘子将集合中的复杂约束引入所导出的整数线性规划问题的目标函数中.因为约束系数矩阵是全幺模矩阵,所以这类整数线性规划问题能用单纯形法容易地求解,从而可在求解线性规划问题的迭代过程中求出不相交QoS路由.数值实验结果表明了所提出方法的有效性.     

高效求解整数线性规划问题的分支算法

为了提高求解一般整数线性规划问题的效率,提出了一种基于目标函数超平面移动的分支算法。对于给定的目标函数整数值,首先利用线性规划松弛问题的最优单纯形表确定变量的上、下界,然后将变量的上、下界条件加入约束条件中对相应的目标函数超平面进行切割,最后应用分支定界算法中的分支方法来搜寻目标函数超平面上的可行解。通过对一些经典的数值例子的求解计算并与经典的分支定界算法进行比较,结果表明,该算法减少了分支数和单纯形迭代数,具有较大的实用价值。     

整数线性规划的切割与分支算法

基于整数线性规划问题的分支定界方法,以子问题或根问题的目标最优值作为参数,构造了一种新的切割不等式,能够方便地切割子问题或根问题的非整数最优解.在分支之前进行这种切割,产生了一种新的求解整数线性规划问题的切割与分支算法.将该算法应用于求解一些经典的数值例子,实验结果表明,与经典的分支定界方法相比,该算法大大减少了分支的数量,提高了计算效率.随着问题规模的增大,该算法的计算优越性体现得更加明显.     

求解煤炭水运配船的免疫优化算法

煤炭水运配船属于多约束混合整数线性规划问题。当问题规模大、约束条件多时很难获得最优解,并且求解时间过长。针对上述问题,提出一种基于免疫克隆算法的求解方案。通过构建相应的数学模型,设计了基于二维矩阵的抗体表示形式和混合整数编码方式,构造了罚函数处理不等式约束。算法使用克隆、变异和抗体浓度抑制等免疫操作,保持了抗体的多样性,避免陷入局部最优。算法仿真表明,该算法在全局最优解和运行速度方面优于遗传算法,优化结果验证了算法的有效性。     

任务分配问题的建模与求解

建立了极大极小任务分配问题的混合整数线性规划模型,提出一种矩阵作业解答,并与穷举解及混合整数线性规划解的计算复杂度进行了比较.理论分析和数值试验表明矩阵作业法对两类任务分配问题,极大极小和总体极小任务分配问题,有效地提供最优解.     

粒子群优化在嵌入式软硬件划分中的应用

针对嵌入式系统设计中的软硬件划分问题,提出了一种基于粒子群优化(PSO)算法的划分策略,并将该算法与整数线性规划、遗传算法、蚁群算法等进行计算机仿真比较。结果表明,该方法获得的最优解优于遗传算法和蚁群算法两种元启发式算法,充分接近由整数线性规划得到的最优解;在算法执行时间方面,该方法也优于其它三种算法。     

基于特征点集GABC算法的WSN覆盖优化

针对人工蜂群算法利用网格点计算网络覆盖率会导致计算量大且容易陷入局部最优解的问题,提出一种基于特征点集的全局最优解人工蜂群算法优化无线传感器网络。首先将目标区域划分成有限个特征点,用传感器对特征点的覆盖来转化为对若干特征点的覆盖计算,减少求解覆盖率的计算量,进而描述整个网络的覆盖情况。然后在特征点集的基础上,将全局最优解人工蜂群算法成功应用在网络覆盖领域,并且重点对比标准人工蜂群算法和基于全局最优解人工蜂群算法在网络覆盖上的性能。仿真实验结果表明基于全局最优解人工蜂群算法优化节点覆盖后,覆盖率得到有效的提升且不易陷入局部最优解。     

鲁棒多目标线性规划模型及混合遗传算法

针对目标函数系数和约束条件系数均在椭球扰动集下的不确定多目标线性规划, 提出了椭球扰动集下的鲁棒多目标线性规划问题。基于每个目标均需获得鲁棒解的假设下给出了定理及证明, 以此把原问题转换为具有二阶锥约束的确定性多目标优化问题。设计了一种混合策略求解算法, 整体流程采用多目标遗传算法, 局部采用SOCP优化软件Sedumi进行计算, 从而获得不确定多目标线性规划的鲁棒解集, 并通过数值算例验证了该算法的有效性。     

一类One to One营销优化模型及其解决方案

针对OnetoOne营销问题进行简单的案例分析,得出了在一般情况下的优化模型。通过把OnetoOne营销优化问题转换成线性规划问题,应用改进的单纯形法、基于Bartels-GolubLU分解的单纯形法和原始-对偶内点法等三种典型的线性规划算法,在MATLAB环境下进行仿真和分析。     

调速泵结构配置协调分解优化算法及实现

建立多级调速泵结构配置连续非线性规划和整数非线性规划二阶段模型.非线性整数规划子问题采用外逼近算法求解.针对连续非线性规划主问题,提出基于割角法的可行域协调分解优化算法,证明割角法陷阱问题并建立判断准则排除已知的陷阱区域,在此基础上构建系列松弛问题得到原优化问题渐进收紧的下界估计,并最终收敛到原优化问题全局最优解.三级调速泵结构配置实例验证了算法的有效性,并给出与其他算法的比较结果.     

Using the primal-dual interior point algorithm within the branch-price-and-cut method

Branch-price-and-cut has proven to be a powerful method for solving integer programming problems. It combines decomposition techniques with the generation of both columns and valid inequalities and relies on strong bounds to guide the search in the branch-and-bound tree. In this paper, we present how to improve the performance of a branch-price-and-cut method by using the primal-dual interior point algorithm. We discuss in detail how to deal with the challenges of using the interior point algorithm with the core components of the branch-price-and-cut method. The effort to overcome the difficulties pays off in a number of advantageous features offered by the new approach. We present the computational results of solving well-known instances of the vehicle routing problem with time windows, a challenging integer programming problem. The results indicate that the proposed approach delivers the best overall performance when compared with a similar branch-price-and-cut method which is based on the simplex algorithm.     

Block Local Elimination Algorithms for Sparse Discrete Optimization Problems

Block local elimination algorithms for solving sparse discrete optimization problems are considered. A numerical example is provided. The benchmarking is done in order to determine the real computational capabilities of block elimination algorithms combined with SYMPHONY solver. The analysis of the results shows that for a sufficiently large number of blocks and rather small size of separators between the blocks for a staircase integer linear programming problem, local elimination algorithms in combination with the solver for subproblems in blocks allow a much faster solution of such problems than the solver itself used to solve the whole problem. The capabilities of the postoptimal analysis (warm start) are also considered for solving packages of integer linear programming problems for the corresponding blocks.     

考虑库区吊机能力的板坯倒垛问题的建模与优化方法研究

研究了钢铁企业板坯库的板坯倒垛(Slab stack shuffling, SSS)问题. 与以往研究倒垛问题不同, 考虑了板坯存储各库区吊机能力的实际限制. 对该问题通过考虑实际约束, 以总倒垛次数最小为目标函数建立了非线性整数规划模型. 基于对问题特征的分析, 分别针对轧制项目间是否存在共同可选板坯的两种情况, 将模型变换为线性整数规划模型. 另外, 利用提出的问题性质, 降低了模型的求解复杂性. 实验结果表明, 对于实际的问题规模, 基于该线性整数规划模型的优化方法能有效地求得问题的最优解.     

A method of network programming in problems of nonlinear optimization

A method of network programming for solving problems of nonlinear optimization is used. A notion of dual problem is introduced. It is proved that a dual problem is a problem of convex programming. Necessary and sufficient conditions for optimality of dual problem of integer linear programming are obtained.     

An algorithm for the biobjective integer minimum cost flow problem

In this paper, we study the single commodity flow problems, optimizing two objectives simultaneously, where the flow values must be integer values. We propose a method that finds all the efficient integer points in the objective space. Our algorithm performs two phases. In the first phase, all integer points on the efficient boundary are found and in the second phase, the efficient integer points that do not lie on the efficient boundary are calculated. In addition, we carry out a computational experiment showing that the number of efficient integer solutions that do not lie on the efficient boundary is greater than the number of integer solutions on the efficient boundary.Scope and purposeIn many combinatorial optimization problems, the selection of the optimum solution takes into account more than one criterion. For example, in transportation problems or in network flows problems, the criteria that can be considered are the minimization of the cost for selected routes, the minimization of arrival times at the destinations, the minimization of the deterioration of goods, the minimization of the load capacity that would not be used in the selected vehicles, the maximization of safety, reliability, etc. Often, these criteria are in conflict and for this reason, a multiobjective network flow formulation of the problem is necessary. The solution to this problem is searched for among the set of efficient points. Although multiobjective network flow problems can be solved using the techniques available for the multiobjective linear programming problem, network-based methods are computationally better. The multicriteria minimum cost flow problem has already merited the attention of several authors and the case which has been considered in literature is that which has two objectives, where the continuous flow values are permissible. However, the integer case of the biobjective minimum cost flow problem has scarcely been studied. Whereas, in many real network flow problems, integer values on flow values are required. In this paper, we propose an approach to solve the biobjective integer minimum cost flow problem. An algorithm to obtain all efficient integer solutions of this problem is introduced. This method is characterized by the use of the classic resolution tools of network flow problems, such as the network simplex method. It does not utilize the biobjective integer linear programming methodology. Furthermore, the method does not calculate dominated solutions, so it is not necessary to incorporate tools to eliminate dominated solutions.     

A two-phase optimization procedure for integer programming problems

This paper presents a simple two-phase method for optimizing integer programming problems with a linear or nonlinear objective function subject to multiple linear or nonlinear constraints. The primary phase is based on a variation of the method of steepest descent in the feasible region, and a hem-stitching approach when a constraint is violated. The secondary phase zeros on the optimum solution by exploring the neighborhood of the suboptimum found in the first phase of the optimization process. The effectiveness of this method is illustrated through the optimization of several examples. The results from the proposed optimization approach are compared to those from methods developed specially for dealing with integer problems. The proposed method is simple, easy to implement yet very effective in dealing with a wide class of integer problems such as spare allocation, reliability optimization, and transportation problems.     

基于混合搜索的含逻辑“与”“或”的RM优化算法

相对于标准约束优化问题,广义约束优化问题（或称析取优化问题）的等式或不等式约束条件中不仅包含逻辑“与”关系,还含有逻辑“或”关系.单调速率（RM）优化问题是广义约束优化问题的一个重要应用.目前RM优化问题已有的解法包括函数变换、混合整数规划、线性规划搜索等算法.随着任务数的增多,这些算法的求解时间较长.提出一种基于线性规划的深度广度混合搜索算法（LPHS）,将广义约束优化问题拆分成若干子问题,建立线性规划搜索树,合理选择搜索顺序,利用动态剪枝算法减小子问题的规模,最终求得最优解.实验结果表明,LPHS算法比其他方法有明显的效率提升.研究成果与计算机基础理论中的可满足性模理论的研究相结合,有助于提高可满足性模理论问题的求解效率,促进该理论在程序验证、符号执行等领域的进一步应用.