Optimisation problems - Far from being a commodity

I am always surprised how many - at first sight - easy, resource optimisation problems, are still unsolved or can only get solved by specialist users.
Almost in every industry, you have optimisation problems, i.e. problems in which resources are constrained (limited capacity) and need to be most effectively planned to come to a solution. Typically, each resource also comes with a number of constraints, which makes the planning exercise even more complex.

Some every-day examples are:

• School exam schedules: create a schedule for all exams for the different school years and directions, taking into account the availability of teachers (sometimes working at multiple schools), availability of classrooms, but also preferences of students (e.g. complex and large classes like mathematics placed after a weekend).
• School schedules for supervision during breaks: create a schedule for the supervision of teachers on the playground during breaks, taking into account the number of hours each teacher should do supervision (based on seniority and working regime), the availability of the teacher at the school (e.g. don’t foresee a teacher for supervision on a day he is not working or he is working at another school) and the preferences of each teacher.
• School class schedules: create a schedule for all classes for the different school years and directions, taking into account the availability of teachers, the number of hours each direction should follow of a specific class and some logical constraints ensuring a good mix (e.g. not all hours of one class on the same day, mix of sciences and languages during a day…​)
• Allocation of students to schools: allocate all students to different schools, taking into account the number of places in each school, which directions are offered at each school, the preferences of students, the distance of the student’s home address to the school, priority students like brothers/sisters of students already at the school…​
• Schedules for work shifts: these schedules should make sure all work gets done, that the schedule is fair and motivating for every employee, but also that potential costs are minimized (e.g. for airplane crew avoid as much as possible hotel costs if crew has to spend the night abroad), e.g.
  • In hospitals: schedules for doctors and nurses
  • In airline companies: schedules for plane crew (pilots and stewards/stewardesses), taking into account flight schedules, minimum rest times, working regimes, ensuring a mix in seniority of the crew, capabilities of pilot to fly with certain planes…​
• Task assignments:
  • Assignment of manual tasks, with different degrees of complexity to a number of resources, taking into account resource availability, resource task backlog, complexity of task and knowledge/expertise of resource…​ Typical examples in the financial services industry are credit analysis and decision tasks and KYC tasks.
  • Allocation of specialists to projects: in a company certain IT specialists like DBAs, architects, DevOps specialists, security specialists…​ are often solicited by multiple projects. The allocation of these specialists is also an optimization problem, taking into account the availability of the specialists, priority of projects, planning restrictions of the projects, effort required on each project…​
• Schedules for usage and maintenance of vehicles, tools and equipment, e.g.
  • Airplane scheduling: determine which aircraft to fly on each route, where and when it should be maintained, whether airplane should make intermediate stops…​
  • Office & desk assignment: determine location of office (optimal for everyone to come to office) and desks to optimize productivity (minimum travel time, maximize collaboration, maximize employee satisfaction, minimize costs…​)
  • Schedules for maintenance of highly used and expensive equipment, e.g. maintenance of electricity centrals, taking into account constraints like electricity price, forecasted electricity consumption, availability of resources to execute the maintenance activities…​
  • Commitment of equipment, e.g. generator commitment, i.e. given the forecasted demand and operating cost of each generator, determine which generators should be activated at which time
• Route planning:
  • Calculation of delivery routes (for transportation companies, postal services, courier services…​): given a list of destinations to deliver something, what is the optimal route to pass by each delivery address, taking into account constraints like traffic jams (current traffic jams, but also forecasted recurring traffic jams), availability of people to sign off for a delivery, urgency of a delivery…​
  • (Multi-modal) Route planning: planning a route, allowing to use different mobility options (car, bike, public transport, shared mobility…​), while taking into account constraints like weather, passengers, personal preferences (e.g. mobility restrictions), availability of mobility options, traffic on the road, cost price…​ The route could be optimized for time, cost price or ecological footprint (or a combination of these different objectives.
• Investment advise optimization:
  • Robo-advise: given a limited amount of money a customer can invest, try to optimize the customer’s portfolio diversification (i.e. minimize correlation between assets, thus minimizing market risk) taking into account multiple constraints, like MiFID2 appropriateness constraints (i.e. only invest in products in which customer has required knowledge and experience), MIFID2 suitability constraints (i.e. the resulting portfolio should meet the customer’s investment objectives), customer’s personal constraints (e.g. only local firms, no foreign currencies, no tobacco or weapon industry, only investment in sustainable companies), internal policy constraints (e.g. no derivatives, maximum 20% in same share, maximum 10% in same sector, bonds should have a minimum B+ rating), cost constraints (i.e. optimize for transaction costs, by avoiding to sell existing positions if not needed and avoiding to buy too much small positions), trading constraints (such as minimum trading quantity and denomination)…​
  • Determine optimal bond portfolio: based on a predefined schedule of future (in and out) cash flows, compose a bond portfolio, for which coupon and reimbursement payments match these cash flows, while meeting also additional objectives and constraints, like maximizing return (i.e. highest interest rate), minimum bond rating, maximum percentage in same bond issuer…​

All the above problems are actually optimisation problems, for which in principle all elements are known upfront (or can at least be estimated), meaning there is little to no forecasting required. This makes a big difference with forecasting problems (often resolved with AI), which usually try to predict future behaviour based on data (and derived insights) from the past. Examples of such forecasting problems are calculation of required cash to be foreseen in ATMs, customer or employee churn predictions, product recommendations, credit scoring (calculate probability of customer not being to reimburse credit)…​

Every one of the above optimisation problems has following elements:

• A (finite) list of resources (e.g. employees, equipment, vehicles, money…​) which should be allocated in the best possible way
• A list of constraints on the resources (e.g. maximum working hours per employee). As it might be impossible to meet all constraints, it is important to set a weight to each constraint, so that hard constraints are forced to be met, while softer constraints are only used for optimization.
• A cost function to determine how well a specific solution to the optimization problem meets the expectations, i.e. indication how well constraints are met and how well the target objective is reached. This target objective can be a single objective (like minimizing cost, minimizing delays…​) or a weighted combination of multiple objectives.

Note that in some cases in order to calculate the cost function, it might be required to work with simulation and forecasting models to calculate certain external or non-mathematical factors (such as traffic jam prediction or employee motivation). It is however best to split these 2 problems, i.e. the optimization problem can be isolated by calling a separate forecasting model to get necessary input for cost function calculation.

Given the specific skills required to solve these issues (not yet commoditized) and also the fact that optimizations often cross certain boundaries (e.g. for exam schedules, it should ideally be done for all schools together, to take into account teachers working at multiple schools), "Optimisation as a Service" seems a very interesting business.

Depending on the frequency of execution of the optimisation problem, different service levels can be foreseen, i.e.

• For a one-shot calculation problem, data can be delivered manually, and very little automation is required.
• For a recurring (daily, weekly, monthly) calculation more automation is required in the delivery of the input data (i.e. resources and their availability and constraints), the execution and delivery of output results, but performance is less of an issue
• Continuous (also real-time) optimization problems, requiring a full automation, with very low latency

While the world is overwhelmed by Machine Learning and AI tools, offerings and consultancy firms, it is strange that these optimisation problems which offer also enormous business potential for many companies, are still the domain of specialists and intuition and a lot of manual work. It will be interesting to see if open source tools (like TensorFlow did for ML and AI) can further commoditize these problems. The business potential is in any case enormous (will Google deliver the necessary revolution here as well or will a new unicorn rise?).

Check out all my blogs on https://bankloch.blogspot.com/