A non-OR colleague recently asked me if one particular optimization model was more complex than another because it had more unique types of constraints modeled on various business rules. I guess in a way it is because by having many types of constraints built for various business rules, the model may be harder for humans to understand.
But when I think in terms of model complexity, I think about how hard the model is to solve. After all, your solver doesn’t care how difficult it was for you to determine how to model a certain business rule. It just cares about the mathematical equations you give it. A constraint that took you days to create may actually be very easy to solve for.
Of course, the perfect example of simple constraints creating complex problems is the Traveling Salesman problem. This problem only has two constraints: the salesman must visit each town and the salesman must return home at the end. And it is that second constraint, that the salesman must return home, that makes the problem so complex.
How do you define complexity when you are modeling operations research problems? Do you think about computation time and P vs NP? Or do you think about how difficult it will be to model the various business constraints?