Débuter avec CPLEX en mode OPL
Kenza Oufaska et OUDANI Mustapha
Université Internationale de Rabat
Plan
Introduction
OPL Studio
Introduction
Historique et Applications
▶ CPLEX est créé par Robert E. Bixby en utilisant le langage C
en 1987
▶ Racheté par ILOG en 1997
▶ Mentionné dans 95% des articles qui citent un solveur
▶ Utilisé comme solveur standard dans les applications de la
chaı̂ne logistique
▶ Employé par plusieurs compagnies aériennes (Delta,
Continental, etc.)
▶ Lauréat du INFORMS Impact Award en 2004
Introduction
Problèmes couverts par CPLEX
▶ Programmation linéaire
▶ Programmation linéaire mixte
▶ Programmation quadratique
▶ Programmation mixte quadratique
▶ Programmation à contraintes quadratiques
▶ Programmation mixte à contraintes quadratiques
Introduction
Algorithmes
▶ Programmation linéaire :
▶ Simplex Primal
▶ Simplex Dual
▶ Point intérieur (barrier)
▶ Programmation quadratique :
▶ Simplex Primal
▶ Simplex Dual
▶ Point intérieur (barrier)
▶ Programmation à contraintes quadratiques :
▶ Point intérieur (barrier)
Introduction à OPL
OPL : Optimization Programming Language
▶ OPL est un langage de haut niveau pour la description des
programmes mathématiques
▶ Développé par ILOG, utilisé avec CPLEX pour modéliser et
résoudre des problèmes d’optimisation
▶ OPL Studio est un Environnement de Développement Intégré
(EDI) pour OPL
Eléments de syntaxe
Définitions des intervalles
▶ Pour créer un intervalle, on utilise le mot-clé range
range I=1..10 ;
range float R=5.0..50.0 ;
Définitions des variables de décisions
▶ Pour déclarer des variables de décisions, on utilise les mots-clés
suivants le type de la variable boolean, int, float, int+, float+
dvar boolean x ;
dvar float y in R ;
Manipulation de CPLEX Studio IDE
Manipulation de CPLEX Studio IDE
▶ Pour lancer CPLEX Studio IDE, utilisez le menu démarrer
▶ Créez un nouveau projet : Fichier → Nouveau → Projet
OPL
▶ Pour insérer un modèle : Nouveau → Modèle (.mod)
▶ Pour insérer des données : Nouveau → Données (.dat)
▶ Pour exécuter un modèle : créer une configuration d’exécution
Manipulation de CPLEX Studio IDE
Manipulation de CPLEX Studio IDE
Manipulation de CPLEX Studio IDE
Le fichier .mod
Manipulation de CPLEX Studio IDE
Le fichier .dat
Exemple de Modèle OPL : Problème de Transport
Modèle (.mod) pour le Problème de Transport
{ string } usines = . . . ;
{string} clients = . . . ;
f l o a t cout [ u s i n e s ] [ c l i e n t s ] = . . . ;
d v a r f l o a t+ x [ u s i n e s ] [ c l i e n t s ] ;
m i n i m i z e sum ( i i n u s i n e s , j i n c l i e n t s )
cout [ i ] [ j ] ∗ x [ i ] [ j ] ;
s u b j e c t to {
f o r a l l ( i i n u s i n e s ) sum ( j i n c l i e n t s )
x [ i ] [ j ] <= o f f r e [ i ] ;
f o r a l l ( j i n c l i e n t s ) sum ( i i n u s i n e s )
x [ i ] [ j ] >= demande [ j ] ;
}
Exemple de Modèle OPL : Problème de Transport
Données (.dat) pour le Problème de Transport
nbr usines = 3 ;
nbr clients = 4 ;
u s i n e s = { ” 1 ” , ” 2 ” , ”3”} ;
c l i e n t s = { ” 1 ” , ” 2 ” , ” 3 ” , ”4”} ;
o f f r e = [ 3 5 , 50 , 40] ;
demande = [ 4 5 , 2 0 , 3 0 , 3 0 ] ;
cout = [ [ 8 , 6 , 10 , 9 ] ,
[ 9 , 12 , 13 , 7 ] , [ 1 4 , 9 , 16 , 5 ] ] ;
Exemple de Modèle OPL : Problème de Sac à Dos
Modèle (.mod) pour le Problème de Sac à Dos
int n = . . . ;
int profit [1.. n] = . . . ;
int poids [ 1 . . n ] = . . . ;
i n t poidmax = . . . ;
dvar i n t x [ 1 . . n ] ;
maximize
sum ( i i n 1 . . n ) p r o f i t [ i ] ∗ x[ i ] ;
s u b j e c t to {
sum ( i i n 1 . . n ) p o i d s [ i ] ∗ x[ i ]
<= poidmax ;
}
Exemple de Modèle OPL : Données pour le Problème de
Sac à Dos
Données (.dat) pour le Problème de Sac à Dos
n = 3 ; poidmax = 59 ; profit = [10, 11, 13] ; poids =
[10, 12, 13] ;