Luis-Marques

In this thesis, we are interested in problems that can be formulated as a sequence of decisions, where dynamic programming is a suitable modeling paradigm. To solve large-scale problems, we study aggregation and disaggregation methods that allow us to construct relaxations of the problem, which are solved to obtain optimistic solutions to these problems. Iterative algorithms are then designed from these relaxations, where the relaxations provide less optimistic solutions as the number of iterations increases. In this thesis, we first provide a literature review of the aggregation and disaggregation methods in the context of dynamic programming formulations. Then, we propose a problem modeling the aggregation of vertices in decision graphs of dynamic programs to construct relaxations and show that many aggregation methods in the literature are special cases of this problem. We then study an application of network flow formulations in a decision hypergraph, and extend some aggregation methods to this case. To validate our approaches, we present computational results on a set of different problems and compare them to similar approaches in the literature. We conclude this thesis with a discussion on the results obtained and propose some perspectives for future work.

[Read more]

In this thesis, we are interested in problems that can be formulated as a sequence of decisions, where dynamic programming is a suitable modeling paradigm. To solve large-scale problems, we study aggregation and disaggregation methods that allow us to construct relaxations of the problem, which are solved to obtain optimistic solutions to these problems
[Read more]

Authors: Luis Marques, François Clautiaux, Aurélien Froger
Abstract: We study the problem of designing a cabinet made up of a set of shelves that contain compartments whose contents slide forward on opening. Considering a set of items candidate to be stored in the cabinet over a given time horizon, the problem is to d [Read more]

We consider general aggregation/disaggregation techniques to address optimization problems that are expressed with the help of sequential decision processes. Our main goals are threefold: a generic formalism that encompasses the aforementioned techniques ; more efficient algorithms to control the aggregation procedures ; open-source codes that leverage and integrate these algorithms to efficiently solve hard combinatorial problems in different application fields.
[Read more]