Projet de Recherche Operationnelle - SM602

Resolution de problemes de transport equilibres (Nord-Ouest, Balas-Hammer, methode du marche-pied avec potentiels).

Structure

RO_projet/
|-- src/                # code source Python
|   |-- __init__.py
|   |-- io_utils.py             # lecture des fichiers et affichage des tables
|   |-- initial_propositions.py # algorithmes Nord-Ouest et Balas-Hammer
|   |-- cost.py                 # cout total d'une proposition
|   |-- graph_utils.py          # graphe biparti, cycles, connexite, BFS
|   |-- stepping_stone.py       # methode du marche-pied avec potentiels
|   `-- main.py                 # CLI interactive
|-- scripts/           # scripts utilitaires (generation de traces, ...)
|   `-- generate_all_traces.py
|-- problems/          # 12 fichiers problem_01.txt ... problem_12.txt
|-- traces/            # 24 traces d'execution (12 problemes x NO/BH)
|-- complexity/        # etude de complexite (phase 5)
`-- README.md

Format des fichiers de problemes

n m
a_{1,1} a_{1,2} ... a_{1,m} P_1
a_{2,1} a_{2,2} ... a_{2,m} P_2
...
a_{n,1} a_{n,2} ... a_{n,m} P_n
C_1 C_2 ... C_m

Les 12 problemes sont issus de la section 4.3 du sujet et tous equilibres (somme des provisions egale a la somme des commandes).

Execution

Depuis la racine du projet :

python src/main.py

Phases

• Phase 1 : fondations (structure, lecture, affichage).
• Phase 2 : algorithmes Nord-Ouest et Balas-Hammer + cout total.
• Phase 3 : methode du marche-pied avec potentiels.
• Phase 4 : interface CLI + generation des 24 traces.
• Phase 5 : etude de complexite.

Tests

Depuis la racine :

python test_phase1.py    # lecture + affichage
python test_phase2.py    # NO + BH + cout total
python test_phase3.py    # marche-pied (resolution complete)
python src/main.py       # CLI interactive

Generation des traces

Avant execution, modifier les variables GROUPE et EQUIPE en haut de scripts/generate_all_traces.py, puis lancer depuis la racine :

python scripts/generate_all_traces.py

Les 24 traces (12 problemes x 2 methodes initiales NO/BH) seront generees dans traces/ au format {GROUPE}-{EQUIPE}-trace{i}-{no|bh}.txt.

Etude de complexite

Pour lancer l'etude rapide (validation, ~1 min) :

python scripts/complexity_study.py --quick

Pour lancer l'etude complete (peut prendre plusieurs heures) :

python scripts/complexity_study.py

Pour generer les graphes une fois le CSV produit :

python scripts/plot_complexity.py

Le generateur de problemes aleatoires equilibres (scripts/random_generator.py) est utilise par le pipeline de mesure ; ses seeds sont deterministes (fonction de la taille et de l'identifiant du run) pour garantir la reproductibilite.

L'analyse experimentale et l'identification des classes de complexite sont consignees dans complexity/analysis.md.

API publique de la phase 3

io_utils.py (ajout) :

display_potential_costs(E_sources, E_targets) -> None

graph_utils.py :

proposition_to_edges(proposition) -> list[tuple[int, int]]
is_acyclic_bfs(edges, n_sources, n_targets)
    -> tuple[bool, list[tuple[int, int]] | None]
is_connected_bfs(edges, n_sources, n_targets)
    -> tuple[bool, list[set[int]]]
find_marche_pied_cycle(edges, new_edge, n_sources, n_targets)
    -> list[tuple[int, int]]

stepping_stone.py :

maximize_on_cycle(proposition, cycle, n)
    -> tuple[list[list[int]], int, tuple[int, int] | None]
add_edges_to_make_connected(proposition, problem, forbidden_edges=None)
    -> tuple[list[list[int]], list[tuple[int, int]]]
compute_potentials(edges, problem)
    -> tuple[list[float | None], list[float | None]]
compute_marginal_costs(problem, E_sources, E_targets)
    -> list[list[float]]
find_improving_edge(marginal_costs, proposition)
    -> tuple[int, int] | None
solve_stepping_stone(problem, initial_proposition, verbose=True)
    -> tuple[list[list[int]], int]