Filtering algorithms for the multiset ordering constraint

Constraint programming (CP) has been used with great success to tackle a wide variety of constraint satisfaction problems which are computationally intractable in general. Global constraints are one of the important factors behind the success of CP. In this paper, we study a new global constraint, the multiset ordering constraint, which is shown to be useful in symmetry breaking and searching for leximin optimal solutions in CP. We propose efficient and effective filtering algorithms for propagating this global constraint. We show that the algorithms maintain generalised arc-consistency and we discuss possible extensions. We also consider alternative propagation methods based on existing constraints in CP toolkits. Our experimental results on a number of benchmark problems demonstrate that propagating the multiset ordering constraint via a dedicated algorithm can be very beneficial.     

A hybrid approach based on stochastic competitive Hopfield neural network and efficient genetic algorithm for frequency assignment problem

This paper presents a hybrid efficient genetic algorithm (EGA) for the stochastic competitive Hopfield (SCH) neural network, which is named SCH–EGA. This approach aims to tackle the frequency assignment problem (FAP). The objective of the FAP in satellite communication system is to minimize the co-channel interference between satellite communication systems by rearranging the frequency assignment so that they can accommodate increasing demands. Our hybrid algorithm involves a stochastic competitive Hopfield neural network (SCHNN) which manages the problem constraints, when a genetic algorithm searches for high quality solutions with the minimum possible cost. Our hybrid algorithm, reflecting a special type of algorithm hybrid thought, owns good adaptability which cannot only deal with the FAP, but also cope with other problems including the clustering, classification, and the maximum clique problem, etc. In this paper, we first propose five optimal strategies to build an efficient genetic algorithm. Then we explore three hybridizations between SCHNN and EGA to discover the best hybrid algorithm. We believe that the comparison can also be helpful for hybridizations between neural networks and other evolutionary algorithms such as the particle swarm optimization algorithm, the artificial bee colony algorithm, etc. In the experiments, our hybrid algorithm obtains better or comparable performance than other algorithms on 5 benchmark problems and 12 large problems randomly generated. Finally, we show that our hybrid algorithm can obtain good results with a small size population.     

The fixed set search applied to the power dominating set problem

In this article, we focus on solving the power dominating set problem and its connected version. These problems are frequently used for finding optimal placements of phasor measurement units in power systems. We present an improved integer linear program (ILP) for both problems. In addition, a greedy constructive algorithm and a local search are developed. A greedy randomised adaptive search procedure (GRASP) algorithm is created to find near optimal solutions for large scale problem instances. The performance of the GRASP is further enhanced by extending it to the novel fixed set search (FSS) metaheuristic. Our computational results show that the proposed ILP has a significantly lower computational cost than existing ILPs for both versions of the problem. The proposed FSS algorithm manages to find all the optimal solutions that have been acquired using the ILP. In the last group of tests, it is shown that the FSS can significantly outperform the GRASP in both solution quality and computational cost.     

一种新的求解多维背包问题的分散算法

为了避免蚁群算法在优化搜索过程中易陷入局部最优和早熟收敛,提出一种求解多维背包问题的新型分散搜索算法。该算法是把蚁群算法的构解方法引入到分散搜索算法中,在搜索过程中,既考虑解的质量,又考虑解的分散性。同时,该分散算法还采用了动态更新参考集与阈值接收算法的阈值参数,以控制搜索空间来加快收敛速度。通过选取国际通用MDKP实例库中的多个实例进行测试表明,该算法可以避免陷入局部最优解,能提高全局寻优能力,其结果优于其他现有的方法,并获得了较好的结果。     

求解TSP问题的多级归约算法

TSP(traveling salesman problem)问题是最经典的NP-hard组合优化问题之一.长期以来,人们一直在寻求快速、高效的近似算法,以便在合理的计算时间内解决大规模问题.由于对较大规模的问题,目前的近似算法尚不能在较短的时间内给出高质量的解,因此提出了多重归约算法.该算法的基本原理是通过对TSP问题的局部最优解与全局最优解之间关系的分析,发现对局部最优解的简单的相交操作能以很高的概率得到全局最优解的部分解.利用这些部分解可以大大缩小原问题的搜索空间,同时也不会降低搜索的性能.这就是所谓的归约原理.再通过多次归约使问题的规模降到足够小,然后对这个较小规模的实例直接用已有的算法求解,最后通过相反的次序拼接部分解,最终得到一个合法的解.在TSPLIB(traveling salesman problem library)中,典型实例上的实验结果表明,此算法在求解质量和求解速度上与目前已知的算法相比有较大的改进.     

Handicapped Person Transportation: An application of the Grouping Genetic Algorithm

An effective method based on the Genetic Algorithms is proposed to solve the Handicapped Person Transportation problem, which is a real-life application for pickup and delivery problems. In these problems, vehicles have to transport (clients, loads, etc.,) from their locations to different destinations (hospitals, shop centres, etc.). The objective of this paper is to implement Grouping Genetic Algorithm to find optimal (or close to optimal) routes for transporting handicapped people in terms of service quality and number of used vehicles. This algorithm is a stochastic search method based on randomized operators for combining solutions and producing better ones. The proposed algorithm has been applied on the handicapped persons transportation problem in the city of Brussels, Belgium. The obtained results are better than the manually generated solutions in terms of service quality and computational effort.     

求解GCP问题的ILSBR算法

图着色问题（GCP,Graph Coloring Problem）是经典的NP-Hard组合优化问题之一。长期以来,人们一直在寻求快速、高效的启发式算法,以便在合理的计算时间内解决大规模问题。由于对规模较大的问题,目前的启发式算法尚不能在较短的时间内给出高质量的解,因此提出了一种基于全局最优解和局部最优解关系的ILS算法（ILSBR）。该算法的基本原理是通过对GCP问题的局部最优解和全局最优解之间关系的分析,发现对局部最优解的简单的相交操作能以很高的概率得到全局最优解的部分解。利用这些部分解构造一种新的扰动策略（RLG重着色）,并将其应用到传统的ILS算法中。在DIMACS标准集中,典型实例上的实验结果表明,采用RBILS算法在求解质量不变的情况下,求解速度上与目前的已知算法相比有较大的改进。     

一种求解TSP问题的离散蝙蝠算法

蝙蝠算法是一种新型的群智能优化算法,在求解连续域优化问题上取得了较好的优化效果,但在离散优化领域的应用较少。研究了求解TSP问题的离散蝙蝠算法,设计了相关操作算子实现算法的离散化,并引入逆序操作使算法跳出局部最优。对TSPLIB标准库中若干经典实例进行测试并与粒子群和遗传算法进行对比分析,结果表明设计的离散蝙蝠算法无论在求解质量还是求解效率上都有明显优势,是一种高效的优化算法。     

全局与局部模型交替辅助的差分进化算法

为求解实际复杂工程应用中的高维计算费时优化问题,提出一种全局与局部代理模型交替辅助的差分进化算法。利用历史样本训练全局和局部代理模型,通过交替搜索全局和局部代理模型得到模型最优解并对其进行真实目标函数评价,实现探索和开采的平衡以减少真实目标函数的计算次数,同时通过针对性地选择个体进行真实目标函数计算,辅助算法快速找到目标函数的较优解。在15个低维测试问题和14个高维测试问题上的实验结果表明,在有限的计算资源情况下,该算法在12个低维测试问题上相较于最优重启策略代理辅助的社会学习粒子群优化算法、基于主动学习的代理模型辅助的粒子群优化算法等表现更好,在7个高维测试问题上相较于高斯过程辅助的进化算法、代理模型辅助的分层粒子群优化算法、求解高维费时问题的代理辅助的多种群优化算法等能找到目标函数的更优解。     

A mixed integer linear program and tabu search approach for the complementary edge covering problem

In this paper we study a complementary edge covering problem (CECP) as a variant of the total edge covering problem (TECP) which has application in the area of facility location. Unlike TECP, the partial cover of an edge through vertices is allowed in CECP such that in a feasible solution the entire edge will be covered. We propose a new mixed integer linear formulation for the problem. A number of size reduction rules are proposed which speed up getting optimal solution(s). Since the CECP is NP-Hard, a solution method based on tabu search is designed to search for optimal or near-optimal solutions. Computational experiments are carried out to evaluate effectiveness of the proposed mathematical formulation and the modified tabu search algorithm. Results justify that the proposed mathematical model can solves problems with up to 40 vertices and 456 edges optimally. Our computational efforts signify that the proposed tabu search is very effective and can find high quality solutions for larger problems in reasonable amount of time.     

An ant colony optimization algorithm for the bi-objective shortest path problem

Multi-objective shortest path problem (MOSP) is an extension of a traditional single objective shortest path problem that seeks for the efficient paths satisfying several conflicting objectives between two nodes of a network. MOSP is one of the most important problems in network optimization with wide applications in telecommunication industries, transportation and project management. This research presents an algorithm based on multi-objective ant colony optimization (ACO) to solve the bi-objective shortest path problem. To analyze the efficiency of the algorithm and check for the quality of solutions, experimental analyses are conducted. Two sets of small and large sized problems that generated randomly are solved. Results on the set problems are compared with those of label correcting solutions that is the most known efficient algorithm for solving MOSP. To compare the Pareto optimal frontiers produced by the suggested ACO algorithm and the label correcting algorithm, some performance measures are employed that consider and compare the distance, uniformity distribution and extension of the Pareto frontiers. The results on the set of instance problems show that the suggested algorithm produces good quality non-dominated solutions and time saving in computation of large-scale bi-objective shortest path problems.     

一种基于优质边求解TSP的蚁群算法

应用蚁群算法求解旅行商问题时发现,算法易陷入局部最优解而停滞,并导致其探索新解能力的降低。提出了一种基于优质边的求解方法,根据算法运行过程中的相关信息选取优质边,在停滞时调整优质边上的信息素;使用改进的选路规则将蚂蚁的路径选择尽可能限制在优质边中,从而改进蚂蚁构造解的质量以增强算法的探索能力。实验结果表明,改进的策略是合理有效的。     

On multiprocessor task scheduling using efficient state space search approaches

Obtaining an optimal schedule for a set of precedence-constrained tasks is a well-known NP-complete problem in its general form. In view of the intractability of the problem, most of the previous work relies on heuristics that try to find reasonably high quality solutions in an acceptable amount of time. While optimal polynomial-time algorithms are known only for a few simple cases (and in other cases can only be obtained through an exhaustive search with prohibitively high time complexity), they may be critically important for applications in which performance is the prime objective. Optimal solutions can also serve as a reference to test the performance of various heuristics. Moreover, an optimal schedule for a program at hand needs to be determined only once (and off-line) but the program using that schedule is in general executed several times. In this paper, we propose optimal algorithms for static scheduling of task graphs with arbitrary parameters to multiple homogeneous processors. The first algorithm is based on the A^* search technique and uses a computationally efficient cost function for guiding the search with reduced complexity. Additionally, we propose a number of effective state-pruning techniques to reduce the search space. For further lowering the complexity, we propose an efficient parallelization of the search algorithm. We parallelize the algorithm with reduced interprocessor communication as well as with static and dynamic load-balancing schemes to evenly distribute the search states to the processors. We also propose an approximate algorithm that guarantees a bounded deviation from the optimal solution but executes in a considerably shorter time. Based on an extensive experimental evaluation of the algorithms, we conclude that the parallel algorithm with pruning techniques is an efficient scheme for generating optimal solutions of reasonably large problems while the approximate algorithm is effective if slightly degraded solutions are acceptable.     

CPGEA: a grouping genetic algorithm for material cutting plan generation

Construction firms specializing in large commercial buildings often purchase large steel plates, cut them into pieces and then weld the pieces into H-beams and other construction components. We formalize the material ordering and cutting problem faced by this industry and propose a grouping genetic algorithm, called CPG_EA, for efficiently controlling the relevant costs. We test the quality of CPG_EA in various ways. Three sets of simulated problems with known optimal solutions are solved using CPG_EA, and the gap between its solutions and optimal solutions is measured. The same problem sets are also solved with an expert system and a multi-start greedy heuristic. CPG_EA solutions are found to be consistently lower cost than the competing methods. The difference in solution quality is most pronounced for difficult problems requiring multiple identical plates in the optimal solution. CPG_EA is also tested using data from actual construction projects of a company faced with this problem. Since an optimal solution for the problems is not available, a lower bound is created. For the historical problems tested, the average percent difference between CPG_EA solutions and the lower bound is 0.67%. To put this performance in context, the results of solving these problems with an expert system and using experienced engineers is also reported. Of these three methods, CPG_EA achieves the best performance and the human experts the worst performance.     

A simultaneous transit network design and frequency setting: Computing with bees

The transit network design problem belongs to the class of hard combinatorial optimization problem, whose optimal solution is not easy to find out. We consider in this paper the transit network design problem in a way that we simultaneously determine the links to be included in the transit network, assemble chosen links into bus routes, and determine bus frequency on each of the designed routes. Our approach to the transit network design problem is based on the Bee Colony Optimization (BCO) metaheuristic. The BCO algorithm is a stochastic, random-search technique that belongs to the class of population-based algorithms. This technique uses a similarity among the way in which bees in nature look for food, and the way in which optimization algorithms search for an optimum of a combinatorial optimization problem. The numerical experiments are performed on known benchmark problems. We clearly show that our approach, based on the BCO algorithm is competitive with the other approaches in the literature and that can generate high-quality solutions.     

A study of one class of NLP problems arising in parametric semi-infinite programming

The paper deals with a nonlinear programming (NLP) problem that depends on a finite number of integers (parameters). This problem has a special form, and arises as an auxiliary problem in study of solutions' properties of parametric semi-infinite programming (SIP) problems with finitely representable compact index sets. Therefore, it is important to provide a deep study of this NLP problem and its properties w.r.t. the values of the parameters. We are especially interested in the case when optimal solutions of the NLP problem satisfy certain properties due to some specific requirements arising in parametric SIP. We establish the values of the parameters for which optimal solutions of the corresponding NLP problem fulfil the needed properties, and suggest an algorithm that determines the right values of the parameters. An example is proposed to illustrate the application of the algorithm.     

Configuration landscape analysis and backbone guided local search.: Part I: Satisfiability and maximum satisfiability

Boolean satisfiability (SAT) and maximum satisfiability (Max-SAT) are difficult combinatorial problems that have many important real-world applications. In this paper, we first investigate the configuration landscapes of local minima reached by the WalkSAT local search algorithm, one of the most effective algorithms for SAT. A configuration landscape of a set of local minima is their distribution in terms of quality and structural differences relative to an optimal or a reference solution. Our experimental results show that local minima from WalkSAT form large clusters, and their configuration landscapes constitute big valleys, in that high quality local minima typically share large partial structures with optimal solutions. Inspired by this insight into WalkSAT and the previous research on phase transitions and backbones of combinatorial problems, we propose and develop a novel method that exploits the configuration landscapes of such local minima. The new method, termed as backbone-guided search, can be embedded in a local search algorithm, such as WalkSAT, to improve its performance. Our experimental results show that backbone-guided local search is effective on overconstrained random Max-SAT instances. Moreover, on large problem instances from a SAT library (SATLIB), the backbone guided WalkSAT algorithm finds satisfiable solutions more often than WalkSAT on SAT problem instances, and obtains better solutions than WalkSAT on Max-SAT problem instances, improving solution quality by 20% on average.     

Nonlinear integer goal programming models for acceptance sampling

Two lexicographic goal programming models are developed for determining the optimal sample size and acceptance number for acceptance sampling plans in quality control. Both models address the conflicting criteria inherent in such sampling problems, namely the average lot inspection cost and the average outgoing quality. The first model assumes a known constant lot fraction defective, while the second relaxes this assumption and instead assumes knowledge of a prior distribution on the fraction of defectives. A three-phase algorithm is developed which exploits the problem structure in order to find optimal solutions after examining a small percentage of the feasible sampling plans. On a set of 64 test problems the algorithm always found the optimal solution, typically after evaluating only 3–5% (and never more than 9%) of the feasible points.     

A hybrid integer and constraint programming approach to solve nurse rostering problems

The Nurse Rostering Problem can be defined as assigning a series of shift sequences (schedules) to several nurses over a planning horizon according to some limitations and preferences. The inherent benefits of generating higher-quality schedules are a reduction in outsourcing costs and an increase in job satisfaction of employees. In this paper, we present a hybrid algorithm, which combines Integer Programming and Constraint Programming to efficiently solve the highly-constrained Nurse Rostering Problem. We exploit the strength of IP in obtaining lower-bounds and finding an optimal solution with the capability of CP in finding feasible solutions in a co-operative manner. To improve the performance of the algorithm, and therefore, to obtain high-quality solutions as well as strong lower-bounds for a relatively short time, we apply some innovative ways to extract useful information such as the computational difficulty of instances and constraints to adaptively set the search parameters. We test our algorithm using two different datasets consisting of various problem instances, and report competitive results benchmarked with the state-of-the-art algorithms from the recent literature as well as standard IP and CP solvers, showing that the proposed algorithm is able to solve a wide variety of instances effectively.     

Transit network design by Bee Colony Optimization

The transit network design problem is one of the most significant problems faced by transit operators and city authorities in the world. This transportation planning problem belongs to the class of difficult combinatorial optimization problem, whose optimal solution is difficult to discover. The paper develops a Swarm Intelligence (SI) based model for the transit network design problem. When designing the transit network, we try to maximize the number of satisfied passengers, to minimize the total number of transfers, and to minimize the total travel time of all served passengers. Our approach to the transit network design problem is based on the Bee Colony Optimization (BCO) metaheuristics. The BCO algorithm is a stochastic, random-search technique that belongs to the class of population-based algorithms. This technique uses a similarity among the way in which bees in nature look for food, and the way in which optimization algorithms search for an optimum of a combinatorial optimization problem. The numerical experiments are performed on known benchmark problems. We clearly show that our approach, based on the BCO algorithm, is competitive with other approaches in the literature, and it can generate high-quality solutions.