How to decide upon groceries daily
and what this has to do with time-varying optimisation problems - by Xian Li
Suppose you are a restaurant owner who has to shop for groceries every day to prepare dinner for your guests. You have a limited budget, and the groceries you are procuring are only used for that day. Your goal is to conjure up the “best” dinner every day. This is an optimisation problem: you try to maximize an objective (the quality of the dinner) subject to constraints (the budget). However, the prices of some ingredients will change slightly from day to day, and therefore, your optimal solution will also change. Such problems are called time-varying optimisation problems. Imagine yourself in a great hurry, with no time to remake your grocery list from scratch. Luckily, you do have the list from yesterday to use as a reference. How would you proceed to tackle this problem?
Usually, solvers for optimisation problems assume the problems to be static, meaning non-time-varying, as if the prices do not change day by day.
When dealing with time-varying optimisation problems, using a static solver to solve the individual problems from each time step from scratch can be slow or sometimes even violate the constraints (your budget). Picture yourself reworking the list and adding everything you want to buy to your basket. Just when you have put all that you desire into it, you have to hurry to your restaurant, since the opening hours are near. You rush to the cashier, only to discover that you are over your budget. This is what typically happens if a conventional optimisation solver is applied for each time step individually; the solutions may not satisfy the constraints when terminated prematurely.
We aim to design a solver for time-varying optimisation problems that explicitly exploits the similarity between time steps. In our approach, we use the grocery list from yesterday as a reference. If we stayed within our budget then, we would be able to easily determine which modifications to the list would keep the list affordable, since the prices of only a few items would change, and only slightly.
And that way, you are finally able to shop with ease, and possibly with time to spare.
Text by Xian Li; illustration created with Gemini
How to decide upon groceries daily and what this has to do with time-varying optimisation problems - by Xian Li