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 matheuristic for the firefighter problem on graphs

In this paper, we describe a computational study conducted on The Firefighter Problem (FFP ), which models fire spreading and containment in a graph. Once the fire breaks out on a set of vertices, the goal is to save as many vertices as possible with limited resources. Practical applications of the FFP occur in areas such as disease control and network security. The FFP is NP‐hard and heuristics have been proposed earlier. Our main contributions include improvements to an existing integer linear programming formulation that led to an average speedup of two to compute exact solutions. Moreover, we developed a novel matheuristic, a technique based on the interoperation between metaheuristics and mathematical programming. We performed extensive experiments on public benchmarks both for parameter tuning and for comparison of our results with those from the literature. A rigorous statistical analysis shows that our new matheuristic outperforms the existing approaches.     

Heuristics for the capacitated dispersion problem

In this paper, we investigate the adaptation of the greedy randomized adaptive search procedure (GRASP) and variable neighborhood descent (VND) methodologies to the capacitated dispersion problem. Dispersion and diversity problems arise in the placement of undesirable facilities, workforce management, and social media, among others. Maximizing diversity deals with selecting a subset of elements from a given set in such a way that the distance among the selected elements is maximized. We target here a realistic variant with capacity constraints for which a heuristic with a performance guarantee was previously introduced. In particular, we propose a hybridization of GRASP and VND implementing within the strategic oscillation framework. To evaluate the performance of our heuristic, we perform extensive experimentation to first set key search parameters, and then compare the final method with the previous heuristic. Additionally, we propose a mathematical model to obtain optimal solutions for small‐sized instances, and compare our solutions with the well‐known LocalSolver software.     

A study on the use of heuristics to solve a bilevel programming problem

The bilevel programming problem is characterized as an optimization problem that has another optimization problem in its constraints. The leader in the upper level and the follower in the lower level are hierarchically related where the leader's decisions affect both the follower's payoff function and allowable actions, and vice versa. One difficulty that arises in solving bilevel problems is that unless a solution is optimal for the lower level problem, it cannot be feasible for the overall problem. This suggests that approximate methods could not be used for solving the lower level problem, as they do not guarantee that the optimal solution is actually found. However, from the practical point of view near‐optimal solutions are often acceptable, especially when the lower level problem is too costly to be exactly solved thus rendering the use of exact methods impractical. In this paper, we study the impact of using an approximate method in the lower level problem, discussing how near‐optimal solutions on the lower level can affect the upper level objective function values. This study considers a bilevel production‐distribution planning problem that is solved by two intelligent heuristics hierarchically related: ant colony optimization for solving the upper level problem, and differential evolution method to solve the lower level problem.     

Hybridizations of GRASP with path relinking for the far from most string problem

Among the sequence selection and comparison problems, the far from most string problem (FFMSP) is one of the computationally hardest with applications in several fields, including molecular biology where one is interested in creating diagnostic probes for bacterial infections or in discovering potential drug targets. In this paper, we describe several heuristics that hybridize GRASP with different path‐relinking strategies, such as forward, backward, mixed, greedy randomized adaptive forward, and evolutionary path relinking. Experiments on a large set of both real‐world and randomly generated test instances indicate that these hybrid heuristics are both effective and efficient. In particular, the hybrid GRASP with evolutionary path relinking finds slightly better quality solutions compared to the other variants when running for the same number of iterations, while the hybrid with backward path relinking finds better quality solution within a fixed running time.     

A matheuristic approach for the minimum broadcast time problem using a biased random-key genetic algorithm

The Minimum Broadcast Time (MBT) is a well-known data dissemination problem whose goal is to find a broadcast scheme that minimizes the number of steps needed to execute the broadcast operation. The problem has many applications in distributed systems and, in particular, the Industry 4.0 domain. Because Industry 4.0 applications rely primarily on the use of large-scale machine to machine communications, they need data dissemination techniques that combine high reliability with low communication latency. This work proposes a Biased Random-Key Genetic Algorithm and a matheuristic for the MBT. We carry out experiments with our algorithms on instances commonly used in the literature (hypercube, shuffle exchange, cube-connected cycles, de Bruijn, Harary graphs), and also on massive synthetic instances (up to 1000 vertices), allowing to cover many possibilities of real industry topologies. Our proposal is also compared with state-of-the-art exact methods and heuristics. Experimental results show that our algorithm is able to outperform the best-known heuristics for the MBT, and also that it is a very good alternative for large instances that cannot be solved by current exact methods.     

A neural network approach for solving nonlinear bilevel programming problem

A neural network model is presented for solving nonlinear bilevel programming problem, which is a NP-hard problem. The proposed neural network is proved to be Lyapunov stable and capable of generating approximal optimal solution to the nonlinear bilevel programming problem. The asymptotic properties of the neural network are analyzed and the condition for asymptotic stability, solution feasibility and solution optimality are derived. The transient behavior of the neural network is simulated and the validity of the network is verified with numerical examples.     

一种求解旅行商问题的离散状态转移算法

本文提出了一种求解旅行商问题的离散状态转移算法,设计了交换、平移、对称等3种转移算子,讨论了算法的收敛性和时间复杂度等问题,研究了参数对算法的影响.实验结果表明,与模拟退火算法及蚁群算法等经典组合优化算法相比,该算法具有耗时短、寻优能力强等优点,这也表明了状态转移算法的适应性很好.     

Genetic algorithm for the personnel assignment problem with multiple objectives

The assignment problem is a well-known graph optimization problem defined on weighted-bipartite graphs. The objective of the standard assignment problem is to maximize the summation of the weights of the matched edges of the bipartite graph. In the standard assignment problem, any node in one partition can be matched with any node in the other partition without any restriction. In this paper, variations of the standard assignment problem are defined with matching constraints by introducing structures in the partitions of the bipartite graph, and by defining constraints on these structures. According to the first constraint, the matching between the two partitions should respect the hierarchical-ordering constraints defined by forest and level graph structures produced by using the nodes of the two partitions respectively. In order to define the second constraint, the nodes of the partitions of the bipartite graph are distributed into mutually exclusive sets. The set-restriction constraint enforces the rule that in one of the partitions all the elements of each set should be matched with the elements of a set in the other partition. Even with one of these constraints the assignment problem becomes an NP-hard problem. Therefore, the extended assignment problem with both the hierarchical-ordering and set-restriction constraints becomes an NP-hard multi-objective optimization problem with three conflicting objectives; namely, minimizing the numbers of hierarchical-ordering and set-restriction violations, and maximizing the summation of the weights of the edges of the matching. Genetic algorithms are proven to be very successful for NP-hard multi-objective optimization problems. In this paper, we also propose genetic algorithm solutions for different versions of the assignment problem with multiple objectives based on hierarchical and set constraints, and we empirically show the performance of these solutions.     

Fuzzy bilevel programming with multiple non-cooperative followers: model,algorithm and application

In centralized decision problems, it is not complicated for decision-makers to make modelling technique selections under uncertainty. When a decentralized decision problem is considered, however, choosing appropriate models is no longer easy due to the difficulty in estimating the other decision-makers’ inconclusive decision criteria. These decision criteria may vary with different decision-makers because of their special risk tolerances and management requirements. Considering the general differences among the decision-makers in decentralized systems, we propose a general framework of fuzzy bilevel programming including hybrid models (integrated with different modelling methods in different levels). Specially, we discuss two of these models which may have wide applications in many fields. Furthermore, we apply the proposed two models to formulate a pricing decision problem in a decentralized supply chain with fuzzy coefficients. In order to solve these models, a hybrid intelligent algorithm integrating fuzzy simulation, neural network and particle swarm optimization based on penalty function approach is designed. Some suggestions on the applications of these models are also presented.     

一种多目标不等面积设施布局问题的启发式算法

多目标不等面积设施布局问题（UA-FLP）是将一些不等面积设施放置在车间内进行布局,要求优化多个目标并满足一定的限制条件。以物料搬运成本最小和非物流关系强度最大来建立生产车间的多目标优化模型,并提出一种启发式算法进行求解。算法采用启发式布局更新策略更新构型,通过结合基于自适应步长梯度法的局部搜索机制和启发式设施变形策略来处理设施之间的干涉性约束。为了得到问题的Pareto最优解集,提出了基于Pareto优化的局部搜索和基于小生境技术的全局优化方法。通过两个典型算例对算法性能进行测试,实验结果表明,所提出的启发式算法是求解多目标UA-FLP的有效方法。     

A Binary Particle Swarm Optimization for the Minimum Weight Dominating Set Problem

统治集合问题(MWDSP ) 的最小的重量是有很多真实世界的应用的一个 NP 难的问题。几个启发式的算法被介绍了生产好优秀答案。然而,他们的答案时间作为例子增加的尺寸很快速成长。在这份报纸,我们为近似解决 MWDSP 建议二进制粒子群优化(FBPSO ) 。基于 MWDSP 的特征,这条途径设计更新统治指导搜索到一个有希望的区域的一个新位置。重申的贪婪禁忌搜索被用来快速提高答案质量。另外,几随机的策略被采用多样化搜索并且阻止早熟的集中。这些方法维持在探索和利用之间的好平衡。在 FBPSO 能识别的 106 组 1 060 例子表演的试验性的研究在一短跑时间接近最佳的答案。在 FBPSO 获得的答案和最好已知的答案之间的平均偏差是 0.441% 。而且, FBPSO 的平均答案时间多不到另外的存在算法的。与增加例子尺寸,特别地, FBPSO 的答案时间比另外的存在算法的更慢慢地成长。     

An exact algorithm for the budget-constrained multiple knapsack problem

This paper is concerned with a variant of the multiple knapsack problem (MKP), where knapsacks are available by paying certain ‘costs’, and we have a fixed budget to buy these knapsacks. Then, the problem is to determine the set of knapsacks to be purchased, as well as to allocate items into the accepted knapsacks in such a way as to maximize the net total profit. We call this the budget-constrained MKP and present a branch-and-bound algorithm to solve this problem to optimality. We employ the Lagrangian relaxation approach to obtain an upper bound. Together with the lower bound obtained by a greedy heuristic, we apply the pegging test to reduce the problem size. Next, in the branch-and-bound framework, we make use of the Lagrangian multipliers obtained above for pruning subproblems, and at each terminal subproblem, we solve MKP exactly by calling the MULKNAP code [D. Pisinger, An exact algorithm for large multiple knapsack problem, European J. Oper. Res. 114 (1999), pp. 528–541]. Thus, we were able to solve test problems with up to 160,000 items and 150 knapsacks within a few minutes in our computing environment. However, solving instances with relatively large number of knapsacks, when compared with the number of items, still remains hard. This is due to the weakness of MULKNAP to this type of problems, and our algorithm inherits this weakness as well.     

解决多目标优化问题的差分进化算法研究进展

差分进化(differential evolution,DE)是一种简单但功能强大的进化优化算法.由于其优秀的性能,其诞生之日起就吸引了各国研究人员的关注.作为一种基于群体的全局性启发式搜索算法,差分进化算法在科学和工程中有许多成功的应用.本文对解决多目标优化问题的差分进化算法研究进行了综述,对差分进化的基本概念进行了详细的描述,给出了几种解决多目标优化问题的差分进化算法变体,并且给出了差分进化算法解决多目标优化问题的理论分析,最后,给出了差分进化算法解决多目标优化问题的工程应用,并指出了未来具有挑战性的研究领域.     

一类非线性两层规划问题的递阶优化解法

提出一种求解一类非线性两层规划问题的新方法．通过引入解耦向量将非线性两层规划问题分解为独立且易于求解的子问题，利用两级递阶结构第1级求解若干优化的子问题，而在第2级利用第1级求解的结果调整解耦向量．所提出的方法借助于分解一协调原理并按迭代方式最终求得问题的最优解．对于含整数的规划问题，通过连续化处理后也可按该方法方便地求解．算例表明所提出的算法是简便而有效的．     

A note on the quadratic assignment problem

The quadratic assignment problem （QAP） is one of the most interesting and challenging combinatorial optimization problems in existence and one of the most difficult problems in the NP-hard class. Many real-life problems in several areas such as facilities location parallel and distributed computing, combinatorial data analysis and combinatorial optimization problems which have many application in computer engineering and industry can be formulated as a QAP. In this paper, the author give a short note on the QAP, giving our rounding approach with the survey of other algorithms that used to solve this important problem.     

Handling multiple objectives with biogeography-based optimization

Biogeography-based optimization (BBO) is a new evolutionary optimization method inspired by biogeography. In this paper, BBO is extended to a multi-objective optimization, and a biogeography-based multi-objective optimization (BBMO) is introduced, which uses the cluster attribute of islands to naturally decompose the problem. The proposed algorithm makes use of nondominated sorting approach to improve the convergence ability effciently. It also combines the crowding distance to guarantee the diversity of Pareto optimal solutions. We compare the BBMO with two representative state-of-the-art evolutionary multi-objective optimization methods, non-dominated sorting genetic algorithm-II (NSGA-II) and archive-based micro genetic algorithm (AMGA) in terms of three metrics. Simulation results indicate that in most cases, the proposed BBMO is able to find much better spread of solutions and converge faster to true Pareto optimal fronts than NSGA-II and AMGA do.     

基于极值动力学的自组织优化算法求解TSP问题

旅行商问题(traveling salesman problem, TSP)具有很强的理论研究和工程应用价值. 在定义离散状态变量和局部适应度的基础上, 分析了TSP优化解的微观特征; 将自组织临界(self-organized criticality, SOC)的概念引入到组合优化领域, 提出了一种基于极值动力学的自组织优化算法. 该算法利用快速下降和间断涨落的动态搜索过程, 高效地遍历解空间中的局部最优解. 针对TSPLIB中典型实例, 计算结果表明其求解效率和优化性能均优于模拟退火和遗传算法等优化方法. 文中算法提供了一种全新的思路, 有助于从系统角度理解组合优化问题的复杂性, 并分析合理的优化动力学过程.     

A genetic algorithm approach to the machine-component grouping problem with multiple objectives

The formation of machine cells and component families is a problem that has engaged the attention of researchers in group technology for over a decade. This paper proposes a bi-criteria mathematical model with a solution procedure based on a genetic algorithm. Trials on a sample problem suggest that the proposed algorithm can be a powerful tool that can be gainfully employed in a cellular manufacturing environment. The algorithm is inherently parallel and is capable of super linear speed-up in multi-processor systems.     

Model and algorithm for bilevel multisized terminal location‐routing problem for the last mile delivery

The last mile delivery is regarded as one of the most expensive but least efficient stretches in the business‐to‐customer supply chain. Designing the last mile delivery system in a lean way is crucial to serve customers efficiently and economically. To address this issue, we propose a bilevel multisized terminal location‐routing problem (BL‐MSTLRP) with simultaneous home delivery and customer's pickup services. The solution method is proposed by combining genetic algorithm (GA) and simulated annealing (SA), called self‐adaptive SGA. Studies for designing the last mile delivery system in a real‐world environment indicate the validity of the proposed model based on the comparison of different scenarios. Numerical experiments are also conducted to evaluate the performance of the presented SGA. Computational results show that the hybrid approach efficiently solves the BL‐MSTLRP.