We first describe four recent methods to cluster vertices of an undirected non weighted connected graph. They are all based on very different principles. The fifth is a combination of classical ideas in optimization applied to graph partitioning. We compare these methods according to their ability to recover classes initially introduced in random graphs with more edges within the classes than between them.
We first describe four recent methods to cluster vertices of an undirected non weighted connected graph. They are all based on very different principles. The fifth is a combination of classical ideas in optimization applied to graph partitioning. We compare these methods according to their ability to recover classes initially introduced in random graphs with more edges within the classes than between them.
We propose a temporal decomposition approach for the one-machine scheduling problem with ready times and due dates. A set of feasible schedules is characterized by means of constraint-based analysis rules. They permit the determination of the feasible locations of each task in a sequence, represented by rank intervals. A decomposition procedure based on comparisons of rank intervals is developed in order to group tasks to be sequenced in the neighbourhood of each other in a feasible solution. Computational...
En este trabajo abordamos el estudio del poliedro asociado al Problema de Rutas de Vehículos con Demanda Compartida, problema de distribución que surge cuando hay que repartir mercancías a un conjunto de clientes utilizando una flota fija de vehículos de capacidad limitada. El objetivo es diseñar las rutas de forma que se minimice la distancia total recorrida. Se diferencia de otros problemas más conocidos de rutas con capacidades en que se permite abastecer la demanda de cada cliente utilizando...
In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem which only differ on a linear transformation of their objective functions. This is notably...
In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem π which only differ on a linear transformation of their objective functions. This is notably...
Se analiza la aplicación de un algoritmo de Programación de Redes, el método Out of Kilter, al análisis y diseño de redes de intercambiadores de calor con utilidades externas múltiples. Tradicionalmente, los métodos heurísticos y termodinámicos han sido los más utilizados. Sin embargo, estos métodos presentan dificultades de aplicación en aquellos problemas, como el planteado en este trabajo, en los que se incorpora más de una utilidad externa de calentamiento. Por el contrario, el método Out of...
Basándonos en algunas definiciones previas, se analiza el problema del árbol generador difuso. En primer lugar se trata su existencia y después se encuentra el árbol generador difuso de mínimo costo mediante una descomposición por α-cortes. El estudio se realiza para dos estructuras diferentes de costos.
The paper presents an algorithm which solves the shortest path problem in an arbitrary deterministic environment with n states with an emotional agent in linear time. The algorithm originates from an algorithm which in exponential time solves the same problem, and the agent architecture used for solving the problem is an NN-CAA architecture (neural network crossbar adaptive array). By implementing emotion learning, the linear time algorithm is obtained and the agent architecture is modified. The...