API du module Seqata

Seqata

Package Julia pour résoudre le problème SEQATA (SÉQuencement d'ATterrissage d'Avions) qui est une version adaptée du problème de la litérature ALP (Aircraft Landing Problem).

main()

Méthode principale de lancement des actions.

L'exécution de chaque action est sous-traitée à une méthode de la forme main_action. Par exemple l'action carlo de la ligne de commande (CLI) entrainera l'appelle à à la méthode main_carlo().

main_carlo()

Méthode principale d'exécution de l'action carlo.

Cette méthode exploite les arguments, construit des variables cursol et bestsol de type Solution, crée une variable solveur de type StupidSolver et appelle sa méthodes solve!(0 pour un nombre itermax d'itération.

main_descent()

Méthode principale d'exécution de l'action descent.

Cette méthode lit l'instance et créer un objet sv::DescentSolver. exploite les paramètres --durationmax et --itermax, sous-traite la résolution à la méthode solve! de l'objet sv ; Elle récupère alors le meilleur résultat obtenu, l'enregistre et affiche des statistiques de la résolution.

main_venture()

Méthode principale d'exécution de l'action venture.

Cette méthode lit l'instance et créer un objet sv::VentureSolver. exploite les paramètres et sous-traite la résolution à la méthode solve! de l'objet sv. Elle récupère alors le meilleur résultat obtenu, l'enregistre et affiche des statistiques de la résolution.

main_stats()

Méthode principale d'exécution de l'action stats.

Cette méthode lit l'instance. Si ne niveau de verbosité est suffisant, réaffiche l'instance dans différent format (dont AMPL). Dans tous les cas des statistiques sur l'instance sont affichées.

main_test()

Méthode principale d'exécution de l'action test.

Cette action est destinée à la mise au point de code (nouveaux solveurs, nouveaux voisinages, ...) Une fois la fonctionnalité opérationnelle, il faut en faire en nouveau test unitaire (i.e. en créant un nouveau fichier dans tests/text_xxx.jl) de façon à assurer la non régression de la fonctionnalité.

main_timing()

Méthode principale d'exécution de l'action timing.

Cette méthode lit une instance, lit une liste de noms d'avion puis résoud le sous-problème de timing (STP). Le choix de l'algorithme de résolution du STP est défini par l'option --timing-algo-solver alias -t qui est exploité directement par le constructeur de l'objet Solution (TODO FAIT LIEN IEN API DE SOLUTION).

La solution résolue est alors affichée sur la sortie standard et enregistrée.

Exemple

./bin/run.jl tim -t lp -i data/01.alp  -p 3,4,5,6,7,8,9,1,10,2
=> 700.0

main_validate()

Méthode principale d'exécution de l'action validate.

Cette méthode lit une instance et une solution associée, Elle vérifie la conformité de cette solution vus-à-vs des contraintes et affiche les différents viols éventuels.

Plane

Encapsule les données d'un avion.

• id: numéro interne commençant en 1, Utilisé pour l'indexation des vecteurs
• name: nom arbitraire, par exemple le numéro commençant en "p1", "p2", ... Mais pour l'instant, c'est un entier pour être conforme à ampl
• kind: le type de l'avion (car kind est un mot clé réservé en julia !)
• at: heure d'apparition de l'avion dans l'oeil du radar (inutilisé)
• lb, target, ub: les heures mini, souhaitées et maxi d'atterrissage
• ep, tp : heures d'atterrissage au lus tot et ou plus tard

REMARQUE : le type Plane est IMMUTABLE, il est lié à un avion de de l'instance et est défini une fois pour toute.

get_cost(p::Plane, t::Int; violcost::Float64 = 1000.0)

Retourne le coût de l'avion, éventuellement pénalisé si hors bornes.

to_s_alp(p::Plane)

Retourne la représentation String de l'avion conforme au format d'instance alp

Instance

Encapsule tout ce qui concerne des données d'une instance (aucune intelligence ni méthode de résolution).

Les principaux attributs sont :

• name: nom de l'instance extrait du fichier
• planes: un vercteur de Plane (dans l'ordre du fichier d'instance)
• nb_planes: nombre d'avion (redondant avec length(planes) )
• nb_kinds: nombre de type d'avion
• sepmat::Matrix{Int} : matrice des temps de séparation indicée par les numéros d'avion. Ne pas utiliser mais préférer les accesseurs getsep(Instance, Plane, Plane) dont les paramètres sont directement deux objets de type Plane

Solution

Représente une solution au problème Seqata avec ses attributs et méthodes.

Les principaux attributs sont les suivants :

• inst::Instance : l'instance associée
• planes::Vector{Plane} : lliste de avions dans l'ordre de la solution
• x et costs : vecteurs des variables de décisions associées à chaque avion
• cost : le coût global
• timingalgosolver : le solveur utilisé par la solution pour résoudre le Sous-Problème de Timing (STP) à ordre des avions fixé). Ce solveur peut être choisi via l'option --timing_algo_solver de la ligne de commande, et il est utilisé par la méthode solve!

Les principales méthodes pour manipuler une Solution sont :

• solve!, tos, toslong, getviol_penality, ...

solve!(sol::Solution)

Résoud le sous-problème de timing de la solution à partir de l'ordre des avions défini par l'attribut planes.

Le choix de l'algorithme utilisé est mémorisé dans l'attribut timing_algo_solver et peut être modifié via la ligne de commande.

Le "!" dans le nom solve!` est une convention indiquant que l'objet est modifié.

REMARQUES :

• Cette méthode peut être appelée par un solveur global qui modifie la solution courante. Cependant cet appel est souvent effectué par une méthode interne à la classe Solution (i.e. dans ce fichier, e.g shuffle!)
• Cette méthode sous traire la résolution du sous-problème de timing (STP) à un TimingSolver passé en paramètre ou défini à la construction de la variable .Solution
• IMPORTANT le TimingSolver utilisé pour résoudre de STP est reponsable de la mise à jour des trois attributs suivants x[], costs[] et cost Au besoin c'est au TimingSolver STP d'appeler explicitement la méthode auxiliaire update_costs!(::Solution)
• Si aucun TimingSolver n'a été spécifié lors de la création de la solution, alors on utilise la résolution au plus tôt (sous-optimale).

solve!(sv::DynprogTimingSolver, sol::Solution)

Résoud le problème de timing (dates d'atterrissage) des avions à permutation fixée par l'ordre des avions de l'objet sol, puis met à jour la solution sol. Utilise la méthode de Programmation Dynamique.

• Modifie les attributs de sv
• Met à jour les attribut x, costs et cost de la solution sol.

solve!(...) effectue l'exploration du voisinage passé en paramètre PARAMS

• nbh::Neighborhood voisinage qui n'est jamais modifié (au besoin il est dupliqué avant mélange)
• mode: mode d'exploration et de sélecytion du voisinage
  • :BEST : choix de la meilleures mutation
  • :RAND : choix de la première mutation améliorante
  • :ALL_BEST : mémorisation de toutes les mutations améliorantes
  • :ALL_RAND : mémorisation de toutes les mutations améliorantes dans un ordre aléatoire

update_costs!(sol::Solution; add_viol_penality = true)

Met à jour les coûts de chaque avion (sol.costs) et le coût global (sol.cost) à partir des dates d'atterrissage supposées connues (sol.x).

Si add_viol_penality est true, les contraintes sont vérifiées et un coût supplémentaire est ajouté.

PRECONDITION : le Vector s.costs est dans le même ordre que s.planes

abstract type AbstractMutation

Représente un mouvement abstrait On pourra mémoriser un vecteur de de struc de ce type pour représenter un voisinage complet.

RatedMutation

Stucture auxiliaire mémorisant une mutation et le gain associé suite à son application à une solution donnée.

Attention, l'objet Solution d'origine n'est pas mémorisé (pour l'instant !) Par contre, la solution résultante ne sera jamais mémorisée (trop coûteux !)

L'attribut optionnel gain (optionnel) est le seul lien entre les solutions d'origine et résultante.

mutate! : applique sur la solution un vecteur de RatedMutation

apply_rmuts!(sv::VnsSolver, sol::Solution; dis_rmuts::Vector{AbstractMutation})

entrées

• sol::Solution : sera modifiée ssi amélioration possible
• rmuts : les mutations (disjointes) à appliquer HYPOTHESE: toutes ces mutations prises séparément sont améliorantes.
• prefix: information spécifique à l'appelant pour les logging (e.g. nmr d'itération, ...)

sortie:

• applied_rmuts::Vector{RatedMutation}: vecteur des rmuts réellement appliquées

Effet de bord:

• modification éventuelle de la solution si amélioration
• écrit la solution améliorée sur disque
• affichage de message en fonction du level

PRINCIPE (résumé) :

On applique l'ensemble des mutations améliorantes à une copie tmpsol de la solution sol.

Si elle n'améliore pas ou si on dégrade la solution tmpsol, alors on recommence avec seulement la première mutation de muts (s'il y en a plusieurs)

Si amélioration, on recopie tmpsol dans sol et retourne les mutations effectivement appliquées

type Neighborhood

Représente un voisinage complet avec sont label et son vecteur de mutation.

Le principal attribut est un Vector de Mutation. Cette collection est triée lors de la construction pour les raisons suivantes :

• AV: rend l'ordre déterministe
• AV: améliore l'efficacité de ma méthode minmax (perf en O(1))
• AV: le coût de ce tri n'est pas très cher au regard du temps de création d'un (grand) voisinage.
• AV: simplifie l'affichage pour les tests (même si c'est secondaire)

ATTRIBUTS

• muts: Vector de mutation triées lors de la construction
• label: nom du voisinage (e.g. "S2", "P4", "D7.5", ...)
• n: largeur totale de la réunion des mutations (bornes incluses) C'est aussi typiquement la taille de l'instance si le voisinage est complet
• idx_first: indice du premier élément perturbé

EXEMPLE Le voisinage de type Swap 2 pour l'intervale de taille 11 [10,20] d'une solution pour l'instance de 500 avions pourrait être le suivant :

muts: [ [10,11]->[11,10], ..., [19,20]->[20;19] ] label: "s2" n: 11 idx_first: 10

generate_nbh(n::Int, label::AbstractString; idx_first=1)

Méthode de haut niveau permettant de générer des voisinages d'après leur nom (i.e. Symbol ou String définissant une union de familles de mutations.

paramètres :

• OLD n::Int: taille de vecteur à explorer (i.e. taille de l'instaance)
• NEW n::Int: indice du dernier élément de l'intervale à explorer (taille de l'instance en général)
• label::AbstractString: nom du voisinage ("s4", "S4","D4", "p3", "p3+d4", ...)
• ;idx_first=1 indice du premier élément de l'intervale à explorer (1 par défaut)

Génère un couple (mutations,label) en fonction du label du voisinage. Le label définit une famille ou une réunion de famille de voisinage (s4, s4+t4, D4, ...)

La construction d'un voisinage peut être la réunion de voisinages élémentaires même si c'est souvent un simple appel à une méthode générique de la classe Mutation

Liste des options disponibles de la méthode auxiliaire (définie dans le fichier Mutation.jl)

muts = generatemutations(n, idxfirst=1, idxlast=-1, addswap=false, addshift=false, addshift2g=false, addpermu=false, shiftmin=1, shiftmax=-1, # gapmin=1, # TODO gapmax=-1, permusize=4, )

Liste des familles de mutations pré-définies

• sN
• SN
• tN
• TN
• dN
• DN
• PN
• 2TN
• 2TNgN
• DN.N

EarliestTimingSolver

Résoud du Sous-Problème de Timing en plaçant les avions le plus tôt possible.

Ce solveur est largement sous-optimum, mais il est rapide à calculer et fourni à coup sûr une solution valide si l'ordre des avions donnés par la solutiom courante est réalisable.

Il est assoié à l'option ----timing-algo-solver earliest (alias -t earliest).

LpTimingSolver

Résoud du Sous-Problème de Timing par programmation linéaire.

Ce solveur résoud le sous-problème de timing consistant à trouver les dates optimales d'atterrissage des avions à ordre fixé. Par rapport aux autres solvers (e.g DescentSolver, AnnealingSolver, ...), il ne contient pas d'attribut bestsol

VERSION -t lp4 renommé en Lp : modèle diam version sans réoptimisation (coldrestart)

• modèle diam simplifié par rapport à lp3 : sans réoptimisation (coldrestart)
• pas de réoptimisation : on recrée le modèle à chaque nouvelle permu d'avion dans le solver
• seules les contraintes de séparation nécessaires à la permu sont créées
• gestion de l'option –assume_trineq true|false (true par défaut, cf lp1)
• contraintes de coût simple (diam) : une seule variable de coût par avion plus un contrainte par segment : cost[i] >= tout_segment[i]

DynprogTimingSolver

Résoud du Sous-Problème de Timing par programmation dynamique.

FayeTimingSolver

Résoud du Sous-Problème de Timing en plaçant les avions le plus tôt possible.

Ce solveur présenté par Alain Faye fait l'object d'une présentation à la ROADEF.

https://hal.archives-ouvertes.fr/hal-02354405

Il est associé à l'option ----timing-algo-solver earliest (alias -t earliest).

VentureSolver

Résoud le problème global par statégie d/ exploration aveugle.

Un voisin est tiré aléatoirement (voisinage large) et est systématiquement accepté. Par défaut, la solution initiale est choisie aléatoirement

DescentSolver
DescentSolver(inst::Instance; startsol::Union{Nothing,Solution} = nothing

Résoud le problème global par statégie de descente avec choix aléatoire du voisin.

Paramètres :

• inst: l'instance à résoudre
• startsol: la solution initiale. Celle-ci peut aussi être passée à chaque appel à la méthode solve!`

Amériorations possibles :

• revoir la gestion des options du solver (utiliser les params par clé-valeur)
• plus besoin de gérer cursol (car ici, bestsol suffit contrairement à VentureSolver)

SteepestSolver

Résoud le problème global par la statégie de descente profonde.

Le constructeur est minimaliste et ne prend que l'instance en paramètre. Les autres attributs sont passés directement à la méthode solve!.

VnsSolver

Résoud le problème global par méthode à voisinage variable.

MipDiscretSolver

Résoud le problème frontale de manière exacte en PLNE.

Utilise un modèle PLNE avec temps discrétisé (variables booléennes x_{it}).

• plus lent qu'un modèle PLNE frontal à temps continu pour une fonction de coût linéaire.
• mais ce modèle est polyvalent car il accepte une fonction de coût arbitraire.
• n'est utilisable que pour les très petites instances.

Description du modèle utilisé

Les données

- P : ensemble des avions p (d'attributs p.lb, p.target, p.ub, ...)
- T : ensemble des dates possibles t in [lb_min,ub_max]
- cost[p,t] : coût de pénalité de l'avion p s'il atterrit à la date t

Les variables

  y[p,t]: indicateur binaire des dates d'atterrissage possibles par avion
      y=1 ssi l'avion p in P atterrit à la date t in T

  x[p] variable dérivée : date d'atterrissage effective de l'avion p
    x[p] = sum(t*y[p,t] forall  t in [lb_min,ub_max]

  costs[p] : coût de chaque avion p compte tenu de sa date d'atterrissage effective
    costs[p] = sum(cost[p,t] * y[p, t] forall t = [p.lb,p.ub]

  total_cost : coût total de la solution
    total_cost = sum(cost[p,t] * y[p,t] for p in P, t in T

L'objectif

Minimiser le coût de pénalité total (total_cost)

Les contraintes

Les dates d'atterrissage sont bornées entre p.lb et p.ub

  p.lb <= x[p] <= p.ub  forall p in P

Chaque avion ne peut avoir qu'une seule date d'atterrissage.

  sum{t in T} y[p,t] = 1  forall p in P

Contraintes de séparation entre tout couple p1 et p2

Principe :
  - on prend toutes les paires d'avions possibles (p1,p2)
  - on ne traite qu'un seul des deux ordres : on fixe d'abord p1
  - on détermine les limites de proximité d'atterrissage de p2
    [t_lb_j,t_ub_j] de la plage d'interdiction
  - on ajoute les contraintes disjonctives des y[p,t] sur cette plage.
    y[p1, t_i] + y[p2, t_j] <= 1
        forall p1 in P, p2 in P  | p1.id < p2.id
        forall t_i in [p1.lb,p1.ub]
        forall t_j in [t_lb_j,t_ub_j]
    avec :
      t_lb_j = max(p2.lb, t_i - sep(p2, p1) + 1) # p2 avant p1
      t_ub_j = max(p2.ub, t_i + sep(p1, p2) - 1) # p2 après p1

MipSolver

Résoud le problème frontale de manière exacte en PLNE.

Exploite l'hypothèse de sujet Seqata, à savoir que la fonction de coût est linéaire en deux morceaux.

Description du modèle utilisé

Les données

- P (planes) : ensemble des avions p (d'attributs p.lb, p.target, p.ub, ...)
  i est l'indice de p dans les variables de décision
- cost[p,t] : coût de pénalité de l'avion p s'il atterrit à la date t

Les variables de décision

x[i in 1:n] : 
date d'atterrissage effective de l'avion i

costs[i in 1:n] : 
coût de chaque avion i compte tenu de sa date d'atterrissage effective

b[i,j] : boolean vrai si l'avion i atterrit avant l'avion j

L'objectif

Minimiser total_cost = sum(costs[i]  for i in 1:n

Les contraintes

Dates d'atterrissage bornées : Les dates d'atterrissage sont bornées entre p.lb et p.ub

p.lb <= x[p.id] <= p.ub  for p in P

Contrainte de séparation : Si i atterrit avant j, alors une durée minimale Sij doit être respectée :

x[j] >= x[i] + S[i,j] - M * (1-b[i,j]))
    for i in 1:n, j in 1:n

ms()

démarre le chrono si nécessaire (la première fois) et retourne la durée écoulée depuis ce démarrage (à la milli-seconde prêt)

ms_reset()

Réinitialise la date de référence du chrono à la date courante.

:(@ms)

chronomètre l'exécution d'une commande.

• affiche la durée depuis le lancement du programme (peut-être long en mode interactif !)
• affiche le fichier depuis lequel cette macro est appelée
• affiche la commande à exécuter
• exécute cette commande
• affiche la durée d'exécution sur la ligne suivante

Exemples

Exemple d'affichage en interactif :

@ms sleep(1)
=>
@ms todo 9349.527s (mode repl):sleep(1) ...
@ms DONE 9350.552s (mode repl):sleep(1) en 1.002s

Exemples depuis en script :

@ms using JuMP
=>
@ms todo 1.876s Seqata_usings.jl:70: using JuMP ... 
@ms DONE 5.864s Seqata_usings.jl:70: using JuMP en 3.988s