Historique: report-roland

Aperçu de cette version: 1 (courant)

Julien Roland to Nancy: Report

The aim of this visit was to develop new models and algorithms for the single and multi-objective inverse knapsack problem in cooperation with my co-supervisor: Jose Rui Figueira.
There were two initial steps for achieving the goals of this mission: to build a taxonomy, and to highlight applications. We started to work simultaneously on the taxonomy and applications. There was a clear link between inverse optimization and uncertainty in our mind. Discussions with Prof. José Rui Figueira led me to take interest in interval programming, and to add this aspect in the taxonomy. Next, we sketched an illustrative application of inverse optimization drawn from portfolio analysis with grateful help from Prof. Bernard Roy. This application take into account both uncertainty on profits in the objective function and an annual budgeting cycle.
This application led us to extend our study of inverse optimization to partial inverse optimization, where only a part of the optimal solution is given as input. Indeed, a partial solution can be used to represent the portfolio selected previously in the case of an annual budgeting cycle. We changed significantly our taxonomy to take this new aspect into account. Then, we asked for help to many renowned scientists (Bernard Roy, Jeffrey Keisler, and Gregory Parnell) to improve this portfolio selection problem. This helped to build an innovative motivation for the partial inverse knapsack problem.
Concluding this mission, we decided to model a first linear program with a pseudo-polynomial number of variables for this newly designed problem. Then, we studied some theoretical properties of this model leading us to a promising algorithm for solving the problem.
This collaboration with José Rui Figueira could lead to a double degree (co-tutelle) between INPL (Ecoles des Mines) and ULB (Université Libre de Bruxelles).
Results obtained during this mission should lead to the submission of a publication entitled: “The Partial Inverse {0,1}-Knapsack Problem”.


Information Version
mer. 09 de mars, 2011 17h00 uendriss 1