Discrete dynamic convexized method for nonlinearly constrained nonlinear integer programming

This paper considers the nonlinearly constrained nonlinear integer programming problem over a bounded box. An auxiliary function is constructed based on a penalty function. By increasing the value of a parameter, minimization of the function by a discrete local search method can escape successfully from a previously converged discrete local minimizer. An algorithm is designed based on minimizing the auxiliary function with increasing values of the parameter. Numerical experiments show that the algorithm is robust and efficient.     

一种求解整数规划与混合整数规划非线性罚函数方法

证明了任何一个变量有界的整数规划问题（IP）和混合整数规划问题（MIP）都可以转化为一个等价的非整数（或连续化）规划问题（NIP），并给出一个用非线性精确罚函数法来求解该等价NIP的方法，从而达到求解IP或MIP的目的，数值实验表明了算法的可行性。该方法可广泛用于各应用领域里IP和MIP的求解，特别是为非线性IP和MIP问题提供了一条通用 的求解途径，对解决许多实际优化问题具有重要意义。     

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

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

混合整数非线性规划问题的改进差分进化算法*

提出一种改进差分进化算法求解混合整数非线性规划问题。该算法利用同态映射方法,解决差分进化算法无法直接处理整数决策变量问题;提出改进的自适应交替变异算子,提高算法的搜索性能;提出一种自适应保留不可行解的方法处理约束条件,并对差分进化算法的选择算子进行改进,提出一种直接处理约束条件的新选择算子。六个常用的混合整数非线性规划问题的实验结果表明了该方法的有效性和适用性。     

Coupling genetic algorithm with a grid search method to solve mixed integer nonlinear programming problems

A new hybrid algorithm is being introduced for solving Mixed Integer Nonlinear Programming ( ) problems which arise from study of many real-life engineering problems such as the minimum cost development of oil fields and the optimization of a multiproduct batch plant. This new algorithm employs both the Genetic Algorithm and a modified grid search method interfacing in such a way that the resulting hybrid algorithm is capable of solving many problems efficiently and accurately. Testings indicate that this algorithm is efficient and robust even for some ill-conditioned problems with nonconvex constraints.     

rs-Sparse principal component analysis: A mixed integer nonlinear programming approach with VNS

Principal component analysis is a popular data analysis dimensionality reduction technique, aiming to project with minimum error for a given dataset into a subspace of smaller number of dimensions.In order to improve interpretability, different variants of the method have been proposed in the literature, in which, besides error minimization, sparsity is sought. In this paper we formulate as a mixed integer nonlinear program the problem of finding a subspace with a sparse basis minimizing the sum of squares of distances between the points and their projections. Contrary to other attempts in the literature, with our model the user can fix the level of sparseness of the resulting basis vectors. Variable neighborhood search is proposed to solve the problem obtained this way.Our numerical experience on test sets shows that our procedure outperforms benchmark methods in the literature, both in terms of sparsity and errors.     

Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem

This paper presents an extended local search algorithm (ELS) for the irregular strip packing problem. It adopts two neighborhoods, swapping two given polygons in a placement and placing one polygon into a new position. The local search algorithm is used to minimize the overlap on the basis of the neighborhoods mentioned above and the unconstrained nonlinear programming model is adopted to further minimize the overlap during the search process. Moreover, the tabu search algorithm is used to avoid local minima, and a compact algorithm is presented to improve the result. The results of standard test instances indicate that when compared with other existing algorithms, the presented algorithm does not only show some signs of competitive power but also updates several best known results.     

Dynamic PSO method for nonlinear constrained programming problems

A new approach is presented to solve the nonlinear constrained programming problems. Firstly, the nonlinear constrained programming problem is transformed into a bi-ohjective optimization problem. Based on the reasonable design of the searching operation and different parameters, a new dynamic particle swarm optimization algorithm （TS-MC） is proposed. The numerical experiments show that the proposed algorithm is effective in dealing with the nonlinear constrained programming problems.     

A recombination‐based matheuristic for mixed integer programming problems with binary variables

This work introduces a heuristic for mixed integer programming (MIP) problems with binary variables, based on information obtained from differences between feasible solutions as well as solutions from the linear relaxation. This information is used to build a neighborhood that is explored as a sub‐MIP problem. The proposed heuristic is evaluated using 45 problems from the MIPLIB repository. Its performance, in terms of solution improvement over the results obtained after exploring 50,000 nodes of the branch‐and‐bound tree, is compared against that of Solution Polishing, which is another recombination‐based heuristic for MIP problems used within the CPLEX solver; as well as against the solution obtained by running the default CPLEX branch‐and‐cut (B&C) method under a same time limit. The computational results indicate that the proposed method is able to yield results that are significantly better than those obtained by the default CPLEX B&C approach and comparable to those of Solution Polishing in terms of the mean solution quality. This equivalence of expected solution quality, coupled with a simpler implementation, suggests the use of the proposed approach as a possible alternative for improving the quality of solutions in MIP problems.     

A genetic algorithm for interval nonlinear integer programming problem

In this paper, we formulate an optimal design of system reliability problem as a nonlinear integer programming problem with interval coefficients, transform it into a single objective nonlinear integer programming problem without interval coefficients, and solve it directly with keeping nonlinearity of the objective function by using Genetic Algorithms (GA). Also, we demonstrate the efficiency of this method with incomplete Fault Detecting and Switching (FDS) for allocating redundant units.     

Detecting infeasibility and generating cuts for mixed integer programming using constraint programming

We study a hybrid MIP/CP solution approach in which CP is used for detecting infeasibilities and generating cuts within a branch-and-cut algorithm for MIP. Our framework applies to MIP problems augmented by monotone constraints that can be handled by CP. We illustrate our approach on a generic multiple machine scheduling problem, and present a number of computational experiments.     

求解整数非线性规划结合正交杂交的离散PSO 算法

针对整数非线性规划问题,提出一种结合正交杂交的离散粒子群优化(PSO)算法.首先采用舍入取整方法,为了减少舍入误差,对PSO中的每个粒子到目前为止的最好位置进行随机修正,将基于正交实验设计的正交杂交算子引入离散PSO算法,以增强搜索性能;然后对PSO算法中的惯性权重和收缩因子采用动态调整策略,以提高算法的搜索效率;最后对一些不同维数的整数非线性规划问题进行数值仿真实验,实验结果表明了所提出算法的有效性.     

A mixed integer nonlinear programming model and heuristic solutions for location,inventory and pricing decisions in a closed loop supply chain

We analyze a network design problem for a closed-loop supply chain that integrates the collection of the used products with the distribution of the new products. We present a mixed integer nonlinear facility location-inventory-pricing model to decide on the optimal locations of the facilities, inventory amounts, prices for new products and incentive values for the collection of right amount of used products in order to maximize the total supply chain profit. We develop heuristics for the solution of this model and analyze the effectiveness of these heuristics and the effects of the parameters on this system through numerical experiments.     

一种求非线性整数规划最优解的仿生算法

从大自然植物生长中得到启发,提出了一种求解非线性整数规划全局最小解的仿生算法。该算法将植物生长过程及生长模式应用到非线性整数规划问题的求解,能够快速得到最优解。通过对各种不同类型非线性整数规划问题的具体求解,表明了该方法十分有效。     

基于混合整数规划的一般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#可控性条件更宽松,可适用于更多类型的一般网,为解决大规模柔性制造系统中死锁监督控制器的结构复杂性问题提供了有力的理论支撑.     

Parametric tabu-search for mixed integer programs

A parametric form of tabu-search is proposed for solving mixed integer programming (MIP) problems that creates and solves a series of linear programming (LP) problems embodying branching inequalities as weighted terms in the objective function. The approach extends and modifies a parametric branch and bound procedure of Glover [Parametic branch and bound. OMEGA, The International Journal of Management Science 1978;6:1–9], replacing its tree search memory by the adaptive memory framework of tabu-search and introducing new associated strategies that are more flexible than the mechanisms of branch and bound.     

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.     

Neural-network-observer-based optimal control for unknown nonlinear systems using adaptive dynamic programming

In this paper, an observer-based optimal control scheme is developed for unknown nonlinear systems using adaptive dynamic programming (ADP) algorithm. First, a neural-network (NN) observer is designed to estimate system states. Then, based on the observed states, a neuro-controller is constructed via ADP method to obtain the optimal control. In this design, two NN structures are used: a three-layer NN is used to construct the observer which can be applied to systems with higher degrees of nonlinearity and without a priori knowledge of system dynamics, and a critic NN is employed to approximate the value function. The optimal control law is computed using the critic NN and the observer NN. Uniform ultimate boundedness of the closed-loop system is guaranteed. The actor, critic, and observer structures are all implemented in real-time, continuously and simultaneously. Finally, simulation results are presented to demonstrate the effectiveness of the proposed control scheme.     

Extended ant colony optimization for non-convex mixed integer nonlinear programming

Two novel extensions for the well known ant colony optimization (ACO) framework are introduced here, which allow the solution of mixed integer nonlinear programs (MINLPs). Furthermore, a hybrid implementation (ACOmi) based on this extended ACO framework, specially developed for complex non-convex MINLPs, is presented together with numerical results.     

非线性零和微分对策的事件触发自适应动态规划算法

针对一类非线性零和微分对策问题,本文提出了一种事件触发自适应动态规划(event-triggered adaptive dynamic programming,ET--ADP)算法在线求解其鞍点.首先,提出一个新的自适应事件触发条件.然后,利用一个输入为采样数据的神经网络(评价网络)近似最优值函数,并设计了新型的神经网络权值更新律使得值函数、控制策略及扰动策略仅在事件触发时刻同步更新.进一步地,利用Lyapunov稳定性理论证明了所提出的算法能够在线获得非线性零和微分对策的鞍点且不会引起Zeno行为.所提出的ET--ADP算法仅在事件触发条件满足时才更新值函数、控制策略和扰动策略,因而可有效减少计算量和降低网络负荷.最后,两个仿真例子验证了所提出的ET--ADP算法的有效性.