Making Dreams Come True (Or Not)
JeanFrancoisPuget 2700028FGP Comments (2) Visits (3366)
Last week, in my What Is The Solution When There Is No Solution entry, I commented about the fact that not all business requirements were actual constraints and that some of these are probably wishes that business people dream to fulfill. Making the difference between wishes and hard constraints is key to success. Indeed, handling wishes as hard constraints may result in infeasible models, which would be useless to the business people that come to you for help.
It turns out that there is a surprisingly simple way to detect that some constraints aren't true constraints, as we will see below. I learned this simple trick the hard way, working with a customer.
It was a rail industry customer. The problem was to route trains through the maze of rail tracks between the long distance rail tracks to the station platforms. There was basically one constraint stating that no two trains could be at the same place at the same time (read, there should be no collision). I guess everyone will agree that it is a very sensible constraint, and not a mere wish!
Devil being in detail, let's look at how that constraint is enforced in reality. Rail tracks are divided in section, say every 500 meters or half a mile, the exact length isn't important here. Then each section is protected by a signal. If a train is already in the section then no other train can enter.
That was reality part, let's look at the dream part. How was this constraint expressed by business people? They said that if a train entered a rail section, then no other train can enter it before one minute is elapsed. This is how we modeled it.
Our issue was that we could not find any feasible solution in a reasonable time using this simple constraint. We were not able to prove that the model was infeasible either, so we were stuck. After trying various tuning and various model reformulations, we went back to the customer saying there was probably no solution to their problem. This is where they asked us about what is the solution when there is no solution
As a way to get out of this dead end, I asked for the actual train routes they were using. After all, trains were running every day without colliding into each other. It meant that the actual schedule was meeting all constraint.. Then we entered the values corresponding to the current train schedule in our model. If the model was right then this would have been a feasible solution. It turned out that it was not. In the current schedule, there was an instance of two trains entering the same rail section, the second one entering 12 seconds after the first one. The one minute distance constraint wasn't met in that case. It was then clear that this one minute constraint was a wish, not a hard constraint. It was also clear that the physical system preventing trains to enter a busy rail section was activated. The physical system was making sure that when two trains followed each other too closely (here by 12 seconds), then some signals were used to prevent a collision.
We modified our model and set the minimum time distance to 12 seconds. We were finding feasible solutions in minutes. We then played with various delay values between 12 seconds and a minute, and could find feasible solutions with a larger minimum delay than 12 seconds.
The lesson here is simple: always use a verified solution to a know instance of the problem to check that your model is right. The verified solution should be a feasible solution to your model. If not, then you know that the infeasible constraints are wishes, not hard constraints, and that they should be handled as such. Detecting which constraints are infeasible is simple : enter the values of the proposed solution into each constraint, one constraint at a time, and check if it is met. One can do it constraint per constraint with a simple script,. Note that infeasible constraints may also be buggy. Our solution test script will find these as well. It is then up to the person modeling the problem to decide if the constraint was wrongly stated, or if it is a wish.
The second lesson is that mission critical optimization applications should always be executed through a safe execution system. Here, the signaling system prevents collisions when trains are too close to each others, whatever optimization comes up with. I feel better knowing that there is a safety net when it comes to executing plans derived on a system that gets input from people not in touch with reality!