Skip to content

Linear assignment problem resolution using Hungarian algorithm and comparing it with GLPK 's solver result.

Notifications You must be signed in to change notification settings

seydou-coulibaly/Linear_assignement_problem

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation



			Dispositions des documents :
			  *Dossiers
				     data/ :  contient quelques instances du problème
             src/  :  contient le code source des algorithmes
             opt/  :  contient le resultat de la valeur des optimums des instances
        *Fichiers
          Format-Instance : décrit le format des instances
          graphique       : graphique comparant les temps d'exécutions des deux algorithmes (GLPK+JUMP et celui implemené)
          README          : Ce fichier
          TempsInstance   : Rélévé des temps d'exécutions des deux algorithmes

          ######################
            Comparaison
          #####################
            On observe que l'algorithme LAP implémenté est meilleure que GLPK+JUMP sur des instances de petites tailles.
            GLPK+JUMP fournit des résultats à moins de 2 min sur les instances de taille 500,600,700 alors que LAP y met
            plus de 18 min pour les résoudre. On oublie pas que cette analyse depend fortement de la forme des données.
            On compte 24 instances dont les 21 premiers sont générées aléatoirement pour une execution rapide et les trois
            derniers sont issues de la collection des instances de OR-Library.

            Remarque : L'analyse a été faite sur un programme deja compilé pour une bonne rapidité

						################
							Exécution
						################

						Lancer include("main.jl")
						puis  											execLap(typeResolution,instance)		****************************
						Où typeResolution : est l'algorithme choisit, ces valeurs possibles sont
								1) LAP				:	algorithme ad-hoc LAP implémenté
								2) GLPK-JUMP	:	utilisation du solver GLPK
						Et instance : nom d'instance

						###################
								EXEMPLE : execLap("GLPK-JUMP","../data/assign5.txt")
						###################

About

Linear assignment problem resolution using Hungarian algorithm and comparing it with GLPK 's solver result.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages