complete.py

import tsplib95
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import time

from ortools.sat.python import cp_model
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

OPTIMUMS = {
    'burma14': 3323,
    'eil51': 426,
    'kroA100': 21282,
}


def charger_instance(fichier):
    """Charge un fichier TSPLIB"""
    probleme = tsplib95.load(fichier)
    villes = list(probleme.get_nodes())
    n = len(villes)
    
    distances = np.zeros((n, n), dtype=int)
    for i, vi in enumerate(villes):
        for j, vj in enumerate(villes):
            if i != j:
                distances[i][j] = int(probleme.get_weight(vi, vj))
            else:
                distances[i][j] = 999999999
    
    nom = fichier.replace('.tsp', '').split('/')[-1].split('\\')[-1]
    
    return {
        'nom': nom,
        'n': n,
        'distances': distances,
        'optimum': OPTIMUMS.get(nom, None)
    }


class SolveursComplets:
    
    def __init__(self, distances):
        self.dist = np.array(distances)
        self.n = len(distances)
    

    def cpsat(self, temps_limite=300, workers=1):
        """
        CP-SAT : Solveur de Programmation par Contraintes
        
        Paramètres :
            - temps_limite : temps maximum de recherche (secondes)
            - workers : nombre de threads (1 = séquentiel, 8 = parallèle)
        """
        model = cp_model.CpModel()
        
        arcs = {}
        for i in range(self.n):
            for j in range(self.n):
                if i != j:
                    arcs[i, j] = model.NewBoolVar(f'arc_{i}_{j}')
        
        model.AddCircuit([(i, j, arcs[i, j]) for i, j in arcs])
        
        model.Minimize(sum(self.dist[i][j] * arcs[i, j] for i, j in arcs))
        
        solveur = cp_model.CpSolver()
        solveur.parameters.max_time_in_seconds = temps_limite
        solveur.parameters.num_search_workers = workers
        
        debut = time.time()
        statut = solveur.Solve(model)
        duree = time.time() - debut
        
        return {
            'methode': f'CP-SAT (workers={workers})',
            'parametres': {'temps_limite': temps_limite, 'workers': workers},
            'temps': duree,
            'statut': solveur.StatusName(statut),
            'distance': int(solveur.ObjectiveValue()) if statut in [cp_model.OPTIMAL, cp_model.FEASIBLE] else None,
            'optimal': statut == cp_model.OPTIMAL
        }
    
    
    def nearest_neighbor(self, temps_limite=300):
        manager = pywrapcp.RoutingIndexManager(self.n, 1, 0)
        routing = pywrapcp.RoutingModel(manager)
        
        dist = self.dist
        def callback(i, j):
            return int(dist[manager.IndexToNode(i)][manager.IndexToNode(j)])
        
        idx = routing.RegisterTransitCallback(callback)
        routing.SetArcCostEvaluatorOfAllVehicles(idx)
        
        params = pywrapcp.DefaultRoutingSearchParameters()
        params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
        params.time_limit.seconds = temps_limite
        
        debut = time.time()
        solution = routing.SolveWithParameters(params)
        duree = time.time() - debut
        
        return {
            'methode': 'Plus Proche Voisin',
            'parametres': {'strategie': 'PATH_CHEAPEST_ARC', 'temps_limite': temps_limite},
            'temps': duree,
            'distance': int(solution.ObjectiveValue()) if solution else None,
            'statut': 'OK' if solution else 'NO_SOLUTION',
            'optimal': False
        }
    
    
    def guided_local_search(self, temps_limite=300):
        manager = pywrapcp.RoutingIndexManager(self.n, 1, 0)
        routing = pywrapcp.RoutingModel(manager)
        
        dist = self.dist
        def callback(i, j):
            return int(dist[manager.IndexToNode(i)][manager.IndexToNode(j)])
        
        idx = routing.RegisterTransitCallback(callback)
        routing.SetArcCostEvaluatorOfAllVehicles(idx)
        
        params = pywrapcp.DefaultRoutingSearchParameters()
        params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
        params.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
        params.time_limit.seconds = temps_limite
        
        debut = time.time()
        solution = routing.SolveWithParameters(params)
        duree = time.time() - debut
        
        return {
            'methode': 'Guided Local Search',
            'parametres': {'metaheuristique': 'GLS', 'temps_limite': temps_limite},
            'temps': duree,
            'distance': int(solution.ObjectiveValue()) if solution else None,
            'statut': 'OK' if solution else 'NO_SOLUTION',
            'optimal': False
        }



def executer_benchmark(fichiers_tsp, temps_limite=60):
    
    resultats = []
    
    for fichier in fichiers_tsp:
        
        print(f"\n{'='*60}")
        print(f" {fichier}")
        print('='*60)
        
        try:
            instance = charger_instance(fichier)
        except Exception as e:
            print(f"❌ Erreur : {e}")
            continue
        
        nom = instance['nom']
        n = instance['n']
        optimum = instance['optimum']
        
        print(f"Villes : {n} | Optimum connu : {optimum}")
        print("-" * 40)
        
        solveur = SolveursComplets(instance['distances'])
        
        methodes = [
            lambda: solveur.cpsat(temps_limite=temps_limite, workers=8),
            lambda: solveur.nearest_neighbor(temps_limite=temps_limite),
            lambda: solveur.guided_local_search(temps_limite=temps_limite),
        ]
        
        for methode in methodes:
            res = methode()
            
            res['instance'] = nom
            res['n'] = n
            res['optimum'] = optimum
            
            if res['distance'] and optimum:
                res['gap'] = ((res['distance'] - optimum) / optimum) * 100
            else:
                res['gap'] = None
            
            resultats.append(res)
            
            dist = res['distance'] if res['distance'] else 'N/A'
            gap = f"{res['gap']:.2f}%" if res['gap'] is not None else '-'
            opt = "✓ OPTIMAL" if res.get('optimal') else ""
            print(f"  {res['methode']:25} | {dist:>8} | gap: {gap:>8} | {res['temps']:.2f}s {opt}")
    
    return pd.DataFrame(resultats)


def generer_rapport(df):

    print("\n" + "="*60)
    print("📊 RAPPORT")
    print("="*60)
    
    print("\nTABLEAU RÉCAPITULATIF\n")
    tableau = df.pivot_table(
        values=['distance', 'gap', 'temps'],
        index='instance',
        columns='methode',
        aggfunc='first'
    )
    print(tableau.round(2).to_string())
    
    # Graphiques
    fig, axes = plt.subplots(1, 2, figsize=(12, 5))
    
    # Gap
    ax = axes[0]
    pivot = df.pivot_table(values='gap', index='instance', columns='methode')
    pivot.plot(kind='bar', ax=ax, color=['#2ecc71', '#3498db', '#e74c3c'])
    ax.set_title('Gap par rapport à l\'optimum (%)', fontweight='bold', fontsize=12)
    ax.set_ylabel('Gap (%)')
    ax.set_xlabel('')
    ax.legend(title='', fontsize=9)
    ax.tick_params(axis='x', rotation=0)
    ax.axhline(y=0, color='green', linestyle='--', alpha=0.5)
    
    # Temps
    ax = axes[1]
    pivot = df.pivot_table(values='temps', index='instance', columns='methode')
    pivot.plot(kind='bar', ax=ax, color=['#2ecc71', '#3498db', '#e74c3c'])
    ax.set_title('Temps d\'exécution (secondes)', fontweight='bold', fontsize=12)
    ax.set_ylabel('Temps (s)')
    ax.set_xlabel('')
    ax.legend(title='', fontsize=9)
    ax.tick_params(axis='x', rotation=0)
    
    plt.tight_layout()
    plt.savefig('resultats.png', dpi=150)
    print("\nGraphique sauvegardé : resultats.png")
    plt.show()
    
    # Classement
    print("\nCLASSEMENT (par gap moyen)")
    classement = df.groupby('methode')['gap'].mean().sort_values()
    for rang, (m, g) in enumerate(classement.items(), 1):
        print(f"   {rang}. {m}: {g:.2f}%")


if __name__ == "__main__":
    
    FICHIERS = [
        'tsplib-master/burma14.tsp',
        'tsplib-master/eil51.tsp', 
        'tsplib-master/kroA100.tsp',
    ]
    
    TEMPS_LIMITE = 60
    
    print("BENCHMARK TSP - MÉTHODES COMPLÈTES")
    print("="*60)
    
    df = executer_benchmark(FICHIERS, TEMPS_LIMITE)
    
    df.to_csv('resultats.csv', index=False)
    print("\nCSV sauvegardé : resultats.csv")
    
    generer_rapport(df)
    
    print("\nTERMINÉ !")