Dans cet article nous caractérisons, par les facettes, l'enveloppe convexe des vecteurs caractéristiques des hyperplans d'un espace projectif fini et d'un espace affine fini.

We present briefly some results we obtained with known methods to solve minimum cost tension problems, comparing their performance on non-specific graphs and on series-parallel graphs. These graphs are shown to be of interest to approximate many tension problems, like synchronization in hypermedia documents. We propose a new aggregation method to solve the minimum convex piecewise linear cost tension problem on series-parallel graphs in O(m3) operations.

In this paper, a graph partitioning problem that arises in the design ofSONET/SDH networks is defined and formalized. Approximation algorithms withperformance guarantees are presented. To solve this problem efficiently inpractice, fast greedy algorithms and a tabu-search method are proposed andanalyzed by means of an experimental study.

Nous construisons des familles de facettes du polytope du sac-à-dos quadratique en 0-1 selon les deux approches suivantes.Le Boolean quadric polytope (introduit dans le cas sans contraintes par Padberg [12]) contenant le polytope du sac-à-dos quadratique, une première approche consiste à se demander sous quelles conditions une facette du premier est aussi une facette du second et quand ces conditions ne sont pas remplies quels liftings permettent d'en faire une facette. Des réponses à ces questions sont données dans le cas de l'inégalité "coupe" introduite par Padberg.Dans une seconde approche, suivant la méthode de linéarisation d'Adams et Sherali [1], nous multiplions par une variable directe ou complémentée une facette du polytope du sac-à-dos linéaire. Nous montrons que cette approche permet d'obtenir des facettes du polytope du sac-à-dos quadratique et nous l'étendons par la suite à la multiplication de facettes du sac-à-dos quadratique lui-même.Des résultats numériques illustrent la mise en oeuvre dans un algorithme de coupes, d'inégalités ainsi obtenues.

Le traditionnel problème d'ordonnancement de type flowshop se généralise en un problème d'optimisation matricielle dansl'algèbre Max-Plus. Une famille de bornes inférieures est présentée pour ce nouveau problème et la preuve est apportée que ces bornes généralisent les bornes de Lageweg et al.

Cet article est un travail de synthèse autour de l'analyse desensibilité pour les problèmes linéaires envariables 0-1. De nombreux aspects sont ainsi abordés : historiqueet formes d'analyse de sensibilité, exemples d'application,complexité, conditions d'optimalité, algorithmes etapproches. Nous dressons par ailleurs quelques perspectives derecherche actuelles dans ce domaine.

We present a hybrid approach for the FrequencyAssignment Problem with Polarization. This problem, viewed asMax-CSP, is treated as a sequence of decision problems, CSPlike. The proposed approach combines the Arc-Consistencytechniques with a performed Tabu Search heuristic. The resultingalgorithm gives some high quality solutions and has proved itsrobustness on instances with approximately a thousand variablesand nearly ten thousand constraints.

Pour établir des plans de production et d'approvisionnements, une entreprise utilise un système de prévisions. Celui-ci est constitué d'une méthode de prévision de la demande et d'une méthode de lot-sizing permettant l'obtention de plans prévisionnels. Nous proposons une démarche permettant d'évaluer la fiabilité des prévisions fournies par un tel système. Cette analyse se base sur l'étude de l'impact des aléas de la demande sur les coûts induits par les plans prévisionnels. Nous avons appliqué ce protocole à un système de prévisions constitué du lissage exponentiel et de la méthode de Florian et Klein [5]. Dans les conditions expérimentales considérées, ce système de prévision fournit des informations fiables.