TP4 : Problème du Sac à Dos 1D & 2D — Comparaison CPLEX et Relaxations

Objectif

Ce projet vise à résoudre et analyser le problème du sac à dos (Knapsack) dans ses versions 1D et 2D. Il s'agit d'appliquer différentes méthodes d'optimisation (exacte et approchée) afin de :

• Comparer CPLEX à la programmation dynamique pour le problème 1D.
• Calculer les relaxations linéaires (1D et 2D).
• Évaluer les gaps d'intégralité entre relaxation et solution optimale.
• Étudier la complexité temporelle selon la taille de l'instance.

Auteurs

• Lucas Ciszowski
• Harrata Sara

Structure du projet

• TP2.c : Contient la fonction main() et lance les benchmarks ou comparaisons.
• TP2Functions.c / TP2Functions.h : Fonctions de génération, lecture, résolution (CPLEX, programmation dynamique, LP) et comparaisons.
• Makefile : Permet de compiler facilement le projet avec CPLEX.

Compilation

Le projet utilise un Makefile compatible avec l’environnement des serveurs pédagogiques de l’ISIMA (où CPLEX est déjà installé).

make

En cas de modification des fichiers source :

make clean
make

Exécution

Lancer les tests standards

./TP2

Options disponibles

./TP2 -F <nom_fichier_instance>     # Charger une instance spécifique (par défaut : instance3.csv)
./TP2 -G <1|0>                       # Générer une instance (1 = déterministe)

Comportement du programme

• Si -G est spécifié : des benchmarks sont automatiquement lancés :

  • Comparaison CPLEX vs Programmation dynamique sur le sac à dos 1D (results_1d_n.csv, results_1d_b.csv).
  • Analyse du gap entre relaxation LP et solution entière en 1D et 2D (results_1d_gap.csv, results_2d_gap.csv).
  • Étude de la complexité temporelle (results_temps1D_exo4.csv, results_temps2D_exo4.csv).

• Sinon :

  • Lecture de deux instances (instance3.csv pour 1D, instance.csv pour 2D).
  • Comparaison entre les deux versions (1D vs 2D).
  • Comparaison des relaxations linéaires vs solution entière.

Résultats générés

• results_1d_n.csv, results_1d_b.csv : temps d’exécution CPLEX vs DP (1D).
• results_1d_gap.csv, results_2d_gap.csv : valeur LP vs entière + gap.
• results_temps1D_exo4.csv, results_temps2D_exo4.csv : courbes de complexité.

Références

Travail réalisé dans le cadre du TP4 — Modélisation et Optimisation (M1 ISIMA)

Enseignants : F. Bendali, R. Chicoisne, R. Colares, C. Liu

Remarques

• Ce projet doit être exécuté sur les serveurs de l’ISIMA (ex : Ada) où CPLEX est installé.
• Les instances sont générées automatiquement si besoin (1D et 2D).