Search

In this paper, we focus on the coloration approach and estimation of chromatic number. First, we propose an upper bound of the chromatic number based on the orientation algorithm described in previous studies. This upper bound is further improved by developing a novel coloration algorithm. Second, we make a theoretical and empirical comparison of our bounds with Brooks’s bound and Reed’s conjecture for class of triangle-free graphs. Third, we propose an adaptation of our algorithm to deal with the team building problem respecting several hard and soft constraints. Finally, a real case study from healthcare domain is considered for illustration.

Les programmes fractionnaires consistent a optimiser un objectif mis sous la forme d'un rapport de deux fonctions lineaires ou non, soumis a un ensemble de contraintes. Differentes versions de ce modele, lineaires ou non lineaires, en nombres entiers ou en continu, ont une multitude d'applications que ce soit en optimisation combinatoire, en programmation stochastique, en bases de donnees ou en economie. Trois grandes strategies de resolution d'un programme fractionnaire emergent dans la litterature. la resolution directe, la resolution par parametrisation et la resolution d'un probleme equivalent a objectif simplifie. Un catalogue de ces modeles et applications mettant en jeu des programmes fractionnaires precede une synthese des methodes de resolution incluant en particulier celles dediees aux programmes hyperboliques (optimisation d'un rapport de deux fonctions affines soumis a des contraintes lineaires) en variables 0-1.