Master Thesis on Optaplanner

[Michał Dudkiewicz]

Hi

I am a Software Engineer and also doing my CS master thesis at Lodz University of Technology (Poland). In the scope of the thesis I would like to contribute somehow to Optaplanner open source code (do some research, compare the results with your benchmarker and end up creating a PR).

I've already used your solver for optimizing employee teams scheduling at my father's company and also did some other optimization at the company using Google OR-Tools (employee scheduling with preferences in the scope of my Engineering Thesis). Although I am not Java fan and my main programming language is C++ on daily basis I think your solver have some advantages over Google OR-Tools and I would also like to take part in developing it.

I have a few ideas that I could realize and contribute to the open source community. Could you please confirm whether working on one of these topics in the scope of my master thesis could be beneficial and interesting for you? Ideally I would like to contribute in a form of PR at the end.

These are the topics I concerned after some research (they lacks in the current implementation):

- using not only the last construction heuristic result, but consider taking a few of them for random restart local search

- a completely new construction heuristic/metaheuristic (I noticed there are some of them mark as not implemented yet in the docs). What about Discrete Lagrange Multipliers method? Have you tried the approach? Or maybe some evolutionary algorithm? I know GA was already tested and prototyped.

Please let me know if any of these ideas would be useful to do in the scope of my master thesis and potentially could end up contributing to your solver somehow. Also please confirm whether anyone else is not working(/already worked) on these in the same time. Or maybe you have some other suggestions or ideas that I could work on?

Thank you for your work. It is really useful for solving many problems at my father's company.

Michał Dudkiewicz

SE

My LinkedIn:
https://www.linkedin.com/in/micha%C5%82-dudkiewicz/

[Holger Brandl]

Thanks Michal,

sounds like a very ambitious and exciting topic to me. 

I'd be also very keen to learn more about your comparison of or-tools and optaplanner. Is there some publication/talk/etc. available detailing the results of your comparative analysis?

Kind regards,

Holger

--
You received this message because you are subscribed to the Google Groups "OptaPlanner development" group.
To unsubscribe from this group and stop receiving emails from it, send an email to optaplanner-d...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/optaplanner-dev/3305eb06-fd3c-4b13-85aa-e3216556f1a5n%40googlegroups.com.

[Lukáš Petrovický]

Michał,

On Sat, Feb 25, 2023 at 1:28 PM Michał Dudkiewicz <michal.du...@gmail.com> wrote:

Please let me know if any of these ideas would be useful to do in the scope of my master thesis and potentially could end up contributing to your solver somehow. Also please confirm whether anyone else is not working(/already worked) on these in the same time. Or maybe you have some other suggestions or ideas that I could work on?

I reviewed your proposals, and they sound interesting. The first one especially made me think of something which we internally call "loop phase". [1]

It's related to more than just construction heuristics, but it is one way to approach "ruin and recreate" semantics in the solver. Essentially, the local search reaches a particular solution, then some code is run, the solution is partially or fully ruined, and the solver loop runs again on this new solution. See [2] for inspiration.

Doing this via a loop phase would require significant changes to the core of OptaPlanner, and I do think that - together with proving by benchmark data that the loop phase provides significant improvements on problems of all kinds - it could be a good master thesis.

(Another approach to the same problem would be to write some generic "ruin and recreate" moves; moves that understand how to ruin a solution and then how to rebuild it back up. This would have the benefit of being both closer to [2] and possibly more flexible. Also much much harder, as the construction heuristics would have to be run *inside* of a move.)

One thing where I would advise a different approach to the one you propose is the idea of a "PR at the end." This is not the best way to work together. Large code dumps are frowned upon, and likely will not be accepted. 

If we can work together in an incremental fashion, step-by-step, starting with proper analysis of the problem and a thorough discussion of the selected approach, the chances of merging your code will be much higher. You should also know that the OptaPlanner project is very demanding in terms of code quality, and we have high standards on performance and test coverage as well.

If all of that sounds like an interesting project for you, then let's set up a meeting and let's get started.

Regards!

[1] https://issues.redhat.com/browse/PLANNER-2445

[2] http://polymorphe.free.fr/cours/ia/tsp/schrimpf-record_breaking_opt_ruin_recreate.pdf

--

Lukáš Petrovický

OptaPlanner Project Lead

lukas.pe...@redhat.com

My work week is Monday to Thursday.
No need to respond outside of your working hours.

[Michał Dudkiewicz]

Holger,
There is no comparison. I used both solvers in my project for solving different problems, but didn't really compare them for solving same problems.
For now,  I found some basic comparison for a specific problem here: https://www.solvice.io/post/comparing-or-tools-vs-optaplanner-for-multi-echelon-inventory-planning
Also if you are interested in some more detailed comparison for different kind of problems I know there is PR opened for MiniZinc support in Optaplanner (https://issues.redhat.com/browse/PLANNER-1853). After it is supported Optaplanner can also compete with OR-Tools in yearly MiniZinc challenge (https://www.minizinc.org/challenge2022/results2022.html). It will be the best comparison I think

Lukas,
thank you for the suggestion about R&R. I've read the paper. It sounds interesting and appealing to me. I will discuss the topic with my supervisor from the university and will let you know tomorrow what we established

[Michał Dudkiewicz]

Lukáš,

Ok, already discussed. Can we set up a meeting and discuss the topic? What is the most suitable date for you? What channel of communication do you prefer? Is MS teams fine?
Any Monday/Wednesday works best for me.

Michał Dudkiewicz

[Lukáš Petrovický]

On Thu, Mar 2, 2023 at 10:03 PM Michał Dudkiewicz <michal.du...@gmail.com> wrote:

Ok, already discussed. Can we set up a meeting and discuss the topic? What is the most suitable date for you? What channel of communication do you prefer? Is MS teams fine?
Any Monday/Wednesday works best for me.

I'm answering off-list.

--

[Michał Dudkiewicz]

Today I defended the master thesis entitled "Extending the OptaPlanner scheduling engine with the implementation of the Ruin and Recreate principle" (suggested in this thread)

Abstract:
The aim of the work is to extend the OptaPlanner planning engine with the Ruin and Recreate principle and to analyze the benefits of its usage while solving various optimization problems. The application of this rule gave positive results in research done by IBM, but to date it has not been implemented in the OptaPlanner engine. In addition to proving the reasonableness of its application, the most universal parameters of this rule will also be proposed, such as the size of the ruination or its variant. It will also be determined what factors affect the effectiveness of ruination and when and how it should be used to give the greatest benefits in the form of the highest possible final value of the objective function.

I attach the actual paper for future reference. It's in polish:
the thesis on my google drive