Décomposition en matrices graphiques de matrices en : application à la résolution de programmes linéaires entiers
Décomposition temporelle et caractérisation de solutions admissibles pour le problème d'ordonnancement à une machine
Décomposition temporelle et caractérisation de solutions admissibles pour le problème d'ordonnancement à une machine
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...
Del poliedro del agente viajero gráfico al de rutas de vehículos con demanda compartida.
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...
Des opérateurs d'échange et une méthode de relaxation pour le problème du voyageur de commerce
Deux remarques sur le flot dynamique maximal de coût minimal
Differential approximation of NP-hard problems with equal size feasible solutions
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...
Differential approximation of NP-hard problems with equal size feasible solutions
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...
Dijkstra's algorithm revisited: the dynamic programming connexion
Diseño de redes intercambiadoras de calor con utilidades múltiples por programación lineal.
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...