Actualités du LIPN

Le séminaire AOC recevra le 9 novembre Alberto Ceselli (Universita’ degli Studi di Milano).

In this talk I consider a location problem arising in telecommunication networks, namely the Two-level Hierarchical Capacitated Facility Location Problem (TLHCFLP): two sets of facilities have to be located, and different devices can be installed in each site, providing different capacities at different costs; single source restrictions enforce each client to be assigned to exactly one facility; location and dimensioning of the facilities have to be optimized simultaneously.

The TLHCFLP has already been tackled with both exact and heuristic algorithms.

First, I revise an exdended formulation which is the basis of our exact algorithms for the design of a network with star-star topoplogy. Then, in order to move towards more realistic models, I introduce two important features of real applications: I evaluate the option of organizing the network connecting clients to facilities as a tree, and I face the problem of survivability of the network among higher level facilities. I present models and algorithms, providing experimental results on datasets of instances from the literature.

This is a joint work with B. Addis and G. Carello.

Le séminaire AOC recevra le 21 septembrel Frédéric Roupin (professeur, LIPN).

Travaux menés en collaboration avec Jérôme Malick, Laboratoire Jean Kuntzmann, INRIA Grenoble.

Nous présentons une nouvelle famille de bornes semidéfinies obtenues par dualité Lagrangienne à partir d’une reformulation continue du problème discret initial. Les relaxations obtenues sont des programmes semidéfinis de moindres carrés, dont le dual peut être résolu efficacement et de manière robuste par une méthode standard de quasi-Newton.

Ces bornes permettent de concurrencer en temps de calcul les bornes classiques (programmation linéaire, quadratique convexe, et semidéfinie) pour certains problèmes combinatoires. En effet, leur qualité (très proche de celle de la programmation semidéfinie) peut être dégradée en échange d’un temps de calcul plus court. Pour cela, il suffit simplement d’ajuster la valeur du multiplicateur de Lagrange associé à une contrainte particulière du primal. Ces bornes sont donc particulièrement utiles dans le contexte d’une méthode de branch-and-Bound, où le rapport qualité/temps de calcul est crucial.

Leur comportement numérique est illustré sur trois problèmes classiques de l’optimisation combinatoire et difficiles à résoudre en pratique : la programmation quadratique en 0-1 sans contrainte, la recherche d’un sous-graphe dense de taille fixé, et la bipartition d’un graphe. Nos résultats montrent qu’il est ainsi possible d’obtenir les bornes usuelles en des temps de calcul inférieurs.

L’équipe OCAD accueille Rosiane de Freitas Rodrigues (D.Sc. DCC/ICE - Federal University of Amazonas COPPE-Federal University of Rio de Janeiro, Brazil ).

This work deals with scheduling problems with unit execution time jobs, time-windows constraints, parallel machines and the objective function of minimizing the total number of tardy jobs. The emphasis is on deterministic scheduling, characterization theorems, polynomial time algorithms and their computational complexities, and the use of graph theoretical tools, whenever is possible. New models and characterizations have been proposed, that result in better algorithms. For the problems 1 | pj=1; rj | sum Uj, and P | pj=1; rj | sum Uj, formulated in the 3-field notation, a time complexity of O(n log n) was obtained. For the problems 1 | pj=1; rj | sum wjUj, and P | pj=1; rj | sum wjUj , a better upper bound with O(n² (1+logm/m) ) time complexity was obtained. The best time complexity for such problems was O(n^3m), based on network flows techniques.

We also consider a multi-purpose machine scheduling problem, where jobs should be executed in some machine belonging to a given subset of the set of machines. The problem is PMPM | pj=1; rj | sum wjUj, with n independent unit-time jobs, time window constraints, m identical parallel multi-purpose machines, and the minimization of the total weighted number of tardy jobs. The best previous complexity for this problem is O(n²m(n + log m)), employing network flow techniques. We develop an algorithm that uses basic concepts of computer science to handle more efficiently successive nesting of on-time jobs, with O(n³) overall time complexity.

It is expected that the results serve as a means for better understanding of other scheduling problems, offering new characterizations and more efficient algorithms.

Le séminaire OCAD accueille Mathieu Lacroix (ATER, LAMSADE, université Paris-Dauphine).

Dans un premier temps, nous considérons le problème lorsque la flotte est composée de plusieurs véhicules, les transbordements sont possibles et le fractionnement des demandes est autorisé. Nous donnons deux formulations à l’aide de programmes linéaires mixtes basés sur un graphe spatio-temporel. Nous présentons des contraintes valides et fournissons, pour chacune des deux formulations, un algorithme de coupes et branchements pour résoudre le problème. Nous comparons finalement les résultats expérimentaux obtenus avec les deux algorithmes.

Nous considérons par la suite le problème lorsque la flotte est composée d’un unique véhicule et le fractionnement des demandes n’est pas autorisé. Nous considérons également la version unitaire de ce problème, c’est-à-dire, lorsque le véhicule ne transporte qu’une seule demande à la fois. Pour ces deux versions, nous donnons une formulation sous forme d’un programme linéaire en nombres entiers. Nous étudions ensuite le polytope des solutions de la version unitaire et développons un algorithme de coupes et branchements. Nous étudions également ce polytope dans la classe des cactus. Nous considérons finalement un cas particulier de la version unitaire du problème lorsque le graphe est complet, chaque sommet est incident à au plus une demande et les coûts vérifient les inégalités triangulaires. Nous montrons que, sous ces hypothèses, le problème se ramène à la recherche d’un cactus de coût minimum vérifiant certaines propriétés. En se basant sur cette transformation, nous proposons une métaheuristique pour résoudre le problème.

Le séminaire OCAD accueille Saïd Hanafi (LAMIH, université de Valenciennes).

Le problème de programmation en nombres entiers mixtes (MIP) consiste à optimiser une fonction linéaire sous des contraintes linéaires d’inégalité et/ou d’égalité, où certaines ou toutes les variables sont des entiers. Les résultats de complexité n’ont pas encore définitivement identifié le niveau de difficulté de ces problèmes, mais des découvertes empiriques suggèrent que les ressources calculatoires requises pour résoudre certaines instances de problème MIP peuvent augmenter exponentiellement avec la taille du problème. Nous présentons plusieurs méthodes hybrides de résolution pour les MIP permettant de générer des bornes inférieures et supérieures de bonne qualité. Les bornes inférieures sont obtenues en résolvant une série de relaxations (relaxation en continu et/ou relaxation en nombres entiers mixtes). La séquence de bornes inférieures est générée en résolvant une série de problèmes réduits obtenus à partir de la relaxation courante et l’historique de la recherche. Ces algorithmes convergent vers une solution optimale du problème en un nombre fini d’itérations. Certains concepts reposent sur un algorithme proposé à la fin des années 1970 par Soyster et al. Différentes améliorations et extensions sont proposées. Les algorithmes combinent à la fois des méthodes de résolution exacte et approchée. Ils sont applicables aux problèmes en variables 0-1 et sont plus efficaces lorsque le nombre de contraintes est petit par rapport au nombre de variables. Les résultats obtenus sur le problème de sac à dos multidimensionnel avec ou sans les contraintes de choix multiples sont intéressants, même si la convergence théorique de l’approche est difficilement utilisable en pratique.