一种求解混合整数非线性规划问题的混合优化方法

提出了一种适用于求解混合整数非线性规划(MINLP)方法(GA-SQP),针对确定型算法在NLP子问题复杂的情况下难以在有限时间内收敛的问题,将MINLP问题分解为一系列简单的NLP子问题,外层用遗传算法搜索最优的整数变量集,内层执行SQP算法解决NLP问题,相比传统的确定性算法,它能减少模型本身的非凸性,从而消除双线性项的求解困难,而相对于智能算法,它充分利用梯度信息,在求解NLP问题上具有明显的效率优势。在改进求解效率上,进一步引入存储机制,减少NLP重复求解从而加速收敛。最后以3个常用的测试函数和水处理网络问题为例,数值计算表明本文提出的方法搜索精度明显优秀于传统的确定型算法和启发式算法。     

一种求解混合整数规划的混合进化算法

提出一种基于正交试验设计的混合进化算法,用于求解混合整数规划问题.进化算法中采用一种混合启发式的变异算子,将正交试验设计作为杂交算子.为了增加种群的多样性,引入一种迁移算子.仿真实验结果表明,与已有的一些算法相比,所提出的求解混合整数规划的混合进化算法能快速收敛到问题的最优解,并且算法的计算量小,解的精度高.     

一种基于罚函数的机器人路径规划方法

给出了一种基于罚函数的机器人路径规划方法;这种方法将机器人的路径规划由一系列带约束非线形规划问题转化为一系列无约束非线形规划问题来求解,仿真结果表明,罚函数方法是一种富有效率的解决机器人路径规划问题的方法,能够大幅度降低运算时间的复杂性,提高移动机器人的实时性。     

求解一类非线性整数规划的新方法

针对一类非线性整数规划问题，通过构造直接高散搜索方向提出了一种十分有效的算法。     

解决混合整数非线性规划问题的混沌局部搜索差分进化算法

为提高差分进化算法的局部搜索能力和避开罚函数方法中罚参数选择问题,提出一种混沌局部搜索策略的差分进化算法(CLSDE)用于解决非线性混合整数规划问题.CLSDE中,只对目标函数中的变量进行编码,约束条件函数中的变量随机产生,每代进化完毕后,对最优个体进行混沌局部搜索.6个基本的测试函数实验结果证明CLSDE比MIHDE具有较好的寻优能力.     

基于量子粒子群求解混合整数非线性规划

在经典微粒群算法的基础上提出一种有较高收敛性能的智能算法：量子粒子群（QPSO）算法。并用于求解混合整数非线性规划问题。实验室证明QPSO算法收敛性能好、速度快,为求解混合整数非线性规划开辟了新途径。     

基于改进果蝇算法求解混合整数非线性规划问题

在科学及工程系统设计中存在许多混合整数非线性规划MINLP(Mixed-Integer Non Linear Programming)问题,该类问题变量类型丰富且约束条件较多,难以求解,为此提出一种改进果蝇算法。该算法对不同类型变量的更新采取不同的策略,并采用周期性的步长函数指导果蝇的寻优,使其避免陷入局部最优。并通过与另外两种常用的算法在稳定性、收敛速度等方面进行了比较,实验结果表明该改进的果蝇算法效果较优,能有效地解决MINLP问题。     

一类非线性整数规划问题的计算机求解

文章针对一类具有特殊性质的非线性整数规划问题,提出了一种具有剔除选择的计算机求解的方法。该求解方法的提出,对解决现实生活中这一类非线性整数规划问题,提供了一种切实可行的途径,这为此类问题的决策提供了有效的手段。     

混沌遗传算法用于求解混合整数规划问题

针对遗传算法的早熟收敛问题,提出了一种混沌遗传算法（CGA）用于解决混合整数规划问题（MIPP）。该算法的基本思想是把混沌变量加载于初始个体的混沌生成和最优个体的混沌搜索过程中。研究结果表明：混沌遗传算法能够有效地解决混合整数规划问题,改善了遗传算法的早熟问题。该算法效果显著,明显提高了解决混合整数规划问题的计算效率,在收敛速度、解的精度和稳定性方面也都优于遗传算法。     

基于金字塔结构的群智能演化策略求解混合整数规划问题

混合整数非线性规划问题（mixed-integer nonlinear programming,MINLP） 广泛应用于科学及工程系统设计,传统的群智能算法在求解混合整数规划问题时,未能很好地解决种群内部个体或者种群之间开采与探索、竞争与协作的矛盾。为了解决这两个矛盾及更高效率地寻优,提出一种基于金字塔结构的群智能演化策略（swarm intelligent evolution strategy based on pyramid structure）的PES算法来求解混合整数规划问题。PES算法中明确的分工机制能够平衡全局与局部搜索的能力,晋升机制解决了种群间竞争与协作的矛盾。利用标准测试函数进行仿真,对比改进的粒子群算法（CLSPSO、CLSPSO2）及改进的差分进化算法（ridDE、ridDE2）的结果,发现PES算法在成功率与精度方面具有优势,也体现了PES算法的有效性。     

多周期混合整数规划购油模型及应用

采用PIMS软件中的多周期混合整数规划技术建立炼油企业购油计划模型，使优化结果与实际购油方式相吻合；采用虚拟周期方法解决原油期末库存质量控制问题；采用滚动处理方式解决炼厂月、季原油选购计划的衔接和全局优化问题。文中还给出了多周期MIP模型技术在某炼厂中的应用以及不同方案的效益对比。     

A new mixed integer linear programming model for product development using quality function deployment

Quality function deployment (QFD) is a product development process performed to maximize customer satisfaction. In the QFD, the design requirements (DRs) affecting the product performance are primarily identified, and product performance is improved to optimize customer needs (CNs). For product development, determining the fulfillment levels of design requirements (DRs) is crucial during QFD optimization. However, in real world applications, the values of DRs are often discrete instead of continuous. To the best of our knowledge, there is no mixed integer linear programming (MILP) model in which the discrete DRs values are considered. Therefore, in this paper, a new QFD optimization approach combining MILP model and Kano model is suggested to acquire the optimized solution from a limited number of alternative DRs, the values of which can be discrete. The proposed model can be used not only to optimize the product development but also in other applications of QFD such as quality management, planning, design, engineering and decision-making, on the condition that DR values are discrete. Additionally, the problem of lack of solutions in integer and linear programming in the QFD optimization is overcome. Finally, the model is illustrated through an example.     

Target setting with minimum improving costs in data envelopment analysis: A mixed integer linear programming approach

This study addresses a problem called cost‐minimizing target setting in data envelopment analysis (DEA) methodology. The problem is how to make an inefficient decision‐making unit efficient by allocating to it as few organizational resources as possible, assuming that the marginal costs of reducing inputs or increasing outputs are known and available, which is different from previous furthest and closest DEA targets setting methods. In this study, an existed cost minimizing target setting heuristics approach based on input‐oriented model is examined to show that there exist some limitations. This study develops a simple mixed integer linear programming to determine the desired targets on the strongly efficient frontier based on non‐oriented DEA model considering the situation in the presence of known marginal costs of reducing inputs and increasing outputs simultaneously. Some experiments with the simulated datasets are conducted, and results show that the proposed model can obtain more accurate projections with lower costs compared with those from furthest and closest target setting approaches. Besides, the proposed model can be realistic and efficient in solving cost‐minimizing target setting problem.     

An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions

We present an exact algorithm for the bilevel mixed integer linear programming (BMILP) problem under three simplifying assumptions. Although BMILP has been studied for decades and widely applied to various real world problems, there are only a few BMILP algorithms. Compared to these existing ones, our new algorithm relies on fewer and weaker assumptions, explicitly considers finite optimal, infeasible, and unbounded cases, and is proved to terminate finitely and correctly. We report results of our computational experiments on a small library of BMILP test instances, which we created and made publicly available online.     

基于混合整数规划的一般Petri网死锁检测方法

信标的受控性是检测柔性制造系统(flexible manufacturing system,FMS)Petri网模型是否存在死锁的关键因素.对于普通Petri网,在任何可达标识下所有信标不被清空是检测网系统非死锁的充分条件.然而,该条件对于建模能力更强的一般Petri网并不适用,max可控性条件由此产生.研究证明,该条件对于一般Petri网的死锁检测过于严格了.虽然其后有很多研究者通过改进max可控性条件以求给出条件更宽松的一般Petri网非死锁的充分条件,但大部分的研究成果都仅仅局限于一种顺序资源共享分配系统Petri网模型S4PR(systems of sequential systems with shared resources)网.因此,本文在max可控性条件的基础上提出了新的名为max#可控的信标可控性条件,并在此条件的基础上实现了基于混合整数规划(mixed integer programming,MIP)的死锁检测方法.与现有研究成果相比,max#可控性条件更宽松,可适用于更多类型的一般网,为解决大规模柔性制造系统中死锁监督控制器的结构复杂性问题提供了有力的理论支撑.     

A Hybrid approach for integer programming combining genetic algorithms, linear programming and ordinal optimization

Hybrid methods are promising tools in integer programming, as they combine the best features of different methods in a complementary fashion. This paper presents such a framework, integrating the notions of genetic algorithm, linear programming, and ordinal optimization in an effort to shorten computation times for large and/or difficult integer programming problems. Capitalizing on the central idea of ordinal optimization and on the learning capability of genetic algorithms to quickly generate good feasible solutions, and then using linear programming to solve the problem that results from fixing the integer part of the solution, one may be able to obtain solutions that are close to optimal. Indeed ordinal optimization guarantees the quality of the solutions found. Numerical testing on a real-life complex scheduling problem demonstrates the effectiveness and efficiency of this approach.     

A linearized polynomial mixed integer programming model for the integration of process planning and scheduling

This paper presents a linearized polynomial mixed-integer programming model (PMIPM) for the integration of process planning and scheduling problem. First, the integration problem is modeled as a PMIPM in which some of the terms are of products of up to three variables, of both binary and continuous in nature. Then, an equivalent linearized model is derived from the polynomial model by applying certain linearization techniques. Although the linearized models have more variables and constraints than their polynomial counterparts, they are potentially solvable to the optimum in comparison to their equivalent polynomial models. Experiments show that the linearized model possesses certain characteristics that are absent from other models in the literature, and provides a fundamental framework for further research in this area.     

Efficient automated schematic map drawing using multiobjective mixed integer programming

We present an efficient multiobjective mixed binary linear program that automates schematic mapping for network visualization and navigation. Schematic mapping has broad applications in representing transit networks, circuits, disease pathways, project tasks, organograms, and taxonomies. Good schematic maps employ distortion while preserving topology to facilitate access to physical or virtual networks. Automation is critical to saving time and costs, while encouraging adoption. We build upon previous work, particularly that of Nöllenburg and Wolff, improving upon the computational efficiency of their model by relaxing integrality constraints and reducing the number of objectives from three to two. We also employ an efficient augmented ϵ-constraint method to assist in obtaining all Pareto optimal solutions, both supported and unsupported, for a given network. Through the Vienna Underground network and a cancer pathway, along with three numerical examples, we demonstrate the applications of our methods. Finally, we discuss future directions for research in this area.     

A dynamic convexized method for nonconvex mixed integer nonlinear programming

We consider in this paper the nonconvex mixed-integer nonlinear programming problem. We present a mixed local search method to find a local minimizer of an unconstrained nonconvex mixed-integer nonlinear programming problem. Then an auxiliary function which has the same global minimizers and the same global minimal value as the original problem is constructed. Minimization of the auxiliary function using our local search method can escape successfully from previously converged local minimizers by taking increasing values of parameters. For the constrained nonconvex mixed-integer nonlinear programming problem, we develop a penalty based method to convert the problem into an unconstrained one, and then use the above method to solve the later problem. Numerical experiments and comparisons on a set of MINLP benchmark problems show the effectiveness of the proposed algorithm.     

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

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