Un algorithme parallèle efficace pour construire un arbre de poids minimal dans un graphe
Un algorithme pour la bipartition d’un graphe en sous-graphes de cardinalité fixée
Nous présentons une méthode de Séparation et Évaluation Progressive pour la bipartition d’un graphe en 2 sous-ensembles ayant une cardinalité fixée. À chaque nœud de l’arbre de recherche, nous calculons une borne inférieure en dualisant les contraintes d’intégralité et en approximant le domaine réalisable par un ellipsoïde. Une borne supérieure est également calculée par la méthode Tabou. Des résultats numériques sont présentés et commentés.
Un Algorithme pour la Bipartition d'un Graphe en Sous-graphes de Cardinalité Fixée
A branch-and-bound method for solving the min cut with size constraint problem is presented. At each node of the branch-and-bound tree the feasible set is approximated by an ellipsoid and a lower bound is computed by minimizing the quadratic objective function over this ellipsoid. An upper bound is also obtained by a Tabu search method. Numerical results will be presented.
Un algorithme pour la résolution du programme linéaire général
Un algorithme pour le problème d'affectation
Un algorithme pour le problème de partitionnement
Un algorithme pour les problèmes de recouvrement
Un algorithme pour pallier l'effet Condorcet
Un algorithme pour résoudre une famille de problèmes de localisation multisources
Un algoritmo de programación geométrica basado en funciones penalidad-multiplicadoras.
El trabajo presenta un nuevo algoritmo para la resolución de un problema de porgramación geométrica primal transformado. El método se basa en las técnicas de tipo lagrangiano aumentado y utiliza como penalidad funciones derivadas de la exponencial para las restricciones con un único término, y de la pérdida cuadrática para las restricciones con más de un término. El problema resultante se resuelve por medio de un método lagrangiano con iteración de tipo Newton, y los parámetros de penalización se...
Un algoritmo de punto interior para programación cuadrática a través de problemas equivalentes separables.
Se presenta un algoritmo de punto interior para la solución de problemas cuadráticos simétricos y definidos positivos, mediante su transformación en problemas equivalentes separables (esto es, la matriz de coeficientes cuadráticos es diagonal y no existen términos cruzados). El algoritmo difiere de otros ya existentes (como el implementado en el sistema LoQo) en el hecho de que soluciona las denominadas "ecuaciones normales en forma primal" (LoQo soluciona el denominado "sistema aumentado") y en...
Un algoritmo interactivo basado en la distancia del máximo ponderado.
A partir de las preferencias locales del decisor, emitido bajo la forma de ciertos niveles de satisfacción para los objetivos, construimos un algoritmo interactivo que genera puntos eficientes de equilibrio, en los que se minimiza la distancia del máximo ponderado entre la región factible y el punto ideal. Para este algoritmo hemos probado la convergencia.
Un algoritmo para el problema de biflujo máximo simétrico no dirigido.
En este trabajo proponemos un algoritmo de O(nmlogU) para resolver el problema de biflujo máximo simétrico en una red no dirigida. Para resolver este problema se introduce un cambio de variable que permite dividir el problema original en dos problemas de flujo máximo. De esta manera se obtiene un algoritmo sencillo y eficiente donde se utilizan las herramientas computacionales propias de la resolución del clásico problema de maximizar un único flujo.
Un couplage entre un algorithme génétique et un modèle de simulation pour l'ordonnancement à court terme d'un atelier discontinu de chimie fine
Un couplage entre un algorithme génétique et un modèle de simulation pour l'ordonnancement à court terme d'un atelier discontinu de chimie fine
In this paper, a discrete-event simulation model is coupled with a genetic algorithm to treat highly combinatorial scheduling problems encountered in a production campaign of a fine chemistry plant. The main constraints and features of fine chemistry have been taken into account in the development of the model, thus allowing a realistic evaluation of the objective function used in the stochastic optimization procedure. After a presentation of problem combinatorics, the coupling strategy is then...
Un domaine très ouvert : les problèmes d'ordonnancement
Un indicateur informatique d'itinéraire pour les réseaux d'autobus
Un método primal de optimización semi-infinita para la aproximación uniforme de funciones.
En este trabajo presentamos un algoritmo que resuelve problemas clásicos de aproximación que pueden ser formulados como programas semi-infinitos lineales. Hemos estudiado la caracterización algebraica de los puntos extremos y demostrado algunas de sus propiedades. Hemos diseñado un procedimiento que genera direcciones factibles a partir de la solución de ciertos programas lineales finitos, que también caracteriza la solución óptima del problema. El método incorpora una etapa interna de purificación...
Un modèle de remplacement adaptatif
Un modelo de economía con núcleo no vacío.
La idea de competencia perfecta, que es fundamental en el estudio del equilibrio económico, supone que la economía a considerar tiene un gran número de participantes, siendo despreciable la influencia en el mercado de cada uno de ellos. Paradójicamente en los modelos clásicos, recogiendo la situación real, se adopta un modelo matemático que no puede verificar esta condición ya que sólo considera un número finito de agentes. Este hecho fue puesto de manifiesto por Aumann ([3],[4]), que fue el primero...