When modeling an optimization problem one of the tasks you will face is to come up with an objective function. This will then serve as a measure for the quality of a solution and the ultimate goal of the optimization algorithm. In the classical problems these are usually quite intuitive: the traveling salesman wants to find the shortest route, when dealing with cutting stock one wants to minimize the number of used master rolls, the machine schedule shall have a minimal makespan, and so forth. In application things quickly become difficult. As models grow more complex so do the objectives and we somehow need to take care of this.
An example is the RWTH Aachen timetabling problem. An obvious part of timetabling is to come up with a student friendly timetable that allows for a large variety of possible lecture combinations. But the problems already start here. Apart from the difficulties associated with gathering the associated data, one needs to solve the - mostly political - problem: minimize the number of conflicts between courses according to the curricula or according to the wishes of the students? There is no trivial solution to this problem (it is appealing to focus on the actual interests - but that would mean to discard combinations that should be available in the official curricula). Nevertheless one needs to make a decision here in order to proceed (in Aachen we decided to focus on the official curricula). On top of this a lot of other factors need to be taken care of. The lecturers availabilities must be considered - and it is not easy to get honest quotes about these from the lecturers. As the RWTH has lecture halls spread over the entire city it is desirable to keep the students travel distances low. Ideally not all students have the same time for their lunch break in order to reduce queues. And there are a lot more things one can wish for. Of course there usually is no solution solving all these issues at the same time and one has to make some trade-offs. In order to get the system implemented within a tight time frame we have often opted for practical, simpler solutions even if we knew these where not the objectives we were looking for in the long run. But the implementation of an optimization system is an ongoing process and one will always find some place to make improvements.
So far I can give you the following advice when trying to define a good objective function for your optimization problem:
- It has to be solvable. This sounds obvious but often I find myself in the situation where it feels almost painful to abandon a (probably more accurate) model in favor of something simpler. But it helps nobody when calculating a solution (with a reasonable optimality gap) takes hours (or days). This can be especially annoying while debugging the first implementation. Better to start simple with a well performing model and then work on a more complicated one if there is still demand for improvements. Also note that it is not unlikely that, given a certain time bound, a better performing model will produce a solution that outperforms the solution found with the more complicated objective - even with respect to that objective.
- Try to do something measurable. While it might be easy to calculate a virtual measure in the model, it is bad if you cannot verify this after implementing the solution. When the objective consists of parts you can (easily) measure in reality, it will be easier to make sure that things work out as planned and furthermore this enables you to make comparisons to the legacy solution that was implemented before your model entered the scene. Make sure you collect enough data from the old solution to calculate these measures early on - depending on the setting it might not be available later on.
- Start simple. It is easy to be carried away by the possibility to simply add just a little bit more and then a little bit on top of that and so on. Because in theory this should be no problem and this way you can satisfy your customer better as you model his desires more closely, or not? Often this path of thinking does yourself (and your customer) a great disservice. Adding more details to your model postpones the time when you implement the first solution and puts additional risk on the project. Here the same concept applies as already mentioned for solvability. Better to start simple and add details as the demand for them arises.
- Avoid the multi objective trap. Of course most realistic problems are multi objective. But dealing with several objectives and their trade offs are one of the fastest ways to drive up the complexity. Calculating multiple points on the efficient frontier is likely not a feasible option once the model is in production. Also different objectives have a tendency not to be easily comparable. So just adding them up, each with its own scalar factor, might likely result in some completely inexpressive number - making it impossible to properly measure what your model is doing. If possible, set bounds to most of the possible objectives and only really optimize one of them. Experiment with those bounds before going into production and do not set them to tight in order to avoid infeasibility.
Hopefully this will help you produce better results with optimization models.
Header photo by Death to the Stock Photo
comments powered by Disqus