Search

Linear programming (LP) is an important field of optimization. Even though, interior point methods are polynomial algorithms, many LP practical problems are solved more efficiently by the primal and dual revised simplex methods (RSM); however, RSM has a poor performance in hard LP problems (HLPP) as in the Klee-Minty Cubes problem. Among LP methods, the hybrid method known as Simplex-Genetic (SG) is very robust to solve HLPP. The objective of SG is to obtain the optimal solution of a HLPP, taking advantages from each one of the combined methods -a genetic algorithm (GA) and the classical primal RSM-. In this paper a new SG method named Improved Simplex Genetic Method (ISG) is presented. ISG combines a GA (with special genetic operators) with both primal and dual RSM. Numerical experimentation using some instances of the Klee-Minty cubes problem shows that ISG has a better performance than both RSM and SG. [ABSTRACT FROM AUTHOR]

Because the efficiency and efficacy in Simulated Annealing (SA) algorithms is determined by their cooling scheme, several methods to set it have been proposed. In this paper an analytical method (ANDYMARK) to tune the parameters of the cooling scheme in SA for the Satisfiability (SAT) problem is presented. This method is based on a relation between the Markov chain's length and the cooling scheme. We compared ANDYMARK versus a classical SA algorithm that uses the same constant Markov chain. Experimentation with SAT instances shows that SA using this method obtains similar quality solutions with less effort than the classical one. Keywords: Satisfiability, Simulated Annealing, Combinatorial Optimization, NP-Hard Problems, Optimization, Heuristics. [ABSTRACT FROM AUTHOR]

Since the apparition of Simulated Annealing algorithm (SA) it has shown to be an efficient method to solve combinatorial optimization problems. Due to this, new algorithms based on two looped cycles (temperatures and Markov chain) have emerged, one of them have been called Threshold Accepting (TA). Classical algorithms based on TA usually use the same Markov chain length for each temperature cycle, these methods spend a lot of time at high temperatures where the Markov chain length is supposed to be small. In this paper we propose a method based on the neighborhood structure to get the Markov chain length in a dynamic way for each temperature cycle. We implemented two TA algorithms (classical or TACM and proposed or TADM) for SAT. Experimentation shows that the proposed method is more efficient than the classical one since it obtain the same quality of the final solution with less processing time. Keywords: Simulated Annealing, Threshold Accepting, Cooling Scheme, Dynamic Markov Chains, Combinatorial Optimization, Heuristic Optimization, SAT problem. [ABSTRACT FROM AUTHOR]

The Support Vector Machine (SVM) is a well known method used for classification, regression and density estimation. Training a SVM consists in solving a Quadratic Programming (QP) problem. The QP problem is very resource consuming (computational time and computational memory), because the quadratic form is dense and the memory requirements grow square the number of data points. The support vectors found in the training of SVM's represent a small subgroup of the training patterns. If an algorithm could make an approximation beforehand of the points standing for support vectors, we could train the SVM only with those data and the same results could be obtained as trained using the entire data base. This paper introduces an original initialization by the Zoutendijk method, called ZQP, to train SVM's faster than classical ones. The ZQP method first makes a fast approximation to the solution using the Zoutendijk algorithm. As result of this approximation, a reduced number of training patterns is obtained. Finally, a QP algorithm makes the training with this subset of data. Results show the improvement of the methodology in comparison to QP algorithm and chunking with QP algorithm. The ideas presented here can be extended to another problems such as resource allocation, considering that allocation as a combinatorial problem, that could be solved using some artificial intelligent technique such as Genetic algorithms or simulated annealing. In such approach ZQP would be used as a measure for effective fitness. [ABSTRACT FROM AUTHOR]

The dynamic nature of cooperative information systems (CIS) makes considerably more difficult the task of modeling interactions among agents. One of the most difficult problems related to the dynamic of a system is how to model and control simultaneously multiple interactions among agents in a friendly way. So far, traditional approaches deal with the problem of modeling interactions in static conditions and commonly with only two agents participating concurrently in cooperative tasks. Consequently, expressiveness becomes a problem related with the representation of multiple interactions in a satisfactory way, particularly in dynamic environments, such as e-business. The paper illustrates the application of a methodology based on Coloured Petri Nets (CP nets) in order to model the interaction mechanism in a CIS in an expressive way. This reduces the associated complexity in the representation of the dynamic of the system in a contact center environment, which is the start point to customer service, where concurrent interactions among users, technical people, process center and the contact center constitute a dynamic process that needs to be permanently monitored and controlled. The methodology provides us important advantages in the representation and reasoning for the interaction mechanism modeled in CIS. The use of CP nets allows analyzing the behavior of the system in the dynamic model using the individual and structural model. Keywords: Cooperative Information Systems, Coloured Petri Nets, Interaction, Agent-Based Software Engineering, Multi-Agent Systems, E-Business. [ABSTRACT FROM AUTHOR]

In this paper we deal with the solution of very large instances of the design distribution problem for distributed databases. Traditionally the capacity for solving large scale instances of NP-hard problems has been limited by the available computing resources and the efficiency of the solution algorithms. In contrast, in this paper we present a new solution approach that permits to solve larger instances using the same resources. This approach consists of the application of a systematic method for transforming an instance A into a smaller instance A' that has a large representativeness of instance A. For validating our approach we used a mathematical model developed by us, whose solution yields the design of a distributed database that minimizes its communication costs. The tests showed that the solution quality of the transformed instances was on the average 10.51% worse than the optimal solution; however, the size reduction was 97.81% on the average. We consider that the principles used in the proposed approach can be applied to the solution of very large instances of NP-hard problems of other problem types. [ABSTRACT FROM AUTHOR]

Simulated Annealing (SA) is usually implemented in a sequential way. We propose a Methodology to Parallel the Simulated Annealing Algorithm (MPSA). This methodology carries out the parallelization of the cycle that controls the temperature in the algorithm. This approach lets a massive parallelization. The initial solution for each internal cycle may be set through a Monte Carlo random sampling to adjust the Boltzmann distribution at the cycle beginning. In MPSA the communication scheme and its implementation must be in an asynchronous way. Through a theoretical analysis we establish that any implementation of MPSA leads to a Simulated Annealing Parallel Algorithm (SAPA) that is in general more efficient than its sequential implementation version. [ABSTRACT FROM AUTHOR]