Hello, I’ve just started experimenting with JaCoP and have a question about whether JaCoP (and constraint programming in general) is an appropriate solution for a problem I’m trying to solve.
I work in the healthcare informatics industry, and my company is interested in building an “engine” for scheduling radiology exams. For this type of scheduling problem, you can imagine various resources that need to be managed, such as nurses, radiology technicians, imaging devices (e.g. CT scanners), examination rooms, etc. Each of these resource types could have constraints on them, such as when they are available, their capacity, etc. A radiology exam may be broken down into several schedulable steps, each with different resource requirements. For example, an MRI exam may require a nurse to perform an injection, followed by a 15 minute wait, followed by the actual MRI scan performed by a radiology technician on a specific piece of equipment. The most complex type of exam would have 3 or 4 schedulable steps, each with different resource requirements, while the simplest exams would only have a single step with a single resource requirement.
When the exam is scheduled (typically by a referring physician), the goal is to provide to the user a list of available dates/times when the required resources are available, and allow them to choose one. The work day is typically broken up into time increments or slots ranging from 10 to 60 minutes, depending on the site, so the final presentation to the user would be in the form of a matrix of slots that they can choose from. For example (O = slot is open/available; X = slot closed):
Mon Tue Wed Thu Fri
09:00 O O X O
09:15 O O X O
09:30 X O O X
17:15 O X O O
17:30 O X X X
17:45 O O X O
In a large institution there could be dozens of imaging sites that can perform the exam, each with several devices. This leads to a fairly large number of candidates that need to be calculated, so the solution needs to be efficient.
From my limited experience with JaCoP, it seems like constraint programming is a very elegant technique for defining the capabilities and constraints of the resources, and which resources are required to perform a specific exam. What I’m not sure about is whether this approach is suited to finding a large number of equally valid solutions, as opposed to a single “best” solution. Most of the examples I’ve seen with JaCoP and other CP libraries seem to be the latter type of problem where the suitability of a solution can be estimated fairly easily based on time to finish or cost. For my problem, I’m not sure you can assign a weight or score to a slot, since the criteria for determining which slots are “better” would vary quite a bit depending on the patient.
I would appreciate any feedback or suggestions that anyone might have as to whether I’m on the right track with JaCoP/CP or if I should be looking elsewhere for a solution.
Thanks very much!
Dear Dan Acton,
Few remarks below. Yes, CP is an elegant approach for many constrained problems, scheduling especially. There are many global constraints in CP that were created with scheduling problems in mind.
In JaCoP, we have started JaCoP so we can apply it to scheduling problems. Therefore, we have a lot of global constraints that can be used in scheduling like problems, diff2, cumulative, binpacking. JaCoP/CP gives you proper tools to address non trivial problem of scheduling resources. There are other constraints that can be of help like regular, network flow, knapsack constraints, geost, … . Each addressing a different structure a problem may exhibit that if model using a global constraint you get a powerful and efficient reasoning algorithm to help you analyse your partial solutions during search.
However, due to the size of your problems (assuming easily of 100-1000 tasks) a CP user must understand well how CP works to be able to design proper search that will use every possible CP technique to make the problem simpler to solve. You will for certain need to sacrify proof of optimality for the search efficiency. It may also be beneficial to use CP in conjunction with other techniques (LP, SAT, LocalSearch) that together will create very powerful hybrid solutions.
Concerning your question "whether this approach is suited to finding a large number of equally valid solutions …". This is not a problem at all. I can give few very basic hints.
1) There is an element constraint, that takes index, list of (vars or ints) and value, you can use it in the following way, index is actual slot for the exam, list of the preference/benefit/quality for each of the possible slots the exam can take, and value is the actual benefit given the choice of the slot. This way you can compute the partial benefit for each of the exams, and then sum it up, later you could search for all solutions, which are not worse than 5% of the best solution found.
2) The approach 1 is very simple/basic and somewhat expensive as you use a combination of element and sum constraint. There are also ExtensionalSupport* constraints that can be used to express any preference function benefit = f(vars), and we have very efficient implementations for those functions. This gives you much more freedom in building your own objective function.
3) Finally, the best approach is to see if your preference/objectives can be expressed as a global constraint, e.g. knapsack constraint, network flow constraint, etc because then the preferences/solution quality is computed using global constraints and then the search can quicker find the set of good quality solutions.
Hope that is of some help. I would not worry about expressing user preferences too much, the aspect of the problem that will be harder is how to make your approach scallable (proper model so it strong enough in terms of reasoning, proper search so that no time is wasted) so that it can give you good quality solutions for problems of the size you will need to tackle.
We always try to help our users, so feel free to contact me by email if you need more help. Sometimes, a quick look at the solution can already help immensely by pointing out problems in the model and search. We also provide paid consultancy if you need a lot of help.
best regards, Radek
Sign up for the SourceForge newsletter:
You seem to have CSS turned off.
Please don't fill out this field.