Academic literature on the topic 'Optimisation combinatoire et linéaire'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Optimisation combinatoire et linéaire.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Journal articles on the topic "Optimisation combinatoire et linéaire"
1
Minoux, M. "Optimisation combinatoire: graphes et programmation linéaire and programmation discréte." European Journal of Operational Research 25, no. 1 (April 1986): 144–45. http://dx.doi.org/10.1016/0377-2217(86)90126-8.
Full text
2
Hamacher, Horst W. "Optimisation Combinatoire—Méthodes Mathematiques et Algorithmiques: Programmation Discrete; Optimisation Combinatoire Methodes Mathematiques et Algorithmiques: Graphes et Programmation Lineaire (Michel Sakarovitch)." SIAM Review 29, no. 1 (March 1987): 143–44. http://dx.doi.org/10.1137/1029022.
Full text
3
BLAD, J., C. SAKAROVITCH, O. CHESNEAU, and C. LECLERC. "Optimisation du plan de renouvellement du réseau d’eau potable de Bordeaux Métropole." Techniques Sciences Méthodes 10 (October 20, 2022): 89–94. http://dx.doi.org/10.36904/tsm/202210089.
Full textAbstract:
Le renouvellement des réseaux est une problématique très présente dans les milieux de l’eau et de l’assainissement. Évidemment, le réseau entier ne peut pas être remplacé chaque année, c’est pourquoi il faut choisir les portions de canalisations à renouveler. Ce choix est guidé par des problématiques économiques, politiques, de sécurité, et liées aux contraintes du terrain. Ces différents aspects peuvent être extrêmement compliqués à prendre en compte simultanément, c’est pourquoi la mise en place d’algorithmes est parfois nécessaire pour aider les experts dans leur travail. La recherche opérationnelle est le domaine de prédilection pour ce type de problématique : elle permet une optimisation selon un ou plusieurs objectifs donnés, tout en respectant les contraintes propres au métier. Dans notre cas, l’objectif porte sur différents critères guidant le choix des canalisations à renouveler : la probabilité de casse, l’âge de la canalisation, le matériau et la probabilité de casse des branchements. Les contraintes quant à elles sont liées directement au métier : la plus importante d’entre elles est de réaliser des chantiers continus, avec un linéaire minimal et maximal par chantier à respecter. En mettant en équation cet objectif et ces contraintes, nous obtenons un programme linéaire à résoudre afin de trouver le plan de renouvellement optimal pour le cas de figure en question. Nous avons donc mis en place ce modèle, puis nous l’avons résolu à l’aide d’un solveur de programme linéaire pour répondre à ce besoin de construction automatisée de chantiers et fournir au client un outil d’aide à la décision dans l’élaboration des plans de renouvellement. Ce projet a été mené pour le réseau d’eau potable de Bordeaux, mais la méthodologie employée est réutilisable pour tout type de réseau, avec un nombre de contraintes métier plus ou moins important.
4
Cheknane, Ali, Boumediene Benyoucef, Jean-Pierre Charles, and Radia Zerdoum. "Optimisation et Conception d'une Grille Collectrice Appliquée aux Photopiles Fonctionnant sous Haute Concentration Solaire." Journal of Renewable Energies 7, no. 2 (December 31, 2004): 95–108. http://dx.doi.org/10.54966/jreen.v7i2.870.
Full textAbstract:
L’objectif du présent travail est d’optimiser les dimensions géométriques de la grille de collecte des cellules solaires sous forte concentration. A ce sujet, une étude bidimensionnelle fixe le dessin des masques de la grille. Notre optimisation s’articulera sur deux modèles de grille, un modèle linéaire et un autre circulaire. Dans cette dernière, nous proposons un modèle mathématique qui sert à la minimisation des pertes de puissance, par conséquent l'amélioration du rendement de conversion. Le taux d'ombre constitue une forme de perte pour les deux modèles. Sa minimisation ne doit pas être réalisée au détriment du coefficient de transparence. Donc, nous sommes amenés, dans notre étude, à choisir un compromis, en introduisant ainsi le taux de conduction qui représente les pertes par effet Joule. A partir du point d’intersection des deux courbes (le taux de conduction et le taux d’ombre en fonction de la dimension à optimiser), nous déduisons les dimensions optimales de la grille.
5
Garba, Issa, Zakari Seybou Abdourahamane, Abdou Amadou Sanoussi, and Illa Salifou. "Optimisation de l'Evaluation de la Biomasse Fourragère en Zone Sahélienne Grâce à l’Utilisation de la Méthode de Régression Linéaire Multiple en Conjonction Avec la Stratification." European Scientific Journal, ESJ 19, no. 33 (November 30, 2023): 52. http://dx.doi.org/10.19044/esj.2023.v19n33p52.
Full textAbstract:
L'objectif de cette étude, conduite dans la zone pastorale du Niger, est d'optimiser l'estimation de la biomasse fourragère à l'échelle des faciès avec la méthode de Régression Linéaire Multiple (RLM). Les données utilisées englobent les mesures in situ de la masse herbacée entre 2001 et 2012, des données pluviométriques de station, les variables agrométéorologiques dérivées des données météorologiques de « l'European Centre for Medium-Range Weather Forecasts » (ECMWF) traitées via AgroMetShell (AMS), les images satellitaires NDVI de SPOT VEGETATION traitées avec le programme « Vegetation Analysis in Space and Time » (VAST) pour obtenir des variables biophysiques à partir des séries annuelles de NDVI décadaires, et les données de pluies estimées RFE provenant du « Famine Early Warning Systems NETwork » (FEWSNET). Les strates ont été identifiées sur la base de la carte des sols de la FAO, la couche des écorégions et les zones bioclimatiques du pays. Le modèle a été développé en utilisant la méthode de la RLM avec une approche ascendante de sélection de variables basée sur le coefficient de détermination (R²) ajusté et la racine de l'erreur quadratique moyenne (RMSE). Pour évaluer la robustesse du modèle, la validation croisée « leave one out – cross validation » (LOO-CV) a été employé pour calculer les R² de validation et effectué un diagnostic systématique des résidus afin de mieux caractériser le modèle. À l'échelle de l'ensemble de la zone d'étude (échelle globale), le RLM a produit un R² ajusté de 0,69 et un RMSE de 282 kg MS.ha-1, avec seulement une légère différence de 2,72 kg MS.ha-1 entre le RMSE de la calibration et celui de la validation. La stratification a amélioré la performance des modèles, avec des résultats prometteurs. Les modèles basés sur les types de sols FAO ont montré des R² élevés pour Ge5-1a, Qc1, Qc7-1a, Ql1-1a et Re35-a. Les écorégions telles que l'Azaouak, le Manga1 et le Manga2 ont également obtenu de bons résultats. Les paramètres des modèles par faciès ont été encore plus prometteurs, avec des R² allant de 0,77 à 0,93. Ces travaux auront un impact significatif en améliorant la qualité des informations utilisées pour planifier les initiatives de développement visant à protéger la société nigérienne contre les crises pastorales.
The aim of this study, conducted in the pastoral zone of Niger, was to optimize the estimation of forage biomass at the scale of the different facies using Multiple Linear Regression (MLR) method. The data used include field measurements of herbaceous mass between 2001 and 2012, station rainfall data, agrometeorological variables derived from meteorological data of the European Centre for Medium-Range Weather Forecasts (ECMWF) processed via AgroMetShell (AMS), SPOT VEGETATION NDVI satellite images processed with the Vegetation Analysis in Space and Time (VAST) program to obtain biophysical variables from annual decadal NDVI series, and estimated RFE rainfall data from the US Famine Early Warning Systems NETwork (FEWSNET) to calculate annual rainfall totals. We identified strata based on the FAO soil map, the ecoregion layer and the country's bioclimatic zones. The model was developed using MLR with a bottom-up variable selection approach based on adjusted R² and root mean square error (RMSE). To assess the model's robustness, we used leave-one-out cross validation (LOO-CV) to calculate the validation R², and carried out systematic residual diagnostics to better characterize the model. At the scale of the entire study area (global scale), the MLR produced an adjusted R² of 0.69 and an RMSE of 282 kg MS.ha-1, with only a slight difference of 2.72 kg MS.ha-1 between the calibration and validation RMSE. Stratification improved model performance, with promising results. Models based on FAO soil types showed high R²s for Ge5-1a, Qc1, Qc7-1a, Ql1-1a and Re35-a. Ecoregions such as Azaouak, Manga1 and Manga2 also performed well. Model parameters by facies were even more promising, with R² ranging from 0.77 to 0.93. This work will have a significant impact in improving the quality of information used to plan development initiatives for protecting Nigerian society from pastoral crises.
6
TALAGRAND, Michel. "Exposé Bourbaki 859 : Verres de spin et optimisation combinatoire." Astérisque, November 6, 2018. http://dx.doi.org/10.24033/ast.496.
Full text
7
Bürgisser, Peter, and Christian Ikenmeyer. "A max-flow algorithm for positivity of Littlewood-Richardson coefficients." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AK,..., Proceedings (January 1, 2009). http://dx.doi.org/10.46298/dmtcs.2749.
Full textAbstract:
International audience Littlewood-Richardson coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the general linear group $\mathrm{GL}(n,\mathbb{C})$. They have a wide variety of interpretations in combinatorics, representation theory and geometry. Mulmuley and Sohoni pointed out that it is possible to decide the positivity of Littlewood-Richardson coefficients in polynomial time. This follows by combining the saturation property of Littlewood-Richardson coefficients (shown by Knutson and Tao 1999) with the well-known fact that linear optimization is solvable in polynomial time. We design an explicit $\textit{combinatorial}$ polynomial time algorithm for deciding the positivity of Littlewood-Richardson coefficients. This algorithm is highly adapted to the problem and it is based on ideas from the theory of optimizing flows in networks. Les coefficients de Littlewood-Richardson sont les multiplicités dans la décomposition du produit tensoriel de deux représentations irréductibles du groupe général linéaire $\mathrm{GL}(n,\mathbb{C})$. Ces coefficients ont plusieurs interprétations en combinatoire, en théorie des représentations et en géométrie. Mulmuley et Sohoni ont observé qu'on peut décider si un coefficient de Littlewood-Richardson est positif en temps polynomial. C'est une conséquence de la propriété de saturation des coefficients de Littlewood-Richardson (démontrée par Knutson et Tao en 1999) et le fait bien connu que la programmation linéaire est possible en temps polynomial. Nous décrivons un algorithme $\textit{combinatoire}$ pour décider si un coefficient de Littlewood-Richardson est positif. Cet algorithme est bien adapté au problème et il utilise des idées de la théorie des flots maximaux sur des réseaux.
8
Zergane, Slimane, and Arezki Smaïli. "Optimisation de la micro-localisation des aérogénérateurs dans un parc éolien." Journal of Renewable Energies 14, no. 4 (October 24, 2023). http://dx.doi.org/10.54966/jreen.v14i4.295.
Full textAbstract:
Dans un parc éolien, il est bien connu que la performance globale du parc est fortement liée aux types d’arrangement des aérogénérateurs dans le site. Un arrangement trop dense entraînerait des pertes considérables de puissance. Dans ce contexte, intervient notre travail, pour déterminer la micro-localisation optimale des éoliennes dans un parc et minimiser l’effet dû aux interférences de sillages des éoliennes. Pour ce faire, nous proposons un modèle numérique, basé sur la description linéaire du sillage, et la méthode d’optimisation de Monte Carlo, afin d’étudier la micro-localisation optimale des turbines en fonction des caractéristiques aérodynamiques et des espacements entre les turbines. La validité des résultats de simulation a été étudiée en utilisant les données expérimentales de NREL.
9
Lewis, Stephen, and Nathaniel Thiem. "Nonzero coefficients in restrictions and tensor products of supercharacters of $U_n(q)$ (extended abstract)." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AN,..., Proceedings (January 1, 2010). http://dx.doi.org/10.46298/dmtcs.2840.
Full textAbstract:
International audience The standard supercharacter theory of the finite unipotent upper-triangular matrices $U_n(q)$ gives rise to a beautiful combinatorics based on set partitions. As with the representation theory of the symmetric group, embeddings of $U_m(q) \subseteq U_n(q)$ for $m \leq n$ lead to branching rules. Diaconis and Isaacs established that the restriction of a supercharacter of $U_n(q)$ is a nonnegative integer linear combination of supercharacters of $U_m(q)$ (in fact, it is polynomial in $q$). In a first step towards understanding the combinatorics of coefficients in the branching rules of the supercharacters of $U_n(q)$, this paper characterizes when a given coefficient is nonzero in the restriction of a supercharacter and the tensor product of two supercharacters. These conditions are given uniformly in terms of complete matchings in bipartite graphs. La théorie standard des supercaractères des matrices triangulaires supérieures unipotentes finies $U_n(q)$ donne lieu à une merveilleuse combinatoire basée sur les partitions d'ensembles. Comme avec la théorie des représentations du groupe symétrique, Les plongements $U_m(q) \subseteq U_n(q)$ pour $m \leq n$ mènent aux règles de branchement. Diaconis et Isaacs ont montré que la restriction d'un supercaractère de $U_n(q)$ est une combinaison linéaire des supercaractères de $U_m(q)$ avec des coefficients entiers non négatifs (en fait, elle est polynomiale en $q$). Dans une première étape vers la compréhension de la combinatoire des coefficients dans les règles de branchement des supercaractères de $U_n(q)$, ce texte caractérise les coefficients non nuls dans la restriction d'un supercaractère et dans le produit des tenseurs de deux supercaractères. Ces conditions sont données uniformément en termes des couplages complets dans des graphes bipartis.
10
Chan, Yao-Ban. "Upper bounds on the growth rates of hard squares and related models via corner transfer matrices." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings, 27th..., Proceedings (January 1, 2015). http://dx.doi.org/10.46298/dmtcs.2486.
Full textAbstract:
International audience We study the growth rate of the hard squares lattice gas, equivalent to the number of independent sets on the square lattice, and two related models — non-attacking kings and read-write isolated memory. We use an assortment of techniques from combinatorics, statistical mechanics and linear algebra to prove upper bounds on these growth rates. We start from Calkin and Wilf’s transfer matrix eigenvalue bound, then bound that with the Collatz-Wielandt formula from linear algebra. To obtain an approximate eigenvector, we use an ansatz from Baxter’s corner transfer matrix formalism, optimised with Nishino and Okunishi’s corner transfer matrix renormalisation group method. This results in an upper bound algorithm which no longer requires exponential memory and so is much faster to calculate than a direct evaluation of the Calkin-Wilf bound. Furthermore, it is extremely parallelisable and so allows us to make dramatic improvements to the previous best known upper bounds. In all cases we reduce the gap between upper and lower bounds by 4-6 orders of magnitude. Nous étudions le taux de croissance du système de particules dur sur un réseau carré. Ce taux est équivalent au nombre d’ensembles indépendants sur le réseau carré. Nous étudions également deux modèles qui lui sont reliés : les rois non-attaquants et la mémoire isolée d’écriture-réécriture. Nous utilisons techniques diverses issues de la combinatoire, de la mécanique statistique et de l’algèbre linéaire pour prouver des bornes supérieures sur ces taux de croissances. Nous partons de la borne de Calkin et Wilf sur les valeurs propres des matrices de transfert, que nous bornons à l’aide de la formule de Collatz-Wielandt issue de l’algèbre linéaire. Pour obtenir une valeur approchée d’un vecteur propre, nous utilisons un ansatz du formalisme de Baxter sur les matrices de transfert de coin, que nous optimisons avec la méthode de Nishino et Okunishi qui exploite ces matrices. Il en résulte un algorithme pour calculer la borne supérieure qui n’est plus exponentiel en mémoire et est ainsi beaucoup plus rapide qu’une évaluation directe de la borne de Calkin-Wilf. De plus, cet algorithme est extrêmement parallélisable et permet ainsi une nette amélioration des meilleurs bornes supérieures existantes. Dans tous les cas l’écart entre les bornes supérieures et inférieures s’en trouve réduit de 4 à 6 ordres de grandeur.
Dissertations / Theses on the topic "Optimisation combinatoire et linéaire"
1
Ben, Messaoud Saïd. "Caractérisation, modélisation et algorithmes pour des problèmes de découpe guillotine." Troyes, 2004. http://www.theses.fr/2004TROY0006.
Full textAbstract:
Le travail de recherche réalisé dans cette thèse concerne le domaine de placement et de découpe à deux dimensions avec prise en compte de la contrainte guillotine. Jusqu'à présent, dans la littérature, aucune définition mathématique de la contrainte guillotine n'a été donnée. L'objet de cette thèse est de caractériser et modéliser formellement la contrainte guillotine et proposer des algorithmes pour résoudre différents problèmes de découpe à deux dimensions. Nous proposons une condition nécessaire et suffisante pour caractériser une configuration guillotine. Ce résultat constitue la base d'un algorithme polynomial permettant de vérifier si une configuration données est guillotine. Cette caractérisation est ensuite exploitée pour mettre au point un modèle linéaire pour le problème de découpe guillotine sur bande. Par la suite, nous étudions le problème de découpe sur bande. Ce problème consiste à placer un ensemble de pièces rectangulairs sur une bande de largeur fixe et de hauteur supposée infinie tout en respectant la contrainte guillotine avec pour objectif la minimisation de la hauteur utilisée. Deux heuristiques constructives sont proposées et ont été testées sur un grand nombre d'instances. L'originalité réside dans la façon de remplir les couches et de déterminer leurs hauteurs. Dans la dernière partie, nous traitons un problème de découpe sur un ensemble de plaques de largeur identique. Une des heuristiques proposées précédement a été généralisée pour résoudre ce problème. L'approche a été testée sur un grand nombre d'instancesThis thesis focuses on a two-dimensional cutting stock problem where guillotine constraint is required. Despite the fact that guillotine constraint was introduced at the very beginning of the cutting stock and bin packing research, no mathematical definition has been given. Then the purpose of the thesis is to characterize and model the guillotine constraint and to propose efficient algorithms to solve variants of the two-dimensional cutting stock. We first give a necessary and sufficient condition for a cutting pattern to be guillotine. And consequently we propose a polynomial algorithm to check this condition for any given pattern. Then we give a linear program that describes explicitly the guillotine constraint by means of the previous condition. Thereafter, we are interested in strip packing problem which consists of packing rectangular items of predetermined sizes into a strip of fixed width and infinite height. The aim is to find cutting pattern that minimizes the total height used and where guillotine constraint is required. Two constructive heuristics are proposed and tested on a great number of instances. The originality lies in the way of filling the shelves and of determining their heights. In the last part, we deal with a variant of the two-dimensional cutting stock, in which, we have an infinite number of rectangular sheets of raw material having identical width. The aim is to cut off a given set of items while minimizing the waste. One of the heuristics proposed previously was generalized and tested on a great number of instances
2
Hamiez, Jean-Philippe. "Coloration de graphes et planification de rencontres sportives : heuristiques, algorithmes et analyses." Angers, 2002. http://www.theses.fr/2002ANGE0053.
Full textAbstract:
Les métaheuristiques sont une source d'inspiration inépuisable pour la résolution efficace de problèmes combinatoires. Nos travaux sur la coloration de graphes et un problème de planification le confirment. Nous avons ainsi développé les premières adaptations de la recherche dispersée pour la coloration et de la recherche tabou pour le problème de planification. Nos résultats rejoignent les meilleurs publiés. Nous avons aussi analysé des solutions du problème de coloration. Nos analyses ont révélé que certains ensembles de sommets sont représentatifs des solutions. Cette information nous a permis, non seulement de caractériser la diversité des solutions, mais aussi d'améliorer un algorithme tabou. Concernant la planification, différentes propriétés de la configuration initiale utilisée par notre algorithme tabou ont été exploitées pour développer, dans un premier temps, une approche de réparation exhaustive. Nos résultats dépassent largement ceux des meilleures approches connues malgré une complexité exponentielle. Pour tenter de diminuer cette complexité, nous avons, là encore, observé les solutions, et les choix effectués pour y parvenir. Cela a été profitable puisque nous avons conçu le premier algorithme à complexité linéaire pour résoudre le problème.
3
Létocart, Lucas. "Problèmes de multicoupe et de multiflot en nombres entiers." Paris, CNAM, 2002. http://www.theses.fr/2002CNAM0430.
Full textAbstract:
L'objet de cette thèse est l'étude et la résolution de problèmes d'optimisation combinatoire dans les graphes : les problèmes de multiflot maximal en nombres entiers et de multicoupe minimale, ainsi que de plusieurs problèmes connexes : les problèmes de coupe et flot multiterminaux, de flots inséparables, de multichemins et de chemins disjoints par les arêtes. Après avoir effectué une étude bibliographique, nous montrons que les problèmes de multiflot et de multicoupe sont polynomiaux dans les arbres orientés puis nous proposons un algorithme de séparation et d 'évaluation afin de résoudre le problème NP-difficile de la multicoupe minimale dans les arbres non orientés. Nous proposons enfin des algorithmes polynomiaux pour les problèmes de coupe et de flot multiterminaux et pour le problème de la multicoupe minimale dans les anneauxThe object of this work is to study and to solve combinatorial optimization problems in graphs : maximum integral multiflow and minimum multicut problems, and some subproblems, as the multiterminal cut and flow, the unspittable flow, the multipath and the edge disjoint path problems are polynomial in directed trees and we propose a polynomial algorithm to solve both problems in rooted trees. We use linear programming and semi-definite programming in a branch and bound algorithm in order to solve the NP-hard minimum multicut problem in undirected trees. We propose also polynomial algorithms for the multiterminal cut and flow problems and for the minimum multicut problem in rings
4
Przybylski, Anthony. "Méthode en deux phases pour la résolution exacte de problèmes d'optimisation combinatoire comportant plusieurs objectifs : nouveaux développements et application au problème d'affectation linéaire." Nantes, 2006. http://www.theses.fr/2006NANT2123.
Full textAbstract:
Dans ce travail, nous nous intéressons à la résolution exacte de problèmes d'optimisation combinatoire multi-objectif par la méthode en deux phases. Pour cela, nous utilisons le problème d'affectation comme support de nos investigations. La méthode en deux phases est un cadre de résolution général qui a été popularisé par Ulungu en 1993 avec comme idée centrale d'exploiter la structure spécifique des problèmes d'optimisation combinatoire pour leur résolution dans un contexte multi-objectif. Elle a depuis été appliquée sur un grand nombre de problèmes, en se limitant toutefois au contexte bi-objectif. Nous apportons des affinements à cette méthode et à son application au problème d'affectation bi-objectif. En particulier, nous proposons des bornes supérieures améliorées et l'utilisation d'un algorithme de ranking comme principale routine pour la seconde phase de la méthode. Nous proposons ensuite une généralisation de cette méthode au contexte multi-objectif, qui est réalisée en deux temps. Pour la première phase, une analyse de la décomposition de l'ensemble des poids en correspondance avec les points supportés extrêmes, nous permet de mettre en évidence une notion d'adjacence géométrique entre ces points, et une condition d'exhaustivité sur leur énumération. La seconde phase consiste en la définition et l'exploration de régions dans lesquelles des énumérations sont nécessaires afin d'achever la résolution du problème. Notre solution repose essentiellement sur une description appropriée de ces régions qui en permet une exploration par analogie avec le cas bi-objectif, et permet donc la réutilisation de stratégies d'exploration existantes pour ce contexte. Les résultats expérimentaux sur le problème d'affectation tri-objectif attestent de l'efficacité de la méthodeThe purpose of this work is the exact solution of multi-objective combinatorial optimisation problems with the two phase method. For this, we use assignment problem as a support for our investigations. The two phase method is a general solving scheme that has been popularized by Ulungu in 1993. The main idea of this method is to exploit the specific structure of combinatorial optimisation problems in a multi-objective context. It has been applied to a number of problems, with a limitation on the bi-objective case. We present improvements in this method and in its application to the bi-objective assignment problem. In particular, we propose improved upper bounds and the use of a ranking algorithm as main routine in the second phase of the method. We propose next a generalisation of this method to the multi-objective case, done in two steps. For the first phase, we analyse the weight set decomposition in correspondance with the nondominated extreme points. This allows us to highlight a geometric notion of adjacency between these points and an optimality condition on their enumeration. The second phase consists in the definition and the exploration of the area inside of which enumerations are required to finalize the resolution to the problem. Our solution is based primarily on an appropriate description of this area, that allows to explore it by analogy with the bi-objective case. It is therefore possible to reuse a strategy developped for this case. Experimental results on three-objective assignment problem show the efficiency of the method
5
Gioan, Emeric. "Correspondance naturelle entre bases et réorientations des matroïdes orientés." Bordeaux 1, 2002. http://www.theses.fr/2002BOR12641.
Full textAbstract:
Dans un matroi͏̈de orienté ordonné, on définit et on étudie, de façons intrinsèque et constructive, une correspondance naturelle entre les bases et les réorientations, préservant les activités énumérées par le polynôme de Tutte. Elle a de fortes propriétés de dualité, et géométriques, et peut-être construite inductivement via les mineurs relatifs au plus grand élément, ou via une décomposition en mineurs d'activités (1,0). Dans un graphe on obtient des bijections actives entre arbres couvrants et classes d'orientations, ou orientations acycliques avec unique puits fixé, ou avec unique puits et unique source adjacents fixés. Géométriquement, on obtient en général des extensions de la programmation linéaire combinatoire, selon l'ordre total des éléments : chaque réorientation est décomposée en régions bornées de mineurs du matroi͏̈de orienté et de son dual, et pour celles-ci on optimise une suite de faces emboîtées pour une suite de fonctions objectives.
6
Lalande, Jean-François. "Conception de réseaux de télécommunications : optimisation et expérimentations." Phd thesis, Université de Nice Sophia-Antipolis, 2004. http://tel.archives-ouvertes.fr/tel-00008012.
Full textAbstract:
Dans cette thèse, nous nous intéressons aux problèmes d'optimisation dans les réseaux de télécommunication. Un premier objectif consiste à identifier les problèmes spécifiques aux réseaux optiques et satellitaires, et à présenter des contributions pour l'optimisation des ressources de ces réseaux. Le second objectif est de présenter une contribution logicielle pour la conception et l'optimisation de réseaux.La première partie débute par la présentation des réseaux optiques WDM. Nous abordons ensuite les modèles pour les réseaux optiques et satellitaires et proposons des méthodes algorithmiques nouvelles pour optimiser l'allocation des ressources de ces réseaux. Nous traitons ainsi le problème du routage, du groupage et de la protection des réseaux WDM successivement dans trois chapitres puis nous nous intéressons à un algorithme dédié à l'allocation de fréquences dans les réseaux satellitaires. Enfin, pour chaque problème, nous présentons des résultats expérimentaux sur des instances de réseaux réels.
La deuxième partie de cette thèse présente les développements logiciels qui ont été entrepris. Le premier chapitre présente le logiciel Porto dédié à la résolution de problèmes de routage, groupage et protection dans des réseaux optiques utilisant trois niveaux de brassage. Dans un second chapitre nous présentons le logiciel Mascopt, une bibliothèque d'optimisation pour le domaine des graphes et des réseaux qui a servi notamment à réaliser les expérimentations présentées dans la première partie.
7
Roupin, Frédéric. "Algorithmes Combinatoires et Relaxations par Programmation Linéaire et Semidéfinie. Application à la Résolution de Problèmes Quadratiques et d'Optimisation dans les Graphes." Habilitation à diriger des recherches, Université Paris-Nord - Paris XIII, 2006. http://tel.archives-ouvertes.fr/tel-00596215.
Full textAbstract:
Cette synthèse de travaux de recherche concerne l'algorithmique dans les graphes et l'utilisation de la pro- grammation linéaire et semidéfinie positive (SDP) dans le cadre de la résolution exacte ou approchée de plusieurs problèmes fondamentaux de l'Optimisation Combinatoire. L'approche semidéfinie, qui conduit à des relaxations convexes mais non-linéaires, a permis d'obtenir de remarquables résultats théoriques en approximation et devient à présent utilisable en pratique (tout comme la programmation linéaire qui en est un cas particulier). Nos travaux comportent une forte composante algorithmique et des études de complexité de plusieurs problèmes d'optimisation dans les graphes. Nous considérons tout d'abord le problème de la recherche d'un sous-graphe dense de taille fixée pour lequel nous présentons un algorithme polynomial avec ga- ranties de performances fondé sur la programmation linéaire et quadratique. Puis, nous étudions les problèmes de multiflots entiers et de multicoupes pour lesquels nous avons identifié de nombreux cas po- lynomiaux dans des graphes particuliers importants en pratique : arborescences, grilles, anneaux. D'une part, les solutions fractionnaires fournies par certaines relaxations linéaires de ces problèmes sont le point de départ d'algorithmes de résolution efficaces. D'autre part, les propriétés des programmes linéaires uti- lisés nous permettent également d'élaborer des algorithmes purement combinatoires et de démontrer leur validité (matrices totalement unimodulaires, théorème des écarts complémentaires). Nous proposons également des approches systématiques pour élaborer des relaxations semidéfinies pour les programmes quadratiques, modèles de très nombreux problèmes combinatoires et continus. Plus précisément, nous étudions les liens entre relaxations semidéfinies et des relaxations lagrangiennes partielles de programmes quadratiques contenant des contraintes linéaires. En particulier, les fonctions quadratiques constantes sur une variété affine sont entièrement caractérisées. Ceci permet de facilement comparer les différentes familles de contraintes redondantes proposées dans la littérature dans l'approche semidéfinie dans le cadre unifié de l'approche lagrangienne. Puis, nous présentons un algorithme pour élaborer des relaxations semidéfinies à partir de relaxations linéaires existantes. L'objectif est de pro- fiter des résultats théoriques et expérimentaux obtenus dans l'approche linéaire. Nous avons développé un logiciel (SDP_S) grâce à ces résultats. Il permet de formuler automatiquement et facilement des relaxations semidéfinies pour tout problème pouvant être formulé comme un programme quadratique en variables bivalentes. Notre méthode peut se généraliser à certains programmes à variables mixtes. Enfin, nous appliquons les méthodes décrites précédemment à une série de problèmes combinatoires classiques. Nos expérimentations montrent que l'approche semidéfinie est à présent pertinente dans la pra- tique sous certaines conditions. Premièrement, nous présentons des méthodes de séparation/évaluation efficaces fondées sur la SDP pour la résolution exacte des problèmes max 2sat et Vertex-Cover. Deuxièmement, nous proposons plusieurs bornes par SDP de grande qualité pour des problèmes particu- lièrement difficiles à résoudre par les approches linéaires : k-cluster, CMAP (un problème de placement de tâches avec contraintes de ressources), et le problème de l'affectation quadratique (QAP). Pour ce dernier nous présentons également un algorithme de coupes performant fondé sur la programmation semidéfinie. Afin d'obtenir des algorithmes efficaces en pratique, nous mettons en oeuvre non seulement nos méthodes d'élaboration de relaxations SDP, mais également des techniques algorithmiques issues de l'approximation polynomiale, ainsi que des outils spécifiques de résolution numérique des programmes semidéfinis.
8
Mancel, Catherine. "Modélisation et résolution de problèmes d'optimisation combinatoire issus d'applications spatiales." Toulouse, INSA, 2004. http://www.theses.fr/2004ISAT0011.
Full textAbstract:
Nos travaux portent sur la modélisation et la résolution de problèmes d'optimisation combinatoire émergeant dans le cadre de la planification de missions spatiales. Ces problèmes de grande taille présentent des caractéristiques communes en termes de types de données, de contraintes et de critères à optimiser. Nous nous focalisons sur l'apport de la programmation linéaire pour ces problèmes, associée à des méthodes de simplification de l'espace de recherche, par décomposition ou grâce à des techniques de propagation de contraintes. Nous avons plus particulièrement étudié deux problèmes. Le premier concerne la planification de communications sonde/satellite et d'expériences dans un projet d'exploration martienne. Une décomposition de ce problème permet de le formuler comme deux problèmes indépendants : un problème de planification des communications que nous modélisons par un programme linéaire en nombres entiers et que nous résolvons de façon exacte par un algorithme classique, et un problème d'aide à la décision pour la planification des expériences, pour lequel nous établissons des courbes d'évaluation de la charge des ressources, déduites de l'application de techniques de propagation de contraintes basées sur un raisonnement énergétique. Le second problème étudié est celui de la planifiacation de prises de vue d'un satellite d'observation de la Terre. Nous proposons un modèle linéaire en variables mixtes et nous développons une approche de résolution par génération de colonnes, qui est une adaptation de la programmation linéaire au traitement de problèmes de grande taille, faisant appel à certaines techniques de décomposition des modèlesIn this work we are concerned with combinatorial optimization problems stemming from space missions planning. These huge problems have some common features concerning the type of data, constraints and criteria to be optimized. We focus on linear programming for modeling and solving these problems, associated to methods for search space simplification, using decomposition or some constraint propagation techniques. We more particularly address two problems. The first one concerns a mission which aims at a scientific investigation of Mars. It consists in planning both communication slots between martian probes and a satellite, and experiments on probes. We use linear integer programming to model and solve to optimality the sub-problem of communication slots planning, and we develop an decision-aid oriented method using constraint propagation for experiments planning. The second problem occurs in the context of the french program of Earth observing with satellites. It consists in selecting and scheduling images taken by one satellite in order to maximize a quality criterion. We give a linear model and we propose a column generation approach, based on the Dantzig-Wolfe decomposition of the model, to calculate upper bounds for this problem and in order to solve it
9
Segura, Jean-Mathieu. "Localisation et affectation : application aux réseaux de contenus." Paris 6, 2011. http://www.theses.fr/2011PA066054.
Full textAbstract:
Sur le réseau Internet, les usagers demandent un accès de plus en plus rapide à des contenus de plus en plus volumineux. Notamment, le service de Vidéo à la Demande (VoD) voit la taille des données échangées augmenter fortement avec l'arrivée de la haute définition et des vidéos en 3D. Les réseaux physiques des fournisseurs d’accès à Internet doivent ainsi sans cesse s'adapter à l'augmentation des demandes de téléchargements. La solution qui a pendant longtemps consisté à augmenter les débits en posant de nouveaux câbles connaît aujourd'hui ses limites. Une nouvelle approche efficace consiste à déployer des réseaux de distribution de contenus (CDN) qui peuvent être décrits comme un ensemble d'équipements, appelés caches, où les données sont dupliquées et stockées au plus proche des utilisateurs. Lors de la conception d'un CDN, plusieurs questions se posent quant au nombre, à la dimension et la localisation des caches, de manière à servir au mieux l'usager. En nous plaçant du point de vue d'un fournisseur d'accès à Internet, nous montrons que la conception d'un service de VoD s'inscrit dans la problématique de localisation et d'affectation de ressources en recherche opérationnelle. En particulier, nous nous intéressons à deux problèmes mêlant localisation et affectation: le problème du 2-p-Médian et le problème de Location-Dispatching. Nous montrons que, dans le cas où le réseau considéré est un arbre, le premier problème est polynomial. Nous formulons le second problème comme un programme linéaire en nombre entiers et nous proposons une étude polyédrale du polytope associé, ainsi que de nouvelles inégalités valides. A partir de cette étude, nous déduisons un algorithme de coupes et branchements pour résoudre le problème. Nous proposons également de nouvelles formulations entières de problèmes de localisation et d'affectation et nous comparons expérimentalement leurs efficacités. En conclusion nous tentons de répondre aux questions posées par la conception de CDN à partir des différentes approches étudiées dans ce document.
10
Haouari, Mohamed. "Les problèmes de tournées avec fenêtres de temps, modélisation et algorithmes de résolution exacte et heuristique." Châtenay-Malabry, Ecole centrale de Paris, 1991. http://www.theses.fr/1991ECAP0183.
Full textAbstract:
Cette thèse présente une nouvelle heuristique en deux phases pour le PTVFT. Des tests empiriques montrent que cdette heuristique est très efficace. De même, plusieurs variantes du PTVFT sont résolues d'une manière exacte grâce à l'approche de génération de colonnes. La taille et la complexité des problèmes résolus dépasse nettement celle des algorithmes déjà publié dans la littérature scientifique.
Books on the topic "Optimisation combinatoire et linéaire"
1
Korte, B. H. Optimisation combinatoire: Théorie et algorithmes. Paris: Springer-Verlag Paris, 2010.
Find full text
2
Meziani, Rachid. Méthodes interactives en optimisation linéaire sur micro-ordinateur: Conception, réalisation et application. Grenoble: A.N.R.T. Université Pierre Mendès France Grenoble 2, 1987.
Find full text
3
Ciarlet, Philippe G. Introduction à l'analyse numérique matricielle et à l'optimisation. Paris: Masson, 1985.
Find full text
4
Maurras, Jean F. Programmation Linéaire, Complexité: Séparation et Optimisation (Mathématiques et Applications). Springer, 2002.
Find full text
5
Baillargeon. Programmation linéaire en gestion: Modèles de programmation linéaire, optimisation et solution informatique. Smg, 1999.
Find full text
6
Recherche Opérationnelle - Tome 1: Programmation linéaire. Optimisation combinatoire. Programmation dynamique. Graphes. Métaheuristiques. ELLIPSES, 2012.
Find full text
7
Introduction to non-linear optimization. London: Macmillan, 1985.
Find full text
8
Introduction to non-linear optimization. New York: Springer-Verlag, 1985.
Find full text
9
Compact Numerical Methods for Computers: Linear Algebra and Function Minimisation. 2nd ed. Taylor & Francis, 1990.
Find full textBook chapters on the topic "Optimisation combinatoire et linéaire"
1
Korte, Bernhard, Jens Vygen, Jean Fonlupt, and Alexandre Skoda. "Programmation linéaire." In Optimisation combinatoire, 51–72. Paris: Springer Paris, 2010. http://dx.doi.org/10.1007/978-2-287-99037-3_3.
Full text
2
Korte, Bernhard, Jens Vygen, Jean Fonlupt, and Alexandre Skoda. "Algorithmes de programmation linéaire." In Optimisation combinatoire, 73–99. Paris: Springer Paris, 2010. http://dx.doi.org/10.1007/978-2-287-99037-3_4.
Full text
3
Korte, Bernhard, Jens Vygen, Jean Fonlupt, and Alexandre Skoda. "Arbres couvrants et arborescences." In Optimisation combinatoire, 131–54. Paris: Springer Paris, 2010. http://dx.doi.org/10.1007/978-2-287-99037-3_6.
Full text
4
Korte, Bernhard, Jens Vygen, Jean Fonlupt, and Alexandre Skoda. "b-couplages et T-joints." In Optimisation combinatoire, 295–314. Paris: Springer Paris, 2010. http://dx.doi.org/10.1007/978-2-287-99037-3_12.
Full text
5
Korte, Bernhard, Jens Vygen, Jean Fonlupt, and Alexandre Skoda. "Multiflots et chaînes arête-disjointes." In Optimisation combinatoire, 493–517. Paris: Springer Paris, 2010. http://dx.doi.org/10.1007/978-2-287-99037-3_19.
Full text
6
Del Moral, Pierre, and Christelle Vergé. "Optimisation et Combinatoire énumérative." In Mathématiques et Applications, 325–46. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014. http://dx.doi.org/10.1007/978-3-642-54616-7_11.
Full text
7
"I.1 Algèbre linéaire et bilinéaire." In Optimisation et analyse convexe, 1–2. EDP Sciences, 2020. http://dx.doi.org/10.1051/978-2-7598-0700-0-003.
Full text
8
"I.1 Algèbre linéaire et bilinéaire." In Optimisation et analyse convexe, 1–2. EDP Sciences, 2020. http://dx.doi.org/10.1051/978-2-7598-0700-0.c003.
Full text
9
SBAI, Ines, and Saoussen KRICHEN. "Tournées de véhicules avec contraintes de chargement : des méthodes de résolution." In Optimisation et apprentissage, 7–27. ISTE Group, 2023. http://dx.doi.org/10.51926/iste.9071.ch1.
Full textAbstract:
Ce chapitre combine deux des problèmes d'optimisation combinatoire les plus étudiés, le problème d'acheminement de véhicules capacitaires (CVRP) et le problème d'emballage de bacs en deux/trois dimensions (2/3D-BPP). Nous fournissons une revue actualisée des variantes du L-CVRP et analysons certaines des méthodes d'optimisation les plus populaires présentées dans la littérature existante. Parallèlement, nous discutons de leurs applications pour résoudre des problèmes concrets.
10
"V.3 La dualité en programmation linéaire." In Optimisation et analyse convexe, 171–216. EDP Sciences, 2020. http://dx.doi.org/10.1051/978-2-7598-0700-0-017.
Full text