Research Proposal

Research proposal for Witek

Supervisors: Joost Berkhout & Ger Koole

• Many decision problems have a dynamic nature, the consequences of our decisions become available step by step over time, and can only be simulated or calculated as a Markov chain. Decisions have long-term consequences, and these consequences are also often of a stochastic nature. To “remember” these consequences the “state” of the system plays a crucial role. Decision problems can roughly be divided in two types of problems: those where the decisions are taken on the fly and are accounted for through a state change, and those where decisions are taken upfront. The first category falls into the framework of stochastic dynamic programming and is currently immensely popular in AI under the name reinforcement learning. The second is equally important but receives much less attention. Examples are the scheduling of people in service centers such as health clinics and call centers. Employees have to be scheduled well in advance, but the consequences in terms of for example waiting times can only be modeled through a stochastic process, for which simulation and Markov chain analysis are the two prime solution methods.

• Other examples are the design of energy systems and appointment scheduling, but the list of possible applications is endless. Note that many service systems have both types of decision problems: for example long-term capacity and employee scheduling problems, and short-term task scheduling and re-adjustments to the schedule.

• The focus of the project is on the second type of problem. Simulation, and to a lesser extend Markov chain analysis, are computationally costly solution methods, and they have to be executed for multiple decisions. Because the decision space is often multi-dimensional enumeration is not possible. Local search can only find local optima and that is for a fixed computational budget not even guaranteed.

• Smarter methods are needed, a very interesting candidate is fitting a machine learning model to a limited set of solutions and then try to find the a (local) optimum. This has the advantage that, once trained, it is much faster to use a ML model than simulation or Markov chain analysis. This is known in the literature as surrogate models and response surface methodology (to be checked), but the current developments in machine learning open possibilities for new versions of algorithms and new applications. A couple of things to look into:

  • applications into for example appointment scheduling and shift scheduling
  • does an iterative approach help, where the test set consists of points close to the optimum of the previous iteration? perhaps in combination with linear regression with squares and interactions which gives a global optimum?
  • can knowledge about the problem (such as monotonicity in a parameter) be included in a smart way in the prediction model.

Some other things to do:

• do a thorough literature review

• write a python package