An Exact Penalty Approach for Mixed Integer Nonlinear Programming Problems

We propose an exact penalty approach for solving mixed integer nonlinear programming (MINLP) problems by converting a general MINLP problem to a finite sequence of nonlinear programming (NLP) problems with only continuous variables. We express conditions of exactness for MINLP problems and show how the exact penalty approach can be extended to constrained problems.

Hybrid particle swarm optimization with chaotic search for solving integer and mixed integer programming problems

A novel chaotic search method is proposed,and a hybrid algorithm combining particle swarm optimization(PSO) with this new method,called CLSPSO,is put forward to solve 14 integer and mixed integer programming problems.The performances of CLSPSO are compared with those of other five hybrid algorithms combining PSO with chaotic search methods.Experimental results indicate that in terms of robustness and final convergence speed,CLSPSO is better than other five algorithms in solving many of these problems.Furthermore,CLSPSO exhibits good performance in solving two high-dimensional problems,and it finds better solutions than the known ones.A performance index(PI) is introduced to fairly compare the above six algorithms,and the obtained values of(PI) in three cases demonstrate that CLSPSO is superior to all the other five algorithms under the same conditions.

Exponential distribution-based genetic algorithm for solving mixed-integer bilevel programming problems

Two classes of mixed-integer nonlinear bilevel programming problems are discussed. One is that the follower＇s functions are separable with respect to the follower＇s variables, and the other is that the follower＇s functions are convex if the follower＇s variables are not restricted to integers. A genetic algorithm based on an exponential distribution is proposed for the aforementioned problems. First, for each fixed leader＇s variable x, it is proved that the optimal solution y of the follower＇s mixed-integer programming can be obtained by solving associated relaxed problems, and according to the convexity of the functions involved, a simplified branch and bound approach is given to solve the follower＇s programming for the second class of problems. Furthermore, based on an exponential distribution with a parameter λ, a new crossover operator is designed in which the best individuals are used to generate better offspring of crossover. The simulation results illustrate that the proposed algorithm is efficient and robust.

Reduction and Analysis of a Max-Plus Linear System to a Constraint Satisfaction Problem for Mixed Integer Programming

This research develops a solution method for project scheduling represented by a max-plus-linear (MPL) form. Max-plus-linear representation is an approach to model and analyze a class of discrete-event systems, in which the behavior of a target system is represented by linear equations in max-plus algebra. Several types of MPL equations can be reduced to a constraint satisfaction problem (CSP) for mixed integer programming. The resulting formulation is flexible and easy-to-use for project scheduling;for example, we can obtain the earliest output times, latest task-starting times, and latest input times using an MPL form. We also develop a key method for identifying critical tasks under the framework of CSP. The developed methods are validated through a numerical example.

Combining Geographic Information Systems for Transportation and Mixed Integer Linear Programming in Facility Location-Allocation Problems

In this study, we aimed to assess the solution quality for location-allocation problems from facilities generated by the software TransCAD®?, a Geographic Information System for Transportation (GIS-T). Such facilities were obtained after using two routines together: Facility Location and Transportation Problem, when compared with optimal solutions from exact mathematical models, based on Mixed Integer Linear Programming (MILP), developed externally for the GIS. The models were applied to three simulations: the first one proposes opening factories and customer allocation in the state of Sao Paulo, Brazil;the second involves a wholesaler and a study of location and allocation of distribution centres for retail customers;and the third one involves the location of day-care centers and allocation of demand (0 - 3 years old children). The results showed that when considering facility capacity, the MILP optimising model presents results up to 37% better than the GIS and proposes different locations to open new facilities.

An efficient algorithm for multi-dimensional nonlinear knapsack problems

Multi-dimensional nonlinear knapsack problem is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to multiple separable nondecreasing constraints. This problem is often encountered in resource allocation, industrial planning and computer network. In this paper, a new convergent Lagrangian dual method was proposed for solving this problem. Cutting plane method was used to solve the dual problem and to compute the Lagrangian bounds of the primal problem. In order to eliminate the duality gap and thus to guarantee the convergence of the algorithm, domain cut technique was employed to remove certain integer boxes and partition the revised domain to a union of integer boxes. Extensive computational results show that the proposed method is efficient for solving large-scale multi-dimensional nonlinear knapsack problems. Our numerical results also indicate that the cutting plane method significantly outperforms the subgradient method as a dual search procedure.

Nonlinear Model-Based Process Operation under UncertaintyUsing Exact Parametric Programming

In the present work, two new, （multi-）parametric programming （mp-P）-inspired algorithms for the solutionof mixed-integer nonlinear programming （MINLP） problems are developed, with their main focus being onprocess synthesis problems. The algorithms are developed for the special case in which the nonlinearitiesarise because of logarithmic terms, with the first one being developed for the deterministic case, and thesecond for the parametric case （p-MINLP）. The key idea is to formulate and solve the square system of thefirst-order Karush-Kuhn-Tucker （KKT） conditions in an analytical way, by treating the binary variables and/or uncertain parameters as symbolic parameters. To this effect, symbolic manipulation and solution tech-niques are employed. In order to demonstrate the applicability and validity of the proposed algorithms, twoprocess synthesis case studies are examined. The corresponding solutions are then validated using state-of-the-art numerical MINLP solvers. For p-MINLP, the solution is given by an optimal solution as an explicitfunction of the uncertain parameters.

A Mixed-Integer Programming Formulation for a Simplified Model of the Double Row Layout Problem

The double row layout problem(DRLP)is to assign facilities on two rows in parallel so that the total cost of material handling among facilities is minimized.Since it is vital to save cost and enhance productivity,the DRLP plays an important role in many application fields.Nevertheless,it is very hard to handle the DRLP because of its complex model.In this paper,we consider a new simplified model for the DRLP(SM-DRLP)and provide a mixed integer programming(MIP)formulation for it.The continuous decision variables of the DRLP are divided into two parts:start points of double rows and adjustable clearances between adjacent facilities.The former one is considered in the new simplified model for the DRLP with the purpose of maintaining solution quality,while the latter one is not taken into account with the purpose of reducing computational time.To evaluate its performance,our SM-DRLP is compared with the model of a general DRLP and the model of another simplified DRLP.The experimental results show the efficiency of our proposed model.

重大突发公共卫生事件中的方舱医院建设情景重建研究

方舱医院建设是应对各类重大突发公共卫生事件的一项重要举措。现有研究大多从医学或政府管理视角定性地探讨方舱医院发挥的重要作用,还鲜有从情景重建视角研究方舱医院床位扩容的最优时空分布。本文首先构建针对重大突发公共卫生事件演化的SEIHRD模型,继而将方舱医院床位扩容问题构建为有限应急资源分配组合优化模型并设计免疫优化算法进行求解。测试结果显示,本文所给出的方舱医院床位扩容时空分布优化方案,能够对重大突发公共卫生事件中的方舱医院建设情景进行有效重建。方舱医院床位数量及其时间节点设置对累计感染者人数具有显著影响,这表明在疫情暴发初期尽早设立方舱医院,能够有效提升收治率、减少总感染人数。同时也要注意,应急救援资金投入存在阈值效应,需要设计合理的方舱医院床位扩容方案以避免应急预算资源的过度浪费。

铁路枢纽双编组站静态配流协同优化研究

枢纽内跨编组站进行协同配流有助于优化枢纽内的车流接续,提高全局配流质量。引入跨编组站协同配流思想,构建铁路枢纽双编组站静态配流协同优化模型,以最小化双编组站的配流总代价、最大化双编组站的总满轴列车数为优化目标,考虑车流量约束、列车到解编发作业与枢纽小运转列车走行的接续时间约束、出发列车满轴与不违编约束、调机资源使用约束。以列车等级、编组去向数及出发时刻排序作为配流代价。设计理想点算法将多目标转化为单目标进行求解,最后运用算例对模型及算法的有效性进行验证。结果表明,双编组站联合配流相较于两编组站单独配流,可使满轴列车总数增加1列、站存车总数减少13辆、配流总代价降低5.4%,从而达到更佳的配流效果。

耦合有机朗肯循环的换热网络全局优化

针对换热网络与有机朗肯循环耦合集成优化问题,建立了严谨的混合整数非线性规划(MINLP)模型。同时,通过添加与物流匹配的关键约束,剔除掉重复性的网络结构,开发了一种新型的枚举算法,将复杂的MINLP模型分解为混合整数线性规划(MILP)和非线性规划(NLP)两个子模型。迭代运行MILP模型,枚举出所有可行的网络结构;再利用全局求解器BARON优化每一个网络结构所对应的NLP模型,求得固定结构的年度总费用;最后对比所有网络结构的年度总费用,筛选出全局最优的设计方案。案例分析结果表明,该算法仅需16 s就能收敛至全局最优解,与文献相比,年度总费用降低33.4%,且所提出的网络结构约束能使重复性的网络结构数量减少81.25%,从而提高算法的优化求解效率。

考虑新能源随机波动和T接线的城市电网连锁故障风险评估

新能源的大量接入给城市电网的安全运行和重要用户可靠供电带来很大挑战,其功率的随机波动易引发电网出现连锁故障风险。提出了一种考虑新能源出力随机波动和城市电网110k V网架T接线开关投切的连锁故障风险评估方法。该方法在连锁故障发生概率和后果严重度的计算中都计及了系统状态的概率分布特性的影响,并采用基于半不变量法的概率潮流计算反映系统状态与新能源功率二者的概率分布特性之间的关系。另外,建立包含110 kV网架T接线开关投切的最小切负荷的混合整数非线性规划模型,并以最小切负荷量来表征系统在连锁故障的严重度。此优化模型通过决策故障下的各组T接线开关的投切状态,减少连锁故障下的切负荷量,进而有效降低连锁故障的风险。同时,通过机会约束描述重要用户负荷节点电压的安全运行范围,以确保重要用户负荷不停电的概率满足给定的置信水平,从而保证重要用户的安全可靠供电。最后,通过某个实际城市片区电网算例验证了所提出的连锁故障风险评估方法的正确有效性。

考虑空间需求不均的模块化公交线路运行方案优化研究

传统固定容量公交车辆难以应对公交线路上空间分布不均的需求。为解决这一问题,引入模块化公交车辆,通过编组与解编的方式实现车队在运行中的容量动态变化,以更贴合需求在空间上的变化。基于运行时空图重构的方法,建立描述模块化公交线路运行方案的优化模型,所构建模型为混合整数非线性规划(Mixed Integer-Nonlinear Program,MINLP)模型,模型决策变量包括车队的运行方案以及模块化公交单元的运行方案。为方便求解,采用时间离散化手段,通过一系列方法将所构建的MINLP模型转化为易于求解的混合整数线性规划(Mixed Integer-Linear Program,MILP)模型,并基于成都市真实公交线路与乘客需求数据进行案例分析。实验结果表明,与传统容量固定式公交相比,模块化公交的应用能够使乘客成本降低11.44%,运营成本降低31.35%,综合降低20.32%的系统总成本。敏感性分析实验结果分析了系统供给与需求变化对系统成本产生的影响。

基于MILP的轻量级密码算法ACE与SPIX的线性分析

研究了轻量级密码算法ACE与SPIX的线性性质.给出了环型与门组合结构精确的混合整数线性规划下的线性性质刻画,并将算法ACE与SPIX的非线性操作转化为环型与门组合.基于此构建了ACE置换与SLISCP置换的混合整数线性规划下的线性模型,求解模型得到了2至4步ACE置换与2至5步SLISCP置换最优的线性迹.证明了7步、12步ACE置换分别达到了128比特与320比特的安全目标,7步、13步SLISCP置换分别达到了128比特与256比特的安全目标.对于任意步数的ACE置换与SLISCP置换,认证加密算法ACE-AE-128与SPIX均能够抵抗明文处理阶段的线性区分攻击.

基于子系统规模调配的烯烃生产过程模拟与优化

针对单个烯烃生产系统节能潜力有限的问题,提出基于烯烃生产子系统规模调配的方法,构建混合整数非线性规划(MINLP)优化模型。以单位产量1 t×h^(-1)为基准规模,当丙烷脱氢和乙烷裂解的规模系数分别为50.0和89.4时(即产量分别为50.0 t×h^(-1)和89.4 t×h^(-1)),系统的能量回收率达到最大,为82.6%。与两者独立子系统相比,公用工程负荷减少502.7 MW,对应的中低压蒸气消耗量减少544.9 t×h^(-1),电能减少0.5 MW,碳排放量减少0.5 t×h^(-1),节能减排的效果非常显著。结果表明,多个系统间能量交互可以有效提高能量回收率,且最优的规模系数使系统整体能量回收率达到最大。

天然气管网稳态运行优化模型的非线性界增强方法

天然气管网稳态运行优化问题在提升能源使用效率、降低运行成本等多方面发挥着重要的作用。该问题由于网络结构复杂、规模大、非线性程度高,所以建模成的混合整数非线性规划模型求解难度非常大。本文基于混合整数线性规划的界增强方法,提出了适用于该问题结构的非线性界增强方法,能够缩紧变量的上下界,使得在线性化方法中更好地逼近原混合整数非线性规划模型。数值结果显示新的方法能够得到更优的可行解,并且加快了天然气管网稳态运行优化问题的求解。

基于自适应无人机数量的节时部署优化算法

为缩短未知环境下移动边缘计算(MEC)系统服务用户所需的平均时延,提高MEC系统服务质量(QoS),设计了一种基于多无人机(UAV)的MEC系统,并针对UAV数量大量增加、因用户平均时延减少呈现边际效应递减所带来的资源浪费问题,设计一种可变UAV数量的节时部署算法。MEC系统首先将UAV部署问题分解为一个双层嵌套问题,外层为最大覆盖问题(MCLP),内层为基于广义指派问题(GAP)的任务卸载问题,并将人为设置的惩罚项加入待优化目标中,在优化过程中使MEC系统UAV数量和用户所需平均时延之间达到平衡。部署算法设计了一种混合算法来针对嵌套问题进行求解,外层使用基于差分进化-蛇优化算法(DE-SO)的联合优化算法来解决UAV的部署覆盖问题,内层使用贪心算法来解决任务卸载问题。仿真实验结果表明,在多种UE分布环境下,相较于CS-G、SAO-G等算法,该算法在适应度、覆盖率等性能上取得了最优表现,相比寻优精度最高的对比算法,DE-SO-G在寻优精度上平均提升5.67%。

潮汐客流需求驱动的地铁列车不成对运行图节能优化方法

针对城市轨道交通客流潮汐现象引起的大客流方向乘客滞留和小客流方向运力虚靡且牵引能耗高的问题,本文提出一种结合快慢车和变编组的不成对运输组织策略,并结合变编组技术提升运力供给灵活度的同时减少运能浪费,此外,开行部分跨站快车加速车底周转。基于此,构建开行方案、时刻表与车底运用计划协同优化模型,决策列车的双向开行频率、编组类型、停站方案、首站发车时刻及车底周转计划,从而最小化乘客的总旅行时间和全线总牵引能耗成本;并设计定制的变邻域搜索算法求解混合整数非线性规划模型。广州地铁14号线案例结果表明:与实际的成对运输方案相比,本文不成对运行方案可以将乘客总旅行时间减少6.52%,全线总牵引能耗降低34.20%,总目标函数减少11.40%;快车的开行加速了车底周转,减少了6列上线列车单元数量,可以更好地实现不成对运输组织;变编组技术可以进一步提升不成对运输计划的灵活性,大幅缩减上线列车单元数量,使线路的平均满载率提升约20%,线路总牵引能耗优化率提升约33%。结合快慢车和变编组技术的不成对运输策略实现运力精准灵活配置的同时节约列车运行能耗成本,达到运营降本增效的目的。

基于弹性需求和动态定价的共享泊位分配

为解决共享车位管理中的车位分配与定价问题,考虑了价格变化对于用户不同停车时长选择的影响,分析在不同停车收费标准下用户停车时长选择的概率,并采用多项式拟合得到精细化的共享停车需求价格弹性函数。进而,为实现停车场价格的动态调整与车位分配,以平台收益最大与用户步行距离最小为目标,构建基于弹性需求和动态定价的泊位分配非线性混合整数规划模型,并设计了遗传算法。最后,设计了包含3个停车场共1000个泊位、共享平台运营时长为3 h的算例,对模型及算法加以验证,通过对比分析,基于弹性需求和动态定价的共享泊位分配方案相比于静态定价,实现平台收益增加19%且满足了大部分停车需求,说明动态定价下共享泊位分配模型及算法的有效性,为共享平台的车位管理提供了新思路。

考虑物料装卸点的过道布置问题及改进灰狼算法求解方法

针对制造和服务系统中假定物料装卸点重合以及设施间物流量对称的不足,结合实际生产布局对过道布置问题进行拓展,以最小化物流成本为目标,提出考虑物料装卸点及非对称流量的过道布置问题,并建立混合整数规划模型。根据问题与模型的特征,设计一种改进灰狼算法进行求解,该算法采用双层整数编码生成初始解,通过将收敛因子非线性化、比例权重动态化对原始灰狼算法进行改进。通过融合反向学习机制和种群更新机制进一步扩大搜索解空间,并添加双阈值停止准则降低多余的迭代次数。将该算法与LINGO求解器对5~49不同规模算例的计算结果进行比较,证明了模型的正确性以及算法的有效性。最后,运用该算法对初始过道布置问题进行求解,并与其他算法的求解结果进行比对,进一步证明了所提算法的优越性。