Dynamic Combinatorial Optimization

Traditionally, a combinatorial optimization problem is specified by describing the problem (say a traveling salesman problem), giving all data (a distance matrix) and specifying a criterion (minimizing total distance). Then, either heuristically or exactly, a solution (a tour) to the problem is found; this type of optimization is called offline. The computation time available for solving offline problems is in many situations sufficient for algorithms to deliver good quality solutions. In contrast to this, there is the set of online optimization problems (say online bin packing) where the data (item size) are only revealed piece by piece, and where a decision must be made after each input received. This is the class of online optimization problems. Here, typically, algorithms must be fast to be practical.In this research proposal we focus on problems that are in between online and off line. Indeed, we envision a setting where the uncertainty about future input increases over time. We are aware of several practical fields where exactly this phenomenon is present. We confine ourselves here to mentioning a (not exhaustive) list of applications: production planning and scheduling, order picking, data association problems. It is our goal to develop efficient and robust algorithms for this type of problem. Such algorithms require usage of historical data as well as available information about the immediate future. This will, among others, require a synergetic approach combining data science and optimization.

Keywords:optimization

Disciplines:Applied economics, Economic history, Macroeconomics and monetary economics, Microeconomics, Tourism