Utilisation du solveur IBM-Cplex via le langage de modélisation OPL

Utilisation du solveur IBM-Cplex via le langage de
modélisation OPL
ECMA
TP noté en binôme (durée 3h30)
mercredi 3 décembre 2014
Le but de ce TP est d’évaluer vos connaissances sur le langage de modélisation OPL. Ce langage
permet d’écrire une instance d’un programme mathématique, mais aussi un modèle général, dans
lequel les données peuvent varier. Le fichier contenant le modèle est suffixé par .mod, et le fichier
contenant les données d’une instance particulière est suffixé par .dat.
Ce TP est composé de 5 exercices, nous vous demandons pour chaque exercice de faire valider
votre modèle par un des enseignants, et de rendre à la fin du TP un compte-rendu contenant les
modèles mathématiques et les résultats des différents tests qui vous sont demandés.
Avant de commencer :
1. Téléchargez le solveur IBM-Cplex à l’adresse suivante :
http://cedric.cnam.fr/~lamberta/MPRO/ECMA/sources/sources_cp.exe
et installez-le.
2. La documentation du langage de modélisation OPL se trouve à l’adresse suivante :
http://cedric.cnam.fr/~lamberta/MPRO/ECMA/doc/oplTutorial.pdf.
3. Les exemples en OPL se trouvent dans le répertoire
C:\Program Files (x86)\IBM\ILOG\CPLEX_Studio125\opl\examples\
Rappel : Comment définir et exécuter une configuration d’exécution ?
Après avoir créé le fichier .mod correspondant à votre modèle, et éventuellement un fichier de
données .dat associé, vous devez créer une configuration d’exécution. Pour cela :
1. Aller dans la fenêtre de gauche "Projets OPL", et cliquer (clic droit) sur "Configurations
d’exécution". Sélectionner "Nouveau" puis "Configuration d’exécution". Donner un nom à
cette configuration (par exemple "Configuration_test_1").
2. Dans la fenêtre "Projets OPL", cliquer (clic droit) sur le nom du fichier .mod à ajouter à
la configuration, et sélectionner "Ajouter à la configuration d’exécution", puis "Configuration_test_1" (i.e. la configuration d’exécution que vous venez juste de créer). Faites de même
pour l’éventuel fichier .dat associé.
3. Enfin, toujours dans la fenêtre "Projets OPL", cliquer (clic droit) sur le nom de votre configuration (ici, "Configuration_test_1"), et sélectionner "Exécuter cette configuration".
1
1
Programmation linéaire
Exercice 1 — Une première
vant :

M ax




s.c.









(P L)













instance en OPL
On veut résoudre le problème (P L) sui-
f (x1 , x2 , x3 , x4 , x5 ) = 3x1 + 5x2 − 6x3 + 2x4 − x5
x1 + 5x2 + 7x3 + 2x4 + 3x5 6 96
4x1 + 2x2 + 6x3 + 1x4 + 4x5 6 68
0 6 x1 6 18
2 6 x3 6 11
4 6 x5 6 16
x2 ∈ {0, 1}
x4 ∈ {0, 1}
x5 ∈ N
1. Lancez Cplex et créez un nouveau projet (File -> new -> opl project). Vous nommerez ce nouveau projet premier_projet.
2. Créez un nouveau modèle (Clic droit sur le projet premier_projet, puis new -> model).
Vous nommerez ce nouveau modèle premier_modele.opl.mod
3. Après avoir écrit (P L) dans le langage OPL, compilez et résolvez (P L). Observez les informations que renvoie IBM-Cplex et indiquez la borne à la racine, la valeur de la solution
optimale, le nombre de nœuds et le temps résolution de (P L).
Exercice 2 — Généralisation
On veut modéliser et résoudre le problème général qui consiste
à maximiser une fonction linéaire sous une contrainte linéaire d’égalité, une contrainte linéaire
d’inégalité, et sous les contraintes que les variables doivent être binaires :

n
X

 M ax z =
ci x i




i=1


n

X

 s.c.
ai xi = b
(P LN E)
i=1


n

X



di xi 6 e




i=1

xi ∈ {0, 1} i = 1, . . . , n
1. Créez le projet PLNE.
2. Créez un nouveau modèle OPL et écrivez le fichier qui représente (P LN E). Le nom de
fichier sera suffixé par .mod (par exemple plne.mod). De plus, vous veillerez à nommer
les données du problème comme proposé dans le modèle (P LN E).
3. Écrivez le fichier qui contient les données du modèle suivant :

M ax z = 12x1 + 15x2 + 5x3 + 16x4 + 17x5



s.c.
2x1 + 6x2 + x3 + 7x4 + 8x4 = 14
(P )
3x1 + 6x2 + 2x3 + 5x4 + 9x4 6 20



xi ∈ {0, 1} i = 1, . . . , 5
Le nom de fichier sera suffixé par .dat (par exemple plne.dat). Résolvez l’instance
associée.
4. Téléchargez les cinq fichiers de données disponibles à l’adresse suivante : http://cedric.
cnam.fr/~lamberta/MPRO/ECMA/data/, et résolvez les instances associées de (P LN E).
Exercice 3 — Ensemble stable de poids maximal
Soit un graphe G = (V, E) où V =
{v1 , . . . , vn } désigne l’ensemble des sommets et E l’ensemble des arêtes. Un sous-ensemble de
sommets S de V est un ensemble stable si aucune paire de sommets de cet ensemble n’est reliée
par une arête. A chaque sommet est associé un poids positif ou nul. Le poids d’un ensemble
stable est égal à la somme des poids de ses sommets. Dans ce problème, nous cherchons à
déterminer, dans G, un ensemble stable de poids maximal.
2
1. Créez le projet StablePoidsMax.
2. Après avoir modélisé le problème du stable de poids maximal sous forme d’un programme
linéaire en variables binaires (en utilisant le fait que pour chaque arête (u, v), au plus un
des deux sommets u ou v peut appartenir à un stable maximal), créez un nouveau modèle
OPL et écrivez le fichier qui représente ce problème.
3. Téléchargez les cinq fichiers de données disponibles à l’adresse suivante : http://cedric.
cnam.fr/~lamberta/MPRO/ECMA/data/, et résolvez les instances associées.
Exercice 4 — Carrés magiques
Pour tout n > 3, un carré magique de taille n est une
matrice n × n contenant une et une seule fois chacun des nombres entiers compris entre 1
et n2 , et dont la somme des éléments sur chaque ligne, chaque colonne et chacune des deux
diagonales est la même (on peut noter qu’une telle matrice n’existe pas pour n = 2).
1. Créez le projet CarreMagique.
2. Après avoir modélisé par un programme linéaire en variables binaires la recherche de
l’existence d’un carré magique de taille n quelconque, créez un nouveau modèle OPL et
écrivez le fichier qui représente ce problème. Comme le problème est hautement symétrique, on cherchera à atténuer cette symétrie (pour faciliter la résolution) en minimisant
la valeur de l’élément en haut à gauche (c’est-à-dire, sur la première ligne et la première
colonne) de la matrice. (On vous conseille de définir les variables binaires suivantes :
xijk = 1 si et seulement si l’élément sur la ième ligne et la jème colonne vaut k.) N’oubliez pas d’exprimer le fait que toute case de la matrice doit contenir un et un seul
élément.
3. Résolvez ce problème n = 2, 3 et 9.
1.1
Programmation quadratique
Exercice 5 — Un programme quadratique
On veut modéliser et résoudre le problème
suivant :

n n

 M ax z = XXq x x


ij i j



i=1 j=1
n
X
(QP )

ai xi 6 b
s.c.




i=1


xi ∈ {0, 1}
i = 1, . . . , n
1. Créez le projet QPNE.
2. Créez un nouveau modèle OPL et écrivez le fichier qui représente ce problème.
3. Quelle propriété doit avoir la matrice des coûts de la fonction objectif pour que le problème
puisse être résolu par un algorithme de sous-gradient ?
4. Téléchargez les cinq fichiers de données disponibles à l’adresse suivante : http://cedric.
cnam.fr/~lamberta/MPRO/ECMA/data/, et résolvez les instances associées.
3

Download Report