Infeasibility test algorithm and fast repair algorithm of job shop scheduling problem

To diagnose the feasibility of the solution of a job-shop scheduling problem（JSSP）,a test algorithm based on diagraph and heuristic search is developed and verified through a case study.Meanwhile,a new repair algorithm for modifying an infeasible solution of the JSSP to become a feasible solution is proposed for the general JSSP.The computational complexity of the test algorithm and the repair algorithm is both O（n） under the worst-case scenario,and O（2J＋M） for the repair algorithm under the best-case scenario.The repair algorithm is not limited to specific optimization methods,such as local tabu search,genetic algorithms and shifting bottleneck procedures for job shop scheduling,but applicable to generic infeasible solutions for the JSSP to achieve feasibility.

Infeasibility Diagnosis on the Linear Programming Model of Production Planning in Refinery

In order to effectively diagnose the infeasible linear programming (LP) model of production planning in refinery, the article proposed three stages strategy based on constraints’ classification and infeasibility analysis. Generally, infeasibility sources involve structural inconsistencies and data errors, and the data errors are further classified intoⅠ, Ⅱ and Ⅲ. The three stages strategy are: (1) Check data when they are inputted to detect data error Ⅰ and repair them; (2) Inspect data whether they are accorded with material balance before solving the LP model to identify data error Ⅱ and repair them; (3) Find irreducible inconsistent system of infeasible LP model and give diagnosis information priority-ranked to recognize data error Ⅲ and structural inconsistencies. These stages could be automatically executed by computer, and the approach has been applied to diagnose the infeasible model well in our graphic I/O petro-chemical industry modeling system.

Evaluation of the sustainable development level of countries along the Belt and Road and its impact factors:Empirical analysis based on the Super-efficiency slacks-based measure and Tobit measure models

Sustainable development is an important component of the Belt and Road Initiative(BRI)and is of great significance for evaluating the levels of sustainable development of countries along this route(henceforth,BRI countries).Therefore,this study aims to identify the factors that influence the levels of sustainable development of BRI countries in a reasonable and objective manner.Eventually,this study employs the super efficiency slacks-based measure(Super-SBM)model,which considers unexpected outputs to measure the level of sustainable development of BRI countries.The dynamic change and composition of the sustainable development level of these countries are calculated using the global Malmquist-Luenberger index.Furthermore,the Tobit model is used to identify the factors influencing the level of sustainable development of BRI countries in general and in various categories.The empirical results suggest the following points.(a)The overall level of sustainable development of BRI countries is low,whereas those of high-income and middle-and high-income countries are relatively high.(b)The overall sustainable development levels of BRI countries declined to a certain extent in 2008 owing to the effect of the financial crisis,.However,the sustainable development level of other countries,barring low-income countries,has gradually increased since 2011.(c)Since 2008,technological progress has replaced technical efficiency as the main driving force behind the improvement of the sustainable development level of BRI countries.(d)A U-shaped relationship is observed between the economic and sustainable development levels of these countries.(e)The level of science and technology and the proportion of renewable energy consumption can promote the sustainable development of these countries.Moreover,a negative correlation exists between the level of opening to the outside world and that of sustainable development of countries that mainly export resource-based products and are dominated by labor-intensive export industries.Barring low-income countries,the energy structure plays an effective role in improving the level of sustainable development.Finally,the study presents suggestions for China in the process of coping with the sustainable development of relevant countries during its promotion of the BRI.

Diagnosis and Resolution of Infeasibility in the Constraint Method for Solving Multi Objective Linear Programming Problems

In this paper we discuss about infeasibility diagnosis and infeasibility resolution, when the constraint method is used for solving multi objective linear programming problems. We propose an algorithm for resolution of infeasibility, which is a combination of interactive, weighting and constraint methods.Numerical examples are provided to illustrate the techniques developed.

Research on Smart Growth of Sustainable Cities Based on Information Entropy and Super-Efficiency DEA Model

Since the “smart growth” was put forward in the late 90s, it has become an accepted design idea and concept in the field of urban design in the world, and has been deeply studied and applied. In order to better promote “smart grown”, we set up an evaluation system, which consists of eleven indicators. In this paper, Oxford City and Fengzhen City are used as the objects of the study. Then smart growth evaluation model is established. The weight of the index is calculated by the entropy method. We use the model to evaluate the development plans of the two cities, from which to calculate the contribution of the indicators on the level of smart growth. Finally, we use the super-efficient data envelopment analysis model (DEA) to rank the importance of the indicators to the smart growth. The results show that the level of smart growth in Oxford is higher than that in Fengzhen. And “Multifunctional Building Density in Central City”, “The Density of Public Area in Central City” two indicators account for more than 36% weight. The contribution of the two indicators is also located in the top two indicators. Two cities focus on the direction of smart growth is also different. In summary, the differences between China and Western countries in urban planning are mainly focused on housing and public resources.

优化船舶操纵性能计算分析

针对优化船舶操纵收敛效果不佳问题,引入多目标进化计算法优化船舶性能设计。基于多目标船舶操纵进化计算法,构建以船舶旋回直径和直线航行能力为评估指标的优化模型,采用基本不可行解差分算子,建立多目标优化计算法架构;选取优化基本不可行解,制定新的选择标准。与MOEA/D算法、加权算法和pareto算法比较分析结果表明,本研究算法可为船舶研究和设计人员提供更多优化船舶操纵设计策略的结果,从根本上提升了设计策略的收敛效能。

针对MUS求解问题的加强剪枝策略

极小不可满足子集(minimal unsatisfiable subsets,MUS)的求解是布尔可满足性问题中的一个重要子问题.对于一个给定的不可满足问题,其MUS的求解能够反映出问题中导致其不可满足的关键原因.然而,MUS的求解是一项极其耗时的任务,不同的剪枝过程将直接影响到搜索空间的大小、算法的迭代次数,从而影响算法的求解效率.提出一种针对MUS求解的加强剪枝策略ABC(accelerating by critical MSS),依据MSS、MCS、MUS这3者之间的对偶性和碰集关系特点,提出cMSS和subMUS概念,并总结出4条性质,即每个MUS必是subMUS的超集,进而在避免对MCS的碰集进行求解的情况下有效利用MUS和MCS互为碰集的特征,有效避免求解碰集时的时间开销.当subMUS不可满足时,则subMUS是唯一的MUS,算法将提前结束执行;当subMUS可满足时,则剪枝掉此节点,进而有效避免对求解空间中的冗余空间进行搜索.同时,通过理论证明ABC策略的有效性,并将其应用于目前最高效的单一化模型算法MARCO和双模型算法MARCO-MAM,在标准测试用例下的实验结果表明,该策略可以有效地对搜索空间进行进一步剪枝,从而提高MUS的枚举效率.

一种基于协同演化的自适应约束多目标进化算法

约束多目标优化(CMOP)问题的求解旨在将有限的搜索资源合理地配置到约束条件的满足与目标函数的优化2个方面,但问题约束的日趋复杂给求解算法带来了巨大挑战。提出一种基于协同演化的自适应约束多目标进化算法,该算法同时进化2个功能互补的种群(主种群和存档种群),使算法在求解复杂约束问题时能够实现约束处理与目标优化之间的良好平衡。首先,主种群进行双重繁殖,首次繁殖过程通过动态适应度分配函数自适应地利用不可行解所携带的有价值信息,使种群在进化前期强调对目标函数的优化,后期强调可行性,二次繁殖则与存档种群进行合作,以提高种群收敛性并维护多样性。然后,提出一种基于角度的选择方案更新存档种群,在保证种群良好多样性的同时保持种群向Pareto前沿的搜索压力。最后,与5种先进的约束多目标进化算法在33个基准问题上进行对比实验,结果表明,所提出的算法在解决各类CMOP问题时与对比算法相比更具优势,其效率平均提高了约67%。

A Combined Homotopy Infeasible Interior-Point Method for Convex Nonlinear Programming

In this paper, on the basis of the logarithmic barrier function and KKT conditions, we propose a combined homotopy infeasible interior-point method （CHIIP） for convex nonlinear programming problems. For any convex nonlinear programming, without strict convexity for the logarithmic barrier function, we get different solutions of the convex programming in different cases by CHIIP method.

A New Infeasible Interior-point Method for Linear Complementarity Problem Based on Full Newton Step

This paper proposes an infeasible interior-point algorithm with full-Newton step for linear complementarity problem,which is an extension of Roos about linear optimization. The main iteration of the algorithm consists of a feasibility step and several centrality steps. At last,we prove that the algorithm has O(nlog n/ε) polynomial complexity,which coincides with the best known one for the infeasible interior-point algorithm at present.

AN INFEASIBLE-INTERIOR-POINT PREDICTOR-CORRECTOR ALGORITHM FOR THE SECOND-ORDER CONE PROGRAM

A globally convergent infeasible-interior-point predictor-corrector algorithm is presented for the second-order cone programming （SOCP） by using the Alizadeh- Haeberly-Overton （AHO） search direction. This algorithm does not require the feasibility of the initial points and iteration points. Under suitable assumptions, it is shown that the algorithm can find an -approximate solution of an SOCP in at most O（√n ln（ε0/ε）） iterations. The iteration-complexity bound of our algorithm is almost the same as the best known bound of feasible interior point algorithms for the SOCP.

A NEW FRAMEWORK OF PRIMAL-DUAL INFEASIBLE INTERIOR-POINT METHOD FOR LINEAR PROGRAMMING

On the basis of the formulations of the logarithmic barrier function and the idea of following the path of minimizers for the logarithmic barrier family of problems the so called "centralpath" for linear programming, we propose a new framework of primal-dual infeasible interiorpoint method for linear programming problems. Without the strict convexity of the logarithmic barrier function, we get the following results: (a) if the homotopy parameterμcan not reach to zero,then the feasible set of these programming problems is empty; (b) if the strictly feasible set is nonempty and the solution set is bounded, then for any initial point x, we can obtain a solution of the problems by this method; (c) if the strictly feasible set is nonempty and the solution set is unbounded, then for any initial point x, we can obtain a (?)-solution; and(d) if the strictly feasible set is nonempty and the solution set is empty, then we can get the curve x(μ), which towards to the generalized solutions.

A Modified Full-NT-Step Infeasible Interior-Point Algorithm for SDP Based on a Specific Kernel Function

This paper proposes a new full Nesterov-Todd(NT) step infeasible interior-point algorithm for semidefinite programming. Our algorithm uses a specific kernel function, which is adopted by Liu and Sun, to deduce the feasibility step. By using the step, it is remarkable that in each iteration of the algorithm it needs only one full-NT step, and can obtain an iterate approximate to the central path. Moreover, it is proved that the iterative bound corresponds with the known optimal one for semidefinite optimization problems.

A Primal-Dual Infeasible-Interior-Point Algorithm for Multiple Objective Linear Programming Problems

A primal-dual infeasible interior point algorithm for multiple objective linear programming (MOLP) problems was presented. In contrast to the current MOLP algorithm. moving through the interior of polytope but not confining the iterates within the feasible region in our proposed algorithm result in a solution approach that is quite different and less sensitive to problem size, so providing the potential to dramatically improve the practical computation effectiveness.

A New Full-NT-Step Infeasible Interior-Point Algorithm for SDP Based on a Specific Kernel Function

In this paper, we propose a new infeasible interior-point algorithm with full NesterovTodd (NT) steps for semidefinite programming (SDP). The main iteration consists of a feasibility step and several centrality steps. We used a specific kernel function to induce the feasibility step. The analysis is more simplified. The iteration bound coincides with the currently best known bound for infeasible interior-point methods.

Multi-Objective Genetic Algorithm to Design Manufacturing Process Line Including Feasible and Infeasible Solutions in Neighborhood

This paper treats multi-objective problem for manufacturing process design. A purpose of the process design is to decide combinations of work elements assigned to different work centers. Multiple work elements are ordinarily assigned to each center. Here, infeasible solutions are easily generated by precedence relationship of work elements in process design. The number of infeasible solutions generated is ordinarily larger than that of feasible solutions generated in the process. Therefore, feasible and infeasible solutions are located in any neighborhood in solution space. It is difficult to seek high quality Pareto solutions in this problem by using conventional multi-objective evolutional algorithms. We consider that the problem includes difficulty to seek high quality solutions by the following characteristics： （1） Since infeasible solutions are resemble to good feasible solutions, many infeasible solutions which have good values of objective functions are easily sought in the search process, （2） Infeasible solutions are useful to select new variable conditions generating good feasible solutions in search process. In this study, a multi-objective genetic algorithm including local search is proposed using these characteristics. Maximum value of average operation times and maximum value of dispersion of operation time in all work centers are used as objective functions to promote productivity. The optimal weighted coefficient is introduced to control the ratio of feasible solutions to all solutions selected in crossover and selection process in the algorithm. This paper shows the effectiveness of the proposed algorithm on simple model.

计及电压不可行分区的配电网无功规划方法

为了高效解决中大型配电系统的无功规划,提出一种计及电压不可行分区的配电网无功规划方法。首先,在电压不可行节点概念基础上,定义电压不可行分区,进而构建配电网无功优化模型。该模型包含无功补偿选址与定容、降损与无功容量优化2个子模型。前者以消除电压异常节点为目标;后者则以降低有功损耗及补偿容量为目标,同时将电压质量作为约束条件纳入目标函数。考虑到无法准确掌握配电拓扑中各节点负荷,定义两种基于系统总负荷的负荷分配模型,研究不同负荷场景对节点电压分布影响。然后,采用改进的引力搜算算法求解无功优化模型。最后,通过对某实际34节点10 kV配电线路进行仿真分析,验证所提规划方法的有效性。

Dynamic analysis of agricultural green development efficiency in China: Spatiotemporal evolution and influencing factors

Green development of agriculture is important for achieving coordinated and high-quality regional development for China. Using provincial data from 1990 to 2020, this work explored the dynamics of agricultural green development efficiency of 31 provinces in China, its spatiotemporal characteristics, and its driving factors using a super-efficiency slacks-based measure(Super-SBM), the Malmquist productivity index(MPI), spatial autocorrelation, and a geographic detector. Results showed that the overall agricultural green development efficiency showed a U-shaped trend, suggesting a low level of efficiency. Although a gradient difference was visible among eastern, central, and western regions, the efficiency gap narrowed each year. Technological progress and efficiency both promoted agricultural green development efficiency, especially technological progress. Agricultural green development efficiency had significant spatial aggregation characteristics, but Moran’s Ⅰ result showed a downward trend from 2015 to 2020, indicating a risk of spatial dispersion in the later stage. The provinces with high agricultural green development efficiency were mainly concentrated in the eastern region, while those with low efficiency were concentrated in the central and western regions. Agricultural green development efficiency was influenced by various factors, which showed differences according to time and region. The impact of the labor force’s education level and technological progress increased during the study period, and significantly facilitated agricultural green development efficiency in the eastern region, while the central and western regions were still affected by the scale level and environmental regulation, reflecting the advantages of the eastern region in terms of economy and technology. In the future, strengthening agricultural scientific and technological innovation and deepening interprovincial cooperation can help further improve the level of green agricultural development. In addition, local governments should formulate more precise local agricultural support policies based on macro-level policies and local conditions.

基于改进的动态多种群粒子群优化算法的配电网重构

提出了一种改进的动态多种群粒子群优化算法(DMS-PSO)的配电网重构算法,引入了基于集合的更新策略来解决组合问题,并结合邻域的学习策略来提高算法的局部搜索能力。此外,为了解决较大比例的拓扑不可行解问题,提出了修复机制。最后,在PG&E 69节点系统仿真结果表明,具有较高的精度和计算效率。

一种从目标空间反向引导种群进化的进化算法

目前进化算法大多是通过解从决策空间到目标空间的映射,来判断解的质量。针对约束多目标优化问题,将极限学习机代理模型与不可行解存档方法相结合,提出一种通过目标向量反向预测来引导决策空间种群进化的算法。在CTP和TYPE系列的测试问题上进行了HV度量、IGD度量的性能测试。与几种经典的算法比较,该算法在大多情况下都表现出具有竞争力的性能,且在高难度问题下比其他算法表现更好。