Search

In this paper we evaluate how constructive heuristics degrade when a problem transits from P to NP-hard. This is done by means of the linear ordering problem. More specifically, for this problem we prove that the objective function can be expressed as the sum of two objective functions, one of which is associated with a P problem (an exact polynomial time algorithm is proposed to solve it), while the other is associated with an NP-hard problem. We study how different constructive algorithms whose behaviour only depends on univariate information perform depending on the contribution of the P or NP-hard components of the problem. A number of experiments are conducted with reduced dimensions, where the global optimum of the problems is known, giving different weights to the NP-hard component, while the weight of the P component is fixed. It is observed how the performance of the constructive algorithms gets worse as the weight given to the NP-hard component increases.

Solving combinatorial optimization problems efficiently requires the development of algorithms that consider the specific properties of the problems. In this sense, local search algorithms are designed over a neighborhood structure that partially accounts for these properties. Considering a neighborhood, the space is usually interpreted as a natural landscape, with valleys and mountains. Under this perception, it is commonly believed that, if maximizing, the solutions located in the slopes of the same mountain belong to the same attraction basin, with the peaks of the mountains being the local optima. Unfortunately, this is a widespread erroneous visualization of a combinatorial landscape. Thus, our aim is to clarify this aspect, providing a detailed analysis of, first, the existence of plateaus where the local optima are involved, and second, the properties that define the topology of the attraction basins, picturing a reliable visualization of the landscapes. Some of the features explored in this article have never been examined before. Hence, new findings about the structure of the attraction basins are shown. The study is focused on instances of permutation-based combinatorial optimization problems considering the 2-exchange and the insert neighborhoods. As a consequence of this work, we break away from the extended belief about the anatomy of attraction basins.

Route optimization methods offer an opportunity to the fisheries industry to enhance their efficiency, sustainability, and safety. However, the use of route optimization Decision Support Systems (DSS), which have been widely used in the shipping industry, is limited in the case of fisheries. In the first part, this work describes the fishing routing problems, reviews the state-of-the-art methods applied in the shipping industry, and introduces a general framework for fishing route optimization decision support systems (FRODSS). In the second part, we highlight the existing gap for the application of DSS in fisheries, and how to develop a FRODSS considering the different types of fishing fleets. Finally, and using the diverse Basque fishing fleet as a case study, we conclude that fishing fleets can be summarized into four main groups whose fishing routes could be optimized in a similar way. This characterization is based on their similarities, such us the target species, fishing gear, and the type and distance to the fishing grounds. These four groups are: (i) small-scale coastal fleet; (ii) large-scale pelagic fleet; (iii) large-scale demersal fleet; and (iv) the distant-water fleet. Distant-water vessels are currently the fleet that can more easily benefit from FRODSS, and they are used as an example here. However, the rest of the fleets could also benefit through adequate adaptation to their operation characteristics, driven by their specific fishing gear and target species.

Route optimization methods offer an opportunity to the fisheries industry to enhance their efficiency, sustainability, and safety. However, the use of route optimization Decision Support Systems (DSS), which have been widely used in the shipping industry, is limited in the case of fisheries. In the first part, this work describes the fishing routing problems, reviews the state-of-the-art methods applied in the shipping industry, and introduces a general framework for fishing route optimization decision support systems (FRODSS). In the second part, we highlight the existing gap for the application of DSS in fisheries, and how to develop a FRODSS considering the different types of fishing fleets. Finally, and using the diverse Basque fishing fleet as a case study, we conclude that fishing fleets can be summarized into four main groups whose fishing routes could be optimized in a similar way. This characterization is based on their similarities, such us the target species, fishing gear, and the type and distance to the fishing grounds. These four groups are: (i) small-scale coastal fleet; (ii) large-scale pelagic fleet; (iii) large-scale demersal fleet; and (iv) the distant-water fleet. Distant-water vessels are currently the fleet that can more easily benefit from FRODSS, and they are used as an example here. However, the rest of the fleets could also benefit through adequate adaptation to their operation characteristics, driven by their specific fishing gear and target species.

A number of local search based algorithms have been designed to escape from the local optima, such as, iterated local search or variable neighborhood search. The neighborhood chosen for the local search as well as the escape technique play a key role in the performance of these algorithms. Of course, a specific strategy has a different effect on distinct problems or instances. In this paper, we focus on a permutation-based combinatorial optimization problem: the linear ordering problem. We provide a theoretical landscape analysis for the adjacent swap, the swap and the insert neighborhoods. By making connections to other different problems found in the Combinatorics field, we prove that there are some moves in the local optima that will necessarily return a worse or equal solution. The number of these non-better solutions that could be avoided by the escape techniques is considerably large with respect to the number of neighbors. This is a valuable information that can be included in any of those algorithms designed to escape from the local optima, increasing their efficiency., TIN2016-78365-R IT1244-19

Given a particular instance of a combinatorial optimization problem, the knowledge about the attraction basin sizes can help to analyze the difficulty encountered by local search algorithms while solving it. As calculating these sizes exhaustively is computationally intractable, we focus on methods for their estimation. The accuracy of some of these estimation methods depends on the way in which the sample of solutions of the search space is chosen. In this paper, we propose a novel sampling method, which incorporates the knowledge obtained by the already explored solutions into the sampling strategy. So, in contrast to those that already exist, our method can adapt its behavior to the characteristics of the particular attraction basin. We apply our proposal to a number of instances of three famous problems: the quadratic assignment problem, the linear ordering problem and the permutation flow shop scheduling problem. We consider permutation sizes $$n = 10$$ and $$n = 12$$ and three different neighborhoods: adjacent swap, 2-exchange and insert, and observe that the new method generally outperforms those that already exist.

The aim of this paper is to introduce the concept of intersection between combinatorial optimisation problems. We take into account that most algorithms, in their machinery, do not consider the exact objective function values of the solutions, but only a comparison between them. In this sense, if the solutions of an instance of a combinatorial optimisation problem are sorted into their objective function values, we can see the instances as (partial) rankings of the solutions of the search space. Working with specific problems, particularly, the linear ordering problem and the symmetric and asymmetric traveling salesman problem, we show that they can not generate the whole set of (partial) rankings of the solutions of the search space, but just a subset. First, we characterise the set of (partial) rankings each problem can generate. Secondly, we study the intersections between these problems: those rankings which can be generated by both the linear ordering problem and the symmetric/asymmetric traveling salesman problem, respectively. The fact of finding large intersections between problems can be useful in order to transfer heuristics from one problem to another, or to define heuristics that can be useful for more than one problem.

In this paper, we propose a tunable generator of instances of permutation-based combinatorial optimization problems. Our approach is based on a probabilistic model for permutations, called the generalized Mallows model. The generator depends on a set of parameters that permits the control of the properties of the output instances. Specifically, in order to create an instance, we solve a linear programming problem in the parameters, where the restrictions allow the instance to have a fixed number of local optima and the linear function encompasses qualitative characteristics of the instance. We exemplify the use of the generator by giving three distinct linear functions that produce three landscapes with different qualitative properties. After that, our generator is tested in two different ways. First, we test the flexibility of the model by producing instances similar to benchmark instances. Second, we account for the capacity of the generator to create different types of instances according to the difficulty for population-based algorithms. We study the influence of the input parameters in the behaviors of these algorithms, giving an example of a property that can be used to analyze their performance.

Local search algorithms are one of the most developed metaheuristics to solve combinatorial optimisation problems. Particularly, hill-climbing algorithms are simple but effective techniques that have been extensively used to deal with this kind of problems. These algorithms draw paths through the search space, choosing at each step a better solution than the current solution. As already known, they stop when a local optimum is reached. It is commonly believed that the closer the solution to the local optimum, the better its fitness. This premiss has a main implication: under this intuition, it is assumed that at each step of a hill-climbing algorithm, the new solution reduces the distance to the local optima. In this paper, we prove that this statement is not necessarily true. In fact, for some permutation-based combinatorial optimisation problems, such as the Permutation Flowshop Scheduling Problem, the Linear Ordering Problem and the Quadratic Assignment Problem, when considering the 2-exchange and the insert neighbourhoods, we find that, in most of the cases, the paths defined by a hill-climbing algorithm do not monotonically reduce the distance to the local optimum. Moreover, this distance remains constant for several steps, or it even increases for some steps. We provide an analysis of the solutions found in the attraction basins according to the distance to the local optimum and to the number of steps of the algorithm. We also give some visual examples of the paths followed by the algorithm.

The solution of many combinatorial optimization problems is carried out by metaheuristics, which generally make use of local search algorithms. These algorithms use some kind of neighborhood structure over the search space. The performance of the algorithms strongly depends on the properties that the neighborhood imposes on the search space. One of these properties is the number of local optima. Given an instance of a combinatorial optimization problem and a neighborhood, the estimation of the number of local optima can help not only to measure the complexity of the instance, but also to choose the most convenient neighborhood to solve it. In this paper we review and evaluate several methods to estimate the number of local optima in combinatorial optimization problems. The methods reviewed not only come from the combinatorial optimization literature, but also from the statistical literature. A thorough evaluation in synthetic as well as real problems is given. We conclude by providing recommendations of methods for several scenarios.

The performance of local search algorithms is influenced by the properties that the neighborhood imposes on the search space. Among these properties, the number of local optima has been traditionally considered as a complexity measure of the instance, and different methods for its estimation have been developed. The accuracy of these estimators depends on properties such as the relative attraction basin sizes. As calculating the exact attraction basin sizes becomes unaffordable for moderate problem sizes, their estimations are required. The lack of techniques achieving this purpose encourages us to propose two methods that estimate the attraction basin size of a given local optimum. The first method takes uniformly at random solutions from the whole search space, while the second one takes into account the structure defined by the neighborhood. They are tested on different instances of problems in the permutation space, considering the swap and the adjacent swap neighborhoods.

The Linear Ordering Problem is a combinatorial optimization problem which has been frequently addressed in the literature due to its numerous applications in diverse fields. In spite of its popularity, little is known about its complexity. In this paper we analyze the linear ordering problem trying to identify features or characteristics of the instances that can provide useful insights into the difficulty of solving them. Particularly, we introduce two different metrics, insert ratio and ubiquity ratio, that measure the difficulty of solving the LOP with local search type algorithms with the insert neighborhood system. Conducted experiments demonstrate that the proposed metrics clearly correlate with the complexity of solving the LOP with a multistart local search algorithm.

Designing customized optimization problem instances is a key issue in optimization. They can be used to tune and evaluate new algorithms, to compare several optimization algorithms, or to evaluate techniques that estimate the number of local optima of an instance. Given this relevance, several methods have been proposed to design customized optimization problems in the field of evolutionary computation for continuous as well as binary domains. However, these proposals have not been extended to permutation spaces. In this paper we provide a method to generate customized landscapes in permutation-based combinatorial optimization problems. Based on a probabilistic model for permutations, called the Mallows model, we generate instances with specific characteristics regarding the number of local optima or the sizes of the attraction basins.

This work is related to the search of complexity measures for instances of combinatorial optimization problems. Particularly, we have carried out a study about the complexity of random instances of the Traveling Salesman Problem under the 2-exchange neighbor system. We have proposed two descriptors of complexity: the proportion of the size of the basin of attraction of the global optimum over the size of the search space and the proportion of the number of different local optima over the size of the search space. We have analyzed the evolution of these descriptors as the size of the problem grows. After that, and using our complexity measures, we find a phase transition phenomenon in the complexity of the instances.

The average weight loss after 48 hours in 14 ambulatory cardiac patients receiving chlorazinal was 1.6 lb., comparing favorably with the response to other oral diuretics. Determinations of blood urea nitrogen and creatinine levels and urinalyses in 29 patients receiving the drug indicated that it tends to increase blood urea and to increase cellular content and casts in the urine in certain patients; an exception was a patient with acute glomerulonephritis in whom the blood urea decreased.