Search

The set covering problem (SCP) is an NP-complete optimization problem, fitting with many problems in engineering. The traditional SCP formulation does not directly address both solution unsatisfiability and set redundancy aspects. As a result, the solving methods have to control these aspects to avoid getting unfeasible and nonoptimized in cost solutions. In the last years, an alternative SCP formulation was proposed, directly covering both aspects. This alternative formulation received limited attention because managing both aspects is considered straightforward at this time. This paper questions whether there is some advantage in the alternative formulation, beyond addressing the two issues. Thus, two studies based on a metaheuristic approach are proposed to identify if there is any concept in the alternative formulation, which could be considered for enhancing a solving method considering the traditional SCP formulation. As a result, the authors conclude that there are concepts from the alternative formulation, which could be applied for guiding the search process and for designing heuristic feasibilit\y operators. Thus, such concepts could be recommended for designing state-of-the-art algorithms addressing the traditional SCP formulation. more...

This research seeks to design, implement, and test a fully automatic high-frequency trading system that operates on the Chilean stock market, so that it is able to generate positive net returns over time. A system that implements high-frequency trading (HFT) is presented through advanced computer tools as an NP-Complete type problem in which it is necessary to optimize the profitability of stock purchase and sale operations. The research performs individual tests of the algorithms implemented, reviewing the theoretical net return (profitability) that can be applied on the last day, month, and semester of real market data. Finally, the research determines which of the variants of the implemented system performs best, using the net returns as a basis for comparison. The use of particle swarm optimization as an optimization algorithm is shown to be an effective solution since it is able to optimize a set of disparate variables but is bounded to a specific domain, resulting in substantial improvement in the final solution. more...

The Machine-Part Cell Formation Problem (MPCFP) is a NP-Hard optimization problem that consists in grouping machines and parts in a set of cells, so that each cell can operate independently and the intercell movements are minimized. This problem has largely been tackled in the literature by using different techniques ranging from classic methods such as linear programming to more modern nature-inspired metaheuristics. In this paper, we present an efficient parallel version of the Migrating Birds Optimization metaheuristic for solving the MPCFP. Migrating Birds Optimization is a population metaheuristic based on the V-Flight formation of the migrating birds, which is proven to be an effective formation in energy saving. This approach is enhanced by the smart incorporation of parallel procedures that notably improve performance of the several sorting processes performed by the metaheuristic. We perform computational experiments on 1080 benchmarks resulting from the combination of 90 well-known MPCFP instances with 12 sorting configurations with and without threads. We illustrate promising results where the proposal is able to reach the global optimum in all instances, while the solving time with respect to a nonparallel approach is notably reduced. more...

Evolutionary algorithms have been used to solve several optimization problems, showing an efficient performance. Nevertheless, when these algorithms are applied they present the difficulty to decide on the appropriate values of their parameters. Typically, parameters are specified before the algorithm is run and include population size, selection rate, and operator probabilities. This process is known as offline control and is even considered as an optimization problem in itself. On the other hand, parameter settings or control online is a variation of the algorithm original version. The main idea is to vary the parameters so that the algorithm of interest can provide the best convergence rate and thus may achieve the best performance. In this paper, we propose an adaptive black hole algorithm able to dynamically adapt its population according to solving performance. For that, we use autonomous search which appeared as a new technique that enables the problem solver to control and adapt its own parameters and heuristics during solving in order to be more efficient without the knowledge of an expert user. In order to test this approach, we resolve the set covering problem which is a classical optimization benchmark with many industrial applications such as line balancing production, crew scheduling, service installation, and databases, among several others. We illustrate encouraging experimental results, where the proposed approach is able to reach various global optimums for a well-known instance set from Beasley’s OR-Library, while improving various modern metaheuristics. more...

We solve a novel inventory-location model with a stochastic capacity constraint based on a periodic inventory control (ILM-PR) policy. The ILM-PR policy implies several changes with regard to other previous models proposed in the literature, which consider continuous review as their inventory policy. One of these changes is the inclusion of the undershoot concept, which has not been considered in previous ILM models in the literature. Based on our model, we are able to design a distribution network for a two-level supply chain, addressing both warehouse location and customer assignment decisions, whilst taking into consideration several aspects of inventory planning, in particular, evaluating the impact of the inventory control review period on the network configuration and system costs. Because the model is a very hard-to solve combinatorial nonlinear optimisation problem, we implemented two heuristics to solve it, namely, Tabu Search and Particle Swarm Optimisation. These approaches were tested over small instances in which they were able to find the optimal solution in just a few seconds. Because the model is a new one, a set of medium-size instances is provided that can be useful as a benchmark in future research. The heuristics showed a good convergence rate when applied to those instances. The results confirm that decision making over the inventory control policy has effects on the distribution network design. more...

Constraint programming effectively solves constraint satisfaction and optimization problems by basically building, pruning, and exploring a search tree of potential solutions. In this context, a main component is the enumeration strategy, which is responsible for selecting the order in which variables and values are selected to build a possible solution. This process is known to be quite important; indeed a correct selection can reach a solution without failed explorations. However, it is well known that selecting the right strategy is quite challenging as their performance is notably hard to predict. During the last years, adaptive enumeration appeared as a proper solution to this problem. Adaptive enumeration allows the solving algorithm being able to autonomously modifying its strategies in solving time depending on performance information. In this way, the most suitable order for variables and values is employed along the search. In this paper, we present a new and more lightweight approach for performing adaptive enumeration. We incorporate a powerful classification technique named Top-kin order to adaptively select strategies along the resolution. We report results on a set of well-known benchmarks where the proposed approach noticeably competes with classical and modern adaptive enumeration methods for constraint satisfaction. more...