seydou-coulibaly/Linear_assignement_problem
Folders and files
| Name | Name | Last commit date | ||
|---|---|---|---|---|
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")
###################