Optimisation et logicielsborne/Docs/cm_ol.pdf · CHAPITRE 1. LES LOGICIELS LIBRES 5 Le d´eveloppement commercial de logiciel libre n’est plus l’exception; de tels logiciels libres

Optimisation et logiciels

Sylvie Borne

[email protected]

2 novembre 2010

Table des matieres

1 Les logiciels libres 3

1.1 Qu’est-ce qu’un Logiciel Libre ? . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Qu’est-ce que le copyleft ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Le logiciel Glpk 5

2.1 Qu’est-ce que Glpk ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Ou le trouver ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.3 Comment l’utiliser ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.4 Le logiciel glpsol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.4.1 Format Cplex lp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.4.2 Format mps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.4.3 Fichier de sortie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.5 L’interface API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.6 Le modeleur GNU MathProg . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Le logiciel LP solve 15

3.1 En lignes de commandes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.2 Via l’API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.3 Via l’IDE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.4 A partir d’un modeleur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.5 En bref . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4 La suite logiciel COIN-OR 26

4.1 Liste des projets COIN par categorie . . . . . . . . . . . . . . . . . . . . . . . 27

4.2 Le projet OSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.3 Le projet CLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.4 Le projet CBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.5 Le projet BCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

TABLE DES MATIERES 3

4.6 Le projet CGL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.7 Le projet CSDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

5 Le logiciel Abacus 34

5.0.1 Les differentes classes d’ABACUS . . . . . . . . . . . . . . . . . . . . . 34

5.0.2 Structure du programme MSIPND . . . . . . . . . . . . . . . . . . . . 36

Chapitre 1

Les logiciels libres

Texte tire du site http ://www.gnu.org/philosophy/free-sw.fr.html

1.1 Qu’est-ce qu’un Logiciel Libre ?

L’expression ≪ Logiciel libre ≫ fait reference a la liberte et non pas au prix. Pour comprendre

le concept, vous devez penser a la ≪ liberte d’expression ≫, pas a ≪ l’entree libre ≫.

L’expression ≪ Logiciel libre ≫ fait reference a la liberte pour les utilisateurs d’executer, de

copier, de distribuer, d’etudier, de modifier et d’ameliorer le logiciel. Plus precisement, elle

fait reference a quatre types de liberte pour l’utilisateur du logiciel :

– La liberte d’executer le programme, pour tous les usages (liberte 0).

– La liberte d’etudier le fonctionnement du programme, et de l’adapter a vos besoins

(liberte 1). Pour ceci l’acces au code source est une condition requise.

– La liberte de redistribuer des copies, donc d’aider votre voisin, (liberte 2).

– La liberte d’ameliorer le programme et de publier vos ameliorations, pour en faire profiter

toute la communaute (liberte 3). Pour ceci l’acces au code source est une condition

requise.

Un programme est un logiciel libre si les utilisateurs ont toutes ces libertes. Ainsi, vous

etes libre de redistribuer des copies, avec ou sans modification, gratuitement ou non, a tout le

monde, partout. Etre libre de faire ceci signifie (entre autre) que vous n’avez pas a demander

ou a payer pour en avoir la permission.

Vous devez aussi avoir la liberte de faire des modifications et de les utiliser a titre prive

dans votre travail ou vos loisirs, sans en mentionner l’existence. Si vous publiez vos modifica-

tions, vous n’etes pas oblige de prevenir quelqu’un de particulier ou de le faire d’une maniere

particuliere.

Vous pouvez avoir paye pour obtenir une copie d’un logiciel libre ou vous pouvez l’avoir

obtenu gratuitement. Mais indifferemment de la maniere dont vous vous l’etes procure, vous

avez toujours la liberte de copier et de modifier un logiciel et meme d’en vendre des copies.

≪ Logiciel libre ≫ ne signifie pas ≪ non commercial ≫. Un logiciel libre doit etre disponible

pour un usage commercial, pour le developpement commercial et la distribution commerciale.

CHAPITRE 1. LES LOGICIELS LIBRES 5

Le developpement commercial de logiciel libre n’est plus l’exception ; de tels logiciels libres

commerciaux sont tres importants.

Dans le projet GNU, nous utilisons le ≪ copyleft ≫ pour proteger ces libertes. Mais des

logiciels libres non-copyleftes existent aussi. Nous croyons qu’il y a de bonnes raisons qui font

qu’il est mieux d’utiliser le copyleft, mais si votre programme est libre non-copylefte, nous

pouvons tout de meme l’utiliser.

1.2 Qu’est-ce que le copyleft ?

Le Copyleft est une facon de rendre un programme ou tout autre œuvre libre, et qui requiert

que toutes les versions modifiees et etendues du programme soient libres egalement.

La maniere la plus simple de faire d’un programme un logiciel libre est de le distribuer dans

le domaine public, sans copyright. Cela autorise les gens a partager le programme et leurs

ameliorations si le cœur leur en dit. Mais cela autorise aussi des personnes indelicates a faire

du programme un logiciel proprietaire. Ils peuvent tres bien y effectuer des changements, juste

quelques-uns ou plusieurs, et distribuer le resultat comme un logiciel proprietaire. Ceux qui

recevront le programme dans sa forme modifiee n’auront pas la liberte que l’auteur original

leur aura donne ; l’intermediaire l’aura fait disparaıtre.

Dans le projet GNU, notre but est de donner a tous les utilisateurs la liberte de redistribuer

et de modifier les logiciels GNU. Si des intermediaires pouvaient enlever cette liberte, nous

aurions beaucoup d’utilisateurs, mais ils n’auraient aucune liberte. Alors, au lieu de mettre

les logiciels GNU dans le domaine public, nous les mettons sous ≪copyleft≫ ou ≪gauche d’au-

teur≫. Le copyleft indique que quiconque les redistribue, avec ou sans modifications, doit aussi

transmettre la liberte de les copier et de les modifier. Le copyleft garantit cette liberte pour

tous les utilisateurs.

Le copyleft fournit aussi un encouragement aux autres programmeurs qui veulent ajou-

ter des logiciels libres. Des programmes importants comme le compilateur C++ de GNU

n’existent que grace a lui.

Chapitre 2

Le logiciel Glpk

2.1 Qu’est-ce que Glpk ?

Glpk signifie GNU Linear Programming Kit. Il s’agit d’un ensemble d’algorithmes permet-

tant de resoudre differents problemes allant de la programmation lineaire (PL) a la program-

mation lineaire en nombres entiers (PLNE).

Ces deux types de problemes sont tres proche en apparence mais demandent a ce jour des

traitements bien differents.

Resoudre un programme lineaire peut se faire en temps polynomial. Glpk propose les 2

plus celebres algorithmes connus : la methode du simplexe (qui n’est pas polynomiale mais

qui est tres efficace) et une methode de points interieurs (qui est polynomiale).

Resoudre un PLNE est un probleme NP-difficile. Glpk utilise le seul algorithme connu

capable de resoudre efficacement tous les PLNE : la methode de branchement (Branch-and-

Bound) qui est exponentielle dans le pire des cas.

2.2 Ou le trouver ?

Glpk est une partie du GNU Project et est distribuee en logiciel libre a sources disponibles

(free software, open source), sous la licence publique generale GNU qui permet de la redistri-

buer ou de la modifier selon les termes publies par la Free Software Foundation.

Ce document resume les fonctionnalites principales du logiciel glpsol ainsi que les formats

principaux de donnees et de description. Pour obtenir des documents sur la bibliotheque C

API, installer le logiciel sous linux ou windows, avoir acces a une Faq,... vous pouvez acceder

a la page dediee a glpk sur le site general GNU :

http ://www.gnu.org/software/glpk/glpk.html.

1. Telecharger un fichier tar.gz sur http ://ftp.gnu.org/gnu/glpk/

CHAPITRE 2. LE LOGICIEL GLPK 7

(ex : glpk-4.44.tar.gz).

2. Decompresser tar -zxvf glpk-4.44.tar.gz.

3. Les instructions d’installation sont alors dans le fichier INSTALL.

4. Prendre soin de se placer en root.

5. Dans le repertoire glpk-4.44, lancer ./configure.

6. Puis make pour compiler le programme.

7. Puis make check pour tester.

8. Puis make install pour installer le logiciel.

9. L’executable glpsol est alors disponible dans /usr/local/bin/, la bibliotheque libglpk.a

dans /usr/local/lib/ et glpk.h dans /usr/local/include/ .

10. La documentation complete est disponible dans glpk-4.44/doc sous la forme de fichiers

postscripts (glpk.ps, gmpl.ps) ainsi que de nombreux exemples dans glpk-4.44/examples.

2.3 Comment l’utiliser ?

Glpk est code en langage C Ansi et on peut acceder directement aux algorithmes par

une API C (Application Program Interface), c’est-a-dire un ensemble de fonctions C. Il est

egalement possible d’acceder aux fonctionnalites de Glpk a partir d’un logiciel, dit solveur,

appele glpsol. Glpk peut traiter des programmes lineaires fournis sous differents formats (lp,

mps) ou decrits a partir d’un langage specialise, appele modeleur, le GNU MathProg.

Il existe ainsi trois facons d’acceder aux algorithmes de Glpk. Tous les olveurs lineaires

similaires a Glpk possedent ces 3 acces.

Si l’on desire une utilisation optimale, securisee, capable de fonctionner pour des grandes

tailles de problemes, il faut utiliser bien entendu l’interface API. Elle existe a l’origine en C

Ansi mais on peut trouver des interfaces externes pour Java, Delphi ou Glpkmex Matlab.

Pour resoudre des programmes de taille plus reduite, le logiciel glpsol est facile d’utilisation.

Il prend un fichier d’entree sous des formats simples et produit un fichier en retour contenant

le resultat. Il est ainsi possible de creer un logiciel complet utilisant glpsol, c’est-a-dire un

programmant creant le fichier d’entree pour glpsol et lisant son fichier de sortie.

Parmi les fichiers d’entree possible, le format modeleur peut etre tres utile. Un modeleur

decrit le PL ou le PLNE en utilisant une description mathematique assez simple. Ce format

de fichier peut ainsi etre lu par glpsol ou par l’interface API.

2.4 Le logiciel glpsol

Si votre systeme Unix/Linux ou Windows est bien configure, la commande glpsol (sous

un terminal Unix/Linux ou sous une fenetre Dos) vous permet d’acceder au logiciel glpsol.

L’usage de glpsol est glpsol [options...] nomdefichier

8 CHAPITRE 2. LE LOGICIEL GLPK

Avec les options principales suivantes :

--help: permet d’acceder a la liste de toutes les options.

-check: ne lance pas d’algorithme, sert a tester les donees d’entrees

--cpxlp: format Cplex lp pour le fichier d’entree PL ou PLNE nomdefichier

--mps: idem format mps,

--glp: idem format GNU lp

--math: idem format modeleur GNU MathProg.

--wcpxlp fichiersortie: ecrit dans fichiersortie le PL ou le PLNE au format Cplex LP

(idem avec –wmps, –wglp)

-o fichiersortie: ecrit dans fichiersortie l’ensemble des resultats dans un fichier “txt”

Il existe egalement des options specifiques aux algorithmes utilises comme par exemple le

choix entre algorithme du simplexe et des points interieurs, de la base intiale pour la methode

de simplexe ou la strategie de branchement dans le Branch-and-Bound.

Exemples :

glpsol --check --wmps entree.mps --cpxlp entree.lp : transfert du format .lp au for-

mat .mps

glpsol -o solution.txt --cpxlp entree.lp : resout entree.lp et donne la solution dans

sortie.txt

2.4.1 Format Cplex lp

Glpk peut donc lire differents formats d’entree. Le plus simple et le plus repandu a ete

cree pour le logiciel Cplex (Ilog). Il revient a ecrire un PL ou un PLNE sous le format habi-

tuel.Voici un petit exemple de programme lineaire sous le format Cplex lp.

\Problem name: exemple.lp

Maximize

obj: 5 x1 + 7 x2

Subject To

c1: 3 x1 - 2 x2 <= -9

c2: 10 x1 + 6 x2 >= 11

c3: 8 x1 + x2 = -6

Bounds

-Inf <= x1 <= 0

1 <= x2 <= 4

End

Cet exemple se passe de commentaires, mais il faut noter que :

- la premiere ligne, optionnelle, indique un nom de probleme

- les noms de la fonction obj ou des contraintes sont optionnels

- les variables peuvent prendre des noms quelconques

- Si une variable n’a pas borne inferieure dans la section Bounds,

elle est consideree positive ou nulle.

Pour les PL mixtes ou entiers, on ajoute une section.

- Integers contenant la liste des variables entieres

- Binary contenant la liste des variables binaires

2.4.2 Format mps

* Problem: UNKNOWN

* Class: LP

* Rows: 3

* Columns: 2


* Non-zeros: 6

* Format: Fixed MPS

*

NAME

ROWS

N R0000000

L R0000001

G R0000002

E R0000003

COLUMNS

C0000001 R0000000 5 R0000001 3

C0000001 R0000002 10 R0000003 8

C0000002 R0000000 7 R0000001 -2

C0000002 R0000002 6 R0000003 1

RHS

RHS1 R0000001 -9 R0000002 11

RHS1 R0000003 -6

BOUNDS

MI BND1 C0000001

UP BND1 C0000001 0

LO BND1 C0000002 1

UP BND1 C0000002 4

ENDATA

2.4.3 Fichier de sortie

Glpsol peut fournir en sortie un fichier .txt donnant la solution du PL ou du PLNE.Le tableau suivant est le fichier .txt correspondant au programme precedent. Il indique le

statut de la solution (optimale ou irrealisable) et la valeur de la fonction objective optimale.Dans le cas d’un PLNE, une valeur supplementaire finissant par (LP) est en fait la valeur duPLNE relaxee des contraintes d’integrite. .

Problem:

Rows: 3

Columns: 2

Non-zeros: 6

Status: OPTIMAL

Objective: obj = 21.75 (MAXimum)

No. Row name St Activity Lower bound Upper bound Marginal

------ ------------ -- ------------- ------------- ------------- -------------

1 c1 B -11.75 -9

2 c2 B 11.5 11

3 c3 NS -6 -6 = 0.625

No. Column name St Activity Lower bound Upper bound Marginal

------ ------------ -- ------------- ------------- ------------- -------------

1 x1 B -1.25 0


2 x2 NU 4 1 4 6.375

Les deux sections concernent les contraintes/lignes (Rows) et les variables/colonnes (Co-

lumns), pour lesquelles sont indiquees :

No le numero des contraintes et des variables

Row (Column) name le nom des contraintes et de variables

St: le statut de la ligne/colonne : B=en base (pour la variable ou la variable d’ecart associee

a la contrainte), NF NL NU NS=Hors-base libre, a borne inf, a borne sup ou valeur fixee.

Activity: Valeur d’activite de la ligne/colonne dans la solution : pour les lignes, c’est la

somme des variables fois leurs coefficients et pour les variables, c’est leur valeur.

Lower/Upper bound: sans commentaire.

Marginal: pour les variables hors-base, c’est le cout reduit.

2.5 L’interface API

On peut acceder directement aux algorithmes par une API C (Application Program Inter-

face), c’est-a-dire un ensemble de fonctions C.

#include <stdio.h>

#include </usr/local/include/glpk.h>

int main()

{

LPX *lp; /* le probleme */

int ia[6+1];

int ja[6+1];

double ar[6+1];

double x1, x2, z;

/* creation du probleme */

lp = lpx_create_prob();

/* le nom du probleme - facultatif */

lpx_set_prob_name(lp, "exemple");

/* c’est un probleme de maximisation */

lpx_set_obj_dir(lp, LPX_MAX);

/* le nom de la fonction objective - facultatif */

lpx_set_obj_name(lp, "obj");

/* on ajoute 3 contraintes et 2 variables */

lpx_add_rows(lp,3);


lpx_add_cols(lp,2);

/* les noms des contraintes et des variables */

/* attention les indices commencent a 1 */

lpx_set_row_name(lp, 1, "c1");



lpx_set_col_name(lp, 1, "x1");

lpx_set_col_name(lp, 2, "x2");

/* les coefficients de la fonction objective */

lpx_set_obj_coef(lp, 1, 5.0);

lpx_set_obj_coef(lp, 2, 7.0);

/* le type et le 2e membre de contraintes */

lpx_set_row_bnds(lp, 1, LPX_UP, 0.0, -9.0);

lpx_set_row_bnds(lp, 2, LPX_LO, 11.0, 0.0);

lpx_set_row_bnds(lp, 3, LPX_FX, -6.0, -6.0);

// LPX_FR : -inf < x < +inf

// LPX_LO : lb <= x < +inf

// LPX_UP : -inf < x <= ub

// LPX_DB : lb <= x <= ub

// LPX_FX : lb = x = ub

/* les bornes des variables */

lpx_set_col_bnds(lp, 1, LPX_UP, 0.0, 0.0);

lpx_set_col_bnds(lp, 2, LPX_DB, 1.0, 4.0);

/* preparation de la matrice */

ia[1]=1; ja[1]=1; ar[1]=3.0; //a[1,1]=3

ia[2]=1; ja[2]=2; ar[2]=-2.0; //a[1,2]=-2

ia[3]=2; ja[3]=1; ar[3]=10.0; //a[2,1]=10

ia[4]=2; ja[4]=2; ar[4]=6.0; //a[2,2]=6

ia[5]=3; ja[5]=1; ar[5]=8.0; //a[3,1]=8

ia[6]=3; ja[6]=2; ar[6]=1.0; //a[3,1]=1

/* chargement de la matrice */

lpx_load_matrix(lp, 6, ia, ja, ar);

/* ecriture du pb dans un fichier pour verification */

//lpx_write_lpt(lp, "toto.lpt");

lpx_write_mps(lp, "toto.mps");


/* resoudre le probleme par l’algo du simplexe */

lpx_simplex(lp);

/* recuperation des resultats */

x1 = lpx_get_col_prim(lp, 1);

x2 = lpx_get_col_prim(lp, 2);

z = lpx_get_obj_val(lp);

printf("Solution :\n");

printf("x1 = %.2f\n x2 = %.2f\n z = %.2f\n",x1,x2,z);

/* sauvegarde des solutions dans un fichier */

lpx_print_sol(lp, "solution_LIN.txt");

/* resoudre le probleme par l’algo des points-interieurs */

lpx_interior(lp);


lpx_print_ips(lp, "solution_PI.txt");

/* resoudre en entier */

lpx_integer(lp);

/* recuperation des resultats */

x1 = lpx_mip_col_val(lp, 1);

x2 = lpx_mip_col_val(lp, 2);

z = lpx_mip_obj_val(lp);

printf("Solution entiere :\n");

printf("x1 = %.2f\n x2 = %.2f\n z = %.2f\n",x1,x2,z);


lpx_print_mip(lp, "solution_MIP.txt");

glp_delete_prob(lp);

return 0;

}

et le makefile associe

PREFIX = /usr/local

CC=gcc

CFLAGS = -Wall -I$(PREFIX)/include

LDFLAGS = -L$(PREFIX)/lib

LDLIBS = -lglpk


exemple: exemple.o

2.6 Le modeleur GNU MathProg

Le langage-modeleur GNU MathProg est une partie du langage AMPL. Il s’agit d’un lan-

gage de description d’un PL sous un format assez naturel. En fait, ce format permet de diviser

un PL entre sa structure et ses donnees. Pour l’utiliser, glpsol necessite ainsi plusieurs op-

tions :

--math: pour indiquer que le fichier est dans ce format

--data fichierdata: indique le fichier des donnees

--display filename: redirige la sortie vers un fichier

Pour comprendre ce qu’est un modeleur, prenons le celebre exemple de Dantzig (1963) :

trouver le cout minimal de transport en respectant les demandes des clients et de l’approvi-

sionnement des usines. La description du probleme dans un fichier de format “modeleur” se

comprend elle-meme :

Fichier transport.math

set I;

/* I est l’ensemble des usines de production */

set J;

/* J est l’ensemble des clients */

param a{i in I};

/* a[i] est la capacite de production de l’usine i en nombre de caisses */

param b{j in J};

/* b[j] est la demande du client j en nombre de caisses */

param d{i in I, j in J};

/* d[i,j] est la distance en milliers de kilometres entre une usine i et un client j */

param f;

/* f est le cout de transport en dollars par caisse et par milliers de kilometre */

param c{i in I, j in J} := f * d[i,j] / 1000;

/* c[i,j] est le cout de transport en Kilo-dollars par caisse de l’usine i au client j */

var x{i in I, j in J} >= 0;

/* x[i,j] est une variable de decision egale au nombre de caisses tranportees de l’usine

i vers le client j */

/* Si on veut les variables x entieres, on ecrit: var x{i in I, j in J} >= 0, integer; */

minimize cost: sum{i in I, j in J} c[i,j] * x[i,j];

/* Objectif: cout total de transport minimum en kilo-dollars */

s.t. CteCapacite{i in I}: sum{j in J} x[i,j] <= a[i];


/* Contrainte due a la capacite max de production de chaque usine i */

s.t. CteDemande{j in J}: sum{i in I} x[i,j] >= b[j];

/* Contrainte due a la demande de chaque client j */

Dans un deuxieme fichier, on place les donnees de l’instance du probleme. Notez que les

dimensions du probleme ne sont pas donnees dans le fichier de description.

Fichier transport.data

data;

set I := Seattle San-Diego;

set J := New-York Chicago Topeka;

param a := Seattle 350

San-Diego 600;

param b := New-York 325

Chicago 300

Topeka 275;

param d : New-York Chicago Topeka :=

Seattle 2.5 1.7 1.8

San-Diego 2.5 1.8 1.4 ;

param f := 90;

end;

En fait un meme fichier de description produira autant de PL ou PLNE qu’il y a de fichiers

de donnees associes. Un fichier modeleur plus un fichier de donnees permet aisni a glpsol de

generer un PL ou un PLNE. On peut visualiser le resultat par exemple en ecrivant le PL ou

PLNE au format Cplex lp avec

glpsol --check --wcpxlp transport.lp --data transport.data.lp --math

transport.math

Ce langage est tres riche, pour en maıtriser les finesses, le fichier lang.ps, qui est fourni

avec les fichiers d’installation, contient une description complete du langage. Mais cette

generation par fichier de description reste neanmoins une etape potentiellement couteuse

pour un probleme de tres grande taille et il est preferable d’utiliser directement l’interface

API dans ce cas.

Le fichier lp cree est le suivant :

\* Problem: transport *\

Minimize

cost: + 0.225 x(Seattle,New~York) + 0.153 x(Seattle,Chicago)


+ 0.162 x(Seattle,Topeka) + 0.225 x(San~Diego,New~York)

+ 0.162 x(San~Diego,Chicago) + 0.126 x(San~Diego,Topeka)

Subject To

CteCapacite(Seattle): + x(Seattle,New~York) + x(Seattle,Chicago)

+ x(Seattle,Topeka) <= 350

CteCapacite(San~Diego): + x(San~Diego,New~York) + x(San~Diego,Chicago)

+ x(San~Diego,Topeka) <= 600

CteDemande(New~York): + x(Seattle,New~York) + x(San~Diego,New~York)

>= 325

CteDemande(Chicago): + x(Seattle,Chicago) + x(San~Diego,Chicago) >= 300

CteDemande(Topeka): + x(Seattle,Topeka) + x(San~Diego,Topeka) >= 275

End

et une fois resolu avec la commande glpsol -o sol.txt --cpxlp transport.lp

Problem:

Rows: 5

Columns: 6

Non-zeros: 12

Status: OPTIMAL

Objective: cost = 153.675 (MINimum)

No. Row name St Activity Lower bound Upper bound Marginal

------ ------------ -- ------------- ------------- ------------- -------------

1 CteCapacite(Seattle)

B 300 350

2 CteCapacite(San~Diego)

NU 600 600 < eps

3 CteDemande(New~York)

NL 325 325 0.225

4 CteDemande(Chicago)

NL 300 300 0.153

5 CteDemande(Topeka)

NL 275 275 0.126

No. Column name St Activity Lower bound Upper bound Marginal

------ ------------ -- ------------- ------------- ------------- -------------

1 x(Seattle,New~York)

B 0 0

2 x(Seattle,Chicago)

B 300 0

3 x(Seattle,Topeka)

NL 0 0 0.036

4 x(San~Diego,New~York)

B 325 0

5 x(San~Diego,Chicago)

NL 0 0 0.009

6 x(San~Diego,Topeka)

B 275 0

Chapitre 3

Le logiciel LP solve

Lp solve est un logiciel libre de la Free Software Foundation (licence GNU lesser general

public license). Lp solve est un logiciel de resolution de programmes lineaires et programmes

lineaires en nombres entiers. Ce solveur est base sur la methode revisee du simplexe et une

methode de type Branch-and-Bound pour les PLNE.

Lp solve est ecrit en langage C ANSI et peut etre compile sous differentes plateformes

comme linux et windows. Toutes les sources sont disponibles, ainsi que de nombreux exemples

et des manuels sur le site http ://lpsolve.sourceforge.net/5.5/. Lp solve a ete developpe par

Michel Berkelaar de l’universite de technologie de Eindhoven. Ces travaux ont ete ameliores

par Jeroen Dirks, Kjell Eikland, Peter Notebaert et Juergen Ebert. La participations de tous

est souhaitee comme pour les autres logiciels libres.

3.1 En lignes de commandes

Aucune installation n’est necessaire pour utiliser lp solve en ligens de commandes. Il suffit

de telecharger et de decompresser le fichier lp solve 5.5.2.0 exe.tar.gz qui peut etre compiler

a la fois sous Windows et sous Linux. Les fichiers obtenus sont lp solve.exe (Windows) et

lp solve (Unix/Linux).

Lp solve accepte en entree les fichiers de style lp ou mps.

En utilisant un fichier mps :

lp solve -max -mps exemple.mps

En utilisant un fichier lp :

lp solve exemple.lp

lp solve -h pour obtenir de l’aide.

Usage of lp_solve version 5.5.0.13:

lp_solve [options] [[<]input_file]

List of options:

-h prints this message

-lp read from LP file (default)

-mps read from MPS file in fixed format

CHAPITRE 3. LE LOGICIEL LP SOLVE 17

-fmps read from MPS file in free format

-rxli xliname filename

read file with xli library

-rxlidata datafilename

data file name for xli library

-rxliopt options

options for xli library

-rbas filename read basis from filename

-rpar filename read parameters from filename

-rparopt options

options for parameter file:

-H headername: header name for parameters. By default ’Default’

-wlp filename write to LP file

-wmps filename write to MPS file in fixed format

-wfmps filename write to MPS file in free format

-wxli xliname filename

write file with xli library

-wxliopt options


-wxlisol xliname filename

write solution file with xli library

-wxlisolopt options


-wbas filename write basis to filename

-wpar filename write parameters to filename

-wparopt options

options for parameter file:

-H headername: header name for parameters. By default ’Default’

-wafter Write model after solve (useful if presolve used).

-parse_only parse input file but do not solve

-nonames Ignore variables and constraint names

-norownames Ignore constraint names

-nocolnames Ignore variable names

-min Minimize the lp problem (overrules setting in file)

-max Maximize the lp problem (overrules setting in file)

-r <value> specify max nbr of pivots between a re-inversion of the matrix

-piv <rule> specify simplex pivot rule

-piv0: Select first

-piv1: Select according to Dantzig

-piv2: Select Devex pricing from Paula Harris (default)

-piv3: Select steepest edge

These pivot rules can be combined with any of the following:

-pivf In case of Steepest Edge, fall back to DEVEX in primal

18 CHAPITRE 3. LE LOGICIEL LP SOLVE

-pivm Multiple pricing. See set_pivoting

-piva Temporarily use First Index if cycling is detected

-pivr Adds a small randomization effect to the selected pricer

-pivll Scan entering/leaving columns left rather than right

-pivla Scan entering/leaving columns alternatingly left/right

-pivh Use Harris’ primal pivot logic rather than the default

-pivt Use true norms for Devex and Steepest Edge initializations

-o0 Don’t put objective in basis

-o1 Put objective in basis (default)

-s <mode> <scaleloop> use automatic problem scaling

-s0: No scaling

-s1: Geometric scaling (default)

-s2: Curtis-reid scaling

-s3: Scale to convergence using largest absolute value

-s:

-s4: Numerical range-based scaling

-s5: Scale to convergence using logarithmic mean of all values

-s6: Scale based on the simple numerical range

-s7: Scale quadratic

These scaling rules can be combined with any of the following:

-sp also do power scaling

-si also do Integer scaling (default)

-se also do equilibration to scale to the -1..1 range (default)

-presolve presolve problem before start optimizing (rows+columns)

-presolverow presolve problem before start optimizing (rows only)

-presolvecol presolve problem before start optimizing (columns only)

-presolvel also eliminate linearly dependent rows

-presolves also convert constraints to SOSes (only SOS1 handled)

-presolver If the phase 1 solution process finds that a constraint is

redundant then this constraint is deleted

-presolvek Simplification of knapsack-type constraints through

addition of an extra variable, which also helps bound the OF

-presolveq Direct substitution of one variable in 2-element equality

constraints; this requires changes to the constraint matrix

-presolvef Identify implied free variables (releasing their expl. bounds)

-presolveg Reduce (tighten) coef. in integer models based on GCD argument

-presolveb Attempt to fix binary variables at one of their bounds

-presolvec Attempt to reduce coefficients in binary models

-presolverowd Idenfify and delete qualifying constraints that

are dominated by others, also fixes variables at a bound

-presolvecold Deletes variables (mainly binary), that are dominated

by others (only one can be non-zero)

-C <mode> basis crash mode See set_basiscrash

-C0: No crash basis


-C2: Most feasible basis

-C3: Least degenerate basis

-prim Prefer the primal simplex for both phases

-dual Prefer the dual simplex for both phases

-simplexpp Set Phase1 Primal, Phase2 Primal

-simplexdp Set Phase1 Dual, Phase2 Primal

-simplexpd Set Phase1 Primal, Phase2 Dual

-simplexdd Set Phase1 Dual, Phase2 Dual

-degen use perturbations to reduce degeneracy,

can increase numerical instability

-degenc use column check to reduce degeneracy

-degend dynamic check to reduce degeneracy

-degenf anti-degen fixedvars

-degens anti-degen stalling

-degenn anti-degen numfailure

-degenl anti-degen lostfeas

-degeni anti-degen infeasible

-degenb anti-degen B&B

-degenr anti-degen Perturbation of the working RHS at refactorization

-degenp anti-degen Limit bound flips

-trej <Trej> set minimum pivot value

-epsd <epsd> set minimum tolerance for reduced costs

-epsb <epsb> set minimum tolerance for the RHS

-epsel <epsel> set tolerance for rounding values to zero

-epsp <epsp> set the value that is used as perturbation scalar for

degenerative problems See set_epsperturb

-improve <level> iterative improvement level

-improve0: none

-improve1: Running accuracy measurement of solved equations on Bx=r

-improve2: Improve initial dual feasibility by bound flips (default)

-improve4: Low-cost accuracy monitoring in the dual

-improve8: check for primal/dual feasibility at the node level

-timeout <sec> Timeout after sec seconds when not solution found

-bfp <filename> Set basis factorization package

-noint Ignore integer restrictions

-e <number> specifies the tolerance which is used to determine whether a

floating point number is in fact an integer.

Should be < 0.5

-g <number>

-ga <number> specifies the absolute MIP gap for branch-and-bound

This specifies the absolute allowed tolerance

on the object function. Can result in faster solving times.

-gr <number> specifies the relative MIP gap for branch-and-bound


This specifies the relative allowed tolerance

on the object function. Can result in faster solving times.

-f specifies that branch-and-bound algorithm stops at first found

solution

-b <bound> specify a lower bound for the objective function

to the program. If close enough, may speed up the

calculations.

-o <value> specifies that branch-and-bound algorithm stops when objective

value is better than value See set_break_at_value

-c

-cc during branch-and-bound, take the ceiling branch first

-cf during branch-and-bound, take the floor branch first

-ca during branch-and-bound, the algorithm chooses branch

-depth <limit> set branch-and-bound depth limit See set_bb_depthlimit

-n <solnr> specify which solution number to return See set_solutionlimit

-B <rule> specify branch-and-bound rule See set_bb_rule

-B0: Select Lowest indexed non-integer column (default)

-B1: Selection based on distance from the current bounds

-B2: Selection based on the largest current bound

-B3: Selection based on largest fractional value

-B4: Simple, unweighted pseudo-cost of a variable

-B5: This is an extended pseudo-costing strategy based on minimizing

the number of integer infeasibilities

-B6: This is an extended pseudo-costing strategy based on maximizing

the normal pseudo-cost divided by the number of infeasibilities.

Similar to (the reciprocal of) a cost/benefit ratio

These branch-and-bound rules can be combined with any of the following:

-Bw WeightReverse branch-and-bound

-Bb BranchReverse branch-and-bound

-Bg Greedy branch-and-bound

-Bp PseudoCost branch-and-bound

-Bf DepthFirst branch-and-bound

-Br Randomize branch-and-bound

-BG GubMode branch-and-bound

-Bd Dynamic branch-and-bound

-Bs RestartMode branch-and-bound

-BB BreadthFirst branch-and-bound

-Bo Order variables to improve branch-and-bound performance

-Bc Do bound tightening during B&B based of reduced cost info

-Bi Initialize pseudo-costs by strong branching

-time Print CPU time to parse input and to calculate result

-v <level> verbose mode, gives flow through the program

if level not provided (-v) then -v4 (NORMAL) is taken.


-v0: NEUTRAL

-v1: CRITICAL

-v2: SEVERE

-v3: IMPORTANT (default)

-v4: NORMAL

-v5: DETAILED

-v6: FULL

-t trace pivot selection

-d debug mode, all intermediate results are printed,

and the branch-and-bound decisions

-R report information while solving the model See put_msgfunc

-Db <filename> Do a generic readable data dump of key lp_solve model variables

before solve

Principally for run difference and debugging purposes

-Da <filename> Do a generic readable data dump of key lp_solve model variables

after solve

Principally for run difference and debugging purposes

-i print all intermediate valid solutions. See set_print_sol

Can give you useful solutions even if the total run time

is too long

-ia print all intermediate (only non-zero values) valid solutions

Can give you useful solutions even if the total run time

is too long

-S <detail> Print solution. If detail omitted, then -S2 is used.

-S0: Print nothing

-S1: Only objective value See print_objective

-S2: Obj value+variables (default) See print_solution

-S3: Obj value+variables+constraints See print_constraints

-S4: Obj value+variables+constraints+duals

-S5: Obj value+variables+constraints+duals+lp model

-S6: Obj value+variables+constraints+duals+lp model+scales

-S7: Obj value+variables+constraints+duals+lp model+scales+lp tableau

3.2 Via l’API

L’API (Application Programming Interface) est un ensemble de routines pouvant etre uti-

lisees a partir d’un programme C/C++, Java, Delphi, Pascal, VB, C#,...

Un exemple de programme C/C++

#include "lp_lib.h"

int demo()


{

lprec *lp;

int Ncol, *colno = NULL, j, ret = 0;

REAL *row = NULL;

/* We will build the model row by row

So we start with creating a model with 0 rows and 2 columns */

Ncol = 2; /* there are two variables in the model */

lp = make_lp(0, Ncol);

if(lp == NULL)

ret = 1; /* couldn’t construct a new model... */

if(ret == 0) {

/* let us name our variables. Not required, but can be useful

for debugging */

set_col_name(lp, 1, "x");

set_col_name(lp, 2, "y");

/* create space large enough for one row */

colno = (int *) malloc(Ncol * sizeof(*colno));

row = (REAL *) malloc(Ncol * sizeof(*row));

if((colno == NULL) || (row == NULL))

ret = 2;

}

if(ret == 0) {

set_add_rowmode(lp, TRUE); /* makes building the model faster

if it is done rows by row */

/* construct first row (120 x + 210 y <= 15000) */

j = 0;

colno[j] = 1; /* first column */

row[j++] = 120;

colno[j] = 2; /* second column */

row[j++] = 210;

/* add the row to lpsolve */

if(!add_constraintex(lp, j, row, colno, LE, 15000))

ret = 3;

}

if(ret == 0) {


/* construct second row (110 x + 30 y <= 4000) */

j = 0;


row[j++] = 110;


row[j++] = 30;



ret = 3;

}

if(ret == 0) {

/* construct third row (x + y <= 75) */

j = 0;


row[j++] = 1;


row[j++] = 1;



ret = 3;

}

if(ret == 0) {

set_add_rowmode(lp, FALSE); /* rowmode should be turned off again when

done building the model */

/* set the objective function (143 x + 60 y) */

j = 0;


row[j++] = 143;


row[j++] = 60;

/* set the objective in lpsolve */

if(!set_obj_fnex(lp, j, row, colno))


ret = 4;

}

if(ret == 0) {

/* set the object direction to maximize */

set_maxim(lp);

/* just out of curioucity, now show the model in lp format on screen */

/* this only works if this is a console application. If not, use

write_lp and a filename */

write_LP(lp, stdout);

/* write_lp(lp, "model.lp"); */

/* I only want to see important messages on screen while solving */

set_verbose(lp, IMPORTANT);

/* Now let lpsolve calculate a solution */

ret = solve(lp);

if(ret == OPTIMAL)

ret = 0;

else

ret = 5;

}

if(ret == 0) {

/* a solution is calculated, now lets get some results */

/* objective value */

printf("Objective value: %f\n", get_objective(lp));

/* variable values */

get_variables(lp, row);

for(j = 0; j < Ncol; j++)

printf("%s: %f\n", get_col_name(lp, j + 1), row[j]);

/* we are done now */

}

/* free allocated memory */

if(row != NULL)

free(row);

if(colno != NULL)

free(colno);


if(lp != NULL) {

/* clean up such that all used memory by lpsolve is freed */

delete_lp(lp);

}

return(ret);

}

int main()

{

demo();

}

Lors de l’execution, on obtient :

/* Objective function */

max: +143 x +60 y;

/* Constraints */

+120 x +210 y <= 15000;

+110 x +30 y <= 4000;

+x +y <= 75;

Objective value: 6315.625000

x: 21.875000

y: 53.125000

3.3 Via l’IDE

Il existe a present un programme appele LPSolve IDE et disponible sous Windows pour

donner un environnement graphique permettant un acces facile a Lp solve. Il utilise l’API

pour acceder au logiciel Lp solve. Il est alors inutile de connaitre la programmation ou les

commandes de l’API. Cette interface donne le modele au solveur et retourne le resultat.

Facile a installer, il suffit de telecharger le fichier lp solve 5.5.2.0 IDE Setup.exe sur le site

http ://lpsolve.sourceforge.net/5.5/ .

Il suffit de taper le modele sous l’onglet ”Source” sous le meme format que l’exemple suivant

et de cliquer sur la fleche verte pour lancer la resolution.

/* Objective function */

max 5 x1 + 7 x2;

3 x1 - 2 x2 <= -9;

10 x1 + 6 x2 >= 11;

8 x1 + x2 = -6;


/* Variable bounds */

-Inf <= x1 <=0;

1<= x2 <= 4;

Toutes les fonctionnalites de Lp solve sont accessibles a partir de l’interface graphique.

– Tout est graphique et controlable par la souris.

– Peut convertir le modele sous un autre format.

– Permet de modifier le modele tres facilement.

– Lecture facile des resultats.

– Controle facile des options.

– Permet d’exporter le modele ou les resultats aux formats HTML, RTF, LaTeX.

– Montre des statistiques sur le modele.

3.4 A partir d’un modeleur

Plusieurs modeleurs disposent d’une interface permettant d’utiliser lp solve comme solveur

lineaire :

– AMPL

– MATLAB

– O-Matrix

– Scilab

– Python

– ...

Par exemple, pour utiliser lp solve a partir du modeleur ampl, il suffit de rajouter une

option dans la ligne de commande ampl.

ampl : model diet.mod;

ampl : data diet.mod;

ampl : option solver lpsolve;

ampl : solve;

3.5 En bref

Lp solve

– est un solveur de PL et PLNE

– n’est pas limite en taille de probleme

– est libre est open source

– peut lire les formats MPS et LP

– possede une interface API

– est facilement utilisable par d’autres languages de programmation

– donne la possibilite de convertir un format en un autre

– permet d’utiliser l’analyse de sensibilite

Chapitre 4

La suite logiciel COIN-OR

COIN-OR (COmputational INfrastructure for Operations Research) est un projet pour

le developpement des logiciels open-source a destination de la communaute de Recherche

Operationnelle.

Le site http ://www.coin-or.org/ regroupe les differents logiciels ainsi que des explications

claires sur leur utilite, leur fonctionnement, ainsi que de nombreux exemples.

Sous l’onglet ”Projects”, on retgrouve la liste des differents projets inclus dans COIN-OR.

Chaque projet est cliquable et ce qui nous amene a une premiere page de description du

projet presentant ses liens avec les autres projets. Une autre page propre a chaque projet

(http ://projects.coin-or.org/Nom projet/) donne les instructions d’installation et les docu-

mentations necessaires a son utilisation.

28 CHAPITRE 4. LA SUITE LOGICIEL COIN-OR

4.1 Liste des projets COIN par categorie

Developer tools

– BuildTools : COIN-OR Unix developer tools and documentation, tools for managing

configuration and compilation of various COIN-OR projects under Linux, Unix, and

Cygwin

– CoinBinary : COIN-OR Binary Distributions, pre-compiled binary distributions of COIN-

OR projects

– CoinWeb : COIN-OR Web Services, COIN-OR Web pages, Subversion, Trac, etc.

– TestTools : TestTools, Python scripts to automatically download, configure, build, test,

and install COIN-OR projects

Graphs

– CGC : COIN-OR Graph Classes, a collection of network representations and algorithms

Interfaces

– CoinMP : CoinMP, a lightweight API and DLL for CLP, CBC, and CGL

– GAMSlinks : GAMS/COIN-OR Links, links between GAMS (General Algebraic Mode-

ling System) and solvers that are hosted at COIN-OR

– NLPAPI : Nonlinear Programming API, a subroutine interface for defining and solving

nonlinear programming problems

– OS : Optimization Services, standards for representing optimization instances, results,

solver options, and communication between clients and solvers in a distributed environ-

ment using Web Services

– OSI : Open Solver Interface, a uniform API for calling embedded linear and mixed-integer

programming solvers

– SMI : Stochastic Modeling Interface, for optimization under uncertainty

Metaheuristics

– OTS : Open Tabu Search, a framework for constructing tabu search algorithms

Modeling systems

– FLOPC++ : FLOPC++, an algebraic modeling language embedded in C++

– GAMSlinks : GAMS/COIN-OR Links, links between GAMS (General Algebraic Mode-

ling System) and solvers that are hosted at COIN-OR




Optimization convex non-differentiable

– OBOE : Oracle Based Optimization Engine, optimization of convex problems with user-

supplied methods delivering key first order information (like support to the feasible set,

support to the objective function)

CHAPITRE 4. LA SUITE LOGICIEL COIN-OR 29

Optimization deterministic linear continuous

– CLP : COIN-OR LP, a simplex solver

– CoinMP : CoinMP, a lightweight API and DLL for CLP, CBC, and CGL

– DyLP : Dynamic LP, an implementation of the dynamic simplex methods

– FLOPC++ : FLOPC++, an algebraic modeling language embedded in C++

– OSI : Open Solver Interface, a uniform API for calling embedded linear and mixed-integer

programming solvers

– VOL : Volume Algorithm, a subgradient algorithm that also computes approximate

primal solutions

Optimization deterministic linear discrete

– BCP : Branch-Cut-Price Framework, a framework for constructing parallel branch-cut-

price algorithms for mixed-integer linear programs

– CBC : COIN-OR Branch and Cut, an LP-based branch-and-cut library

– CGL : Cut Generator Library, a library of cutting-plane generators

– CHiPPS : COIN-OR High Performance Parallel Search Framework, a framework for

constructing parallel tree search algorithms (includes an LP-based branch-cut-price im-

plementation)

– SYMPHONY : SYMPHONY, a callable library for solving mixed-integer linear programs

Optimization deterministic nonlinear

– DFO : Derivative-Free Optimization, a package for solving general nonlinear optimization

problems when derivatives are unavailable

– Ipopt : Interior-Point Optimizer, for general large-scale nonlinear optimization

– NLPAPI : Nonlinear Programming API, a subroutine interface for defining and solving

nonlinear programming problems

– SVM-QP : Support Vector Machine Quadratic Programming, support vector machine

quadratic programming

Optimization deterministic nonlinear discrete

– Bonmin : Basic Open-source Nonlinear Mixed INteger programming, an experimental

open-source C++ code for solving general MINLP (Mixed Integer NonLinear Program-

ming) problems

– LaGO : Lagrangian Global Optimizer, for the global optimization of nonconvex mixed-

integer nonlinear programs

Optimization deterministic semidefinite continuous

– CSDP : CSDP, an interior-point method for semidefinite programming

Optimization stochastic

– SMI : Stochastic Modeling Interface, for optimization under uncertainty


Optimization utility

– CoinUtils : COIN-OR utilities, utilities, data structures, and linear algebra methods for

COIN-OR projects

– CppAD : CppAD, a tool for differentiation of C++ functions




Web services





4.2 Le projet OSI

Un API (Application Program Interface) unifie pour les solveurs de PL et PLNE de COIN-

OR tels que CLP, BCP, CBC, ABACUS,... ou exterieurs a COIN tels que CPLEX, GLPK,

MOSEK, OSL, SoPlex, SYMPHONY, XPRESS-MP,...

4.3 Le projet CLP

CLP (COIN-OR LP) est un solveur lineaire base sur l’algorithme du simplexe.

CLP is a high quality open-source LP solver. Its main strengths are its Dual and Primal

Simplex algorithms. It also has a barrier algorithm for Linear and Quadratic objectives. There

are limited facilities for Nonlinear and Quadratic objectives using the Simplex algorithm. It

is available as a library and as a standalone solver.

#include "ClpSimplex.hpp"

int main (int argc, const char *argv[])

{

ClpSimplex model;

int status;

if (argc<2)

status=model.readMps("../../Data/Sample/p0033.mps");

else

status=model.readMps(argv[1]);

if (!status) {

model.primal();

}

return 0;

}

4.4 Le projet CBC

CBC (COIN-OR Branch-and-Cut) est une bibliotheque portant sur les algorithmes de

coupes et branchements pour la resolution des programmes lineaires en nombres entiers.

CBC is an open-source MILP solver. It uses many of the COIN components and is designed

to be used with CLP or dylp. It is available as a library and as a standalone solver.

#include "CbcModel.hpp"

// Using as solver

#include "OsiClpSolverInterface.hpp"

int main (int argc, const char *argv[])


{

OsiClpSolverInterface solver1;

// Read in example model

// and assert that it is a clean model

int numMpsReadErrors = solver1.readMps("../../Data/Sample/p0033.mps","");

assert(numMpsReadErrors==0);

// Pass data and solver to CbcModel

CbcModel model(solver1);

// uncomment to reduce printout

//model.setLogLevel(1);

//model.solver()->setHintParam(OsiDoReducePrint,true,OsiHintTry);

// Do complete search

model.branchAndBound();

/* Print solution. CbcModel clones solver so we

need to get current copy */

int numberColumns = model.solver()->getNumCols();

const double * solution = model.solver()->getColSolution();

for (int iColumn=0;iColumn<numberColumns;iColumn++) {

double value=solution[iColumn];

if (fabs(value)>1.0e-7&&model.solver()->isInteger(iColumn))

printf("%d has value %g\n",iColumn,value);

}

return 0;

}

4.5 Le projet BCP

BCP (Branch-and-Cut-and-Price) est une structure aidant au developpement d’algorithmes

de generation de coupes, generation de colonnes et branchements permettant la resolution de

programmes linaires en nombres entiers ou mixtes.

BCP is a parallel framework for implementing branch, cut, and price algorithms for solving

mixed integer programs (MIPs). BCP provides the user with an object-oriented framework

that can be used to develop an efficient problem class specific MIP solver without all the

implementational effort. involved with implementing a branch and bound framework from

scratch.

What is Branch-Cut-Price (BCP) ?

BCP is a parallel framework for implementing branch, cut, and price algorithms for solving

mixed integer programs (MIPs). BCP provides the user with an object-oriented framework

that can be used to develop an efficient problem class specific MIP solver without all the


implementational effort. involved with implementing a branch and bound framework from

scratch.

Who should use BCP?

Because BCP is an open-source framework, users have the flexibility to customize any as-

pect of their BCP algorithm. BCP is appropriate for researchers who would like to experiment

with different MIP formulations, new cut and/or variable generation techniques, branching

strategies, etc., as well as power users who would like to solve intractable problems in a parallel

environment.

How do I get it and how do I install it ?

You should read the InstallationAndGettingStarted document.

How is BCP parallelized ?

BCP processes the Branch-and-Bound search tree nodes in parallel by employing a mas-

ter/slave model. BCP is designed for a distributed network via a message passing protocol

(currently PVM, or a serial version).

Is there any alternative to BCP?

SYMPHONY is a very similar open-source, parallel branch, cut, and price framework im-

plemented in C. SYMPHONY compiles under MSVC++ and can also be compiled for shared

memory architectures with an OpenMP compliant compiler. It has a more simplified interface

and may be a better option for some users.

4.6 Le projet CGL

CGL (Cut Generator Library) est une bibliotheque d’algorithmes de generation de coupes.

The COIN-OR Cut Generation Library (Cgl) is an open collection of cutting plane imple-

mentations (”cut generators”) for use in teaching, research, and applications. Cgl can be used

with other COIN-OR packages that make use of cuts, such as the mixed-integer linear pro-

gramming solver Cbc. Each cut generator has its own Maintainer who leads the development

of its functionality, testing, and documentation. See below for a listing of available generators.

All the generators are combined in one library when Cgl is compiled. New contributions are

welcome.

– Combinatorial cuts :

o CglAllDifferent

o CglClique

o CglKnapsackCover

o CglOddHole

– Flow cover cuts :

o CglFlowCover

– Gomory cuts and variants :

o CglGomory

o CglRedSplit


– Lift-and-project cuts :

o CglLiftAndProject

o CglLandP

– Mixed integer rounding cuts and variants :

o CglMixedIntegerRounding

o CglMixedIntegerRounding2

o CglTwomir

o CglResidualCapacity

– Strengthening :

o CglDuplicateRow

o CglPreprocess

o CglProbing

o CglSimpleRounding

4.7 Le projet CSDP

CSDP est une methode de point interieur pour la programmation semi-definie.

Chapitre 5

Le logiciel Abacus

Avec glpk et lp solve -> nombre de variables et nombre de contraintes polnomial.

Mais comment gerer des formulations avec par exemple un nombre de contraintes expo-

nentiel ?

Probleme de voyageur de commerce ou probleme du sous-graphe 2 arete-connexe ?

Une solution parmi beaucoup d’autres : ABACUS ABACUS=A Branch And CUt System

Abacus fait depuis peu parti des projets COIN-OR. Abacus n’est pas un solveur lineaire.

C’est une interface entre l’utilisateur et le solveur. Initialement le solveur utilise etait Cplex,

mais depuis quelques mois, depuis l’entree de Abacus dans le projet COIN-OR, Abacus utilse

l’interface OSI et peut donc utiliser plusieurs solveurs comme CLP (le solveur de COIN-OR).

ABACUS est un logiciel fournissant une trame pour l’implementation d’algorithmes de

separation et evaluation (Branch-and-Bound Algorithms) qui peuvent etre completes par une

generation automatique de coupes (Branch-and-Cut Algoritms), ou de colonnes (Branch-

and-Price Algorithms), ainsi que de combinaisons de ces methodes. ABACUS a initialement

ete developpe par Stefan Thienel. Le fonctionnement d’ABACUS repose sur les concepts de

la programmation orientee objet avec le langage C++. ABACUS est implemente comme

une collection de classes C++. L’implementation d’un programme de resolution se fait en

derivant certaines classes d’ABACUS et en redefinissant certaines methodes de ces classes.

Cette demarche permet d’introduire dans le programme de resolution d’un probleme, des

algorithmes specifiques au dit probleme.

5.0.1 Les differentes classes d’ABACUS

L’implementation d’une nouvelle application avec ABACUS passe par la derivation de

certaines classes propres au logiciel et la redefinition de certaines methodes. La figure 5.1

presente le diagramme de classes donnant les relations entre les principales classes du logiciel.

Toutes les classes du logiciel ABACUS derivent d’une meme classe appelee ABA ABACUSROOT.

La classe ABA MASTER est la classe centrale du programme. Elle controle le processus d’opti-

misation. Elle gere les principaux parametres du probleme. Pour chaque nouvelle application,

une classe propre au probleme doit deriver de cette classe. Tous les objets qui ont besoin d’un

36 CHAPITRE 5. LE LOGICIEL ABACUS

ABA SUB

ABA GLOBAL

ABA MASTER ABA CONSTRAINTABA VARIABLE

ABA ABACUSROOT

ABA CONVAR

Figure 5.1 Diagramme de classes d’ABACUS

acces a des informations globales du probleme devront posseder un pointeur sur l’instance de

la classe ABA MASTER correspondante.

La classe ABA SUB represente un sous-probleme c’est-a-dire un nœud de l’arbre de branche-

ment. Lorsque l’optimisation commence, le nœud racine doit etre initialise avec un objet de

la classe ABA SUB.

ABACUS propose des concepts de base pour la representation des variables et des con-

traintes. La classe ABA VARIABLE represente les variables du probleme. La classe ABA CONSTRAINT

decrit les differentes contraintes. Les variables et les contraintes sont stockees dans des pools.

CHAPITRE 5. LE LOGICIEL ABACUS 37

5.0.2 Structure du programme MSIPND

L’implementation du programme de resolution du probleme MSIPND a necessite la cretation

de classes derivees des classes specifiques d’ABACUS et la surcharge de differentes methodes.

La figure 5.2 donne une vue d’ensemble des differentes classes du programme.

ABA SUB

ABA GLOBAL

ABA MASTER

C MSIPNDmaster C MSIPNDsub C var arete C ctecoupesom

C ctecoupe

C ctepartition

C ctecutcycle

C cteSpartition

ABA CONSTRAINTABA VARIABLE

ABA ABACUSROOT

ABA CONVAR

Figure 5.2 Diagramme de classes du programme MSIPND

La classe C var arete est derivee de la classe ABA VARIABLE. Elle permet de preciser les at-

tributs specifiques aux variables de notre application. On definit par exemple que les variables

sont en 0-1 pour notre probleme.

Pour chaque classe de contraintes (contraintes de coupes reduites a un sommet, de coupes,

de partition, de coupe-cycle et d’etoile-partition), nous avons cree une classe specifique (C ctecoupesom,

C ctecoupe, C ctepartition, C ctecutcycle, C cteSpartition). Pour chacune de ces nou-

velles classes, nous avons surcharg les methodes coeff(), genRow() et slack(). La surcharge

de ces methodes permet d’acceler le programme.

La classe C MSIPNDmaster est derivee de la classe ABA MASTER. Cette classe contient entre

autres les methodes initializeOptimization() et initializeParameters() ainsi que la

definition des pools de contraintes.

La classe C MSIPNDsub est derivee de la classe ABA SUB. Les instances de cette classes

representent les nœuds du probleme. Parmi les methodes de cette classe, on peut remarquer

la methode feasible() qui teste la faisabilite d’une solution, la methode separate() qui

permet de gerer la generation de coupes. Les differentes procedures de separation pour les

differentes classes de contraintes sont des methodes de cette classe.

Pour un acces rapide a ces classes, nous avons partage le programme en differents fichiers

38 CHAPITRE 5. LE LOGICIEL ABACUS

situes dans le repertoire principal :

– MSIPNDmain.cpp contient le programme principal,

– MSIPNDmaster.h et MSIPNDmaster.cpp contiennent les attributs et les methodes de la

classe C MSIPNDmaster,

– var arete.h et var arete.cpp contiennent les attributs et les methodes de la classe

C var arete,

– MSIPNDsub.h et MSIPNDsub.cpp.

Pour chaque classe de contraintes, nous avons trois fichiers differents : un fichier .h et un

.cpp contenant les attributs et les methodes de la classe associee au type de contraintes et

un fichier .cpp contenant les procedures de separation associees a la classe de contraintes. La

declaration de ces dernieres methodes se trouvant dans le fichier MSIPNDsub.h.

En resume, nous avons les fichiers suivant :

– pour les contraintes de coupe reduites a un sommet :

ctecoupesom.h et ctecoupesom.cpp,

– pour les contraintes de coupe :

ctecoupe.h, ctecoupe.cpp et MSIPNDsubcoupe.cpp,

– pour les contraintes de partition :

ctepartition.h, ctepartition.cpp et MSIPNDsubpartition.cpp,

– pour les contraintes de coupe-cycle :

ctecutcycle.h, ctecutcycle.cpp et MSIPNDsubcutcycle.cpp,

– pour les contraintes d’etoile-partition :

cteSpartition.h, cteSpartition.cpp et MSIPNDsubSpartition.cpp,

Les instances de notre probleme peuvent etre modelisees sous forme de graphes. La struc-

ture de graphe utilisee est situee dans le repertoire graphe. Ce repertoire contient differents

fichiers :

– graphe.h et graphe.cpp contenant la structure de graphe,

– goldberg.cpp contenant l’implementation de l’algorithme de Goldberg et Tarjan qui est

utilisee pour la separation des contraintes de coupes,

– barahona.cpp contenant l’implementation de l’algorithme de Barahona pour la separation

des contraintes de partition,

– reduction.cpp contenant l’implementation des differentes operations de reduction de

graphes definies dans la section ??.

Les deux autres repertoires entree et sortie contiennent respectivement les instances du

probleme que nous avons traitees et les solutions obtenues a l’aide de notre algorithme.

Un makefile est egalement fourni pour permettre de compiler le programme. Les fichiers

lance sont de petits scripts permettant de lancer l’execution des jeux d’essais.

Le repertoire MSIPND contient egalement un fichier de parametres intitule

.mes parametres abacus dans lequel nous pouvons preciser differents parametres qu’ils soient

propres a ABACUS comme la strategie de branchement, le temps limite d’execution du pro-

gramme, ou qu’ils soient lies a notre implementation comme ceux permettant de definir quelles

classes de contraintes le programme doit considerer.

Documents

Optimisation et logicielsborne/Docs/cm_ol.pdf · CHAPITRE 1. LES LOGICIELS LIBRES 5 Le d´eveloppement commercial de logiciel libre n’est plus l’exception; de tels logiciels libres