GSoC 2017 – Week 4

It’s the fourth week, and we’re nearly done with the first round of developments. My main objective for the first round was migrating the Operation Theater module to the latest platform, and I’ve completed about 80% of it. There’s just one more thing to finish – to get the scheduler working.

The OT module uses a tool named Optaplanner for scheduling theater activities. It’s an open source constraint satisfaction solver written in Java. We can model the theater planning activity as a constraint satisfaction problem (CSP) and use Optaplanner to get a somewhat optimal solution in a given amount of time. As you might know, CSPs are  considered to be either NP-complete or harder.

Let’s start with a few definitions before we get to the nitty-gritty.

Constraint satisfaction problem – a problem with a limited set of resources, and constraints on possible paths to a solution. A solution needs to satisfy the given constraints and employ available resources.
NP-completeness – the abbreviation NP means Nondeterministic Polynomial time. We’ll need to go way out of our topic to describe what each of those terms mean exactly, so let’s get a high-level idea. Simply put, NP-complete means the following;

  • It’s easy to verify a given solution of such a problem, in a reasonable amount of time.
  • We don’t know an efficient method to get such a solution.

The best-known characteristic of NP-complete problems is that we don’t have a fast way to solve them. All current methods grow exponentially more complex as the size of the problem grows. ?

You already know that theater scheduling is a CSP. What else are CSPs? Well, think about creating timetables in a university. Or scheduling nurses in a hospital. Planning car assembly lines. Investment portfolio optimization. Cutting steel sheets in an optimal manner. All of these are constraint satisfaction problems. Aaand planning problems. They have goals that they wish to optimize and limited resources under constraints. You can refer the documentation of Optaplanner for a good description of them[1].

Anyway, the OT module has an implementation of Optaplanner based off of version 6.0.0. That one isn’t working nicely with the shiny new other libraries that we’re using, so I need to migrate it to version 7.0.0.

There are two ways I can do this.

  1. Make the changes that happened in Optaplanner through versions 6.0.0 to 7.0.0.
  2. Write a new solution in the latest version, using the earlier implementation as a guide.

I thought a little on this and realized that while I could write a new solution, then I’d need to check how the current implementation communicates with the Optaplanner engine and write matching API endpoints to ensure proper functionality. Given the limited amount of time I have with all the work of the internship, I thought it’s best to first try to migrate the existing solution.

So right now, I’m working on making necessary changes to the solution so that I can get it running asap. Let’s see how optimal we can get.

Published by