Approximation algorithms for combinatorial multicriteria optimization problems

The computational complexity of combinatorial multiple objective programming problems is investigated. NP-completeness and # P -completeness results are presented. Using two definitions of approximability, general results are presented, which outline limits for approximation algorithms. The performance of the well-known tree and Christofides' heuristics for the traveling salesman problem is investigated in the multicriteria case with respect to the two definitions of approximability.     

Generating combinatorial test suite using combinatorial optimization

Combinatorial testing (CT) is an effective technique to test software with multiple configurable parameters. It is used to detect interaction faults caused by the combination effect of parameters. CT test generation aims at generating covering arrays that cover all t-way parameter combinations, where t is a given covering strength. In practical CT usage scenarios, there are usually constraints between parameters, and the performance of existing constraint-handling methods degrades fast when the number of constraints increases.The contributions of this paper are (1) we propose a new one-test-at-a-time algorithm for CT test generation, which uses pseudo-Boolean optimization to generate each new test case; (2) we have found that pursuing the maximum coverage for each test case is uneconomic, and a possible balance point is to keep the approximation ratio in [0.8,0.9]; (3) we propose a new self-adaptive mechanism to stop the optimization process at a proper time when generating each test case; (4) extensive experimental results show that our algorithm works fine on existing benchmarks, and the constraint-handling ability is better than existing approaches when the number of constraints is large; and (5) we propose a method to translate shielding parameters (a common type of constraints) into normal constraints.     

An approximation algorithm for interval data minmax regret combinatorial optimization problems

The general problem of minimizing the maximal regret in combinatorial optimization problems with interval data is considered. In many cases, the minmax regret versions of the classical, polynomially solvable, combinatorial optimization problems become NP-hard and no approximation algorithms for them have been known. Our main result is a polynomial time approximation algorithm with a performance ratio of 2 for this class of problems.     

Water wave optimization for combinatorial optimization: Design strategies and applications

Although the community of nature-inspired computing has witnessed a wide variety of metaheuristics, it often requires considerable effort to adapt them to different combinatorial optimization problems (COPs), and few studies have been devoted to reducing this burden. This paper proposes a systematic approach that consists of a set of basic steps and strategies for adapting water wave optimization (WWO), a simple and generic metaheuristic, to concrete heuristic algorithms for different COPs. Taking advantages of the generic algorithmic framework, designers can only focus on adapting the prorogation operator and the wavelength calculation method according to the combinatorial properties of the given problem, and thus easily derive efficient problem-solving algorithms. We illustrate and test our approach on the flow-shop scheduling problem (FSP), the single-objective multidimensional knapsack problem (MKP), and the multi-objective MKP, and then present an application to a machine utilization optimization problem for a large manufacturing enterprise. The results demonstrate that our approach can derive concrete algorithms that are competitive to the state-of-the-arts. Our approach also provides insights into the adaptation of other metaheuristics and the development of new metaheuristics for COPs.     

New meta-heuristic for combinatorial optimization problems: Intersection based scaling

Combinatorial optimization problems are found in many application fields such as computer science,engineering and economy. In this paper, a new efficient meta-heuristic, Intersection-Based Scaling (IBS for abbreviation), is proposed and it can be applied to the combinatorial optimization problems. The main idea of IBS is to scale the size of the instance based on the intersection of some local optima, and to simplify the search space by extracting the intersection from the instance, which makes the search more efficient. The combination of IBS with some local search heuristics of different combinatorial optimization problems such as Traveling Salesman Problem (TSP) and Graph Partitioning Problem (GPP) is studied, and comparisons are made with some of the best heuristic algorithms and meta-heuristic algorithms. It is found that it has significantly improved the performance of existing local search heuristics and significantly outperforms the known best algorithms.     

Critical phenomena in a collective computation algorithm for combinatorial optimization problems

This paper discusses the critical temperature (control parameter) of an annealed neural network, a typical collective computation for combinatorial optimization problems.It is shown that the theoretical critical temperatures determined by our estimation agree with those derived by computational experiments in graph partitioning problems and in the travelling salesman problem.     

A note on robustness tolerances for combinatorial optimization problems

We consider so-called generic combinatorial optimization problem, where the set of feasible solutions is some family of nonempty subsets of a finite ground set with specified positive initial weights of elements, and the objective function represents the total weight of elements of the feasible solution. We assume that the set of feasible solutions is fixed, but the weights of elements may be perturbed or are given with errors. All possible realizations of weights form the set of scenarios.A feasible solution, which for a given set of scenarios guarantees the minimum value of the worst-case relative regret among all the feasible solutions, is called a robust solution. The maximum percentage perturbation of a single weight, which does not destroy the robustness of a given solution, is called the robustness tolerance of this weight with respect to the solution considered.In this paper we give formulae for computing the robustness tolerances with respect to an optimal solution obtained for some initial weights and we show that this can be done in polynomial time whenever the optimization problem is polynomially solvable itself.     

Measuring instance difficulty for combinatorial optimization problems

Discovering the conditions under which an optimization algorithm or search heuristic will succeed or fail is critical for understanding the strengths and weaknesses of different algorithms, and for automated algorithm selection. Large scale experimental studies - studying the performance of a variety of optimization algorithms across a large collection of diverse problem instances - provide the resources to derive these conditions. Data mining techniques can be used to learn the relationships between the critical features of the instances and the performance of algorithms. This paper discusses how we can adequately characterize the features of a problem instance that have impact on difficulty in terms of algorithmic performance, and how such features can be defined and measured for various optimization problems. We provide a comprehensive survey of the research field with a focus on six combinatorial optimization problems: assignment, traveling salesman, and knapsack problems, bin-packing, graph coloring, and timetabling. For these problems - which are important abstractions of many real-world problems - we review hardness-revealing features as developed over decades of research, and we discuss the suitability of more problem-independent landscape metrics. We discuss how the features developed for one problem may be transferred to study related problems exhibiting similar structures.     

Multi-center variable-scale search algorithm for combinatorial optimization problems with the multimodal property

Combinatorial optimization problems (COPs) are discrete problems arising from aerospace, bioinformatics, manufacturing, and other fields. One of the classic COPs is the scheduling problem. Moreover, these problems are usually multimodal optimization problems with a quantity of global and local optima. As a result, many search algorithms can easily become trapped into local optima. In this article, we propose a multi-center variable-scale search algorithm for solving both single-objective and multi-objective COPs. The algorithm consists of two distinct points. First, the multi-center strategy chooses several individuals with better performance as the only parents of the next generation, which means that there are a number of separate searching areas around the searching center. Second, the next generation of the population is produced by a variable-scale strategy with an exponential equation based on the searching center. The equation is designed to control the neighborhood scale, and adaptively realize the large-scale and small-scale searches at different search stages to balance the maintenance of diversity and convergence speed. In addition, an approach of adjusting centers is proposed concerning the number and distribution of centers for solving multi-objective COPs. Finally, the proposed algorithm is applied to three COPs, including the well-known flexible job shop scheduling problem, the unrelated parallel machine scheduling problem, and the test task scheduling problem. Both the single-objective optimization algorithm and the multi-objective optimization algorithm demonstrate competitive performance compared with existing methods.     

A novel differential evolution mapping technique for generic combinatorial optimization problems

Differential evolution is primarily designed and used to solve continuous optimization problems. Therefore, it has not been widely considered as applicable for real-world problems that are characterized by permutation-based combinatorial domains. Many algorithms for solving discrete problems using differential evolution have been proposed, some of which have achieved promising results. However, to enhance their performance, they require improvements in many aspects, such as their convergence speeds, computational times and capabilities to solve large discrete problems. In this paper, we present a new mapping method that may be used with differential evolution to solve combinatorial optimization problems. This paper focuses specifically on the mapping component and its effect on the performance of differential evolution. Our method maps continuous variables to discrete ones, while at the same time, it directs the discrete solutions produced towards optimality, by using the best solution in each generation as a guide. To judge its performance, its solutions for instances of well-known discrete problems, namely: 0/1 knapsack, traveling salesman and traveling thief problems, are compared with those obtained by 8 other state-of-the-art mapping techniques. To do this, all mapping techniques are used with the same differential evolution settings. The results demonstrated that our technique significantly outperforms the other mapping methods in terms of the average error from the best-known solution for the traveling salesman problems, and achieves promising results for both the 0/1 knapsack and the traveling thief problems.     

A negotiation framework for linked combinatorial optimization problems

We tackle the challenge of applying automated negotiation to self-interested agents with local but linked combinatorial optimization problems. Using a distributed production scheduling problem, we propose two negotiation strategies for making concessions in a joint search space of agreements. In the first strategy, building on Lai and Sycara (Group Decis Negot 18(2):169–187, 2009), an agent concedes on local utility in order to achieve an agreement. In the second strategy, an agent concedes on the distance in an attribute space while maximizing its local utility. Lastly, we introduce a Pareto improvement phase to bring the final agreement closer to the Pareto frontier. Experimental results show that the new attribute-space negotiation strategy outperforms its utility-based counterpart on the quality of the agreements and the Pareto improvement phase is effective in approaching the Pareto frontier. This article presents the first study of applying automated negotiation to self-interested agents each with a local, but linked, combinatorial optimization problem.     

Information support systems for problem solving

The occurrence in the literature of success stories dealing with (management) information systems is rare indeed. This paper addresses some of the possible factors that make it difficult to design and implement successful information (and decision support) systems. More specifically, we consider the role of problem formulation and specification, including goal setting, in the design of information systems.     

Applying combinatorial optimization metaheuristics to the golf scramble problem

One typical golf tournament format is termed a 'Scramble,' comprised of four-person teams. The participants are rank-ordered into four equally sized 'flights' based on integer-valued handicaps determined by skill level. One participant from each flight is selected to make up a team. Of interest is the assignment of teams in an 'equitable' fashion, where equitable is defined as minimizing the difference between the largest and smallest sum of the handicaps. For a typical tournament of 36 teams there are over 10 ¹²⁴ unique assignments. Since in general there are duplicate handicap values, the number of 'equivalent' assignments is reduced (but still very large). Various heuristics are explored for efficiently identifying an optimal or near optimal solution. These include descent heuristics, simulated annealing, tabu search, and genetic algorithms. Genetic algorithms outperform other heuristics by taking advantage of the problem structure.     

Solving constrained combinatorial optimization problems via importance sampling in the grand canonical ensemble

Combinatorial optimization problems are usually NP-hard. These problems are generally tackled by heuristic or branch-and-bound methods. The aim of this paper is to tackle constrained combinatorial optimization problems by importance Monte Carlo sampling. For this, we show that every constrained combinatorial optimization problem can be represented by a thermodynamical system in a suitable grand canonical ensemble given by the quantities of temperature, volume, and chemical potential. In order to find optimum solutions of the optimization problem, the grand canonical Monte Carlo method can be applied to the corresponding thermodynamical system. This method will amount to importance sampling, i.e. good feasible solutions of the optimization problem will be preferably sampled, provided that the intensive quantities of temperature and chemical potential are appropriately chosen. Our approach extends the standard importance sampling approach in the canonical ensemble to tackle unconstrained combinatorial optimization problems. The knapsack problem is considered as a prototype example.     

Bound sets for biobjective combinatorial optimization problems

In this paper we introduce the concept of bound sets for multiobjective discrete optimization. We prove general results on lower and upper bound sets for combinatorial optimization problems with multiple objectives. We present general algorithms for constructing lower and upper bound sets for biobjective problems and provide numerical results on five different problem types.     

Individual differences and the effects of an information aid in performance of a fault diagnosis task

Two experiments are reported that investigated the performance of operators in a fault diagnosis task. Naval engineers working in the Ship's Control Centre (SCC) on board of frigates of the Royal Netherlands Navy were asked to solve a number of unfamiliar fault problems. In the first experiment, it was shown that there was a high correlation (0·85) between the number of problems correctly solved and the availability of system knowledge. In addition there was an effect of the level of formal education. In a second experiment it was shown that the provision of a simple help facility that compensates for a lack of system knowledge leads to a substantial increase in the number of problems that were correctly solved. The percentage of correct solutions increased from 62 to 89%. This increase was the same for operators with either an electrical engineering or a mechanical engineering background although the former group performed slightly better than the latter. These results show that the conclusion of Morris and Rouse (1985a) that instruction in the theoretical principles on which a system is based is less effective than the training of diagnostic procedures, underestimates the importance of system knowledge for the solution of fault diagnosis problems.     

Decision support for “messy” problems

Problems that are non-quantitative and not bound to a narrow knowledge domain have been served unsatisfactorily by decision support and expert systems. Alternative techniques that address this type of problem are explained here using two key concepts: problem type dependent process support and domain related knowledge. Process support refers to the program steps and the data items useful in finding the solution. Domain related knowledge is knowledge drawn from a specific domain, yet through abstraction applicable to a wider range of problems. Results of preliminary empirical analyses suggest that both concepts are useful.     

Search spaces representation in optimization problems

We present formally a search space representation method in combinatorial optimization problems, as well as a tool for the visualization of the trajectories of heuristic algorithms based on this method. A software that develops the ideas of the formal method is presented. Several numerical examples are given.     

Superior/Inferior Segment-Discriminated Ant System for combinatorial optimization problems

The Ant Colony Optimization method is a heuristic algorithm for solving various optimization problems, particularly the combinatorial optimization problems. Traditional ant-optimization methods might encounter search stagnation owing to a biased pheromone map that is dominated by local optimal trails. To overcome this drawback and lower the number of solution constructions for finding the optima, this paper presents an improving ant-optimization system, the Superior/Inferior Segment-Discriminated Ant System (SDAS). This system proposes a segment-based pheromone update strategy to deposit pheromone on superior segments and withdraw pheromone from inferior ones. The method uses the control-chart technique to define superior and inferior limits to partition the constructed solutions into superior, inferior, and ordinary solutions. Inferior and superior segments are then extracted from the superior and inferior solutions by stochastic set operations. Since the pheromone map is not easily dominated by any local optimal trail, the solution search is more efficient and effective. Several benchmarks from the TSP-LIB and OR-LIB were used as sample problems to test the proposed system against other ant-optimization systems, including the AS, ACS, AS_rank, AS_elite, and MMAS. Numerical results indicated that the SDAS obtains solutions that are similar to or better than others. Maturity index for the pheromone map was discussed and experimental results showed that the proposed method was able to prolong the time for the map to maturity to avoid earlier search stagnation.     

Designing for creativity: Considerations for DSS development

Decision support systems (DSS) can be designed to support the creative and intuitive aspects of decision making. Our purpose is to provide a new perspective for the design of DSS by focusing on the important external factors that have been shown to influence creative activity. Design guidelines can then be developed by viewing a DSS as a special environment that incorporates these factors.