Titre :

Set partitioning problem with equity constraint: application and column-generation based approach

Auteur(s) :

Ogier, Maxime [Auteur]
Recherche Opérationnelle pour les Systèmes de Production [G-SCOP_ROSP]
Catusse, Nicolas [Auteur]
Recherche Opérationnelle pour les Systèmes de Production [G-SCOP_ROSP]
Cung, Van-Dat [Auteur]
Recherche Opérationnelle pour les Systèmes de Production [G-SCOP_ROSP]
Boissière, Julien [Auteur]
Laboratoire d'Informatique, Systèmes, Traitement de l'Information et de la Connaissance [LISTIC]

Titre de la manifestation scientifique :

Ninth International Colloquium on Graphs and Optimization

Ville :

Sirmione

Pays :

Italie

Date de début de la manifestation scientifique :

2014-07-07

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

In this problem two sets of actors are considered: a set of clients with their location and demand, and a set of suppliers with their location, scope of action and a minimal profitability threshold. A supplier is able to ...
Lire la suite >In this problem two sets of actors are considered: a set of clients with their location and demand, and a set of suppliers with their location, scope of action and a minimal profitability threshold. A supplier is able to deliver a subset C of clients if (1) all the clients of C are located inside its scope of action, and (2) the profitability when delivering the clients of C is greater than its threshold. The profitability is computed as the ratio between the total demand of the subset C and the distance to travel for delivering the clients of C. This distance can be computed based on the Travelling Salesman Problem (TSP). The optimization problem consists in finding a partition of the set of clients maximizing the number of suppliers able to deliver the subsets of clients. An original equity constraint is added: The gap between the minimum and maximum profitability of the selected parts need to be lower than a given value. This problem is NP-hard as a generalization of the Set Partitioning problem and a formulation as an Integer Linear Program is proposed. As the number of variables (parts) is too large, a column generation-based approach is proposed at the root node of the Branch & Bound tree. This solving method seems to have a good trade-off between computational time and quality of solutions obtained. Nevertheless, our ILP formulation has a weak linear relaxation leading to the generation of infeasible integer solutions far from satisfying the equity constraint. To improve the solutions, we propose to modify the formulation for the linear relaxation by removing the equity constraint and penalizing the deviation from a profitability target in the objective function. An iterative algorithm is then proposed in order to dynamically adjust the target and the associated penalty cost. Besides, the sub-problem of finding new columns with implicit description is hard to formulate: the number of suppliers able to deliver a subset of clients depends on the profitability ratio, and the computation of this ratio requires to solve a TSP tour but without knowing the subset of clients. To overcome this difficulty, a heuristic has been developed to solve the sub-problem. But the optimality of the solution at the end of the column-generation process is no longer guaranteed. Some results on real case application are presented, and compared to exact solutions for small instances using CPLEX 12.6 and a local search method for larger instances.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL