Self-adaptive metaheuristics for solving a multi-objective 2-dimensional vector packing problem

In this paper, a multi-objective 2-dimensional vector packing problem is presented. It consists in packing a set of items, each having two sizes in two independent dimensions, say, a weight and a length into a finite number of bins, while concurrently optimizing three cost functions. The first objective is the minimization of the number of used bins. The second one is the minimization of the maximum length of a bin. The third objective consists in balancing the load overall the bins by minimizing the difference between the maximum length and the minimum length of a bin. Two population-based metaheuristics are performed to tackle this problem. These metaheuristics use different indirect encoding approaches in order to find good permutations of items which are then packed by a separate decoder routine whose parameters are embedded in the solution encoding. It leads to a self-adaptive metaheuristic where the parameters are adjusted during the search process. The performance of these strategies is assessed and compared against benchmarks inspired from the literature.     

Efficient lower bounds and heuristics for the variable cost and size bin packing problem

We consider the variable cost and size bin packing problem, a generalization of the well-known bin packing problem, where a set of items must be packed into a set of heterogeneous bins characterized by possibly different volumes and fixed selection costs. The objective of the problem is to select bins to pack all items at minimum total bin-selection cost. The paper introduces lower bounds and heuristics for the problem, the latter integrating lower and upper bound techniques. Extensive numerical tests conducted on instances with up to 1000 items show the effectiveness of these methods in terms of computational effort and solution quality. We also provide a systematic numerical analysis of the impact on solution quality of the bin selection costs and the correlations between these and the bin volumes. The results show that these correlations matter and that solution methods that are un-biased toward particular correlation values perform better.     

Branch-and-bound algorithm for the maximum triangle packing problem

This work addresses the problem of finding the maximum number of unweighted vertex-disjoint triangles in an undirected graph G. It is a challenging NP-hard combinatorial problem and it is well-known to be APX-hard. A branch-and-bound algorithm which uses a lower bound based on neighborhood degree is presented. A naive upper bound is proposed as well as another one based on a surrogate relaxation of the related integer linear program which is analogous to a multidimensional knapsack problem. Further, a Greedy Search algorithm and a genetic algorithm are described to improve the lower bound. A computational comparison of lower bounds, branch-and-bound algorithm and CPLEX solver is provided using randomly generated benchmarks and well-known DIMACS implementation challenges. The empirical study shows that the branch-and-bound finds the optimal triangle packing solution for small randomly generated MTP instances (up to 100 vertices and 200 triangles) and some DIMACS graphs. For some larger instances and DIMACS challenges graphs, we remark that our lower bound outperforms CPLEX solver regarding the triangle packing solution and the computation time.     

The min-conflict packing problem

In the classical bin-packing problem with conflicts (BPC), the goal is to minimize the number of bins used to pack a set of items subject to disjunction constraints. In this paper, we study a new version of BPC: the min-conflict packing problem (MCBP), in which we minimize the number of violated conflicts when the number of bins is fixed. In order to find a tradeoff between the number of bins used and the violation of the conflict constraints, we also consider a bi-objective version of this problem. We show that the special structure of its Pareto front allows to reformulate the problem as a small set of MCBP. We solved these two problems through heuristics, column-generation methods, and a tabu search. Computational experiments are reported to assess the quality of our methods.     

Two metaheuristic approaches for solving multidimensional two-way number partitioning problem

In this paper, we address two metaheuristic approaches, a Variable Neighborhood Search (VNS) and an Electromagnetism-like metaheuristic (EM), on an NP-hard optimization problem: Multi-dimensional Two-way Number Partitioning Problem (MDTWNPP). MDTWNPP is a generalization of a Two-way Number Partitioning Problem (TWNPP), where a set of vectors is partitioned rather than a set of numbers. The simple k-swap neighborhoods allow an effective shaking procedure in the VNS search. The attraction–repulsion mechanism of EM is extended with a scaling procedure, which additionally moves EM points closer to local optima. Both VNS and EM use the same local search procedure based on 1-swap improvements. Computational results were obtained on 210 standard instances. Direct comparison with results from the literature confirm the significance of applying these methods to MDTWNPP.     

Ensemble of multi-objective metaheuristic algorithms for multi-objective unconstrained binary quadratic programming problem

Metaheuristics have been widely utilized for solving NP-hard optimization problems. However, these algorithms usually perform differently from one problem to another, i.e., one may be effective on a problem but performs badly on another problem. Therefore, it is difficult to choose the best algorithm in advance for a given problem. In contrast to selecting the best algorithm for a problem, selection hyper-heuristics aim at performing well on a set of problems (instances). This paper proposes a selection hyper-heuristic based algorithm for multi-objective optimization problems. In the proposed algorithm, multiple metaheuristics exhibiting different search behaviors are managed and controlled as low-level metaheuristics in an algorithm pool, and the most appropriate metaheuristic is selected by means of a performance indicator at each search stage. To assess the performance of the proposed algorithm, an implementation of the algorithm containing four metaheuristics is proposed and tested for solving multi-objective unconstrained binary quadratic programming problem. Experimental results on 50 benchmark instances show that the proposed algorithm can provide better overall performance than single metaheuristics, which demonstrates the effectiveness of the proposed algorithm.     

Solving the one-dimensional bin packing problem with a weight annealing heuristic

In this paper, we develop a new procedure that uses the concept of weight annealing to solve the one-dimensional bin packing problem. Our procedure is straightforward and easy to follow. We apply it to 1587 instances taken from benchmark problem sets and compare our results to those found in the literature. We find that our procedure produces very high-quality solutions very quickly and generates several new optimal solutions.     

Emergent nature inspired algorithms for multi-objective optimization

Many real-world decision-making situations possess both a discrete and combinatorial structure and involve the simultaneous consideration of conflicting objectives. Problems of this kind are in general of large size and contains several objectives to be “optimized”. Although Multiple Objective Optimization is a well-established field of research, one branch, namely nature inspired metaheuristics is currently experienced a tremendous growth. Over the last few years, developments of new methodologies, methods, and techniques to deal with multi-objective large size problems in particular those with a combinatorial structure and the strong improvement on computing technologies (during and after the 80s) made possible to solve very hard problems with the help of inspired nature based metaheuristics.     

A pure quasi-human algorithm for solving the cuboid packing problem

We excavate the wisdom from an old Chinese proverb “gold corner, silver side and strawy void”, and further improve it into “maximum value in diamond cave” for solving the NP-hard cuboid packing problem. We extract, integrate and formalize the idea by west modern mathematical tools, and propose a pure quasi-human algorithm. The performance of the algorithm is evaluated on two sets of public benchmarks. For 100 strongly heterogeneous difficult benchmarks, experiments show an average packing utilization of 87.31%, which surpasses current best record reported in the literature by 1.83%. For 47 difficult benchmarks without orientation constraint, experiments show an average volume utilization of 92.05%, which improves current best record reported in the literature by 1.05%. Supported by the National Natural Science Foundation of China (Grant No. 60773194), the National Basic Research Program of China (Grant No. 2004CB318000), and Postdoctoral Science Foundation of China (Grant No. 20070420174)     

A hybrid multi-objective shuffled frog-leaping algorithm for a mixed-model assembly line sequencing problem

In this paper, a mixed-model assembly line (MMAL) sequencing problem is studied. This type of production system is used to manufacture multiple products along a single assembly line while maintaining the least possible inventories. With the growth in customers’ demand diversification, mixed-model assembly lines have gained increasing importance in the field of management. Among the available criteria used to judge a sequence in MMAL, the following three are taken into account: the minimization of total utility work, total production rate variation, and total setup cost. Due to the complexity of the problem, it is very difficult to obtain optimum solution for this kind of problems by means of traditional approaches. Therefore, a hybrid multi-objective algorithm based on shuffled frog-leaping algorithm (SFLA) and bacteria optimization (BO) are deployed. The performance of the proposed hybrid algorithm is then compared with three well-known genetic algorithms, i.e. PS-NC GA, NSGA-II, and SPEA-II. The computational results show that the proposed hybrid algorithm outperforms the existing genetic algorithms, significantly in large-sized problems.     

A constraint-programming-based approach for solving the data dissemination problem

Systems of mobile Systems are intermittently connected networks that use store-carry-forward routing for data transfers. Independent systems collaborate and exchange data to achieve a common goal. Data transfers are only possible between systems that are close enough to each other, when a so-called contact occurs. During a contact, a sending system can transmit to a receiving system a fixed amount of data held in its interna then assume it holds at a til buffer. We assume that the trajectories of component systems are predictable, and consequently that a sequence of contacts may be considered. This dissemination problem is aimed at finding a transfer plan such that a set of data can be transferred from a given subset of source systems to all the recipient systems. In this paper, we propose an original constraint-programming-based algorithm for solving this problem. Computational results show that this approach is an improvement on the integer-linear-programming-based approach that we proposed in a previous paper.     

Efficient algorithms for real-life instances of the variable size bin packing problem

In this paper we present a local search heuristic for real-life instances of the variable size bin packing problem, and an exact algorithm for small instances. One important issue our heuristic is able to satisfy is that solutions must be delivered within (milli)seconds and that the solution methods should be robust to last minute changes in the data. Furthermore we show that we are able to incorporate the concept of usable leftovers on a single bin, and the implementation of many additional constraints should be supported by the straightforward solution representation. The heuristic is compared to others from the literature, and comes out ahead on a large subset of the instances.     

Analysis of FPTASes for the multi-objective shortest path problem

We propose a new FPTAS for the multi-objective shortest path problem with non-negative and integer arc costs. The algorithm uses elements from both an exact labeling algorithm and an FPTAS proposed by Tsaggouris and Zaroliagis [25]. We analyze the running times of these three algorithms both from a theoretical and a computational point of view. Theoretically, we show that there are instances for which the new FPTAS runs arbitrarily faster than the other two algorithms. Furthermore, for the bi-objective case, the number of approximate solutions generated by the proposed FPTAS is at most the number of Pareto-optimal points multiplied by the number of nodes. By performing a set of computational tests, we show that the new FPTAS performs best in terms of running time in case there are many dominated paths and the number of Pareto-optimal points is not too small.     

A multi-objective scatter search for a dynamic cell formation problem

Cellular manufacturing system—an important application of group technology (GT)—has been recognized as an effective way to enhance the productivity in a factory. Consequently, a multi-objective dynamic cell formation problem is presented in this paper, where the total cell load variation and sum of the miscellaneous costs (machine cost, inter-cell material handling cost, and machine relocation cost) are to be minimized simultaneously. Since this type of problem is NP-hard, a new multi-objective scatter search (MOSS) is designed for finding locally Pareto-optimal frontier. To demonstrate the efficiency of the proposed algorithm, MOSS is compared with two salient multi-objective genetic algorithms, i.e. SPEA-II and NSGA-II based on some comparison metrics and statistical approach. The computational results indicate the superiority of the proposed MOSS compared to these two genetic algorithms.     

A unified hyper-heuristic framework for solving bin packing problems

One- and two-dimensional packing and cutting problems occur in many commercial contexts, and it is often important to be able to get good-quality solutions quickly. Fairly simple deterministic heuristics are often used for this purpose, but such heuristics typically find excellent solutions for some problems and only mediocre ones for others. Trying several different heuristics on a problem adds to the cost. This paper describes a hyper-heuristic methodology that can generate a fast, deterministic algorithm capable of producing results comparable to that of using the best problem-specific heuristic, and sometimes even better, but without the cost of trying all the heuristics. The generated algorithm handles both one- and two-dimensional problems, including two-dimensional problems that involve irregular concave polygons. The approach is validated using a large set of 1417 such problems, including a new benchmark set of 480 problems that include concave polygons.     

Quasi-physical global optimization method for solving the equal circle packing problem

The equal circle packing problem is a well-known challenge in geometry.It is also a natural,clear and fair test system for global optimization.This paper presents a quasi-physical global optimization algorithm for solving the equal circle packing problem.The algorithm simulates two kinds of movements of N elastic disks: smooth movement driven by elastic pressures and violent movement driven by strong repulsive forces and attractive forces.The smooth movement makes the disks reach a locally optimal configura...     

求解等圆Packing问题的拟物型全局优化算法

等圆Packing问题是一个著名的几何难题,也是全局优化领域的一个天然明白客观公正的算法试金石.文中为等圆Packing问题提出了一个拟物型的全局优化算法.在算法中,N个圆饼在弹性挤压力的作用下平缓地运动,到达某个局部最优格局;适当的时期,又在高强度的引力和斥力的作用下剧烈地运动,跳出局部最优格局的陷阱,到达前景可能更...     

C-PSA: Constrained Pareto simulated annealing for constrained multi-objective optimization

In recent years, evolutionary algorithms (EAs) have been extensively developed and utilized to solve multi-objective optimization problems. However, some previous studies have shown that for certain problems, an approach which allows for non-greedy or uphill moves (unlike EAs), can be more beneficial. One such approach is simulated annealing (SA). SA is a proven heuristic for solving numerical optimization problems. But owing to its point-to-point nature of search, limited efforts has been made to explore its potential for solving multi-objective problems. The focus of the presented work is to develop a simulated annealing algorithm for constrained multi-objective problems. The performance of the proposed algorithm is reported on a number of difficult constrained benchmark problems. A comparison with other established multi-objective optimization algorithms, such as infeasibility driven evolutionary algorithm (IDEA), Non-dominated sorting genetic algorithm II (NSGA-II) and multi-objective Scatter search II (MOSS-II) has been included to highlight the benefits of the proposed approach.